## Adobe Interview Question for Software Engineer / Developers

• 0

Country: India

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

BST does provide us information which helps us to do better than a normal binary tree code...we can know at first whether to go to the right child or the left child accordingly whereas in binary tree we have to consider all the possibilities of the right child as well as left child of the root to find the LCA.

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

Let x and y be the elements whose lowest common ancestor we want
First do inorder traversal of the binary tree, store in a list A
Second, do post order traversal of binary tree , store in list B
Find all the numbers in A which are between x and y and call the list C
Find their rank in B, which ever number in C comes last in B is the lowest common ancestor of x and y.

Correctness
List A contains ancestors of x and y and only one common ancestor, which is the lowest common ancestor.
There is only one common ancestor, because in binary tree inorder we traverse left , root , right hence between two elements x and y the root of sub tree is lowest common ancestor.
we use post order to find that node as in post order root is visited last

To understand this solution you can take a look at

Comment hidden because of low score. Click to expand.
0

wow ！！！Brilliant!

Comment hidden because of low score. Click to expand.
0

I guess it will fail in case both the nodes are leftmost nodes. Please correct me if i am wrong.

Comment hidden because of low score. Click to expand.
0

One change: Find all the numbers in A which are between x and y (including x and y) and call the list C

Comment hidden because of low score. Click to expand.
0

What you are suggesting will result in visiting every node twice. and also an extra memory is required for inorder and preorder.

what i propose is

``````LCA_BT(struct node *root,struct node *p,struct node *q)
{
struct node * left,*right;
if(root==NULL)
return root;
if(root== p or  root ==q)
return root;
left=LCA_BT(root->left,p,q);
right=LCA_BT(root->right,p,q);
return (left?left:right);
}``````

Please do correct me if i am wrong...

Comment hidden because of low score. Click to expand.
0

if both left and right are non-empty then return the root.

``if (left && right) return root ;``

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

A Bottom-up Approach (Worst case O(n) ):

``````Node *LCA(Node *root, Node *p, Node *q) {
if (!root) return NULL;
if (root == p || root == q) return root;
Node *L = LCA(root->left, p, q);
Node *R = LCA(root->right, p, q);
if (L && R) return root;  // if p and q are on both sides
return L ? L : R;  // either one of p,q is on one side OR p,q is not in L&R subtrees
}``````

Comment hidden because of low score. Click to expand.
0

Won't work if the node is not present in the tree.

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

1.Take level order of the tree.
2.move the pointers p & q whose lca is to be found towards their parents,where both of them meet is the lca.
level order traversal O(n)
finding p & q in the queue O(n)
now NCA:
parentp=parent(p);
parentq=parent(q);
while(parentp!=paerntq)
{
if(parentp!=parentq)
p=parentp;
else
q=parentq;
parentp=parent(p);
parentq=parent(q);
}
return queue[parentp];
}
time complexity on whole=O(n)
space : large amount

Comment hidden because of low score. Click to expand.
0

I'm thinking of a similar algorithm to yours. First, find the level of p and q by continuously performing p = p.parent, q = q.parent until they hit the root (I assume we are given the pointers to p and q). So we can get the level of p & q (say Lp, Lq) in O(logn) time.

Then, if Lp > Lq, perform p = p.parent Lp-Lq times to make p and q at the same level (similarly if Lq > Lp). After this, we can set a while loop and let p = p.parent and q = q.parent "simultaneously" in each iteration, until they hit the same node, which is the lca.

The time complexity will be O(logn) without no extra space used. Do you think this algorithm is gonna work?

=========

Note that p and q must locate at the two different branches of the lca, so for BST, we just do the following:

Node n = root;
if(p.value > n.value && q.value > n.value) // assume distinct elements
n = n.right;
else if (p.value < n.value && q.value < n.value)
n = n.left;
else
return n;

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

//C code to find Least Common Ancestor

#include<stdio.h>
#include<stdlib.h>

struct node
{
int data;
struct node *left;
struct node *right;
};

struct node *newNode(int data)
{
struct node *n=(struct node *)malloc(sizeof(struct node));
n->data=data;
n->left=NULL;
n->right=NULL;
return n;
}

int covers(struct node *root,struct node *p)
{
if(root==NULL)
return 0;
else if(root==p)
return 1;
else
return (covers(root->left,p) || covers(root->right,p));
}

struct node * LCA(struct node *root,struct node *p,struct node *q)
{
if(covers(root->left,p) && covers(root->left,q))
return LCA(root->left,p,q);
if(covers(root->right,p) && covers(root->right,q))
return LCA(root->right,p,q);
return root;

}

int main()
{
struct node *root=newNode(12);
root->left=newNode(20);
root->right=newNode(24);
root->left->left=newNode(11);
root->left->right=newNode(10);
root->left->right->right=newNode(8);

struct node *ans=LCA(root,root->left->left,root->left->right->right);
printf("The LCA is %d\n",ans->data);
return 0;
}

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

for bst: the easier path only..

start p=root
given nodes m,n(the values) m<n deduce.
if p->value < both m,n then p=p->left
if p->value > both m,n then p=p->right
if......>m&.....<n, then it is the ancestor.

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

Step1:- first do preorder travsal,take a array which have the nodes value before first node seen;
Step 2:- do the postorder travsals,tke another arrey which have the nodes value after both node seen ...
Step3- take intersection of both arrey,,,,,after that the node whose value is lowest is the lowest ancestor of given binary tree....
Ex..two node 17 and 5 whose lowest ancestor 10
/ \
15 12
/ \
13 14
/ \ / \
17 18 11 5
/ \
20 21
preorder: 10,15,13,17,18,20,21,14,11,5
a[]={10,15,13}
postorder: 17,20,21,18,13,11,5,14,15,12,10
b[]={ 14,15,12,10}
intersection is { 10,15}
lowest is 10
so ans is 10...

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

Algorithmic complexity O(n)
Correct me if I am wrong on a case

``````//using the fact that it is BT and not BST
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <list>
using namespace std;
typedef struct node snode;
struct node
{
int data;
struct node *left, *right;
};

// helper function to allocate new node with given data
struct node* newNode(int data)
{
struct node* node = (struct node*)malloc(sizeof(struct node));
node->data = data;
node->left = node->right = NULL;
return (node);
}

//maintain two lists
list<snode *> s1,s2;

//function to search the data for existance
int searchData(snode *root,int data,int mode){
//null node base
if(root==NULL){
return -1;
}

//data is in this node, hence return 1
if(root->data == data){
return 1;
}

//else look left and right for possibilities
//lf is left flag, rf is right flag
int lf,rf;
switch(mode){
//mode 1 for first num, mode 2 for second num
case 1:
if(root->left != NULL){
//first push this node
s1.push_back(root->left);
//then search
lf=searchData(root->left,data,mode);

//since it is found then return 1 flag
if(lf==1){
return 1;
}

//else revert the list to the old state
s1.pop_back();
}
if(root->right!=NULL){
//first push this node
s1.push_back(root->right);
//then search
rf=searchData(root->right,data,mode);

//since it is found then return 1 flag
if(rf==1){
return 1;
}

//else revert the list to the old state
s1.pop_back();
}
break;
case 2:
if(root->left != NULL){
s2.push_back(root->left);
lf=searchData(root->left,data,mode);
if(lf==1){
return 1;
}
s2.pop_back();
}
if(root->right!=NULL){
s2.push_back(root->right);
rf=searchData(root->right,data,mode);
if(rf==1){
return 1;
}
s2.pop_back();
}
break;
}
return -1; //to be safe
}

#define debugStates

void monitorLCA(snode * root,int data1,int data2){
int lf,rf;

//initialize the lists with the root
s1.push_back(root);
s2.push_back(root);

//search entries
lf = searchData(root,data1,1);
rf = searchData(root,data2,2);

#ifdef debugStates
//DEBUG control
cout<<"lf is "<<lf<<", rf is "<<rf<<endl;
//contents display
for(list<snode *>::iterator it=s1.begin();it!=s1.end();++it){
cout<<(*it)->data<<" ";
}
cout<<endl;
//contents display
for(list<snode *>::iterator it=s2.begin();it!=s2.end();++it){
cout<<(*it)->data<<" ";
}
cout<<endl;
#endif // debugStates

if(lf==-1 || rf==-1){
cout<<"data invalid"<<endl;
return;
}

//now maintain the last matched node and start popping
snode * last;
while((s1.front())->data == (s2.front())->data){
last = s1.front();
s1.pop_front();
s2.pop_front();
}

cout<<"the lca was "<<(last->data)<<endl;
}

//DRIVER
int main(){
snode * root = newNode(5);
root->left = newNode(3);
root->left->left=newNode(1);
root->left->right=newNode(6);
root->right=newNode(2);
root->right->left=newNode(9);
root->right->right=newNode(8);
monitorLCA(root,100,6);
return 0;
}``````

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

C++ 11
1. Traverse tree until you find one of the nodes. While doing that collect the nodes in the path whose right tree you haven't traversed yet.

2. Search each node's right subtree of the nodes found in the above to check if it contains the other node. The first one that passes this test is the lowest common ancestor.

``````shared_ptr<vector<shared_ptr<TreeNode>>> FindPath(shared_ptr<TreeNode> t, shared_ptr<TreeNode> n1, shared_ptr<TreeNode> n2) {
if(t == nullptr) {
return nullptr;
}
if( t == n1 || t == n2) {
auto path = make_shared<vector<shared_ptr<TreeNode>>>();
path->push_back(t);
return path;
}
else {
if(t->left) {
auto path = FindPath(t->left, n1, n2);
if(path) {
if(t->right) {
path->push_back(t);
}
return path;
}
}
if(t->right) {
auto path = FindPath(t->right, n1, n2);
if(path) {
return path;
}
}

}
}
bool TreeContains(shared_ptr<TreeNode> t, shared_ptr<TreeNode> n) {
if(t == nullptr) {
return false;
}
if( t == n) {
return true;
}
return TreeContains(t->left, n) || TreeContains(t->right, n);
}
shared_ptr<TreeNode> FirstCommonAncestor(shared_ptr<TreeNode> t, shared_ptr<TreeNode> n1, shared_ptr<TreeNode> n2) {
auto path = FindPath(t, n1, n2);
auto path_length = path->size();
if(path_length > 0) {
auto other_node = path->at(0) == n1 ? n2 : n1;
if(TreeContains(path->at(0), other_node)) {
return path->at(0);
}
for(int i = 1; i < path_length; i++) {
if(TreeContains(path->at(i)->right, other_node)) {
return path->at(i);
}
}
} else {
return nullptr;
}

}``````

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.

### 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.