Recursive algorithm Interview Questions | Glassdoor

# Recursive algorithm Interview Questions

12

interview questions shared by candidates

## Recursive algorithm Interview Questions

Sort: RelevancePopular Date

### Software Engineer at Google was asked...

May 8, 2010
 Write a function Brackets(int n) that prints all combinations of well-formed brackets. For Brackets(3) the output would be ((())) (()()) (())() ()(()) ()()() 11 Answerspublic class Parenth2 { static int total = 3; static private void Brackets(String output, int open, int close, int pairs) { if ((open == pairs) && (close == pairs) && output.length() == total * 2) { System.out.println(output); } else { if (open < pairs) Brackets(output + "(", open + 1, close, pairs); if (close < open) Brackets(output + ")", open, close + 1, pairs); } } public static void main(String[] args) { Brackets("", 0, 0, total); } }You almost got thte answer, just a couple of errors... /* * To change this template, choose Tools | Templates * and open the template in the editor. */ /** * * @author Owner */ public class Parenth4 { static private void Brackets(String output, int open, int close, int pairs, boolean opened, boolean closed, int total) { if ((open == pairs) && (close == pairs) && output.length() == total * 2) { System.out.println(output); } else { if ((open < pairs)) Brackets(output + "(", open + 1, close, pairs,true, closed, total); if ((close < open)&& opened) Brackets(output + ")", open, close + 1, pairs,opened,closed, total); } } public static void Brackets(int total) { Brackets("", 0, 0, total,false,false, total); } public static void main(int number){ Brackets(number); } }This is a DP/memoization question, I believe. The base case is 0 and 1 bracket (the answer is empty or (). The recurrence is: bracket(n) = all combination of results from bracket(n-1) and from bracket (1) from bracket(n-2) and bracket(2) . . from bracket(1) and bracket(n-1) lastly, '(' . bracket(n-1) ')' The DP version of the above recurrence is straightforward. (Btw, this recurrence obviously will produce duplicate, but it's not hard to produce a modification that does not produce duplicate.) ;)Show More ResponsesHere is a F# implementation: let rec Br total output openp closep = if openp = total && closep = total then printfn "%s" output else if openp < total then Br total (output + "( ") (openp + 1) closep if closep < openp then Br total (output + " )") openp (closep + 1) let Brackets total = Br total "" 0 0 Brackets 5 let read = System.Console.ReadLine()void parens(int nPairs) { parens("", nPairs, nPairs); } void parens(string ans, int leftCount, int rightCount) { if (leftCount==0 && rightCount==0) { cout 0) { parens(ans+"(", leftCount-1, rightCount); } if (rightCount>leftCount) { parens(ans+")", leftCount, rightCount-1); } }To Remove duplicates simply use java Set :) public static String bracket(int a) { Set s = new TreeSet(); bracketIntern(s, a, "", ""); System.out.println(s); return s.toString(); } public static void bracketIntern(Set set,int a, String preFix,String suffix) { if(a == 1) { set.add(preFix+"()"+suffix); return; } bracketIntern(set, a-1, preFix+"()", suffix); bracketIntern(set, a-1, preFix+"(", ")"+suffix); bracketIntern(set, a-1, preFix, "()"+suffix); }I think you can also build a trie, and the traverse the trie to print out all the combinations.Complete python program to print the all combinations of well-formed brackets. How to calculate its Big-o? The recursive recurrence seems a little bit complicated. ---- def brackets(n): sol = [] li = [' ' for x in range(n*2)] def recu_brackets(opened, closed): if n - opened: li[opened + closed] = '(' recu_brackets(opened + 1, closed) if n - closed and opened > closed: li[opened + closed] = ')' recu_brackets(opened, closed + 1) if opened == n and closed == n: sol.append(''.join(li)) recu_brackets(0, 0) print ' '.join(sol) brackets(3)wasn't all that neat. o well public class MakeBrackets{ static List make(int number){ List list = new LinkedList(); if (number == 0) {list.add(""); return list;} if (number == 1) {list.add("()"); return list;} for (int i = 0; i < number; i++){ for (String item : make(i)){ for (String item2 : make(number - 1 - i)){ list.add("(" + item + ")" + item2); } } } return list; } public static void main(String[] args){ System.out.println(make(Integer.parseInt(args[0]))); } }def brackets(n): return bracketsPrefix("", n, n) def bracketsPrefix(prefix, opens, closes): total = 0 assert opensopens: total += bracketsPrefix(prefix+")", opens, closes-1) if opens>0: total += bracketsPrefix(prefix+"(", opens-1, closes) return total if __name__=="__main__": for i in range(6): n = brackets(i) print i,n x = raw_input("** ")This question gets so popular and I found this article has a really good explanation: https://goo.gl/E0m0EC

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

Feb 7, 2011
 Implement a power function to raise a double to an int power, including negative powers.11 AnswersCould be implemented many ways. I got the feeling that the interviewer wanted to see you approach the problem in multiple ways and demonstrate confidence in your math and recursive skills.#include #include #define MAX_ARRAY_LENGTH 256 double power(double, unsigned int); int main(int argc, char** argv) { double a = atof(argv[1]); int b = atoi(argv[2]); double result = power(a, b >> 31 == 0 ? b : -b); if ((unsigned int) b >> 31 == 1) { result = 1 / result; } printf("%f\n", result); return 0; } double power(double a, unsigned int b) { switch (b) { case 0: return 1.0; case 1: return a; default: return (b & 1) == 0 ? power(a * a, b >> 1) : power(a * a, b >> 1) * a; } }c implementation of the above (no recursion): int ipow(int base, int exp){ int result = 1; while(exp){ if(exp & 1) { result *= exp; } exp >>= 1; base *= base; } return result; }Show More Responsesint power(double n, int exp) { bool npower = (exp < 0) ? true : false; double result = 1; exp = abs(exp); // get the absolute value for (int i = 0; i < exp; i++) { if (npower) { result = result/n; } else { result = result*n; } } return result; }C# code verified: static double Power(double d, int exp) { if (d == 0 || exp == 0) { if (exp >= 0) { return 1; } else { return double.PositiveInfinity; } } int expAbs = Math.Abs(exp); double res = d; for (int i = 1; i 0) ? (res) : (1 / res); }double power(double x, int y) { if(y == 0) return 1; int sign = 1; if(y < 0) sign = -1; y = abs(y); double d = power(x, y/2); if(y%2 == 0) d = d*d; else d = x*d*d; if(sign == -1) return 1.0/d; else return d; }I am surprised that not a single person here had noticed that the guy asked to raise a DOUBLE to a given power. Men, double are not integers. Their exponent is stored in a part of their binary representation. If you multiply n times a double you will make n times a rounding error and n useless calculations. Just changed the binary part of the double that is related to its exponent, and here it is, your double has been raised to a given power, a you absolutely lost no precision, and you've made 0 calculations. This is basic stuff, every university teaches that to its students... floating numbers representation...I believe interviewer is expecting for this public static double Power(double x, int y) { double result = 1; bool isNegative = y 0) { if ((y & 1) > 0) { result *= x; } y = (y >> 1); x *= x; } if (isNegative) result = 1 / result; return result; }Verified C# static double Pow(double b, double exp) { if (exp == 0) return 1; else if (exp > 0) return b * Pow(b, exp - 1); else return 1 / Pow(b, -exp); } Does it get more compact?TD's answer is interesting, but not very useful. If you actually try it you'll find that since the double's base is 2, any changes to the exponent portion approximately multiply (or divide) numbers by a power of two. I say approximately here, since TD forgot to mention that the number itself isn't stored in float point numbers, only the digits after the implied 1. So yes, it's important to know how floating point numbers work, but modifying the exponent portion of a floating point number is a fundamentally incorrect solution.public double power(double num, int exp) { if(exp == 0) return 1; double res = 1; for(int e=Math.abs(exp);e>0;num*=num,e>>=1) { if( (e&1) == 1) res *= num; } return (exp>0)?res:1.0/res; }

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

May 9, 2012
 You are given an integer N and an integer M. You are supposed to write a method void findBestCoinsThatMinimizeAverage(int N, int M) that prints the best collection of N coins that minimize the average number of minimum coins needed to generate values from 1 to M. So, if M = 100, and N = 4, then if we use the set {1, 5, 10, 25} to generate each value from 1 to 100, so that for each value the number of coins are minimized, i.e. 1 = 1 (1 coin), 2 = 1 + 1 (2 coins),..., 6 = 1 + 5 (2 coins), ..., 24 = 5 + 5 + 5 + 5 + 1 + 1 + 1 + 1 (8 coins), and we take the average of these coins, we would see that the average comes out to ~5.7. But if we instead use {1, 5, 18, 25}, the average would come out to be 3.7. We are to find that set of N coins, and print them, that produce the minimum average.8 AnswersI just started working on this problem, but here is a rough outline: 1. Generate all subsets of N coins. 2. For each subset, generate the minimum multi-set required to materialize the total values 1...M; say for subset of coins N(i), we name each multi-set of coins N(i),M(j) where j is some value between 1 and M. 3. For fixed i, get the average over j for each multi-set N(i),M(j). 4. Choose the subset N(i) that maps to the lowest average size of the multi-sets that are generated from N(i). Time will be O(2^N), since we are generating each subset of N. Feedback much encouraged to get this down to a polynomial solution.We need some way to narrow down the subsets of N that we consider. Perhaps we could start by enumerating the subsets of N lexicographically, and then performing a binary search on the array of subsets to help us choose? Just a thought, not very developed yet.Why is 24 = 5 + 5 + 5 + 5 + 1 + 1 + 1 + 1? Should it not be 10+10+1+1+1+1?Show More ResponsesI doubt this question really was a Facebook interview question (although I am not a Facebook employee nor do I have any connection with Facebook). Anyway, here is a research paper precisely on this problem: http://www.cs.uwaterloo.ca/~shallit/Papers/change2.pdf It is written by a well known researcher in algorithms and he says on page 6 (problem 5) that this problem is hard and that he wasn't able to find a polynomial time algorithm for it. So the best way to do do it is to enumerate all possible denomination subsets, and then for each value and each denomination system, compute what the minimum number of coins for that value is using the well known dynamic programming approach. And to the previous commenter (A): you are absolutely right.Just based on the reading of the problem it sounds very much like a variation of the Knapsack problem (optimization) which is NP Hard. The problem grows exponentially harder as N grows. Except for small values of N, algos for computation are not likely to return for a long time.very slow... need to reduce generating coins sets... public class Solution { private static ArrayList coins = new ArrayList(); private static void generatesets(int[] n, int k, int M, int N) { if (k == N) { coins.add(n.clone()); return; } for (int i=n[k-1]+1; i averagecnt) { minc = averagecnt; res = coinset; } } System.out.println(Arrays.toString(res)); } }Not sure of the proof of correctness; just an iterative algo trying to implement pattern; more test-cases will be helpful. import java.io.IOException; import java.util.Scanner; import java.util.Set; import java.util.TreeSet; public class BestCoins { public static void main(String[] args) throws IOException { final Scanner in = new Scanner(System.in); while (true) { System.out.println("Enter total number of coins : N : "); int n = in.nextInt(); System.out.println("Enter max coin value : M : "); int m = in.nextInt(); Set coins = new TreeSet(); findBestCoinsThatMinimizeAverage(m, n, coins, true); System.out.println("Best coin set is " + coins); } } private static void findBestCoinsThatMinimizeAverage(int m, int n, Set coins, boolean minimize) throws IOException { System.out.println(m + " " + coins + " " + minimize); // new BufferedReader(new InputStreamReader(System.in)).readLine(); if (m <= 1) { coins.add(1); return ; } int coin = minimize? m/n : m-m/n; if (coin == 0) { coin = 1; } coins.add(coin); if (coin == 1) { coins.add(m-1); return; } int remainingM = minimize? coin-1 : m-coin; findBestCoinsThatMinimizeAverage(remainingM, n, coins, !minimize); } }Here is my solution to it: https://dotnetfiddle.net/qnCdop Exponential time complexity. BTW for M=100, N=4 I get {38, 11, 3, 1}, not {1, 5, 18, 25} as the question specifies. One of us is wrong.

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

Apr 27, 2012
 Write a program that given 4 coin denominations and a dollar amount finds the best way to express that amount using the coins given. I.e. you have coins with denominations of 1c, 7c, 13c,19c and you have to express \$2.12 with the least number of coins. There is always a 1c coin but the other 3 are arbitrary.6 AnswersTurns out , this problem only has an elegant solution when the coin denominations are divisible by each other, such as the US coins (1, 5, 10, 25). Otherwise, it requires a (slightly optimized) brute force algorithm. I was told so by the interviewer after struggling with it using different approaches for about 40 minutes.If you have a coin of value 1, you can use a greedy algorithm: always select the most valued coin, until you have less money left that this value. Remove the coin, try again with less coins and the money left. Otherwise, just bruteforce and memoization, to implement a simple dynamic programming approach where you want to minimize the number of coins used, caching on the amount of money left to divide.Greedy algorithm is not right at all for general cases. This is a very classical questioin. If you fail on this question, I would say that it is probably your fault.Show More ResponsesIn all my years of giving and receiving interview questions I have never seen this one. It is definitely NOT a classical programming problem. Asking whether a candidate knows of an obscure academic puzzle does not sound like a good interview question.int main() { int currency[] = {19,13,7,1}; int money = 212; int i=0; int div=0; while (money>0) { div = money/currency[i]; money = money%currency[i]; if(div>0) { coutIt is a classical programming question that derives from the first fit decreasing algorithm in discrete (decision) mathematics.

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

### Game Programmer at Zynga was asked...

Feb 8, 2012
 How do you find the max depth of a binary tree?5 AnswersI used recursion, passing the current depth to each child and returning the max value they returned plus one to the caller.how about bfs?breadth first search will be better than the recursion method for min-depth searching, but works same as recursive in the case of finding max depth problemShow More Responsespublic static int maxDepth(TreeNode root) { if (root == null) return 0; //base case return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1; }This entirely depends on the implementation. It can be calculated as the integer log base 2 of the highest index of the tree. This would prevent quite a few cache misses from traversing the tree each time, and would be a fairly quick calculation using bitwise operations. int val;// the value int result;// the result int tmp; result = (val > 0xFFFF ? 0 : 1) >= result; tmp= (val > 0xFF ? 0 : 1) >= tmp; result |= tmp; tmp= (val > 0xF ? 0 : 1) >= tmp; result |= tmp; tmp= (val > 0x3 ? 0 : 1) >= tmp; result |= tmp; result |= (val >> 1); While this may seem like a lot, assuming the tree is small, these calculations are actually quite fast, don't involve branching, and don't require arbitrary pointers to sub-tree members. This works best for trees that are either complete or nearly complete, however, since otherwise there will be a lot of wasted memory for indices that contain nothing.

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

Mar 18, 2009
 Write an algorithm that does an in-order traversal of a tree recursively. Now, write the same algorithm iteratively.4 AnswersHint: You'll want to use a stack in the iterative version.Haha, I got that same question on my interview. It made me sweat, because I knew I was supposed to use a stack, but I had never done it before. It was fun working it out on my own.public void inOrder(Node* root) { if(root == NULL) return; inOrder(root->left); cout element; inOrder(root->right); }Show More Responses// recursive void InorderTraversal( Node *root) { if ( root== NULL) return ; // status 2 InorderTraversal( root->left ); // status 1 Print (root); InorderTraversal(root->right); // status 0 } // NON-Recursive Version for Pre/In/Post-Order the idea behind this method is to employ a stack to emulate the recursion void NonRecTraversal( Node *root ) { if ( root == NULL ) return ; stack stk; bool flag = 2;// the key: keep track of the status of the top element stk.push(root); while( !stk.empty()) { if ( flag == 2 ) { /* Print (node) ; this is preorder */ if ( stk.top()->left != NULL ) stk.push(stk.top()->left ); else flag = 1; } else if ( flag == 1) { /* Print (node) ; this is inorder */ if ( stk.top()->right != NULL) { stk.push(stk.top()->right); flag = 2; } else flag = 0; } else { /* Print (node) ; this is postorder */ Node *temp = stk.top(); Stk.pop(); If ( !stk.empty() && stk.top()->left == temp ) Flag = 1; // come back from left child Else Flag = 0; // come back from right child } } }

### Senior Python Software Engineer at Disqus was asked...

May 4, 2012
 Write a Unix glob implementation in python. Globbing lets you use * for zero or more characters, ? for a single character, [] for a character range.1 AnswerThe key to this problem is recursion and avoiding quadratic complexities, so you need to convert your text into words and then compose those words into a trie (not tree) of indexed characters. You then traverse that trie, recursing as necessary, to produce a list of matching words and their indices into the original text. Note: I made the whole search corpus into a trie, and I shouldn't have for maximum points. I should have only trie-d the first three or four characters and used linear matching for the rest of the words into order to save on memory.

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

Apr 3, 2012
 The 2nd interview was a coding exercise with the following premise: Given a destination page and a page with all the links embedded in it, write a function that determines if the destination is "reachable". You must protect against cyclical / infinite recursion.1 AnswerCreate a hashmap of all the pages you visited. Add a queue to all the new pages you find in a given page. Use the queue and the hashmap to keep looking for the page until queue is empty.

### Member of Technical Staff at VMware was asked...

Oct 15, 2009
 I don't remember exactly, but some standard low-level C/C++/Java questions. Maybe something about string manipulation, bit play, recursive algorithms, threads, networking, etc.1 AnswerVery standard, you should be able to handle it.
110 of 12 Interview Questions