Recursive algorithm Interview Questions | Glassdoor

# Recursive algorithm Interview Questions

12

interview questions shared by candidates

## Recursive algorithm Interview Questions

Sort: RelevancePopular Date

May 8, 2010

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); int b = atoi(argv); 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; }

May 9, 2012

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.