CareerCup

Can you explain the problem with an example?

I believe he means
[code]
1
2 5 7 9

Returns 5

A btree is not only a balanced tree, but the data in it is sorted. For example,

7,         16
1,2,5,6       9,12      18,21

A median can be obtained by sorting all nos from lowest to highest and picking the middle number. This is easy if the list length is odd: if it is even, then the common method is to take the mean of the middle two nos in the list.

So, the median of a Btree depends on how many elements are in the list and not on the order. Since the median is a property of the actual elements, one has to traverse through the entire elements in the Btree.

Solution 1 is to just iterate through the Btree and add it to an array. So, in the above example, the array will be 1,2,5,6,7,9,12,16,18,21. There are 10 entries i.e. even number i.e. median is (7+9)/2 = 8.

Solution1 assumes that one does not know the total number of elements in the Btree.
Usually, Btree implementations know the number of elements in the array. If so, then solution 2.

Solution 2 is to just iterate to find either the middle number in an odd length set OR the middle two nos in an even set and find the mean. No extra memory is needed for the array.

Hi,

I just need to know the interview procedure at Adobe for Java Development Profile.
Need the information so that I can have the basic idea for the same.

Regards,
Mohit

Hi,

If anyone has successfully cleared all the interview rounds or knows about it, then please share the same for Adobe Interview rounds(no. of technical and that of HR) , how to proceed , I vknow core Java , JSP Servlets .Is it sufficient or they expects more with the 21/2 yrs experience developer

21/2 means 2 and a half years.

21/2 = 10.5 ? they'll hire you without asking all these silly questions.

@ruralBrute

still at 10.5, u wl have to take written test :-)

1. count the no. of nodes in the btree (len)

int ht(nodeptr p)
{
   if(!p) return 0;
   else return( ht(p->left)+ht(p->right)+1);
}

2. prob is to find len/2th node if (len=even) or len/2th and len/2 + 1 th node and hence to find their avg. which is the median
3. Finfing k-th smallest node in a binary search tree

1.maintain no of left sub tree elements in each node.
2.if k=n+1 , then root is the kth node
3.if k<n, search for kth node in root->left
4.if k>n+1, search for k-n-1 th node in root->right