Adobe Interview Question for Computer Scientists


Country: India
Interview Type: Written Test




Comment hidden because of low score. Click to expand.
4
of 4 vote

if each node in tree has pointer to it's parent, then we can find the LCA even if tree's root is not given. In this case this problem will be similar to finding intersection of two linked list.
keep traversing two nodes separately till parent is null. this way we can find the length of these two lists. get the difference of these two lengths and in bigger list , traverse till this length difference, and after that keep moving forward in these two list and compare the parent nodes.
When parent node is same that node will be LCA.
This can also be solved using two stacks. Keep putting parent node of each given node on stack till parent node is null. pop each node from stack and compare, if they are same then keep popping, when the node is different, then that node is LCA.

- OTR August 10, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can you tell what all input is given please

- Popoyee August 10, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

two node's addresses

- guptasunny158 August 10, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

But with a node how can you go upwards in binary tree. Does you tree structure will store a link to its parent node also ?

- Popoyee August 10, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I am also confused at the same point, how will I go upward :(

- guptasunny158 August 10, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Suppose the tree is -
20
/ \
10 30
/ \
5 17
/ \
1 7
and we need to find out the common ancestor of node 1 and node 17.

1. Then first of all compute the smallest node . In our case its 1.
2. After that traverse upward (Please note in my node there is also a pointer to the parent node.) till we get the last ancestor which is greater than the other node(i.e Node 17).
3. Return the last ancestor which is greater than the other node(i.e Node 17) which is the desired result.

- partha August 10, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 4 vote

There is an unique propriety for the common ancestor for two node in a BST,
The value of ancestor node must be in the middle of the two node, while the parent of the lowest common ancestor must be either both greater than or less than both node(if there is a parent node for the common ancestor).

The reason is if there is a node on the ancestor path is either greater or less then both given nodes, then, the two node must lay on the same side of that ancestor's sub tree, which means it could not be the lowest common ancestor.
If we follow down the path, till there is a node whose value is in the middle the two node, then, the two node must lay on different sub tree of that node.

Using this propriety, should be very easy to find the common ancestor.

Cheers!

- Tuotuo August 10, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 3 votes

This is obvious. The question is how to traverse a tree without root and additional pointer in nodes?
Cheers!

- thelineofcode August 20, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

1) Choose either node, search up the tree until the root is found (parent == null).
2) Determine the lower value node, call it n1. Call higher value n2.
3)

n = root
while(n != null){
    if( n == n1 || n == n2 || (n1 < n && n2 > n) ) 
        return n;
    elseif( n2 < n )
        n = n.left;
    else 
        n = n.right;
}

- bcorso August 11, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This problem could be solved by using X-OR operation.
1. store address in left link of node is X-OR (parentNodeAddress,LeftNodeaddress) and similarly for right.
2. in this way at a given node by performing X-OR we can get parent node.
3. In this way we can find LCA by O(n) time without knowing root address.

- RATAN LAL ISI KOLKATA August 13, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

can you explain it a bit more? how to access the parent?

- akie September 06, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

In this problem i assume parents address is given & the idea is just to find the intersection of two lines .....
The phsedo code is like this :

struct node* LCA(struct node* a, struct node* b){
int height1 = get_height(a);
int height2 = get_height(b);
int Dy = abs(height1-height2);
if (height1>height2) {
for(int i =Dy;i>=0;i--)
a = a->parents;
while(a!=b) {
a = a->parents;
b = b->parents;
}
return a;
} else if (height1<height2) {
// same as above....
}
}

I hope the code is clear, if any issue let me know.

- Nishant Pandey August 15, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I am assuming that the node-parent relationship is provided (we know that the root of the tree is not given).

struct bst *LCA(struct bst *n1, struct bst *n2)
{
  if(n1==NULL && n2==NULL)
     return NULL;
  else if(n1==NULL || n2==NULL)
   return NULL;
  else if(n1==n2)
    return n1;
  else
  {
      if(n1->data < n2->data)
            return LCA(n1,n2->parent);
      else if(n2->data<n1->data)
            return LCA(n1->parent,n2);
  }
  return NULL;
}

- Anonymous August 18, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Nice one! But question is asked for iterative method!

- Psycho October 02, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

If the parent-child relationship is known, we use a hash table:

while(n1!=NULL)
{
   hash_table[n1]=1;
   n1=n1->parent;
}
while(n2!=NULL)
{
  if(hash_table[n2]==1)
    return n2;
  n2=n2->parent;
}
return NULL;

We can also use the data stored in each node to hash the values. The caveat with this latter approach is it cannot handle the duplicates.

- Anonymous September 06, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This question is exactly similar to another popular question "Given two singly linked lists and they both intersect at one point (ie, forming a Y shaped list). Find where the two linked lists merge"

So we can simply boil down this question to simple question.

// As root->parent is NULL, we don't need to pass root in.
Node *LCA(Node *p, Node *q) {
  int h1 = getHeight(p);
  int h2 = getHeight(q);
  // swap both nodes in case p is deeper than q.
  if (h1 > h2) {
    swap(h1, h2);
    swap(p, q);
  }
  // invariant: h1 <= h2.
  int dh = h2 - h1;
  // coming the deeper node to the same level w.r.t. root 
  for (int h = 0; h < dh; h++)
    q = q->parent;
  //At same level
  while (p && q) {
    if (p == q) return p;
    p = p->parent;
    q = q->parent;
  }
  return NULL;  // p and q are not in the same tree
}

- Psycho October 02, 2013 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More