# Data structures Interview Questions

interview questions shared by candidates

## Data structures Interview Questions

Write a function that returns the depth of a tree. 4 Answerspublic static int depth(Node root, int level) { if(root != null) { if(depth(root.right, level + 1) > depth(root.left, level + 1)) return depth(root.right, level + 1); else return depth(root.left, level + 1); } return level; } Slightly simplified :] (I think this works; not doubling up on the recursive calls either) public static int depth(Node root, int level) { if (root == null) return level-1; return Math.max(depth(root.right, level+1), depth(root.left, level+1)); } int finddepth(node_t* node) { if(node == NULL) return -1; else return 1 + MAX(finddepth(node->lchild), finddepth(node->rchild)); } Show More Responses This person is a product leader at Amazon who may be able to give you some good advice. Good luck! https://www.rooftopslushie.com/profile/ask |

Write an algorithm that does an in-order traversal of a tree recursively. Now, write the same algorithm iteratively. 4 AnswersHint: You'll want to use a stack in the iterative version. Haha, I got that same question on my interview. It made me sweat, because I knew I was supposed to use a stack, but I had never done it before. It was fun working it out on my own. public void inOrder(Node* root) { if(root == NULL) return; inOrder(root->left); cout element; inOrder(root->right); } Show More Responses // recursive void InorderTraversal( Node *root) { if ( root== NULL) return ; // status 2 InorderTraversal( root->left ); // status 1 Print (root); InorderTraversal(root->right); // status 0 } // NON-Recursive Version for Pre/In/Post-Order the idea behind this method is to employ a stack to emulate the recursion void NonRecTraversal( Node *root ) { if ( root == NULL ) return ; stack stk; bool flag = 2;// the key: keep track of the status of the top element stk.push(root); while( !stk.empty()) { if ( flag == 2 ) { /* Print (node) ; this is preorder */ if ( stk.top()->left != NULL ) stk.push(stk.top()->left ); else flag = 1; } else if ( flag == 1) { /* Print (node) ; this is inorder */ if ( stk.top()->right != NULL) { stk.push(stk.top()->right); flag = 2; } else flag = 0; } else { /* Print (node) ; this is postorder */ Node *temp = stk.top(); Stk.pop(); If ( !stk.empty() && stk.top()->left == temp ) Flag = 1; // come back from left child Else Flag = 0; // come back from right child } } } |

Give me 5 different ways of finding the median (middle element) of a linked list. For the sake of simplicity, assume the list has odd number of ints. Also mention the runtime for each. Follow up: What's the fastest way you could find the median? What is the runtime? Oh.. and yes, code your answer(s) in any language of your preference. 4 AnswersHint: think of different data structures you could use here function Node(data){ this.data=data; this.next=null; } function LinkedList(){ this.head=null; this.add=function(node){ node.next=this.head; this.head=node; } } var myList = new LinkedList(); for(var i=0;i<9;i++) myList.add(new Node(Math.random())); var tmp = []; var cur=myList.head while(cur){ if(cur) tmp.push(cur) cur=cur.next; } console.log(tmp[Math.ceil(tmp.length/2)].data) function Node(data){ this.data=data; this.next=null; } function LinkedList(){ this.head=null; this.add=function(node){ node.next=this.head; this.head=node; } } var myList = new LinkedList(); for(var i=0;i<9;i++) myList.add(new Node(i)); var cur=myList.head var half=myList.head var i=0; while(cur){ if(i%2) half = half.next; cur=cur.next; i++; } console.log(half); Show More Responses public int findLinkedListMedian() { Link fastLink = head, slowLink = head; while(fastLink != null) { fastLink = fastLink.next; fastLink = fastLink.next; slowLink = slowLink.next; } return slowLink.key; } |

### Software Engineer Intern at TechSmith was asked...

Given a singly linked list, how can you find if there is a loop in the list? 3 AnswersI came up with an O(N^2) method, but he told me there is a simpler O(N) method. (Look it up if you are interested) if you get back to the starting node after reversing the list, that means there is a loop in the list. http://ostermiller.org/find_loop_singly_linked_list.html |

Given an array of integers, all but one of which appears an even number of times, find the one integer which appears an odd number of times. 3 AnswersI answered him that we can do a XOR, and then he asked me to it in another way and wanted me to write a code, read out so that he could note it. I wrote the code using HashMap. XOR fails for an invalid input [2,4,6,6] as it will return 6. You should validate your args and in this case the cost of validating your args is the same as obtaining the solution Create a hash set. Iterate through the array. If the set contains this value already, remove it Else add the value to the set In the end, if a value was in the array an even number of times, it is no longer in the set. Otherwise, it's still in the set. After iterating through the array, the set will contain only one value, the one that was repeated an odd number of times. |

Print the nodes of a complete binary tree in level order. 2 AnswersBreadth first search Detailed analysis and solution are available in the following blog: http://codercareer.blogspot.com/2011/10/no-11-print-binary-trees-from-top-to.html |

### Software Engineer at Zynga was asked...

Blocking queue implementation. Coding was required. 2 AnswersConventional implementation that can be found in most data structures and algorithms books or Wikipedia. get the synchronization right on the push and offer on the BlockingQueue. Use either Locks or wait / notify mechanism. |

How would you print last n elements of a linked list, n being small compared to size of linked list? 3 AnswersUse an "output array" of n elements, populating it with elements encountered in the linked list. After the examining/saving the first n elements in the linked list, loop back to the beginning of the output array and start overwriting the existing values. Continue traversing/overwriting/looping to the end of the linked list. The output array will contain the last n values, with its index indicating the starting point from which you can print the last n values of the lined list.. take two pointers to the linked list. the first pointer points to the start, move the second pointer by n-steps. Now, move both pointers by one step each until the second pointer reaches the end. At this stage your first pointer will be pointing to the nth last element in the list. Simply print the value and keep moving the first pointer till the end. #include using namespace std; struct Node{ Node * next; int data; }; Node * addFront(Node * head, int val){ Node * temp = new Node; temp->data = val; temp->next = head; head = temp; return head; } void display(Node * head){ if (head != NULL) { coutdatanext; } coutnext == NULL) { coutnext; distanceBetweenTwoPointers++; } while (first->next != NULL) { first = first->next; second = second->next; } coutnext != NULL) { coutdatanext; } coutdatadata = 2; head->next = NULL; head = addFront(head, 5); head = addFront(head, 7); head = addFront(head, 6); head = addFront(head, 3); display(head); // print last n elements of the linked list displayLastNElements(head, 3); return 0; } |

### Software Engineer at Amazon was asked...

You are to write a spell checker. Discuss the API, Data Structures and Algorithms. 3 AnswersDid not know the answer but worked through the answer interactively with the interviewer. This was during a phone interview. Did not get the full solution, but still got accepted for the site visit. two parallel approaches are needed: sounds like (mapping) single typo (search by character) This person is a product leader at Amazon who may be able to give you some good advice. Good luck! https://www.rooftopslushie.com/profile/ask |

### Software Development Engineer at Amazon was asked...

Create a Queue using two Stacks. 2 AnswersThere was no coding required, only showing/drawing how it would work and describe its algorithmic complexity. The solution uses two operation swap() which swaps the top elements in both stacks move(0 or 1) if it's 0 them moves top item from stack 0 to stack 1 and vice versa Given stack S0 and S1 move(0)= push(S1, pop(S0)) swap() = x = pop(S0) push(S0,pop(S1)) push(S1,x) So the solution is to repeat swap and move. By induction, a 1 item stack is already a queue. Given this works for i, here is how it would work for i+1 (to make this example simple I will show it for i=4) Since it works for 4 then you have the following stacks: S0 S1 e1 e2 e3 e4 (push new element into S0) S0 S1 e5 e1 e2 e3 e4 (move) S0 S1 e1 e5 e2 e3 e4 (swap) S0 S1 e5 e1 e2 e3 e4 (move) S0 S1 e2 e5 e3 e1 e4 (swap) S0 S1 e5 e2 e3 e1 e4 (move) S0 S1 e3 e5 e4 e2 e1 (swap) S0 S1 e5 e3 e4 e2 e1 (move) S0 S1 e4 e5 e3 e2 e1 (swap) e5 e4 e3 e2 e1 (move, move, move, move) S0 S1 e1 e2 e3 e4 e5 |