Algorithm Interview Questions | Glassdoor

# Algorithm Interview Questions

785

interview questions shared by candidates

## Algorithm Interview Questions

Sort: RelevancePopular Date

### Software Engineer at Yelp was asked...

Jan 27, 2014
 Given a list of strings, write a function to calculate the longest common prefix (LCP) of all those strings.6 Answersdef min_length(words): min_len = float('inf') for word in words: if len(word) < min_len: min_len = len(word) return min_len def lcp(words): max_length = min_length(words) longest = "" if len(words) == 0: return "" for it in xrange(0, max_length): current = words[0][it] same = True for word in words[1:]: if word[it] != current: same = False break if same: longest += current else: return longest return longest if __name__ == "__main__": assert lcp(["anna", "any", "ant"]) == "an" assert lcp([""]) == "" assert lcp(["anna", "anna"]) == "anna" assert lcp(["foo"]) == "foo"Or def yp(words): shortest_word = min(words, key=len) lcs = shortest_word cutoff_id = len(lcs) # advantage here: dont copy/slice the sting O(N) for word in words: for n in range(cutoff_id - 1, 0, -1): # go backwards to make less cmp if word[n] != lcs[n]: cutoff_id = n return [lcs[:cutoff_id]] if __name__ == "__main__": print( yp(["anna", "any", "ant"]) ) print( yp(["anna", "anna"]) ) print( yp([""]) ) print( yp(["foo"]) )def find_lcp(words): lcp = 0 while(True): current_char = words[0][lcp] # yes, this fails if the first word is empty for w in words: if w[lcp] != current_char or lcp+1 > len(w): return words[0][:lcp] lcp += 1 print find_lcp(['aaaaac', 'aab', 'aac'])Show More Responsespublic class LeastCommonPrefix { public static String lcp(String[] words) { int maxLen = words[0].length(); for(int i=1; i

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

May 15, 2009
 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. Upon completion, asked to improve the algorithm in terms of both time and space, eventually asked to do it in O(n) time and constant space.4 Answersxor the entire array, all the integers which appear an even number of times will cancel eachother outint[] theArray = new int[]{1, 1, 2, 2, 3, 3, 3, 4, 4, 10, 10, 10, 10, 10, 11, 11, 12, 12}; Map theMap = new HashMap(); for (int i = 0; i mapKeys = theMap.keySet(); for(int keyInt : mapKeys) { if(theMap.get(keyInt) % 2 != 0) { System.out.println(keyInt + " occurs odd number of times"); } } }I was also asked this in 2010,march.Show More ResponsesXOR

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

Apr 18, 2012
 how to get the most significant bit from a byte?3 AnswersI couldnt understand what he ment by byte. I thought eight bits in binary format. But what he was asking about converting a decimal number into binary and getting the most significant bit out of it.right shift the number by 7 positions and you get the most significant bit printf("%d",n>>7);If he was asking about converting a decimal integer number into binary and getting the most significant bit out of it, then the answer is just: divide by 2, again and again until you get the last '1'; Or using programming code: while(x) { x >>= 1; ++n; }

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

Jul 13, 2012
 Create a data structure that minimizes time complexity of retrieving median and inserting new element. Getting median should be O(1) and insertion should be O(log(n)).5 AnswersA heap in which the root is the median and it has max heap of the lower half on left and min heap of the rest on right.Can we not use a BST which is kept balance after every insertion using AVL ? The median is always the root of this tree, so median is retrieved in O(1) and insertion/deletion is O(log n) for balanced tree.I guess a Red-Black tree would be a more appropriate data structure to use. Since it is a perfectly balanced tree data structure, the median would always be at the root. The insertion takes time proportional to the height of the tree i.e. O(logn)Show More ResponsesWe can use two heaps, one max heap, one min heap. Large values are pushed into the min heap, and small values are pushed into the max heap. Keep the difference of the number of elements in the two heaps smaller than 2. The median will be the top of the heap with more elements or the average of the tops of the two heaps if they have same number of elements. I think this is easier to implement.array?binary search when do insertion?

### Java Developer at Goldman Sachs was asked...

May 10, 2011
 Fibonacci implementation3 AnswersI got the same f-ing question todayChetan Trikha is a no gooder vice president of Goldman, who has learnt fibonnaci in school and has never used it, and is asking candidates to implement it, whereas nobody can on the fly.//Fibonacci Sequence Generation using Recrusion Ex. /* Fib(0) is 0 [base case] * Fib(1) is 1 [base case] * For all integers n > 1: Fib(n) is (Fib(n-1) + Fib(n-2)) [Recursive definition] */ public int GenerateFibonacci(int count) { if (count <= 1) return 1; else return GenerateFibonacci(count - 1) + GenerateFibonacci(count - 2); }

### Software Engineering Intern at Palantir Technologies was asked...

Jun 3, 2013
 You have a set of envelopes of different widths and heights. One envelope can fit into another if and only if both the width and height of one envelope is greater than the width and height of the other envelope. What is the maximum number of envelopes can you russian doll?3 AnswersSort the list of envelopes by x-coordinate. Then you already have the envelopes increasing by x-coordinate. Then, this is just a classic dynamic programming problem in disguise, the longest increasing sequence. Here, we want to find the sequence of envelopes that are increasing in y-coordinate, since after sorting we already have it increasing in x. Sorting takes O(n log n) and the algorithm itself runs in O(n^2), so total running time of O(n^2)Anonymous (Aug 16, 2013): Your algorithm is only valid if the width of each envelope equals to it's height, or is either greater or smaller than it's height. It would give incorrect result if there are envelopes with a different primary side. For example it will not work if there are the following envelopes in the set: 8x3, 10x5 and 4x9. The answer here should be all 3 envelopes, but will be 1 using your algorithm (4x9) since the height of the second envelope in the sorted list (8x3) is smaller than 9. Therefore initial sorting has to be by the primary side (as opposed to a specific side). Basically, an additional if-clause is required.use topological sort

### Software Engineer at IBM was asked...

Jun 24, 2012
 to developd to class software describe it3 Answersto make all software in android techno... because bascially android is open source wihich is based on linux kernal so it's not possible to make all softwere in android..no... because bascially android is open source wihich is based on linux kernal so it's not possible to make all softwere in android..

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

Nov 5, 2013
 About the details, and interviewer will communicate with you when you are typing. 3 AnswersDivision - Divide A/B - repeatedly subtract B from A, until A < B. At which time print the number of subtractions as the quotient. The left over value in B, is the remainder.More efficient - http://www.prasannatech.net/2009/01/division-without-division-operator_24.htmlFor the sum case of digits try a binary search type approach: Let S be the sum we are searching for Sort the array - you can do this in n*Log(n) (see http://en.wikipedia.org/wiki/Sorting_algorithm) Here is where the binary search idea comes in Divide the sorted array into sub arrays A1 and A2. Take the mid elements of both sub arrays as pivots p1 and p2. This gives us 4 sub-sub arrays - In A1, we have the left of p1 as A11 to the right of p1 as A12. In A2, we have to the left of p2 as A21 and right of p2 as A22. If p1 + p2 > S then we look in A12 and A13, A11 and A13 and A11 and A12 If p1 + p2 < S look in A12 and A14

### 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 Engineer at VMware was asked...

Oct 28, 2013
 You are given a dictionary, such as /usr/share/dict/words, containing a list of words, one per line. You are also given seven tiles. Each tile is either blank or contains a single lowercase letter (a-z). List all of the words from the dictionary that can be produced by using some or all of the seven tiles, in any order. A blank tile is a wildcard, and can be used in place of any letter. Try to use a minimal amount of memory. 1. Find all of the words that can be formed if you don't have to deal with blank tiles. (You may skip this step and go straight to step 2). 2. Find all of the words that can be formed, including those where blank tiles are used as wildcards. 3. Would you do things differently if you had to process several hundred tile sets with the same dictionary?4 AnswersI provided a brute force solution.I think terinary search tree is better for this. minimal space.What about a bloomfilter on the dictionary to quickly search if the tile permutation is inside the dictionary or not?Show More ResponsesCreate a Trie Keep on traversing from the root, if wildcard encountered, visit all children.
6170 of 785 Interview Questions