# Algorithm Interview Questions

interview questions shared by candidates

## Algorithm Interview Questions

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

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 Responses Use dynamic programming. 3432 If 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 |

Output a single linked list in reverse, in linear time and constant space, and recursively 5 Answersvoid recursive_reverse(nodeptr inlist) { if (inlist->next == NULL) { printf(" %d ", inlist->value); return; } recursive_reverse(inlist->next); printf(" %d ", inlist->value); } here it is a java code for reversing a linked list recursively Node reverse(Node head) { return reverse(head,null); } Node reverse(Node head,Node tail) { Node tmp = head.next; head.next = tail; tail = head; if (tmp == null) return head; head = tmp; return reverse(head,tail); } void revis(Node*node, Node* ptr){ if(node==null)return; revis(node->next,node); node->next=ptr; } Show More Responses Reversing it recursively always needs at least O(n) space in memory. def reverse(lst): if not lst or len(lst) == 1: return lst else: return reverse(lst[1:]) + [lst[0]] |

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:55 This 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:55 Show More Responses The 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 |

I was asked two questions. Q 1. You are given two version numbers of a software, like Version 10.3.4 and Version 10.3.41. Write a program to find out which of the version numbers are the latest. If version 1 is latest output -1, if version number 2 is latest output +1 else output 0 if same version. Both the version numbers are taken as string. He also asks to make the program of minimum time complexity as we can. At the end he also asked the difference between an iterative program and one with recurrence and their advantages and disadvantages. Q 2. Given two files with a list of application IDs (or some kind of data) stored in them , write a program to compare the data in the two files and output all the common data found in each. What data structure would you use and why ? Give a minimum time and space complexity algorithm. Why did you choose the particular data Structure or algorithm ? 7 Answers1. This was a little tricky. You have to check for the decimal place in both the versions and then Store that part of the string till the decimal place in a temporary variable and then convert them to integer and check which one is greater. You have to keep on doing that till you reach the end of the version numbers or till when you find the answer 2. In the second question you can use Linked lists and then Binary Search Algorithm. The interviewer will ask you the reason for this. Why not just delimit the string with "." Then you'll have an array of string numbers. Then loop with the array from 0 -> n (depending on how many decimals there was) and compare. Return when one is greater than the other. You will have to check if you get a index out of bounds if one has more decimals than the other. Over all, that should be in n time. As for #2. HashTable it. Also n time. Show More Responses If you are using c++, can't you just use the "compare" method that is built into the string class? Maybe not the best solution... the time complexity is O(n). public static void main(String[] args) { String ver1 = "10.22.7.3"; String ver2 = "10.22.8.4.1"; String split1[] = ver1.split("\\."); String split2[] = ver2.split("\\."); int max = split1.length > split2.length ? split1.length : split2.length; for (int i = 0; i i) { System.out.println(+1); break; } else if (split2.length i) { System.out.println(-1); break; } else { if (Integer.parseInt(split1[i]) > Integer.parseInt(split2[i])) { System.out.println(-1); break; } else if (Integer.parseInt(split1[i]) < Integer .parseInt(split2[i])) { System.out.println(+1); break; } } } } String v1="10.3.4"; String v2="10.3.41; double v12=v1.parseDouble(); double v22=v2.parseDouble(); If(v12>v22) { System.out.print(-1);} else if(v22>v12) {System.out.print(1);} else{ System. out. print(0);} Q:2 List a= new LinkedList(); List b= new LinkedList(); while(a.hasNext()) { ( int =1; i |

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

How do you check if a Linked List has a recurring loop? 4 AnswersI thought of using a hash table to store the values of each node, and adding values to the table as we iterate through the Linked List. This would only work if the values are unique. It was the not fastest or best either. With some hints, I came to a better solution of iterating through the Linked List twice - one that hops 1 node each time and the other hops 2 nodes each time. If the latter loop surpasses or reaches a node from the first, there exists a loop. There would be no loop of course when both reach the end of the Linked List. There is a blog discussing this problem, as well as another problem to find the entry node in the loop. There is a blog discussing this problem, as well as another problem to find the entry node in the loop. The link of the blog is: http://codercareer.blogspot.com/2012/01/no-29-loop-in-list.html Show More Responses /* Jun Zheng, Rice Univ C++, Xcode 4.5.2 Interview question of GS Check if a linkedlist has circle, phead points to the start node */ bool ifCircular(node* phead){ node* pfast=phead; node* pslow=phead; while(pfast !=NULL && pfast->next !=NULL){ pfast=pfast->next->next; pslow=pslow->next; if(pfast==pslow) return true; } return false; } |

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

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 b 7 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 question See 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; i def 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 |

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[5]; 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[0] == '-' || str[0] == '+' || str[0] == '*' || str[0] == '/') { curr += str[0]; str = str.substr(1); } else // a number { do { curr += str[0]; str = str.substr(1); } while (!str.empty() && str[0] >= '0' && str[0] <= '9'); } return curr; } Show More Responses Use 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...

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 work Show More Responses #define N 2 #define SIZE 3 int tab[SIZE]; int max; int sovj; for(i=0; i |

### Search Engineer, Front End at LinkedIn was asked...

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_algorithm Show More Responses borrow 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] |

### Software Engineer at Facebook was asked...

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 Responses For 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; }) |