Data structures Interview Questions | Glassdoor

# Data structures Interview Questions

117

interview questions shared by candidates

## Data structures Interview Questions

Sort: RelevancePopular Date

### Senior Software Engineer at TripAdvisor was asked...

May 2, 2010
 What is the efficiency of finding an element in an unsorted array of strings3 AnswersO(n)O(n/2), no?Complexity is O(n) but running time can be faster if run parallel.

### Senior QA Engineer at Yahoo was asked...

Mar 11, 2009
 Given a dictionary, with all possible anagrams of a word, how would you test it out and what is the Data Structure that you will use to construct it with Design of the same.2 AnswersI said a tree with root nodes as the first alphabet and each branch containing a word. The other solution was to use arrays, but i was unable to get the full answer to this.I would use a Trie. Trie's are a neat data structure that let you build dictionaries seamlessly and you can easily keep track at the head nodes of how many sub nodes you have, where each sub node counts as a completed word. Trie's are commonly used to build dictionaries that support fast prefix look-up.

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

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

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

Mar 19, 2009
 Given two linked lists A and B, return a new linked list C, where C consists of all elements in A or B that are contained in only A or only B.2 AnswersHint: hash table!public static void createUniqueListC(List listA, List listB) { Set set = null; List list = null; if (listA != null && listB != null) { set = new LinkedHashSet(); list = listA; int length = listA.size() + listB.size(); for (int i=0; i=listA.size()) { list = listB; i = 0; length = length - listA.size(); } if (!set.add(list.get(i))) { set.remove(list.get(i)); } } Iterator itr = set.iterator(); while (itr.hasNext()) { System.out.println(itr.next()+" "); } } }

### Member of Technical Staff IV at Juniper Networks was asked...

Jul 6, 2009
 Given a binary tree, how would you write program for getting mirror image of tree in O(n) time? Is it possible ? Assume you have no constraints on space.2 Answersif t is nul return; Mirror(Right) Mirror(Left) changeNodes(t)//call mirror( root, img_root) //img_node is passed by reference mirror (node, img_node ): if (node == NULL) return img_node.left = node.right img_node.right = mode.left mirror (node.right, img_node.left) mirror (node.left, img_node.right)

### Software Engineer at TripAdvisor was asked...

Apr 27, 2012
 How would you implement an LRU Cache (LRU - Least Recently Used). What would your data structure look like. This was also a whiteboard problem.2 AnswersThe answer is to use a LinkedHashMap or a similar data structure because it allows O(1) on all needed operations.LinkedHashMap works only if an item is used only once, so you need to implement your own O(1) insertion, deletion and search that are tailored to LRU.

### Software Engineer Internship at Palantir Technologies was asked...

Oct 18, 2011
 Print the nodes of a complete binary tree in level order.2 AnswersBreadth first searchDetailed 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 Amazon was asked...

Apr 28, 2009
 You are to write a spell checker. Discuss the API, Data Structures and Algorithms.2 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)

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

Nov 3, 2011
 You're given a set of strings. You want to test if any two strings in the set are anagrams.2 AnswersI gave a solution that involved sorting the strings and using that as elements of a new set to check for anagrams. They asked me to reduce the memory footprint of my solution without sacrificing the O(N) time (N = number of strings, we assumed that string lengths were O(1)). I suggested that if the strings represent words in a natural language, we might be able to apply the same Huffman encoding to everything in the set, which maybe could reduce space by, say, 50%. They seemed satisfied with that solution.You could also check to see if the words have the same number of characters and same characters using a hash map. Only anagrams can satisfy that.

### Software Engineer at LinkedIn was asked...

Sep 13, 2011
 Design data structure to implement T9 dictionary1 AnswerTrie structure
3140 of 117 Interview Questions