# Software Engineering Interview Questions in San Jose, CA

Software engineering interview questions shared by candidates

## Top Interview Questions

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

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

The question was the following. I'm rephrasing the question to make it clear for everyone to understand: - You are going on a one-way flight trip that includes billions of layovers. - You have 1 ticket for each part of your trip (i.e: if your trip is from city A to city C with a layover in city B, then you will have 1 flight ticket from city A to city B, and 1 flight ticket from city B to city C. - Each layover is unique. You are not stopping twice in the same city. - You forgot the original departure city. - You forgot the final destination city. - All the tickets you have are randomly sorted. Question are: - Design an algorithm to reconstruct your trip with minimum complexity. - How would you improve your algorithm. Example: - randomly sorted: New York->London San Francisco-> Hong Kong Paris->New York London->San Francisco - sorted: Paris->New York New York->London London->San Francisco San Francisco-> Hong Kong 9 AnswersAnswer: 1. Select a ticket from the pool of tickets that is different from all the previously selected starting tickets. 2. Keep a count on how many tickets you have used. 3. Keep walking on the ticket path until you exhaust all possible paths without going back. Increment count every time a ticket is used. 4. If the final count equals the total number of tickets you have, you've got the path sorted. 5. Otherwise, repeat from step 1. Can be improved via parallelization where you can shoot off multiple threads each having its own starting ticket in parallel. Whenever a thread completes the sorting based on step 4, stop all other threads. Represented it as a direct graph, the number of nodes are N+1, the number of edges are N, topological sorted, Time = O(N) Represented as a directed graph. Start from node without any entering edge O(n) and follow the path O(n). Show More Responses Hmm, I implemented this graph using a Hashtable : Note that this solution will only work for unique layovers... The starting cities are the keys, and the ending cities are the values I forgot to finish my answer: loop through all the entries { add the start->end pairs in there (checking to see if the start doesn't already exist) and an empty entry for the end city (again, only if it doesn't already exist). In the case that you add a start->end entry, the start becomes your global start. } Then just follow the white rabbit from the global start at the end to get your list :) If I've screwed up somewhere please let me know, thanks! I think its simpler than that. Just count all of the cities on the tickets. The original departure and final location city will appear once (assuming unique layovers, an odd number of times with non-uniqueness) this is O(n). Then, follow the path, which I think is O(n^2) because you have to check the remaining remaining tickets each time. none of these will work for billions of layovers. you can not load billions of layovers into memory. Benquan Yu, yes but to reconstruct the whole path we'll always need O(N) memory, either RAM memory or disk space. Eh |

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

print out all prime numbers in a given string. abc2134kd31 -> 2, 13, 3, 3 10 Answerseasy Code in C# - verified working: static void PrintPrimes(string str) { int i; string lastNum = null; foreach (char c in str) { if (Int32.TryParse(c.ToString(), out i)) { lastNum = lastNum += i.ToString(); int concatNum = Int32.Parse(lastNum); // Iterate through all nums for (int ix = 0; ix < lastNum.Length; ix++) { string currNumStr = lastNum.Substring(ix, (lastNum.Length - ix)); int currNum = Int32.Parse(currNumStr); // Print out if prime if (isPrime(currNum)) { Console.WriteLine(currNum); } } } else { lastNum = null; } } } static bool isPrime(int x) { for (int i = 2; i <= Math.Sqrt(x); i++) { if (x % i == 0) return false; } return true; } btw, correct answer is not "2, 13, 3, 3" but "2, 13, 3, 3, 31" Show More Responses Here is the answer bool isPrime(int num) { for (int i=2;i '9' || currentChar < '0') { return false; } int currentDigit = currentChar - '0'; num = num*(current+1); num += currentDigit; } return true; } void PrintPrimes(char* text, int length) { if (length == 0) { return; } int currentIndex; int currentLength; while (currentIndex < length) { char* temp = new char[currentLength+1]; strcpy(temp, text+currentIndex, currentLength); int num; if (ConverToNum(temp, currentLength, &num)) { if (isPrime(num)) { Console.WriteLine(num); } currentLength++; } else { // couldn't convert to a number therefore we hit a non-integer currentIndex = currentIndex + currentLength + 1; currentLength = 0; } } } public class Prime { /** * @param args */ public static boolean isInteger(char c) { try { Integer.parseInt(String.valueOf(c)); return true; } catch (NumberFormatException nfe) {} return false; } public static void main(String[] args) { // TODO Auto-generated method stub String str="abc2134d31"; findprime(str); } static boolean isPrime(int x) { for (int i = 2; i <= Math.sqrt(x); i++) { if (x % i == 0) return false; } return true; } private static void findprime(String str) { // TODO Auto-generated method stub for(int i=0;i $str = "35713m2m16mmm16mm97m47"; for($i=0;$i<=strlen($str);$i++) { if (!is_numeric(substr($str,$i,1))) { continue; } for($j=$i+1;$j<=strlen($str);$j++) { if (is_prime((int)substr($str,$i,$j-$i))) { print substr($str,$i,$j-$i).","; $i=$j-1;break; } if (!is_numeric(substr($str,$i,$j-$i))) { $i=$j-1;break; } } } function is_prime($i) { if($i == 2) return true; if($i % 2 != 1 || $i == 1) return false; $d = 3; $x = sqrt($i); while ($i % $d != 0 && $d < $x) $d += 2; return (($i % $d == 0 && $i != $d) * 1) == 0 ? true : false; } Vishal's code has a small bug, if you input test61test , it checks if 6 is prime, if it is it does the checknext function, it should implement checknext regardless that number being prime or not. public class Prime { //Take any string and print all the prime numbers in it /** * @param args */ public static boolean isInteger(char c) { try { Integer.parseInt(String.valueOf(c)); return true; } catch (NumberFormatException nfe) {} return false; } public static void main(String[] args) { // TODO Auto-generated method stub String str="ibby37primete61s43"; findprime(str); } static boolean isPrime(int x) { for (int i = 2; i <= Math.sqrt(x); i++) { if (x % i == 0) return false; } return true; } private static void findprime(String str) { // TODO Auto-generated method stub for(int i=0;i javascript version: var isPrime = function (n) { if (n === 2) return true; if (n < 2 || n % 2 === 0) return false; for (var d = 3, t = n; d < t; t = ~~(n/d), d += 2) { if (n % d === 0) return false; } return true; }; var printPrimes = function (s) { var i, j, k, c, d, result = []; for (i = 0, j = s.length; i < j; i++) { c = s.charAt(i); if (!isNaN(c)) { if (isPrime(~~c)) result.push(c); for (k = i + 1; k < j; k++) { d = s.charAt(k); if (!isNaN(k)) { c += s.charAt(k); if (isPrime(~~c)) result.push(c); } else { break; } } } } return result; } java version public boolean isPrime(int n){ if(n = 0 && c - '0' findPrimes(String str){ char[] chars = str.toCharArray(); List nums = new LinkedList(); for(int i = 0; i < chars.length; i++){ String temp = ""; for(int k = i; k < chars.length; k++){ char x = chars[k]; if(isNum(x)){ temp += x + ""; if(isPrime(Integer.parseInt(temp))){ nums.add(temp); } } else break; } } return nums; } A recursive C++ version: // borrowed from http://en.wikipedia.org/wiki/Primality_test#Java_implementation bool isPrime(unsigned x) { // x in [2, 3] if (x 1); // x divisible by 2 or 3 if (!(x%2) || !(x%3)) return false; // chug along: // if x is not prime, x = a * b, where either a or b < int(sqrt(x)) // it's enough to check until i^2 <= x for (int i = 5; i*i <= x; i += 6) if (!(x%i) || !(x%(i+2))) // divisible by i or (i+2) return false; return true; } bool isNumber(char c) { return ('0' <= c && c <= '9'); } void printPrimes(const string& str, string temp, int i) { if (str.empty()) return; if (temp.size() == str.size()) { printPrimes(str.substr(1), "", 0); return; } temp += str[i]; if (isPrime(atoi(temp.c_str()))) printf("%s\n", temp.c_str()); printPrimes(str, temp, i+1); } void printPrimes(string str) { for (int i = 0, j = 0; j < str.size(); ) { // skip non-numerical chars while (!isNumber(str[++i])); // continue while numerical chars j = i; while (isNumber(str[j++])); printPrimes(str.substr(i, j-i), "", 0); i = j; } } |

### Software Engineer at Ooyala was asked...

Given two integer arrays. Find the Largest Common sub array. For example, arr1 = {1,2,3,2,3,2} arr2={2,2,3,3,4,5}, the largest common sub array is {2,2,3,3} 8 AnswersI try to an array as a hash table. index is the element, value is the times the element appears in arr1, and then traversal arr2, with the hash table. The problem of my algorithm is that I need to know the range of the arrays' element value, because I need to use that to define the size of my array. The interview asked me if I was familiar with the STL hashmap, which i was not Was this asked in phone interview ? sort + join - looks like the answer Show More Responses The question is confusing.You are sayin common sub array but the sub array is present only in 2nd array. common sub array should be {2,3} instead of {2,2,3,3} it seems from the answer that the question is actually the longest common subsequence, which is a dynamic programing problem this has several answers but no need for dynamic programming solution. 1. sort + join - O(nlogn) 2. keep counts for integers in array or hashmap - O(n) but need lot of extra space O(n) Seems the question is to give an array with the common elements between the two arrays. If this is the case, you should use a HashMap. The keys are numbers in the first array. The value is the number of times each one shows up. Have an array for the result. Then go over the second array. Look for each number in the hashMap. If it's there and the value is greater than 0, append it to the result and reduce in 1 the value in the hashmap for that number. public static Integer [] commonElements ( int [] a, int [] b ){ java.util.HashMap h = new java.util.HashMap (); for ( int e: a ){ if (h.containsKey(e))h.put(e, h.get(e)+1); else h.put(e, 1); } java.util.ArrayList resultAL = new java.util.ArrayList (); for ( int e: b){ if ( h.containsKey(e)&&h.get(e)>0){ resultAL.add(e); h.put(e, h.get(e)-1); } } Integer[] result = resultAL.toArray(new Integer [ 0 ]); return result; } |

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 Google was asked...

Was asked how I would implement division without using division or mod operators. The answer should return in the form quotient r remainder. 8 AnswersAnswer 1: Use subtraction and keep a count of how many times subtracted. When the remainder is smaller than the divisor, count is your answer, and whatever is left is the remainder. Was then asked the complexity in terms of binary. After that, was asked to come up with a solution with better complexity. Answer 2: Multiply the divisor by two until it is larger than the dividend. Go back one, subtract that out, multiply again. This solution will have a much better complexity. I could not get second solution. Though its really interesting .... e.g. 39/3 1. multiply 3 with 2 until it gets bigger 3->6->12->24->48 (using 8 3. Sub that out 39-24 = 14 4. Go to 1 1. multiply 3 with 2 until it gets bigger than 29: 6,12,24,48 2. Go back one: 24 =>8 3. Sub that out: 39-24 = 15 1. multiply 3 with 2 until it gets bigger than 15: 6,12,24 2. Go back one: 12 =>4 3. Sub that out: 15-12 = 3 1. multiply 3 with 2 until it gets bigger than 3: 6 2. Go back one: 3=>1 3. Sub that out: 3-3 = 0 Answer: 8+4+1 = 13 Show More Responses I think you're very close, but perhaps the interviewer was suggesting to think of the quotient in terms of being a binary number. // QuickDivide, implemented in Java public static String QuickDivide(int num, int denom) { int quotBits = 1; // start with a single bit quotient int quot = 0; // get number of quotient bits while (Math.pow(2,quotBits) * denom = 0; bitExp--) { if (num >= Math.pow(2, bitExp)* denom) { // add to quotient and subtract from numerator quot += Math.pow(2,bitExp); num -= Math.pow(2, bitExp) * denom; } } // numerator is holding remainder return String.format("%1$d R %2$d", quot, num); } // gets leftmost bit position public native static int __builtin_clz(int n); /** * Divide x by y. * @return {result, reminder} */ public static int[] div(int x, int y) { int py = __builtin_clz(y); int res = 0; while(x > 0) { int px = __builtin_clz(x) - py; x -= y << px; if (x < 0) { x += y; px--; } res += 1 << px; } return new int[] {res, x}; } Besides the returning format, and according the algorithm above, I would write in C the following function: void div(int N, int D) { int Q = 0; int x = N; int it = 1; while (x >= D) { if ( x < (D << it) ) { x -= (D << (it-1)); Q += (1 << (it-1)); it = 0; } it++; } cout << "Quotient: " << Q << " Remainder: " << x << endl; } public class Division { public static void main(String[] args) { int num = 23, denom = 7; System.out.println(Divide(num, denom)); } public static String Divide(int num, int denom) { int quotBits = 1; // start with a single bit quotient int quot = 0; // get number of quotient bits while ((denom = 0; bitExp--) { if (num >= (denom< despite these comments, I would do a binary search on the quotient. the upper bound is the dividend |

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

Find the balance point in an array. (The index where the sum of the elements to the left it is the same as the sum of the elements to the right of it.) 7 Answerspublic class Solution { public static int solve(int[] arr){ int mid = arr.length/2; int sumLeft=0; int sumRight=0; int index = -1; boolean flagLeft= false; boolean flagRight= false; for(int i=0;isumRight && !flagLeft){ sumRight+=arr[mid]; sumLeft-=arr[mid-1]; mid--; flagRight=true; } else if(sumLeft==sumRight){ index=mid; break; } else{ return -1; } } return index; } public static void main(String args[]){ int [] temp = {9,5,4,1,3,10,5}; int t = solve(temp); System.out.println("Index: "+t); //Output the index } } more complicated than it needs to be. or: long sumLeft = arr[0]; long sumRight = arr[arr.length-1]; int i=1, j = arr.length-2; for (; i sumRight) { sumRight += arr[j--]; }else { sumLeft += arr[i++]; sumRight += arr[j--]; } } return i; Show More Responses The 3rd solution is brilliant but it is only applicable to arrays containing only non-negative values. The solution to solve the problems regardless of value signs but using addition O(n) memory: public static int BalanceImprove(int[] a) { //as we discussed we need two extra arrays to store the sums from left to right and from right to left int[] leftSums = new int[a.length]; int[] rightSums = new int[a.length]; //now we compute sums for leftSums, but as each sum is depending on previous sum, we need assign the 1st sum to a[0] leftSums[0] = a[0]; for(int i=1; i=0; i--) rightSums[i] = rightSums[i+1]+a[i]; //now compare each value in left and right sum arrays to find match for(int i=0; i By adding one more array and do DP, your sum from left to right and right to left arrays will save more computations. But the most easy case should be one pass do a sum, second pass use one tmp to calculate sum_left, if its' half of sum-a[i], then you get it. - Find total sum of all elements in the array. - Now iterate to array again and keep adding element value to sum1 - keep doing it and subtract the value of the element from total sum - loop this untill we reach a point i where sum1 = sum - element[i]. - i is the index of that element which divides the array into two similar parts - Complexity O(N) def balance_point(arr): s1, s2 = 0, sum(arr)-arr[0] for i in range(len(arr)-2): if s1 == s2: return s1 s1 += arr[i] s2 -= arr[i+1] print balance_point([10, -2, 1, 3, 4, 2]) |

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

You are a parking lot attendant in a lot that has one open spot, and you want to move the cars from their original positions into a new arrangement. Create a program that will print out instructions on how to move the cars most efficiently. 7 AnswersThe problem is not too difficult, what you have to do is find the empty spot, then look in the desired arrangement for what car should be in that spot, and move that car there. Repeat until complete. Does this really work? If I the empty spot is expected to be the same, but the positions of two (or more) cars are switched, how to rearrange it without a complete search? It's the Tower of Hanoi Problem. Show More Responses So there are actually 2 empty spots then or is there a way to 'stack' cars I don't know of? The parking lot problem has nothing to do with Tower of Hanoi, which requires O(2^n -1). This problem, however, can be solved in O(n) - that's because all you need to do is to perform (0 or more) rotations using the empty parking spot. Here is a C# implementation, using generics and .NET 4.0 Tuple: IEnumerable> RearrangeCars( TCar emptyCarMarker, IDictionary initial, IDictionary desired) { // reverse the lookup: car -> spot Dictionary pending = initial.ToDictionary(p => p.Value, p => p.Key); // remove emptySpot from lookup TSpot emptySpot = pending[emptyCarMarker]; pending.Remove(emptyCarMarker); while (pending.Any()) { // check if the empty spot is where is should be if (desired[emptySpot].Equals(emptyCarMarker)) { while (true) { // pick a car (any car would do) var carToMove = pending.First(); // check if this car is already in its desired position if (desired[carToMove.Value].Equals(carToMove.Key)) { // remove from pending, no moving is necessary pending.Remove(carToMove.Key); if (pending.Any() == false) yield break; } else { yield return new Tuple(carToMove.Key, carToMove.Value, emptySpot); // move the car TSpot newSpot = emptySpot; emptySpot = carToMove.Value; pending[carToMove.Key] = newSpot; break; } } } // move the car into its desired spot var car = desired[emptySpot]; var newEmptySpot = pending[car]; yield return new Tuple(car, newEmptySpot, emptySpot); emptySpot = newEmptySpot; pending.Remove(car); } } Note that there is a while-loop inside another while-loop. However, the complexity is still O(n) since at every iteration of internal or external loop, the "pending" map is reduced by one element. Below are some examples (emptyCarMarker == ""). EXAMPLE 1: Input: initial == { "", "B", "A"} desired == { "", "A", "B"} Output: (B, 1, 0) // move car B from spot #1 to #0 (A, 2, 1) // move car A from spot #2 to #1 (B, 0, 2) // move car B from spot #0 to #2 EXAMPLE 2: Input: initial == { "", "B", "A", "D", "C" } desired == { "A", "B", "", "C", "D" } Output: (A, 2, 0) (D, 3, 2) (C, 4, 3) (D, 2, 4) Here is a Java Implementation, using Google's guava library for the BiMap. It takes O(n) to first create the BiMap and O(n) to move the cars, total O(2n), i.e. O(n) time complexity. import com.google.common.collect.BiMap; import com.google.common.collect.HashBiMap; import java.util.Map; import java.util.Set; class ParkingAttendant { static class ParkingConfiguration { static final Integer EMPTY = -1; Integer moves = 0; BiMap conf, i_conf; static ParkingConfiguration getInstance(int[] conf){ return new ParkingConfiguration(conf); } private ParkingConfiguration(int[] conf){ this.conf = arrayToMap(conf); this.i_conf = this.conf.inverse(); } BiMap arrayToMap(int[] arr){ BiMap m = HashBiMap.create(arr.length); for(int i=0;i> entrySet(){ return conf.entrySet(); } } static void moveCars(ParkingConfiguration from, int[] to){ for(int pos=0; pos e : p.entrySet()){ int pos = e.getKey(); int car = e.getValue(); System.out.format("%1$s, ", ParkingConfiguration.EMPTY.equals(car)?"_":car); } System.out.println("]"); } static void printCars(int[] p){ System.out.print("["); for(int pos=0; pos |

### 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)); } } |

**31**–

**40**of

**6,130**Interview Questions

## See Interview Questions for Similar Jobs

- Senior Software Engineer
- Software Developer
- Software Development Engineer
- Intern
- Software Engineer Intern
- Data Scientist
- Analyst
- Engineer
- Product Manager
- Software Engineer II
- Business Analyst
- Consultant
- Associate Software Engineer
- Staff Software Engineer
- Java Developer
- Director
- Project Manager
- Senior Software Developer
- Software Engineering Intern
- Software Engineer III