CareerCup

Is it a tree or binary tree?

2.Given a regular expression and a text,find the min no of replacements to be done.
could you elaborate a little bit more of 2nd programming question? give an example would be helpful.

3.Implement diff command of Unix.

Hi, I am going to be on site next week. Could you give me some tips about the interview at Yahoo? BTW, which team did you have an interview with?

Thanks!

1 was using memoisation to find value in a recurrence relation.
----
What does this mean?Memoization?

for the first question is it the binary tree or binary search tree?

LCA(TREE, x, y)
p = root[TREE]
while p != NULL
if key[x] <= key[p] <= key[y]
return p
else if key[x], key[y] <= key[p]
if leftChild[p] = x or leftChild[p] = y
return p
else
p = leftChild[p]
else
if rightChild[p] = x or rightChild[p] = y
return p
else
p = rightChild[p]
return

Node a,b;
Find the path pa from node a to the root (do not include node a in pa).
Create an empty hashmap, from node to boolean value.

for every node n in pa, add n->true to the hashmap.

Start at b. Keep finding the parent. For every node in the path, hash and see if node is in hashmap. If so, return node as LCA.

complexity: log n for path finding. Space is log n, where n is the number of nodes in the binary tree.

stack1 = getPathToRoot(node1);
stack2 = getPathToRoot(node2);

while(stack1.top == stack2.top) {
node = stack1.pop();
stack2.pop();
}

print "LCA is ", node, "\n";


getPathToRoot(node) {

stack.push(node);
while(node->parent) {
stack.push(parent);
}

node = node->parent;
}

stack1 = getPathToRoot(node1);
stack2 = getPathToRoot(node2);

while(stack1.top == stack2.top) {
node = stack1.pop();
stack2.pop();
}

print "LCA is ", node, "\n";


getPathToRoot(node) {

stack.push(node);
while(node->parent) {
stack.push(parent);
}

node = node->parent;
}

great solution!

@rohit
i dont think so this will works
did you tried runned it?

even if you rewrite the correct written statement, it will just prints the parent for watever value you got second time(i mean if you get data1 after data2, it will print data1's parent)

//algorithm1 for general tree

(1) iterate thro as usual with one more param as level
(2) when u got the first node, after then dont increase the level, (it will automatically decreses by 1 as it returns to upper nodes) and make sure you have the node data at that level in a temp variable
(3) traverse as usual without increamenting level anymore
(4) when you got the second node then watever the temp node contains is the LCA

//algorithm2 for general tree

(1) make a character array path(ex"162"=root->1st node->6th node->2nd node) for both nodes seperately
(2) the path which is common prefix of this arrays is the LCA
(3) if the prefix is NULL then root is the LCA

Say node1 is at height h1 and node2 at height h2.
assuming h1 > h2 (for which conditions can be put in code)
h_diff = h1 - h2;
Traverse toward root for node1 (node associated with h1) path for h_diff.
Now start checking the condition
node1->parent == node2->parent;
and traverse one step towards root untill you get the solution.

Ok. Here's how I'd go.
Assuming that the level (i.e. depth, e.g: root is at level 0) is stored in each node, do the following:

Node *get_common_ancestor(Node *n1, Node *n2)
{
    if (n1 == NULL)
        return n2;

    if (n2 == NULL)
        return n2;

    //if n1 was deeper in the tree.
    while (n1->level > n2->level) {
        n1 = n1->parent;
    }
    
    //if n2 was deeper in the tree.
    while (n2->level > n1->level) {
        n2 = n2->parent;
    }

    //now, move both of them 1 level up at a time an compare
    while (n1 != NULL && n2 != NULL) {
        if (n1 == n2) {
            return n1; //This is the common ancestor.
        }
        n1 = n1->parent;
        n2 = n2->parent;
    }
    return NULL; //No common ancestor found. Essentially, both nodes are in diff. trees
}

This will work for non-binary trees too.

Anonymous has a better solution.
Refer http://www.careercup.com/question?id=57101 for my solution

node* LCA(node* l1, node* l2)
{

int h1=0,h2=0;
node* t1=l1,*t2=l2;

while(t1!=NULL)
{
t1=t1->parent;
h1++;
}
while(t2!=NULL)
{
t2=t2->parent;
h2++;
}

int h=h1-h2;

if(h>0)
{
while(h-- >0 )
l1=l1->parent;

}

else
{
h=-h;

while(h-->0)
l2=l2->parent;

}


while(l1!=NULL && l2!=NULL)
{
if(l1==l2)
return l1;

else
{
l1=l1->parent;
l2=l2->parent;
}

}


return null;

}

Node* CommonNode(NodeStruct* Node)
{
....if(Node == NULL) return NULL;
....if(Node == Node1 || Node == Node2) return Node;
....NodeStruct temp1 = CommonNode(Node->left)
....NodeStruct temp2 = CommonNode(Node->right)
....if(temp1 != NULL && temp2 != NULL)
....{
........printf("The common node is %d", Node->value);
........exit(1);
....}
....if(temp1 != NULL) return temp1
....if(temp2 != NULL) return temp2
}

@other Balaji: your method is correct. just one minor correction.

if (n1 == NULL) {
   return n1;
}

Cheers.

I will have two pointers traversing independently through the tree.. one searching for n1 and the other for n2 and they also maker a note of all the nodes they traverse. I prefer using root-left-right traversal. Once they have found the nodes... compare the traversal path and find the node closest to the node and also present in the traversal path of the other node. This should be the LCA.

/// How About recursion Sulition

struct Node
{
    int val;
    Node * left;
    Node * right;
    Node(int v) : val(v), left(NULL), right(NULL)
    {   
    }   
};

bool is_in_tree(Node * root, Node * n)
{
    if(NULL == root) return false;
    if(root == n) return true;
    return is_in_tree(root->left, n) || is_in_tree(root->right, n); 
}

Node * common_ancestor(Node * root, Node * n1 , Node * n2) 
{
    if((root == n1) || (root == n2)) return root;
    bool is_n1_in_left = is_in_tree(root->left, n1);
    bool is_n2_in_left = is_in_tree(root->left, n2);
    if(is_n1_in_left && is_n2_in_left) return common_ancestor(root->left, n1, n2);
    else if(is_n1_in_left && !is_n2_in_left) return root;
    else if(!is_n1_in_left && is_n2_in_left) return root;
    else return common_ancestor(root->right, n1, n2);
}

consider it as a binary tree nd post ur comment u asshole...therwise shut de fuck up