Data structures Interview Questions | Glassdoor

# Data structures Interview Questions

117

interview questions shared by candidates

## Data structures Interview Questions

Sort: RelevancePopular Date

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

Mar 19, 2009
 Binary tree with parent pointers, given two nodes find common ancestor. 3 AnswersHint: use a hash tableFor each node traversed from the root, if both values are less than the current Node, then move to the left if both values are greater than the currentNode, then move to the right, if the value of current Node is between value 1 and value 2, then you have found the nearest common ancestor.Rajiv, you can't do that is tree is by parent pointers. you need to bubble up from the given nodes and put parents to a hash.

### Software Engineer at Microsoft was asked...

Apr 29, 2009
 Write a code for finding a certain element in an unsorted array assuming element definitely exists. How can we improve the efficiency?3 Answersi think the simplest way to solve is to scan it once, it will have O(n) complexity well any other answers?it's O(n) to improve efficiency sort it first : O(nlgn) then every look-up becomes O(lgn)O(n) ia always smaller than O(nlogn)+O(logn). hence linear search will always be efficient

### Software Development Engineer Intern at Microsoft was asked...

Mar 18, 2009
 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 } } }

Oct 1, 2010

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

Feb 1, 2011
 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 solutionCreate 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.

### Software Developer Intern at Expedia was asked...

Aug 27, 2012

May 15, 2010
 How would you implement a stack to achieve constant time for "push", "pop" and "find mininum" operations? 3 AnswersThe catch is to use another stack to remember the minimum. The other operations already take constant time.to the last poster, actually, depending on how you implement it, push and pop might NOT be constant...that's the problem right? you could implement a stack with an array and pushes and pops WOULDN'T be constant. I think a possible solution would be to use a linkedlist. pushes and pops are constant because you're just adding another node to the head.With an array you can implement in Push/Pop in constant time. The expansion/contraction of the array can be implemented such that the amortized cost is constant.

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

Jun 29, 2010
 1. Find common elements between two arrays of integers. 2. Find cycles in a graph. 3. Efficiently find duplicate elements in an array of numbers with bounded entries (for example, elements are between 0 and 99). 4. Reverse word sequence in a string inplace. 5. Efficiently find all Pythogorean triplets in a given array of integers. 6. Find all anagrams in a list of words. 7. Set operations.2 Answers@1: Can you first mergesort the two arrays, and then do the following? That'll be nlogn runtime? I haven't tested it out... int i=0, j=0; while ( i sorted_array2[j] ){ j++; } else { //must be equal printf("Common element: %d\n", sorted_array1[i]); i++; j++; } }for #1 you just have to hash the first array and then if(contains) the hash table against each element of the second array O(n) # of comparisons

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

Mar 29, 2012
 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

### Java Engineer at Nextlabs was asked...

Jan 12, 2012
 3. Trees (binary and otherwise) form the basis of many common data structures. Please describe some of these data structures and when they might be used.2 Answers- Manipulate hierarchical data. - Make information easy to search (tree traversal,binary search tree) - Make information easy to use in a sorted lists of data 1. all the items 2. a section of a tree 3. Searching for an item 4. Adding a new item at a certain position on the tree 5. Deleting an itemTrees can be differentiated by the types of properties maintained during insertion and removal operations. Ideal is a balanced tree. There are tradeoffs between the maintenance and speed of access. Sometimes you want only approximate balance of your tree (less maintenance). Heaps are one example of a resource implemented using trees. Design choice may also depend on the statistical nature of the data inserted.
2130 of 117 Interview Questions