Algorithm Interview Questions | Glassdoor

# Algorithm Interview Questions

763

interview questions shared by candidates

## Algorithm Interview Questions

Sort: RelevancePopular Date

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

Apr 29, 2009
 How many unique paths are there from B-L point to the T-R point of a chess table? What would be your approach to calculate this?6 AnswersZhat would depend on whether there exist restrictions on the moves your piece can make.No it wouldn't. The question asks how many unique paths there are, not how many unique paths a certain piece can make. Also, I think we must assume the unstated rule that a given square may only be crossed in a given path once - otherwise the answer is infinity!@NCLrry: If you can only move up and right, but not left or down, then there are fewer paths and that is usually how I have seen this puzzle worded.Show More ResponsesUse dynamic programming.3432If only allow moving in vertical or horizontal direction: f(x, y) = f(x-1, y) + f(x, y-1); where f(1,1) = 1 f(8,8) = 3432 If allow moving in vertical or horizontal or diagonal direction: f(x, y) = f(x-1, y) + f(x, y-1) + f(x-1, y-1); where f(1,1) = 1 f(8,8) = 48639

Nov 8, 2010

### 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

Feb 10, 2013

### Summer Analyst at Goldman Sachs was asked...

Feb 16, 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

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

Jan 3, 2013
 Given a string of format '2+3*2-1', calculate and return the result. No parenthesis in the input, just integers and + - * / operators. Operator precedence has to be considered. Linear time complexity and minimal data structure use is preferred.4 AnswersI did 2 pass on input string.I also did two passes on the input string. I created the following helper classes: Calculate, which takes in the input string, the location of the operation and the operation itself, and returns the result of the calculation. It's not too hard to figure out how to extract the operands from the string (just iterate backwards/forwards until you bump into the end, beginning or another operator). InsertResultInStr, which takes in the input string, the location of insertion and places a given integer into the input string. I couldn't prove this, but I think its true that the result of a multiplication between m and n digit numbers can always fit in the concatenation of those numbers with '*' in the middle. Sorry if the explanation is a little confusing, but InsertResultInStr(input, 3, 6) for input string = "2 + 3*2* - 1" should result in string = "2 + 6 - 1". Now, in the main fn, iterate through the string until we find a '*' or a '/', and when we do, calculate the answer via Calculate(), then InsertResultInStr(). Then iterate through the string again looking for '+' and '-', and finally convert the final string to an int and return it. One thing that is not clear in the description is what we should do to handle if a/b is not an int. My guess is that a/b will always return an integer. I guess you can handle this in any way you want: ignore the stuff after the decimal point, or maybe keep the maximum amount of precision that your string-space can handle.I used a different approach by making use of a queue: - parse the string, and push in the operands and operators onto a queue - evaluate the queue My general approach was this: - read in lhs, operator and rhs - if operator is "+" or "-", enqueue lhs and operator > if string is empty, we are done parsing --> enqueue rhs > else, prepend rhs to the string (e.g. str = rhs + str), to be parsed further - else, the operator is "*" or "/" --> perform the operation on lhs and rhs, and prepend the result to the string Final step is evaluating the queue -- simply dequeue lhs, operator and rhs and evaluate. (*note: this was tricky to get right on paper, and I've made a few mistakes which I had to debug) // Given: a well-formatted string e.g. "2 + 2*3 - 1". Evaluate the expression. string getCurr(string& str); int eval(string str) { if (str.empty()) return -1; // operand / operator queue std::queue q; // construct it char buf; while (!str.empty()) { string lhs = getCurr(str), oper = getCurr(str), rhs = getCurr(str); // evaluate directly if (oper == "*") { int res = atoi(lhs.c_str()) * atoi(rhs.c_str()); // restore the string str = itoa(res, buf, 10) + str; } // evaluate directly else if (oper == "/") { int res = atoi(lhs.c_str()) / atoi(rhs.c_str()); // restore the string str = itoa(res, buf, 10) + str; } else // "+" or "-" { q.push(lhs); q.push(oper); // finished parsing the expression if (str.empty()) q.push(rhs); else // restore the string str = rhs + str; } } // evaluate the queue int res, rhs; string oper; res = atoi(q.front().c_str()); q.pop(); while (!q.empty()) { oper = q.front(); q.pop(); rhs = atoi(q.front().c_str()); q.pop(); if (oper == "+") res += rhs; else // "-" res -= rhs; } return res; } string getCurr(string& str) { if (str.empty()) return ""; string curr(""); // operator if (str == '-' || str == '+' || str == '*' || str == '/') { curr += str; str = str.substr(1); } else // a number { do { curr += str; str = str.substr(1); } while (!str.empty() && str >= '0' && str <= '9'); } return curr; }Show More ResponsesUse 2 stacks. one for operands and one for operators. Keep pushing in operator as long as the newly pushed opertor has higher precedence than the "top of stack " operator. if not, pop out 2 operands and calculate result and again push it on stack

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

May 12, 2010
 Extract the N largest floating point numbers from a large file of floating point numbers.4 AnswersTo do this efficiently you need to keep your largest number list sorted and you only need to make comparisons to the smallest number in the list. Remember that sorted list insertion is O(lg n).its about extracting from file of floating point numbers. so have to use scanner to extract floating point numbers and add it in to the list or array and sort it, using Collections.sort or Arrays.sort function of JAVA.maxheap will do the workShow More Responses#define N 2 #define SIZE 3 int tab[SIZE]; int max; int sovj; for(i=0; i