Adobe Interview Question for Software Engineer / Developers






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

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.

Q2) 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).

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

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

- anon August 14, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Postorder is a form of DFS and if needed, any node related information (like number of children already visted, the depth etc) can be also pushed onto the stack, along with the node, instead of modifying the node.

So, that solution is correct. In fact, there was some code posted too.

- Anonymous August 14, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Q5. The expression can be rewritten => a + (((dx +c)*x + b)*x)*x)
The powers of x can be computed in O(logN). For eg: x^4 = (x^2)^2

- Sriram August 13, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- xbai@smu.edu August 13, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

One stack is enough. See DFS solution mentioned before.

- Anonymous August 13, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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--;
      }
   }
}

- Anonymous August 14, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

BUG: Need to pop the leaf too...
perhaps more bugs, but idea should be clear I hope.

- Anonymous August 14, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- anon August 14, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Anonymous August 14, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- j August 14, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- anon August 14, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- anon August 14, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- anon August 14, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Anonymous August 14, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- anon August 14, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- anon August 14, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- anon August 14, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous August 14, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- anon August 14, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Anonymous August 14, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

1.ANS :: Find the total levels in a binary tree and add +1 to the level we will get the height of the tree

- DNS August 14, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I agree this BFS approach is much simpler and less error-prone than DFS. A stack, plus two counter variables serve the purpose.

- anon August 14, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Anonymous August 14, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- j August 14, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

In DFS you can push all children too...

- k August 14, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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);
        }
    }
}

- Developer August 15, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Anonymous August 15, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Thanks! That explains why so many of the postings with code look crappy. When I include some blanks on any empty lines it worked as expected.

- Developer August 18, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Ans6 Use an array of 26 size, increment the counter by 1 for each character. In the array, where the value found to be 0, that is the missing element. This can be performed in O(n) time complexity

- NoOne August 14, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

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

I think linked list will be better

- anshulzunke September 12, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}

- neh August 15, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}

- neh August 15, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- Kishore Jinka August 16, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//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;
}

- infinity August 23, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

What a crappy asshole! Programming using getch() conio.h :-O
Are you in CS 101 programming class !!!

- anonymous August 23, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- BIPLOVESARKAR August 24, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Rather h = new int[k] is deallocated with delete h, instead of delete[] h;

- Anonymous September 07, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@anonymous
fuck off loser.. you cant write code to shit in your life

- Anonymous April 10, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}

- Ravi November 15, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}

- Ravi November 15, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Q4 Answer)
struct BinaryTreeNode *MirrorOfBinaryTree(struct BinaryTreeNode *root)
{
struct BinaryTreeNode *temp;
if(root) {
MirrorOfBinaryTree(root->left);
MirrorOfBinaryTree(root->right);
temp=root->left;
root->left=root->right;
root->right=temp;
}
return root;
}

- pirate July 13, 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