Algorithm Interview Questions | Glassdoor

# Algorithm Interview Questions

780

interview questions shared by candidates

## Algorithm Interview Questions

Sort: RelevancePopular Date

### Quant Research Intern at Susquehanna International Group (SIG) was asked...

Mar 17, 2013
 Suppose you have 100 GB of data that you want to sort, but you only have 1 GB of memory. How would you sort this data?8 AnswersHint: This isn't really a difficult question (just was an unexpected one for me). You don't really need to know the answer to figure this out. As it turns out, the obvious thing actually works here (and it is a known sorting algorithm).Can you expand on this? What is sorting algorithm?Sorting algorithm = a computer algorithm to sort a list of objects. Well pretend you just have 2 GB of data (for simplicity, assume they are integers) and 1 GB of memory, since the technique is the same. And pretend you want to sort these integers in increasing order. What would you do? Like, what's the first idea that comes to your mind?Show More ResponsesYou do an on disk merge sort, bring chunks in to memory and sort using quick sort, then had the sorted data in to buckets (files). When your done merge them using a merge sort.Yep, exactly.External sortbucket sort. Sort each bucket, then merge.Mark

May 31, 2011
 Given a set of non-overlapping integer ranges (1,3) (5,8), etc., and an input integer, what is the best way to organize the data and allow for quick search based on the input, etc.5 AnswersProbably a BST or a balanced tree of some kindSome sort of a balanced tree would be optimal. Each tree node represents a an interval. We just need to define the less than, equal to operators. Less than is simply defined if the value x you are searching for is less than the beginning of the interval in the node. Equals is if x is within the interval.BST is more than enough given the non overlap. Also defining the less operator would be good.Show More ResponsesInterval search tree. It's made exactly for this purpose.Why not just sort the ranges based on the lower key. and for each query, just perform a binary search, always find answers in O(lgn).

### Senior Applications Developer at Deutsche Bank was asked...

Feb 14, 2011
 We have a pond containing a single bacterium. The number of bacteria double every 5 minutes, and the pond is full of them in 24 hours. If we started with the same pond but two bacteria, how long will it take to fill the pond?4 AnswersI struggled with this a bit and got close. I believe answer is: 23:55This is a clear case of Geometric progression. Find the nth term Tn1 = a*r^(n-1). where n = (24 * 60)/5,a = 1 and r=2. when the initial value (a) = 2, the values become n = ?, a = 2 and r = 2. Since Tn1 = Tn2, Equate the RHS of both the equation. Since the base are equal, equate the powers, doing so will give the n value. When n is convert into minutes one get 23 hrs 55 minutes.this is easy, you don't need all the math. The pond was half full five minutes before, so it's 23:55Show More ResponsesThe first pond started with 1 bacterium and doubled to 2 in five minutes. Therefore, the second pond will take 5 minutes less than the first to be full. ie: 23:55

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

Feb 10, 2013

Dec 13, 2013
 Given a string write a function which prints all the subsets of the string. Now make the function to return only unique solutions. For example if they give you "abc" you print out a ab abc ac b bc c Now for the unique solution constraint, if they give you "aba" the output should be: a ab aba b7 AnswersThere is a divide & conquer strategy with this problem. Divide string into two halves. Recursively print the string on left and then on right. Finally, for each string on left, combine it with every string on the right. (Note this will not give the unique solution.) To obtain the unique solution, a simple way is to use a set to keep track of every substrings we have constructed. If element is already in the set, we simply not add it. In the end, we print out every element in the set. Maybe there is a better way without using extra memory.What about counting the number of each character in a string? for "aba" we have a-2, b - 1. now recursive solution which takes charecter, for a we choose 0a, 1a, and 2a and push to the 'b' where take 0b or 1b. now we have "", "a","aa","ab","b". all subsets + empty one.@Allen: The interviewer specified that he wants a recursive solution and you are not allowed to use extra memory. Note: The interviewer gave me a big hint: "What happens if you sort the array and simply generate all the subsets?"Show More Responses@Marius: what do you mean by "sort the array"? There is no array in the questionSee this link and view discuss session for solution to unique subsets https://oj.leetcode.com/problems/subsets-ii/So this requires subsets to be printed and not substrings; ordering of characters doesn't matter. So sort the characters and generate unique subsets. import java.util.Arrays; import java.util.Scanner; public class UniqueSubsetGenerator { public static void main(String[] args) { final Scanner in = new Scanner(System.in); while (true) { System.out.println("Enter string : "); final String masterWord = in.nextLine(); char[] word = masterWord.toCharArray(); Arrays.sort(word); generateUniqueSubsets(word, 0, ""); } } private static void generateUniqueSubsets(char[] word, int start, String prefix) { //System.out.println("start " + start + " prefix " + prefix); if (start >= word.length) { System.out.println(prefix); return; } char ch = word[start]; int count = 1; for (int i=start+1; idef uniqueSubsets(inpStr): inpStr = sorted(inpStr) subSets = [] uniqueSubsetsHelper(subSets, "", 0, inpStr) return subSets def uniqueSubsetsHelper(subSets, currSet, index, inpStr): if index == len(inpStr): subSets.append(currSet) if index >= len(inpStr): return charLen = getLen(index, inpStr) for i in range(charLen + 1): posSet = currSet + inpStr[index] * i uniqueSubsetsHelper(subSets, posSet, index + charLen, inpStr) def getLen(index, inpStr): currChar = inpStr[index] currLen = 0 while index < len(inpStr): if inpStr[index] == currChar: currLen += 1 else: return currLen index += 1 return currLen

Jun 30, 2010
 Find the Kth hisghest element in a given array.5 Answers1. Sort the array and get the element. 2. Put in binary tree. Travel from root and get the kth node.binary tree would not work unless it was balanced and even then searching for the kth highest node would be overly complex. Better answer - Perform k iterations of a bubble sort. Run time would be O(kn). To prevent O(n^2) (k ~ n) reverse bubble sort if k > n/2.http://en.wikipedia.org/wiki/Selection_algorithmShow More Responsesborrow the way of splitting array in quicksort, which can achieve O(n) time in average for any k. The more detail of this algorithm is: select a pivot value, and split the array into three parts. The elements in the first part are less or equal to the pivot value or empty, the second part is one element which is equal to the pivot, and elements in the last part is great them the pivot value or empty. If the index of the second part element is equal to k, then just return it, else if it is greater than k, then go to split the first part recursively, else go to split the third part recursively.function _kth(array, k) { return array.sort(function (a, b) { return b - a; }).slice(0, k); } _kth([1, 23, 12, 9, 30, 2, 50], 3); // [50, 30, 23]

Sep 2, 2012
 Write a function that finds the square root of a decimal number.4 AnswersA binary search with a constraint for precision. We should also take care of the interval (0.00, 1.00).// iterative (function(n){ var lo=0; var hi=n; var tries=500; var prev; while(tries--){ var curr=hi-((hi-lo)/2); var prd=curr*curr; if(prd===n || prev==curr){ break; } prd>n ? hi=curr : lo=curr; prev=curr; } console.log(curr, curr*curr, 500-tries) })(64)// recursive with closure use (function(n){ var lo=0; var hi=n; var tries=500; var prev; function rec(){ var curr=hi-((hi-lo)/2); var prd=curr*curr; if(prd===n || prev==curr || !tries--){ return curr; } prd>n ? hi=curr : lo=curr; prev=curr; return rec() } var result = rec(); console.log(result, result*result, 500-tries) })(25)Show More ResponsesFor the above, I would set my high to be the max(x, 1), Let say's one call any of your functions with 1/4, or with any 0 epsilon) && (epsilon 100) return; return guess; })

### Software Engineer II at Orbitz Worldwide was asked...

Dec 11, 2010
 How can you solve n^m efficiently only using +, -, *, /.4 AnswersThis is one solution that doesn't deal with negative exponents exp(n, m) { if (m == 0) return 1 if (m == 1) return n exp = exp(n, m / 2) if ( isOdd(m) ) exp = exp * n return exp }int f(int n, int m) { if(m==0) return 1; if(m==1) return n; n=n*f(n,(m-1)); return n; }There is no need to solve it recursively. it is pretty simple int calculateExp(int n, int m) { exp = n for (i = 1; i <= m; i++) { exp = exp*n } return exp; }Show More ResponsesDisadvantage of recursion is the large amount of space on the stack for a large m in this case.

Jan 13, 2012