# Algorithm Interview Questions

interview questions shared by candidates

## Algorithm Interview Questions

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

(a) first, write a function to calculate the hamming distance between two binary numbers (b) write a function that takes a list of binary numbers and returns the sum of the hamming distances for each pair (c) find a solution for (b) that works in O(n) time. 10 Answers(for question 1) public static String addBinaryStrings(String a, String b) { if ((null == a) || (null == b)) return null; return int2bstring(bstring2int(a) + bstring2int(b)); } public static int bstring2int(String a) { int sum = 0; int multiplier = 1; while (a.length() > 0) { String lastChar = a.substring(a.length()-2, a.length()); if (lastChar.equals("1")) sum += multiplier; multiplier *= 2; a = a.substring(0, a.length()-1); } return sum; } public static String int2bstring(int i) { if (0 == i) return "0"; String s = ""; while (i > 0) { if ((i % 2) == 0) { s = "1" + s; } else { s = "0" + s; } i /= 2; } return s; } (for question 2) public static int hammingDistance(String a, String b) { int numDigits = Math.max(a.length(), b.length()); int numDiff = 0; for (int i = 0; i < numDigits; i++) { String ithDigitA = extractDigit(a, i, numDigits); String ithDigitB = extractDigit(b, i, numDigits); if (!ithDigitA.equals(ithDigitB)) numDiff++; } return numDiff; } public static String extractDigit(String a, int i, int n) { if (i < n - a.length()) return "0"; return a.substring(i-n+a.length(), i-n+a.length()+1); } public static int setHamming(String[] a) { int numDiff = 0; int numDigits = 0; for (int i = 0; i < a.length; i++) { numDigits = Math.max(numDigits, i); } for (int i = 0; i < numDigits; i++) { int num0s = 0; int num1s = 0; for (String aa : a) { String ithDigitAA = extractDigit(aa, i, numDigits); if (ithDigitAA.equals("0")) { num0s++; } else { num1s++; } } numDiff += (num0s * num1s); } return numDiff; } A: int distance( int num1, int num2 ) { int distance; while( num1 != 0 && num2 != 0 ) { distance += num1&1!=num2&1; num1=num1>>1; num2=num2>>1; } return distance; } B: int distanceSum( std::vector nums ) { std::unordered_map digits; for( auto& num : nums ) { int digit = 1; while( num != 0 ) { digits[digit]+=num&1; num = num>>1; digit++; } } int distanceSum = 0; for( auto& p : digits ) { distanceSum += nums.length()-p.second; } return distanceSum; } Show More Responses for Problem C: /** * This solution is O(n) *I wrote it this way so its easier to be understood. **/ public int getHammingTotalFromBinaryNumbersList(List binaryNumbers){ Map binaryCounter = new HashMap; // Key is the _[1 or 0] on the binary number, so if you're at position 1, and you get 0, the key will be 0_1 String positionKey; int totalCount; int maxPosition = 0; foreach(String binaryNumber in binaryNumbers){ if(binaryNumber.Length-1 > maxPosition){ maxPosition = binaryNumber.Length-1; } for(i = 0; i 10001 10101 int GetHammingDistance(string s1, string s2) { Debug.Assert(s1.Length == s2.Length); int distance = 0; for(int i=0; i input, int n, out List distances) { if(n==2) { distances.Add(GetHammingDistance(input[0], input[1])); } for(int i=0; i {XY} GetAllPairsHammingDistance(zyx, 2, "")=> {XY, ZY} GetAllPairsHammingDistance(zxy, 2, "")=> {XY, ZY, ZX} XYZ 0 1 2 = 3 X Y Z | | | 0 1 | Y | |_ 0 1 = 2 Y Z | | | |_Z |_Y Problem 1. Add two binary numbers represented as ASCII strings with result also in form of an ASCII string // // Add two binary strings, the solution as follows: // 1) convert binary strings to unsigned integers // 2) Add resulting integers // 3) Convert the result back to binary string // 4) Reverse the string to obtain the resulting string // // // Convert binary ASCII string to unsigned integer by successive divide by 2 // uint binStr_to_uint(const char *pStr, int *size) { char *pEnd = pStr; uint num = 0; while(*pEnd) num = (num >= 1; //divide by 2 } *pStr = 0; //terminate the string } // Reverse a string void reverseString(char *pStr) { char *pEnd = pStr; while(*pEnd++) ; pEnd -= 2; //point to last string char char *pTmp; while(pStr size2 ? size1 : size2; char *pResult = malloc(sizeRes + 2); //add space for carry and EOS if(pResult == 0) return 0; uint_to_binStr(num2, pResult); reverseString(pResult); return (pResult); } Problem 2. Find Humming distance between two numbers. The problem did not specify what format the numbers are in, so I assumed unsigned integers. // // Find Humming distance // int hummingDistnce(uint num1, uint num2) { num1 = num1 ^ num2; //Humming distance is simply an XOR num2 = 0; while(num1) { ++num2; //count '1' bits num1 &= num1 - 1; } return num2; } The second part of the problem is simple, just traverse the list selecting pairs of numbers and call hummingDistance() function each time. Corrections to my previous example: // Convert binary ASCII string to unsigned integer by successive divide by 2 should say ....multiply by 2 instead of divide by 2 Another minor error fix, function uint_to_binStr(uint num) definition should also have a pointer to char parameter like below: void uint_to_binStr(uint num, char *pStr) Third correction, In function reverseString(), the temporary char variable should be defined as "char tmp;" instead of "char *pTmp", so the code block should be: char tmp; while(pStr < pEnd) { tmp = *pEnd; *pEnd-- = *pStr; *pStr++ = tmp; public static int hammingDistance(int a, int b) { int xor = a ^ b; int distance = 0; while (xor > 0) { xor = (xor - 1) & xor; distance++; } return distance; } public static int hammingDistance(int[] array) { int sum = 0; for (int i=0; i<32; i++) { int mask = 1 << i; int num0s = 0; int num1s = 0; for (int value : array) { if ((value & mask) != 0) { num1s++; } else { num0s++; } } sum += num0s * num1s; } return sum; } |

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

Print a singly-linked list backwards, in constant space and linear time. 10 AnswersOne can create a function that takes a node as an argument and checks whether the next of the passed node is NULL or not.In case it is not NULL,the same function is again called for the NEXT node.if the Next of the passed node is NULL,the function prints the value of the node and returns. void f1(node* p) { if(p->next!= NULL) { f1(p->next) } else { print ("%d",p->value); } } Arpit, that's not constant space, that's linear (stack) space, since you will have as many function calls waiting to be returned on the stack as there are nodes. The trick is to reverse the list first (constant space, linear time when done iteratively or tail-recursively) then print it in order (against constant space, linear time). void f1(LinkedListNode lln) { if(lln.next != null) f1(lln.next); System.out.print(lln.value); } Show More Responses Bobby, that is not constant space because it uses O(N) stack space. There are obvoius O(N^2)-time O(1)-space algorithms, and obvious O(N) time O(N) space algorithms. This is my best guess. Assuming you have exclusive access to the list, you can reverse it, walk it, and then reverse it again. Something like this: #include #include struct node { int value; struct node * next; }; void print_backwards( node * head ) { node * prev = NULL; node * cur = head; node * next; while( cur ) { next = cur->next; cur->next = prev; prev = cur; cur = next; } cur = prev; prev = NULL; while( cur ) { printf( "%d\n", cur->value ); next = cur->next; cur->next = prev; prev = cur; cur = next; } assert( prev == head ); } main() { node a, b, c; a.value = 1; a.next = &b; b.value = 2; b.next = &c; c.value = 3; c.next = NULL; print_backwards( &a ); } Reverse the list, print, then reverse it back. 3 O(n) operations = O(n). O(1) space used. Reverse the list, print, then reverse it back. 3 O(n) operations = O(n). O(1) space used. void BWDisplayLinkedList(node* pHead) { if(!pHead) return; BWDisplayLinkedList(pHead->next); cout data "; } Does this work well? Reverse a list, print it, and then reverse it again. struct node *reverse(struct node *oldlist) { struct node *newlist = NULL; while(oldlist!=NULL) { struct node *temp = oldlist; oldlist=oldlist->next; temp->next=newlist; newlist=temp; } return newlist; } void display(struct node **q) { struct node *temp; temp = *q; if(*q==NULL) { printf("List is empty\n\n"); } else { while(temp!=NULL) { printf("%d=>",temp->data); temp=temp->next; } printf("||\n\n"); } } //p is our list p = reverse(p); display(&p); p = reverse(p); Thanks to recursion :) void print_backward(node* n) { if(n == NULL) return; print_backward(n->nxt); cout val << endl; } Yes recursion does the job in linear and constant time. :-) |

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

Convert a binary search tree to a sorted, circular, doubly-linked list, in place (using the tree nodes as the new list nodes). 8 AnswersRecursively: - convert the left subtree (returns a dbl-linked list (DLL) with a head ptr & tail ptr) - convert the right subtree (same) - connect the left DLL tail to the right DLL head bi-directionally - return the combined list (head = left-head, tail = right-tail) struct StackEntry { Node *pNode; bool fVisit; }; inline void linkNodes(Node *pLeft, Node *pRight) { pLeft->pNext = pRight; pRight->pPrev = pLeft; } inline void visitNode(Node **ppFirst, Node **ppPrev, Node *pNode) { if(ppPrev == NULL) { *ppFirst = pNode; *ppPrev = pNode; } else { linkNodes(*ppPrev, pNode); *ppPrev = pNode; } } void doubleLink(Node *pRoot) { stack stack; Node *pFirst = NULL; Node *pPrev = NULL; StackEntry rootEntry = {pRoot, false}; stack.push(rootEntry); while(stack.size() != 0) { StackEntry &top = stack.top(); stack.pop(); if(top.fVisit) { visitNode(&pFirst, &pPrev, top.pNode); } else { StackEntry entry; if(pNode->pLeft != NULL) { entry.pNode = pNode->pLeft; entry.fVisit = false; stack.push(entry); } entry.pNode = pNode; entry.fVisit = true; stack.push(entry); if(pNode->pRight != NULL) { entry.pNode = pNode->pRight; entry.fVisit = false; stack.push(entry); } } } if(pPrev != NULL) { linkNodes(pPrev, pFirst); } } class TreeNode { TreeNode* left; TreeNode* right; int value; } TreeNode* MakeCircularDoublyLinked(TreeNode* head) { DoublyLink(head, head); return MakeCircular(head); } TreeNode* MakeCircular(TreeNode* node) { TreeNode* leftEnd = node; while (leftEnd->prev != NULL) { leftEnd = leftEnd->prev; } listNode* rightEnd = node; while (rightEnd->prev != NULL) { rightEnd = rightEnd->prev; } rightEnd->next = leftEnd; leftEnd->prev = rightEnd; return leftEnd; } listNode* DoublyLink(TreeNode* current, TreeNode* prevTreeNode) { if (current == NULL) { return NULL; } current->left = DoublyLink(current->left, current); if (current->left != NULL) { current->left->right = current; } current->right = DoublyLink(current->right, current); if (current->right != NULL) { current->right->left = current; } if (prevTreeNode->left == current) { // we are processing the left subtree, return the rightmost // element to the parent while (current->next != NULL) { current = current->next; } } else if (prevTreeNode->right == current) { // we are processing the right subtree, return the leftmost // element to the parent while (current->prev != NULL) { current = current->prev; } } return current; } Show More Responses Detailed analysis and solution is available in the following blog: http://codercareer.blogspot.com/2011/09/interview-question-no-1-binary-search.html Java, non-recursive. O(n) time, O(1) space: import java.util.Stack; public class TreeToCircList { public static class Node { public Node left = null; public Node right = null; public int data; } public void convert(Node node) { boolean leftChecked = false; Node prev = null; Node start = null; Stack s = new Stack(); while(node != null) { if(leftChecked == false && node.left != null) { s.push(node); node = node.left; } else { // Perform the linking node.left = prev; if(prev != null) prev.right = node; else start = node; // Mark start of the list prev = node; if(node.right != null) { node = node.right; leftChecked = false; } else if(s.empty() == false) { node = s.pop(); leftChecked = true; } else { node = null; } } } // Find the first node to link with the last node if(prev != null) { start.left = prev; prev.right = start; } } } Thanks to recursion .. this is a sorted linked list .. to make it circular just make a pointer from the last to the head. :) bst_node* getList(bst_node* nd) { if(nd == NULL) return NULL; bst_node* head; bst_node* l = getList(nd->lft); bst_node* r = getList(nd->rt); if(l != NULL) { head = l; head->lft = nd; nd->lft = r; } else { head = nd; head->lft = r; } return head; } void print_list(bst_node* bst) { bst_node* head = bst; while(head != NULL) { cout val lft; } } void BinTree::convert() { Node * head, * tail; convert_to_dlist(root, head, tail); Node * current = head; while(current != tail) { cout val right; } cout val val left; } cout val left, lhead, ltail); convert_to_dlist(node -> right, rhead, rtail); if(lhead == NULL && rhead == NULL) { head = node; tail = node; head -> left = head; head -> right = head; } else if(lhead == NULL && rhead != NULL) { head = node; head -> right = rhead; rhead -> left = head; tail = rtail; head -> left = tail; tail -> right = head; } else if(lhead != NULL && rhead == NULL) { head = lhead; head -> left = node; node -> right = head; tail = node; tail -> left = ltail; ltail -> right = tail; } else { head = lhead; tail = rtail; ltail -> right = node; node -> left = ltail; node -> right = rhead; rhead -> left = node; head -> left = tail; tail -> right = head; } return; } Solution by recursive in-order traversal. To make code simply I did not make linked list circular. It can be done by simply modification to return both head and tail and connect them outside recursion. Node Convert(Node root) { if (root == null) return null; Node last = null; return InOrder(root, ref last); } Node InOrder(Node node, ref Node last) { Node left = null; if (node.Left != null) left = InOrder(node.Left, ref last); node.Left = last; if (last != null) last.Right = node; last = node; if (node.Right != null) InOrder(node.Right, ref last); return left ?? node; // return the smallest node which will be the head } |

Describe a routine which returns the set of integers in {1..100} divisible without remainder by 3 but not by 9. 12 AnswersI'm assuming the question wants us to find integers that are divisible by 3 but not by 9. This can be easily obtained using a mod function inside the following if statement: if(number % 3 == 0 && number % 9 != 0) Here is a short program I wrote in c++ to show how to solve this problem. Instead of returning the set of integer, I just printed them out on the screen: #include #include using namespace std; int main(int argc, char** argv) { int i = 0; vector list; vector::iterator it; for(i = 1; i <= 100; i++) { if(i%3 == 0 && i%9 != 0) { list.push_back(i); } } for(it = list.begin(); it != list.end(); it++) { cout << *it << endl; } return 0; } If I missed anything, please let me know. Happy coding and problem solving! That'll certainly work, Tyler, but the OP indicated he was interviewing for a Ruby On Rails - not C++ - gig. put those integers into an array, pick every third element, out of which discard every third element. Show More Responses python [x for x in range(0,100) if x % 3 == 0 and x % 9 != 0] 1) start from number = 3 Loop while(number <= 100) 2) display number 3) number = number+3, display number 4) number = number+6 Loop (1..100).map { |i| (i % 3).zero? && !(i % 9).zero? ? i : nil }.compact (1..100).select { |x| x%3 == 0 && x%9 != 0 matt has the best answer A variation on Matt's answer: (1..100).select { |n| n % 3 == 0 }.reject { |n| n % 9 == 0 } The requirement doesn't say if the input has to be a Range. If it doesn't have to be, then we don't need to traverse each element but to simply calculate it. def get_nums_by_3_not_by_9(max) arr = [] x = max.to_i / 3 x.times do |i| next if i % 3 == 0 arr << i * 3 end return arr end (1..100).select do |n| n%3 ==0 and n%9 != 0 end (1..100).to_a.delete_if{|x| !(x%3==0 && x%9>0)} or (1..100).to_a.select{|x| x%3==0 && x%9>0} or (1..100).to_a.map{|x| x%3==0 && x%9>0 ? x : nil}.compact or (1..100).to_a.reject{|x| !(x%3==0 && x%9>0)} |

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

Given a list of integers, some of which may be negative, extract the pair that sums to the largest number. 8 AnswersThe naive solution is O(n^2). The trick is to sort the list in O(n lg n) then pick the two largest numbers from the front. you can get the largest two number in O(n), right? sum those two numbers up. Whoops, I wrote the wrong question. Here's what I meant to say: given a list of integers, find a pair that sums to a given value. Show More Responses Keep a list of integers, and set it to 1 if they are in within the list. for (int i = 0; i < n; ++i) dp[array[i]] = 1; for (int i = 0; i < n; ++i) if (dp[S - array[i]] && S - array[i] != array[i]) print S - array[i] and array[i] because they sum to S This is the subset problem. This is O( n ), but requires O( S ) space. @bleh: I guess the solution will work if all the elements are +ve, in this case however the elements are negative. So probably we can use hash instead of arrays. if both hashing and the subset solution aren't good enough - 1. Sort the array o(n) or o(nlogn) - pick the one you can sell 2. Have two pointers - one at the end and the other at the beginning 3.a. If the sum is less than S increment the one in the beginning 3.b. If the sum is greater than S decrement the one at the end 3.c If the sum is S - you are done 3.d If the two pointers have met or crossed over - you are done Amazon really loves dynamic programming eh? I've come across many interview questions with the knapsack and coin-change problems #define SIZE 3 int tab[SIZE]; int sum; int max=-MAXINT; int sovi, sovj; for(i=0; i max) { max=sum+tab[j]; sovi=i; sovj=j; } } } printf("\n i: %d j:%d", sovi, sovj); |

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

How would you find the pairs of numbers that added to some specific number in an array. 7 Answersi program in java..so i will talk from the arrayLists perspective. suppose we want to find out a+b = 123; for(int i=0; i2000 records.but below that, sorting and above operation is efficient. you must play with different possibilities. Your answer (using arrayList.indexOf(...)) is worse than sorting. Sorting is O(log n), finding an item in an unsorted array using ArrayList.indexOf is O(n). Given an unsorted array input (e.g. int[] input), sort it using Array.sort(input) ... this is O(log n). Start at input[0] of the sorted array and calculate it's complementary value. Go to the end of the array and iterate backwards until you find the complementary value or less. If it's less repeat for input[1] and iterate backwards from the previous last item ... keep going. This is at worst proportional to n/2, ie O(n). I realize I wasn't totally clear in my first paragraph ... searching for the complementary value of one item is O(n), but you have to the search for (at worst) every item, so your solution is O(n^2). Show More Responses Duh - sorting is O(nlog n) ... Using hashing, this can be done in O(N). store the n/2 mod i in the corresponding hash bucket. Now check the each hash bucket and you are done. sort the array (o(n(log(n)) and take two pointers at both the ends say p1 and p2 if p1+ p2 move the pointer p2 by 1 and add to check if (p1+p2) > n -> move the pointer p1 by 1 and add to check if (p1+p2) = n ->print the pair [traversal takes o(n)] finally thus can be done in o(n) I will not waste o(nlogn) in sorting the array. Instead assuming that the sum we looking for is k, i will divide the array into 2 arrays. First array will contain all values which are less than k/2 Second array will contain all values > k/2 This is bcoz in a sum if one number is less than k/2, the other has to be larger. I will iterate over the smaller array of the 2 since they would rarely be equal. For each x in array 1, i will find the k-x in array 2. Complexity will be O(n). |

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

If you have a file containing millions of integers, how would you sort the data in the file using extremely limited resources, such a s 1GB of memory? 8 AnswersWhat was the answer? In my opinion, I would answer this way: Sort each x integers (x is the number of integers that the memory can hold) then save it to the a file (n files) . Then for each file maintain a current index initiated with 0. Loop through n file and take the max integer, put it into the result file, and increase the file's current index to one. Continue doing it till the end. An integer is only 4 bytes! I am just saying, a million integers should consume about 4 MB of memory, and easily fit in 1 GB! So "millions" had better be closer to a quarter billion if memory is an issue. OK, to answer the intended question, I would solve it with statistics. Compute bucket ranges by using a random subset of the file, with bucket size chosen such that the expected portion of the entire file will fit within the memory available. Divide the file into these buckets, and sort the buckets individually. Concatenate the sorted buckets to create a single sorted file. To Kurt: You missed one step. Concatenating buckets will not make a sorted list. You have to merge the buckets. However, for merging you do not necessarily have to load the whole bucket into memory. Show More Responses millions is not too much , you can build a int array which have millions of cells. The array take only several mega bytes . Initialize to zero for every cell, then traverse the file and keep track of every integer by array , eg . 4789 will make array[4789]++ , this could handle duplicate number . Finally scan the array ... the interviewer is looking for the word "divide and conquer". read the n number of integers and write them in a binary tree. hold the left and right value in a datastructure which keeps track of the file an integer is written to. something like this class NumHolder { int min; int max; String fileName; } Map partInfo = new HashMap() for (int i=0; i 100000 //100000 = sum number that determines how many part files will be created. writeToOtherFileToo writeToPartFile update partInfo with this write } its called 'external sorting'... read more on wiki... divide the file in chunks, sort individuals chunks using quicksort and store in files. Then use merging step of merge sort on those saved files. This would be external sort. use external sorting algorithm similar to merge sort which splits and merges files instead of arrays in memory |

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

There are n pots with different # gold coins in them. Two players play a game, where each player can select a pot at either ends. maximize the gold 7 AnswersUse dynamic programming to solve the same. Could explain the logic, but again did not find the time to code it up. What does "maximize the gold" mean in this game? If it means to keep the heavier pots for the end of the game and keep the two sides balanced, then I think you need to sort the N pots and redistribute so that the heaviest is in the middle and the two sides are balanced. Since a pot can contain only a limited number of gold, I would use a count sort algorithm for an average time of O(N+k). When re-distributing, I would balance the two sides starting by the heaviest pot, according to the individual sides's weight. For example: 1, 4, 10, 2, 3, 4, 2 Counting sort: 1:. 2:.. 3:. 4:.. 5: 6: 7: 8: 9: 10:. Sorted list: 1, 2, 2, 3, 4, 4, 10 If K is odd, remember the heaviest = 10 Re-distributing by weights: 4, 3, 1 4, 2, 2 Final list: 1, 3, 4, 10, 4, 2, 2 To maximize the gold means, each player wants to maximize the amount of gold the player gets by selection of one pot at a time (either leftmost or rightmost). Player 1 selects a pot, followed by player 2, followed by player 1 etc. How does the player select picking Left or right one ? Maximize gold means sum of the gold coins of all the pots selected by a player. I did not follow how sorting helps Show More Responses How about take differences and get the side that gives you a better gain. For example: 8 7 4 6 Take 6 Then take 7 I think the idea is that each person takes turns choosing the currently leftmost or rightmost pot and tries to maximize the sum of all the pots they take. You can't be greedy because of situations like this: 10, 100, 10, 5 If you were greedy, you would take 10 first, and the other person would take 100. If you instead took 5, they would be forced to take one of the 10's, leaving the 100 available for you to take. The recursive idea here is minimax. The maximum I get from X to Y is the maximum of either the gold at X + what's left over when the other player takes from X+1 to Y, or the gold at Y + what's left over when the other player takes from X to Y-1. As an implementation note, we should keep track of the amount both players get over each interval. If the other player gets R gold, with T gold leftover for me, when choosing from the subrange X+1 to Y, then from the range X to Y, I can easily say that if I choose to take the gold from X, I get T + gold[X] gold, leaving R gold for the other person. This makes the code much simpler. Since each case is based only on subcases of a smaller length (e.g. from X to Y, which is length Y - X, only depends on X to Y-1 and X+1 to Y, both of length Y-X-1), we can build up the cases in order of length. C++ DP implementation would look something like this: pair dp[n][n]; for (int i = 0; i L = dp[i + 1][i + len]; pair R = dp[i][i + len - 1]; if (gold[i] + L.second > gold[i + len] + R.second) dp[i][i + len] = make_pair(gold[i] + L.second, L.first); else dp[i][i + len] = make_pair(gold[i + len] + R.second, R.first); } } The amount of gold I get is dp[0][n - 1].first Use induction: Suppose that I know how to play best with N arbitrary pots. What's my best move with N+2 pots? Trivial cases: N=0 and N=1. With N+2 pots, I can chose L or R. After that my opponent chooses L or R. Then it's my turn again, but this time, with N pots, I know how to play, by induction hypothesis. So what's the best move? It's the one that maximizes the worst case scenario (that is, my opponent playing her best). What's the worst if I pick the left? It's the value of the left pot plus the minimum of two scenarios: 1. the opponent picks L and I do my best with what's left and 2. the opponent picks R and I do my best with what's left. I do the same calculation assuming that I take the right first. The best of the two worst scenarios maximizes my goal. Here's the code in C++: enum Move ( L, R, E }; // left, right, end of game Move BestMove(int const * left, int const * right, int & minGain) { if (left == right) // there's nothing left in between { minGain = 0; return E; } if (right - left == 1) // just one left { minGain = *left; return L; // arbitrary choice } // I take left, she takes right int xLL; BestMove(left + 2, right, xLL); // I take the left, she takes the right, or vice versa int xLR; BestMove(left + 1, right - 1, xLR); // I take the right, she takes the right int xRR; BestMove(left, right - 2, xRR); // my worst if I take left int wLeft = *left + std::min(xLL, xLR); // my worst if I take right int wRight = *(r-1) + std::min(xLR, xRR); // the better of the two minGain = std::max(wLeft, wRight); return (wLeft >= wRight)? L: R; } void main() { int pots[] = { 2, 4, 10, 2, 3, 1 }; int minGain; Move m = BestMove(a, a + 6, minGain); } Dynamic programming public class GoldPots { public static int max(int a, int b) { return a < b ? b : a; } public static int solve(int[] a, int player) { int n = a.length; int[][] m = new int[n][n]; int[] sums = new int[n]; sums[0] = a[0]; for(int i = 1; i < n; i++) { sums[i] = sums[i-1] + a[i]; } for(int i = 0; i < n; i++) { m[i][i] = a[i]; } int sumij; for(int k = 1; k < n - 1; k++) { for(int i = 0; i < n - k; i++) { for(int j = i + k; j < n; j++) { sumij = sums[j] - sums[i] + a[i]; m[i][j] = max(sumij - m[i + 1][j], sumij - m[i][j-1]); } } } return m[0][n-1]; } public static void main(String[] args) { int[] a = {1,9,5,3,6,2}; System.out.println(solve(a,0)); } } |

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

Implement the "see and tell" algorithm with a given seed number x and a number of iterations y. Output the result on iteration y 10 AnswersThe description of the problem was very fussy at first. Hi didn't mention the "see and tell" algorithm, just started to show some example inputs and outputs on collabedit and asked to code a function to generate those outputs. FYI : http://en.wikipedia.org/wiki/Look-and-say_sequence Here is a quick solution in PHP: Show More Responses java solustion: public static String seeAndTellAlgo(String num, int i) { if (i == 0) { return num; } // get next number String next = getNext(num); System.out.println(next); return seeAndTellAlgo(next, i - 1); } public static String getNext(String num) { if (num == "") { return num; } if (num.length() == 1) { return "1" + num; } String result = ""; char[] numChar = num.toCharArray(); int[] records = new int[256]; char pre = numChar[0]; records[pre]++; for (int i = 1; i < numChar.length; i++) { char cur = numChar[i]; if (cur != pre) { int count = records[pre]; records[pre] = 0; result += String.valueOf(count) + Character.toString(pre); } if (i == numChar.length - 1) { if (cur != pre) { result += '1' + Character.toString(cur); } else { result += String.valueOf(records[cur] + 1) + Character.toString(cur); } } records[cur]++; pre = cur; } return result; } Solution in c++ #include #include #include #include #include #include std::vector countOcuurence(std::deque lnsQueue, int len) { int prev = -1; int count = 0; std::vector output; while(!lnsQueue.empty()) { if(prev == -1) { prev = lnsQueue.front(); count++; lnsQueue.pop_front(); } while((!lnsQueue.empty()) && (lnsQueue.front() == prev)) { count++; lnsQueue.pop_front(); } output.push_back(count); output.push_back(prev); prev = -1; count = 0; } return output; } void lookandsay(int seedX, int iterY) { std::ostringstream outstring; std::deque lookNsayQueue; std::vector lookNsayV; int len,k; outstring 0) { for(int i=0;i Recursive solution in php function seetell($seed,$n){ if($n>0){ $seed = str_split($seed); $output = ""; $last = $seed[0]; $count = 1; for($i=0;$i The previous solutions seem a bit long; here's a recursive C++ solution: string my_itoa(int x) { char res[64]; sprintf_s(res, "%d", x); return string(res); } void lookAndSay(string& str, string& temp, int n) { if (n + to the resulting string, remove identical chars from str, and recurse temp += my_itoa(count) + c; lookAndSay(str.substr(i), temp, n); } import java.util.LinkedList; public class LookAndSay { /** * http://en.wikipedia.org/wiki/Look-and-say_sequence */ public static void main(String[] args) { System.out.println(lookAndSay(1, 7)); } public static String lookAndSay(int x, int y) { LinkedList list = new LinkedList(); list.addFirst(new Node(x, 1)); for (int i=0; i spread(LinkedList list) { LinkedList spread = new LinkedList(); for (Node node : list) { spread.addLast(new Node(node.count, 1)); spread.addLast(new Node(node.number, 1)); } return spread; } public static LinkedList collect(LinkedList list) { LinkedList collect = new LinkedList(); collect.addLast(list.removeFirst()); while (!list.isEmpty()) { Node head = list.removeFirst(); Node tail = collect.getLast(); if (tail.number == head.number) { tail.count++; } else { collect.addLast(head); } } return collect; } public static class Node { public int number; public int count; public Node(int number, int count) { this.number = number; this.count = count; } public String toString() { return "{number:" + number + ", count" + count + "}"; } } } import java.util.ArrayList; import java.util.List; import java.util.Scanner; public class LookAndSayGenerator { public static void main(String[] args) { final Scanner in = new Scanner(System.in); while (true) { System.out.println("Enter starting number : "); final String start = in.nextLine(); System.out.println("Enter sequence length : "); final int nextN = in.nextInt(); System.out.println("Sequence : " + lookAndSaySequence(start.toCharArray(), nextN)); } } private static List lookAndSaySequence(char[] start, int nextN) { List sequence = new ArrayList(); if (nextN == 0) { return sequence; } int rep = 0; char ch = '\0'; String next = ""; for (int i = 0; i 0) { next = next + String.valueOf(rep) + String.valueOf(ch); rep = 1; ch = start[i]; } } if (rep != 0) { next = next + String.valueOf(rep) + String.valueOf(ch); } sequence.add(next); sequence.addAll(lookAndSaySequence(next.toCharArray(), nextN - 1)); return sequence; } } |

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

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 Responses I 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. |