Data structures Interview Questions | Glassdoor

# Data structures Interview Questions

117

interview questions shared by candidates

## Data structures Interview Questions

Sort: Relevance Popular Date

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

Mar 23, 2011
 Given a (potentially large) array of integers, all but one repeating an even number of times, how would you find the one repeating an odd number of times in an efficient way? eg [1 2 3 3 2 2 1 4 2] should return 4 7 Answers Use any collection data structure to insert and remove the numbers, such that at the end the only one remaining will be the one repeated an odd number of times. For example we can use a tree. We consider on number at the time. We first search for the number in the tree. If found, we will remove it. Otherwise, we will insert it. At the end, the number (or the numbers, in general) repeated an odd number of times will be in the tree. For the complexity it is necessary to perform an amortized analysis. Another data structure that we can use is the hashmap. However, the space consumption and management could be high, if the map automatically resizes. Ex-or the numbers. For the odd occurrence, the ex-oring will not result in zero. Ex-oring is a great idea, one other solution is to sort the array and then in one pass you can find out the number that occurs odd number of time with quicksort avg case nlogn and worst case n^2 Show More Responses Few steps of counting sort can help us do it in O(n) time. Step I: find min and max, thus the range Step 2: initialize array of the range with 0 Step3: as numbers come in, increment the a[number] by 1. Step4: scan the array to find the odd number. Ex-or is a good solution only if 0 is not in the input list. If 0 occurs odd number of times, not sure it will report it. Tellig about zero is an excellent catch.. +1 by using LINQ it can be acheived. var numList = new List() {1 ,2, 3, 3, 2, 2, 1, 4, 2 }; var oneOccurance = numList.GroupBy(x => x).Where(y => y.Count() == 1).Select(y => y.Key); //Ans = {4}

Jan 13, 2012

### Financial Software Developer at Bloomberg L.P. was asked...

Oct 1, 2010
 How would you print a linked list in reverse order? 4 Answers public Node reverseList(Node root) { Node rev = root; Node current;// = root; Node fwd = root.left; rev.left=null; while (fwd!=null) { current = fwd; fwd=current.left; current.left=rev; rev=current; } return rev; } @blakdogg: The question is not about how to reverse the link list but to print it in reverse. Here is my solution: void reversePrint(Node* current) { if (current) { reversePrint(current->next); printf ("%s \n", current->data); } } Jon: Your solution would crash on a large data set. Too much stack space used. The first solution was a hint at the overall solution which would be to use that function twice. Once to reverse the list, then print, then reverse it back. Show More Responses void printReverseLinkedList (Node node) { if (node.next != null) { printReverseLinkedList(node.next); } System.out.println(node.data); }

Dec 5, 2012
 "Reverse" of the problem if finding k-th smallest element in a tree: I had to find k-th largest. 4 Answers Keep a global or reference counter increase it every time you encounter a tree node. Return when the counter == k. do an in-order traversal which gives you a sorted list. the rest is obvious. do an in-order traversal which gives you a sorted list. the rest is obvious. Show More Responses The tree data structure is red herring, it does not help in any way to find the kth element The solution to this problem is called partial sorting and can achieve O(n) - number of nodes time complexity

Feb 10, 2013

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

Oct 19, 2010
 Given an infinite stream of numbers, find the top 50 integers. What's the data structure to use, and what's the time complexity. 4 Answers Use a min-heap. Use a B-Tree with max degree 50. The worst case complexity should be O(log n) for insertion as well as search if you are using a min heap and say the first insertion you do happened to be the largest element. then? Show More Responses @birbal: First, you should let the min-heap fill completely and then you should compare every incoming number with the top element and insert that in the heap if it is greater than the least element. I have the working code with me...

Jun 23, 2012

### Software Development Engineering Intern at Amazon was asked...

Jun 23, 2012
 Write a function that returns the depth of a tree. 3 Answers public 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)); }

### Software Development Engineer Co-Op at Amazon was asked...

Apr 30, 2012
 How to print a link list reversely 3 Answers The simplest solution would be: 1. Traverse a linked list from head to tail 2. During traversal, push all the elements of the node into a stack 3. Once the traversal is done, pop all elements and this will print the linked list in reverse order ... Looking fwd for an optimized solution ... void printLLreverse(Node *headNode) { //this is going to just iterate through the LL //add each element to a stack and //print the stack when we are finished stack llStack; Node* currNode = headNode; while(currNode) { llStack.push(currNode->data); currNode = currNode->next; } while(llStack.size() > 0) { cout << llStack.top(); llStack.pop(); } } the stack solution is good, you can also use recursion void printReverse(ListNode node) { if(node == null) return; printReverse(node.next); System.out.println(node.value); }

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

Oct 13, 2010
 Given a singly linked list, how can you find if there is a loop in the list? 3 Answers I 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
1120 of 117 Interview Questions