Adobe Interview Question
Software Engineer / DevelopersFor Q1, you probably didn't realize the challenge to implement it "non recursively". Stack based implementation of preorder/inorder traversal is not appropriate to use, unless there is a 'depth' field associated with each node. So, postorder seems perfect one without any modification made to data structure.
Q1: Use 2 stacks to find the hieght
Stack* S, T;
\\S=new Stack.....etc.
int height=0;
Void StoreNextLevel(Stack A, Stack B){
while(A.IsNotEmpty){
Node n = A.Pop();
if(n.left)
B.Push(n.left);
if(n.right)
B.Push(n.right);
}
S.Push(root);
while(S.IsNotEmpty and T.IsNotEmpty){
StoreNextLevel(S,T);
height++;
Stack* temp;
temp = S; S = T; T=temp;
}
height-=1;
//cause if there is only root node, the height = 0 not 1;
}
One stack solution as suggested by DFS.
Maintain current depth, and when we hit a leaf, update max_depth.
int Height(Tree t) {
if (t is null) throw ...;
Stack s;
Hash visited;
s.Push(t);
visited.Add(t);
int cur_Depth = 1;
int max_Depth = 1;
while (!s.IsEmpty()) {
Tree t = s.Top();
if (t.IsLeaf()) {
if (cur_depth > max_depth) max_depth = cur_depth;
continue;
}
bool needsPopping = true;
foreach (Tree child in T.children) {
if (visited.Contains(child)) {
continue;
}
s.Push(child);
cur_depth++;
needsPopping = false;
break;
}
if (needsPopping) {
s.Pop();
current_depth--;
}
}
}
Isn't it better if you take this as challenge to post a solid code, rather than code muddled up with random thoughts? It'd help you, and help many others running your code for different inputs. Thanks.
LOL @anon.
What random thoughts are you talking about? The idea is pretty clear. Doing a depth first search _works_. If you cannot comprehend it, it is your f**ing problem.
Easy...
One cannot edit posts, so one should expect code with bugs, especially if people are just writing them down while adding the comment.
@anon: It is quite clear actually. In fact, this was written to make it work even with n-ary trees...
@anonymous: I admit you are way too smarter than me. Now, can I humbly request you to implement the code entirely (just for binary tree), probably expecting only 15-20 mins for you? You can post it to ideone.com, and share the link. I really like to see your implementation approach using DFS that mimic either inorder or preorder traversal (that use single stack) to solve the problem. Thanks.
To better explain my confusion, let we've a simple iterative preorder traversal procedure like below. Help me to understand how to modify it to get the depth of the tree.
void Preorder (Tree* root)
{
if (!root) return ;
stack <Tree *> nodes ;
nodes.push (root) ;
while ( !nodes.empty() ) {
Tree* node = nodes.top() ;
nodes.pop();
//visit node
if ( node->right ) nodes.push (node->right);
if ( node->left) nodes.push (node->left);
}
}
I know it's possible if we change stack<Tree *> to keep associated nodes depth also, like, stack< pair<Tree *, int> >, which is conceptually analogous to using extra depth field at each node of the tree (though NOT direct modification, yet it double the required space). I want to know how to solve without taking any additional space than keeping pointers to visited nodes only. Thanks for your help in advance.
I also know how to use post-order traversal, or data structure with parent-link or thread-links to compute depth of a tree. But, I'm stick to use inorder or preorder traversal using single stack of visited node's pointer without any modification to the tree structure.
Not sure why anon is trying to impose additional restrictions not part of the original problem. He/she also seems to be under the misconception that the only possible ways to perform DFS are pre/post/inorder.
There are at least two ways to implement DFS using a single stack. One way is to push all the children of a node, which would possibly require storing depth field for each node.
The other (which mimics the call stack of the recursive method and is similar to the code posted above) is to push children one by one. This will keep a node on the stack if any of its children are not visited and the depth of current node then can be implicitly computed by push and pop and one would not need to store per node depth information.
Mimicking the call stack is a general way to attack such problems of "iterative-only" (which have easy recursive implementations).
For instance, @anon, try your extra space constraints/BFS approach for the mirror image problem. Maybe there is a way, but it seems it might be difficult.
As to your "challenge", search the web. You will find plenty of links. To start you off, google Morris Traversal.
Well, I faced this challenge when once I implemented the same problem few months back. I tried to implement it using iterative in/pre-order traversal, but understood that it is NOT possible. The reason to use in/preorder was that it's a lot simpler to implement than iterative postorder traversal (specially if only 1 stack is allowed). I know the implementation about Morris Inorder traversal from Adam Drozdek's data structure book. I googled it, and the interesting thing is that I didn't find a single reference what I was looking for. If you can implement it, or get a link; please share with me. Thanks.
Regarding your details on this part
"The other (which mimics the call stack of the recursive method and is similar to the code posted above) is to push children one by one. This will keep a node on the stack if any of its children are not visited and the depth of current node then can be implicitly computed by push and pop and one would not need to store per node depth information."
This seems absolutely IMPOSSIBLE unless you've "visited flag" (or, explored children count for n-ary tree) on each node. Consider below binary tree:
8
/ \
5 12
/ \ \
2 7 25
how could you distinguish these 2 cases:
(1) node 5 is reached from parent 8 (so explore left, for example), and
(2) node 5 is reached from left-child 2 (so explore right)
so this NEEDS to modify the data structure.
BTW, I saw how you did it, keeping additional information of visited children. But, that would make the complexity of your algorithm O(n^2) in worst case (for extra check if a child is already visited a not). That surely is not appealing at all. We must have to keep it O(n), otherwise an "hasta la vista" message from the interviewer is inevitable to hear back.
"No need for per node depth information" does mean you cannot store other info. Mimicking the call stack would mean you also store the local variable/state information of the recursive implementation with each stack element (that is what the compiler does with the stack frames, you know). For binary trees, this would mean storing a boolean flag and for n-ary trees, some kind of count.
The space is still asymptotically optimal: Theta(n).
With the visited hash, the complexity is O(n) for binary trees of course, even though you iterate the child list from the start.
If you are worried about worst case hash table performance, by maintaining counts/pointer to next child to visit, it will be still be O(n).
Sorry, if the interviewer would think that is Omega(n^2), then he is an idiot.
Also, you seem to be under the mistaken impression that interviewers look for the best possible solution. For instance, consider what you are hung up on: an in-order with minimal space. If they really expect you to completely solve and code in 60 minutes, a problem for which academic papers need to been written, then they are total idiots.
btw, you are just polluting this thread with problems which weren't asked in the first place (in an attempt to save face by your first 'challenge' comment I suppose).
And, I never claimed that you can do in-order on a read only binary tree with one stack and not maintaining any extra information. I don't really care. Wasted enough time on this already. Do your own searches. Morris traversal should be a good _starting point_. You could try following the references etc and find some algorithms/impossible results. If you don't the problem might still be open.
Good luck.
Well, many interviewers are TOO STRICT (which I've heard from peers who applied for internship/full time at MS, Google, FB, Amazon, Yahoo etc.) with the resource provided to you. Theoretically, O(n) = O(1000n), but practically surely it's not. If an interviewer imposes a restriction, it's not a candidate's insanity to look for SIMPLEST and LEAST error-prone solution for a particular problem. As you mentioned, time is a critical issue; and above all it's the correctness.
Well I'm concluding it with this impression : either BFS or DFS (that mimics a post-order traversal of nodes) is suitable to solve it with given constraints of
(i) O(n) worst case time (just FYI, worst case hash lookup is never O(1) that you claimed above),
(ii) one stack of visited nodes ONLY (no additional states - be it local or whatever),
(iii) no modification of tree structure (visited flags/count).
15-20 mins is pretty sufficient for this, as it deals with least amount of coding. Lastly, I hoped to see your polished code that might take less than typing comments back and forth. Unfortunately, I didn't see any. No offense.
Thanks.
Just fyi, you have a reading comprehension problem.
Never claimed hashtable was O(1) worst case. In fact, it was specifically mentioned if you are worried about worst case hashtable performance, then maintain a count/flag to make it worst case O(1).
No offense, but I don't really care what you think. I only engaged in this conversation as people might be misled by your inaccurate comments and unrelated problems.
Mimicking the call stack of the recursive implementation is good way to solve these problems and is a good tool to have handy if you are in the process of interviewing.
(btw, the bfs(with marker) and dfs solutions don't meet your constraints...)
Good interviewers (from my own experience and peers already working at google/ms) look for how you approach the problem. One cannot expect perfect code from anyone in a short span of 15-20mins, unless the problem is trivial (like fizzbuzz or something).
It is true, that if the candidate knocks the question out the park, there might be a progressive tightening of the constraints. But expecting a solution which has research papers written on it is quite stupid.
I just hope others understand what was intended: Try the approach of mimicking the call stack when given such problems in an interview.
Also, apologies if I caused you some distress.
End of discussion from me. Good luck.
1.ANS :: Find the total levels in a binary tree and add +1 to the level we will get the height of the tree
I agree this BFS approach is much simpler and less error-prone than DFS. A stack, plus two counter variables serve the purpose.
LOL again @anon.
DFS is simpler. All you need to do is maintain the depth, which is easy: push implies +1, pop implies -1.
BFS requires storing more state. For instance, how do you know when to increment the level? You need some extra state for that.
Actually BFS might be simpler. All you need is to put a 'marker' node after you enqueue the root. Each time you see the marker node, increment the level and enqueue it again. If anytime the queue is empty after dequeing the marker node, you are done.
Since we push all the children, it becomes simpler.
In DFS, even though conceptually the right approach, you need some per node extra state to determine whether you pop the node, or push the next child, but that is easy I suppose.
Both are quite simple, IMO. And there is really not much of a challenge with DFS as anon seems to think, IMO.
I use a flag per node, but only one stack to accomplish a post-order iterative traversal. O(n) time complexity, space complexity depends on how you keep track of the node state. I kept it simple and just used a bool.
The basic algorithm is simple and easy to understand and if you needed to do a pre-order or in-order traversal it can easily be adapted by simply reordering how the nodes are pushed onto the stack. Very similar to what we do with recursive algorithms. Simple, slick and neat.
template<class T>
struct Node {
Node(T _data) : item(false),data(_data),
left(0), right(0){}
Node() : item(false),data(), left(0), right(0){}
Node* asItem() { item=true; return this;}
Node* asLink() { item=false; return this;}
bool isItem() const {return item; }
bool item; T data; Node* left; Node* right;
};
typedef Node<int> Tree;
size_t findBSTHeight(Tree* root) {
if(!root) return 0;
size_t maxHeight=0;size_t height=0;
stack<Tree*> s; s.push( root->asLink() );
while( !s.empty() ) {
root = s.top(),s.pop();
if( root->isItem() ) {
maxHeight = max(maxHeight,height);
--height;
} else {
++height;
s.push(root->asItem());
if( root->right ) s.push(root->right);
if( root->left ) s.push(root->left);
}
}
return maxHeight-1;
}
void preOrderIterative(Tree* root) {
if(!root) return;
std::stack<Tree*> s; s.push(root);
while( !s.empty() ) {
root = s.top(),s.pop();
if( root->isItem() ) {
std::cout << root->data << std::endl;
} else {
if( root->right ) s.push(root->right);
if( root->left ) s.push(root->left);
s.push( root->asItem() );
}
}
}
void inOrderIterative(Tree* root) {
if(!root) return;
std::stack<Tree*> s; s.push(root);
while( !s.empty() ) {
root = s.top(),s.pop();
if( root->isItem() ) {
std::cout << root->data << std::endl;
} else {
if( root->right ) s.push( root->right);
s.push( root->asItem() );
if( root->left ) s.push( root->left);
}
}
}
There is a bug in the careercup software. If you have an empty line in the code, the next line loses the space information. Workaround is to have some spaces in your "empty" lines.
(Q2) Asked which data structure should be used to store browser history.
We can store in browser history in an array
Hash table will suffer from problems like Rehashing when we have to increase the size of the table, while adding more data every history is created. As we don't want to increase the load factor
Day-time along with URL is already coming in a sorted order. So, we just need to append history to our array.
For finding things like : most visited websites, we can attach some key with the URL and store in the array, then simply find the most frequent keys.
Please correct me if i am wrong .....
int find_height(struct node * t)
{
s1.push(t);
check[t]=1;
int current_height=1;
int max_height=1;
while(!(s1.empty()))
{
t=s1.top();
//cout<<" value of t is "<<t->value<<"\n";
//cout<<"current height is \n"<<current_height<<"\n";
if(t->left==NULL && t->right==NULL)
{
if(current_height>max_height)
max_height= current_height;
check[t]=1;
current_height=current_height-1;
s1.pop();
continue;
}
if(check[t->left]==1 && check[t->right]==1)
{
s1.pop();
check[t]=1;
current_height=current_height-1;
continue;
}
if(t->left!=NULL)
{
if(check[t->left]!=1)
{
s1.push(t->left);
current_height++;
}
if(check[t->left]==1)
{
if(t->right==NULL)
{
s1.pop();
check[t]=1;
current_height=current_height-1;
}
else
{
s1.push(t->right);
current_height++;
}
}
}
else
{
if(check[t->right]!=1)
{
s1.push(t->right);
current_height++;
}
else
{
s1.pop();
current_height=current_height-1;
check[t]=1;
}
}
}
return(max_height);
}
int find_height(struct node * t)
{
s1.push(t);
check[t]=1;
int current_height=1;
int max_height=1;
while(!(s1.empty()))
{
t=s1.top();
//cout<<" value of t is "<<t->value<<"\n";
//cout<<"current height is \n"<<current_height<<"\n";
if(t->left==NULL && t->right==NULL)
{
if(current_height>max_height)
max_height= current_height;
check[t]=1;
current_height=current_height-1;
s1.pop();
continue;
}
if(check[t->left]==1 && check[t->right]==1)
{
s1.pop();
check[t]=1;
current_height=current_height-1;
continue;
}
if(t->left!=NULL)
{
if(check[t->left]!=1)
{
s1.push(t->left);
current_height++;
}
if(check[t->left]==1)
{
if(t->right==NULL)
{
s1.pop();
check[t]=1;
current_height=current_height-1;
}
else
{
s1.push(t->right);
current_height++;
}
}
}
else
{
if(check[t->right]!=1)
{
s1.push(t->right);
current_height++;
}
else
{
s1.pop();
current_height=current_height-1;
check[t]=1;
}
}
}
return(max_height);
}
We can find out the height by using level order traversal (non-recursive). One queue is enough.
public static int getHeightOfBTUsingLevelOrder(BTNode btRootNode){
if(btRootNode == null) return 0;
Queue queue = LLQueue.createQueue();
queue.enQueue(btRootNode);
queue.enQueue(null);
int level = 0;
while(!queue.isEmpty()){
Object tempNode = queue.deQueue();
if(tempNode == null){
if(!queue.isEmpty()) queue.enQueue(null);
level++;
}else{
BTNode tempBTNode = (BTNode) tempNode;
if(tempBTNode.getLeft() != null){
queue.enQueue(tempBTNode.getLeft());
}
if(tempBTNode.getRight() != null){
queue.enQueue(tempBTNode.getRight());
}
}
}
return level;
}
//if we use link list data stucture
#include<iostream.h>
#include<conio.h>
struct node
{
node *left;
int data;
node *right;
};
struct stack1
{
node *p;
int level;
stack1 *next;
};
struct stack2
{
int height,data;
stack2 *next;
};
int tree[]={2,4,6,4,7,3,12,10,1,8,16,14},N=12;
node *buildtree(int l)
{
if(l>=N)
return NULL;
node *temp;
temp=new node;
temp->data=tree[l];
temp->left=buildtree(2*l+1);
temp->right=buildtree(2*l+2);
return temp;
}
void disp(node *bt)
{
if(bt==NULL)
return;
disp(bt->left);
cout<<" "<<bt->data;
disp(bt->right);
}
void main()
{
clrscr();
node *bt=new node;
bt->right=NULL;
bt->data=9999;
stack2 *top2=NULL,*temp1;
stack1 *top1=NULL,*temp;
int h1=-1;
bt->left=buildtree(0);
disp(bt);
top1=new stack1;
top1->p=bt;
top1->level=0;
top1->next=NULL;
bt=bt->left;
h1++;
cout<<"\n";
while(top1!=NULL)
{
if(bt->left!=NULL)
{
if(bt->right!=NULL)
{
temp=new stack1;
temp->p=bt;
temp->level=h1;
temp->next=top1;
top1=temp;
}
h1++;
bt=bt->left;
}
else
{
if(bt->right==NULL)
{
temp1=new stack2;
temp1->height=h1;
temp1->data=bt->data;
temp1->next=top2;
top2=temp1;
if(top1->p->right!=NULL)
{
bt=top1->p->right;
temp=top1;
h1=top1->level;
top1=top1->next;
h1++;
delete temp;
}
else
{
temp=top1;
top1=top1->next;
delete temp;
}
}
else
{
bt=bt->right;
h1++;
}
}
}
temp1=top2;
while(temp1!=NULL)
cout<<" (n="<<temp1->data<<",h="<<temp1->height<<")",temp1=temp1->next;
getch();
}
//if we use only array to represant tree then
#include<iostream.h>
#include<conio.h>
void main()
{
clrscr();
int /*tree[]={2,5,3,7,8,2,1,6,8,6,4,9},*/N=6;
int i,j,*h,t,k,p;
for(i=2;(i-1)<N;i=i*2);
i=i-2;
k=(N-(i/2))+((i/2)-(N/2));
h=new int[k]; // stores the height of each brach
j=N-1;
k=0;
p=(((i+1)/2)-1);
while(j>p)
{
t=j;
h[k]=1;
while(t>0)
{
h[k]+=1;
t=((t+1)/2)-1;
}
k++;
j--;
}
j=((i/2)-(N/2));
while(j>0)
{
t=j;
h[k]=1;
while(t>=0)
{
h[k]++;
t=((t+1)/2)-1;
}
k++;
j--;
}
for(j=0;j<k;j++)
cout<<" "<<h[j];
getch();
delete h;
}
What a crappy asshole! Programming using getch() conio.h :-O
Are you in CS 101 programming class !!!
i hope getch() is not a big concern..... yeah you are right i am a 3rd class programmer....!!!! thanks... i love to use getch() in programs....
Question 1;
struct {
tree_node *st[20];
int head;
} stack;
int isempty()
{
if (stack.head == 0)
return 1;
else
return 0;
}
void push(tree_node *n)
{
stack.st[(stack.head)++] = n;
}
tree_node *pop()
{
return stack.st[--(stack.head)];
}
int current[20];
int head = 0;
void get_height(tree *t)
{
if (NULL == t->root) {
printf("Root is null\n");
return;
}
stack.head = 0;
head = 0;
int cur = 0;
int tem = 0;
int max = 0;
tree_node *n = t->root;
push(n);
while (!isempty()) {
n = pop();
printf("poped = %d\n", n->val);
if (NULL == n->left && NULL == n->right){
max = (cur > max) ? cur : max;
printf("Reached leaf\n");
cur = current[--head];
} else {
tem = 0;
if (NULL != n->right) {
push(n->right);
printf("pushed right = %d\n", n->right->val);
}
if (NULL != n->left)
{
push(n->left);
printf("pushed left = %d\n", n->left->val);
if (NULL != n->right) {
cur++;
tem = 1;
current[head++] = cur;
}
}
if (!tem)
cur++;
}
printf("cur = %d\n", cur);
}
printf("height = %d\n", max);
}
Question 1;
struct {
tree_node *st[20];
int head;
} stack;
int isempty()
{
if (stack.head == 0)
return 1;
else
return 0;
}
void push(tree_node *n)
{
stack.st[(stack.head)++] = n;
}
tree_node *pop()
{
return stack.st[--(stack.head)];
}
int current[20];
int head = 0;
void get_height(tree *t)
{
if (NULL == t->root) {
printf("Root is null\n");
return;
}
stack.head = 0;
head = 0;
int cur = 0;
int tem = 0;
int max = 0;
tree_node *n = t->root;
push(n);
while (!isempty()) {
n = pop();
printf("poped = %d\n", n->val);
if (NULL == n->left && NULL == n->right){
max = (cur > max) ? cur : max;
printf("Reached leaf\n");
cur = current[--head];
} else {
tem = 0;
if (NULL != n->right) {
push(n->right);
printf("pushed right = %d\n", n->right->val);
}
if (NULL != n->left)
{
push(n->left);
printf("pushed left = %d\n", n->left->val);
if (NULL != n->right) {
cur++;
tem = 1;
current[head++] = cur;
}
}
if (!tem)
cur++;
}
printf("cur = %d\n", cur);
}
printf("height = %d\n", max);
}
Q1) Do DFS maintaining current depth and max depth . Any time you push, current depth++, any time you pop, current depth-- and if you reach a leaf, try to update the max depth.
- Anonymous August 13, 2011Q2) If you want to do word wheeling on initial prefixes use a trie. Break up a url: www . careercup .com -> www, careercup, com. Ignore www and com and put careercup into a trie.
If you want to do word wheeling on any suffix, use a suffix trie/tree.
Q3). Sort each word and insert into trie.
Q4) Any recursive method can be converted to iterative method. In fact that is what your compiler is doing for you: by using the processor stack! A good way to solve these problems is to write the recursive code, and mimic how the stack looks like, when that recursive method runs.
Q5) Sriram already mentioned. Horner's method.
Q6) Use an array of 26 and update the counts. Assuming we can have array like aaabbbbc (all need not appear).