Vertical Sum of a Binary Tree

 Posted on December 18, 2011  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

please explain doubly linked list method in words Anonymous - Apr 6, 2014please explain doubly linked list method in words Added the basic algo for that: 1. Start with the root node and empty double list listNode 2. Add the value of the rootNode to the current listNode 3. Now whenever you go left, pass listNode.left and root.left and call step1 and 2 recursively. 4. Similarly for right node Please let me know if I have not explained it properly. [Read More]
Binary Tree  BT  kodeknight  Amazon  hashmap  Interview Question  hashtable  binary-search-tree  BST  Doubly Linked List  DLL 

Vertical Sum of a Binary Tree

 Posted on December 18, 2011  (Last modified on August 7, 2020)  |  4 minutes  |  Kinshuk Chandra

Question : Find vertical sum of given binary tree. Example: 1 / \\ 2 3 / \\ / \\ 4 5 6 7 The tree has 5 vertical lines Vertical-1: nodes-4 => vertical sum is 4 Vertical-2: nodes-2 => vertical sum is 2 Vertical-3: nodes-1,5,6 => vertical sum is 1+5+6 = 12 Vertical-4: nodes-3 => vertical sum is 3 Vertical-5: nodes-7 => vertical sum is 7 We need to output: 4 2 12 3 7 [Read More]
Binary Tree  BT  kodeknight  Amazon  hashmap  Interview Question  hashtable  binary-search-tree  BST  Doubly Linked List  DLL 

Median of 2 sorted arrays of equal size n

 Posted on September 13, 2011  (Last modified on August 7, 2020)  |  7 minutes  |  Kinshuk Chandra

Question  There are 2 sorted arrays A and B. Write an algorithm to find the median of the array obtained after merging the above 2 arrays(i.e. array of length 2n). The complexity should be O(log(n)) Solution Before going to solution what is the median. What is Median? Median: In probability theory and statistics, a median is described as the number separating the higher half of a sample, a population, or a probability distribution, from the lower half. [Read More]
Adobe  kodeknight  Microsoft  yahoo  divide and conquer  Amazon  array  two-sorted-arrays  median  incomplete  two-arrays  sorted-array 

Important ds question

 Posted on April 26, 2010  (Last modified on August 7, 2020)  |  16 minutes  |  Kinshuk Chandra

a) Write a function that validates whether a tree is a BST or not. b) Write a function to find the common ancestor of two given nodes of binary tree. c) In a BST, value of two of the nodes got exchanged by mistake. Write a function to correct the BST. d) In a array, there exists a majority element(a no. repeated atleast n/2 + 1 times) and rest of the no. [Read More]
kodeknight  Microsoft  Amazon  Data Structures  DS  sorting  binary-search-tree  BST