# Software Engineering Interview Questions in San Jose, CA

Software engineering interview questions shared by candidates

## Top Interview Questions

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

Implement a function rotateArray(vector<int> arr, int r) which rotates the array by r places. Eg 1 2 3 4 5 on being rotated by 2 gives 4 5 1 2 3. 18 AnswersI started with the trivial O(n) time and O(n) space algo. The best algo can do this in O(1) space. def rotate(vec, r) : if r <= 0 : return vec L = len(vec) r %= L (cnt, beg) = (0, 0) while cnt < L : cur = beg tmp = vec[cur] while True : next = (cur + r) % L tmp1 = vec[next] vec[next] = tmp tmp = tmp1 cur = next cnt += 1 if cur == beg : break beg += 1 return vec private static Vector rotateArray(Vector items, int r){ if(items==null){ return items; } if(r==items.size()){ return items; } LinkedList list=new LinkedList(items); for(int i=1; i (list)); } Show More Responses public static void rotateArray(int[] in, int r){ int i =0,j = in.length -1; reverseArr(in, i, j); reverseArr(in, 0, r -1); reverseArr(in, r, j); } public static void reverseArr(int[] in, int si, int ei){ int i =si,j = ei; while (i <= j){ int tmp = in[i]; in[i] = in[j]; in[j] = tmp; i++; j--; } } Algorithm mentioned by Kruk is incorrect. Here is an example: Given array:{1,2,3,4,5,6,7,8,9,10} and you want to rotate 7 times. The answer is {8,9,10,1,2,3,4,5,6,7}, but the above algorithm produces {4,5,6,7,8,9,10,1,2,3}. Sorry, I misunderstood the question as left rotation, instead of right rotation. http://ideone.com/yxWRl O(n) runtime, O(r) extra space http://ideone.com/Gv6Lo A very nice O(n) solution with O(n) space Using STL magic.. with O(r) extra space. void rotate(vector &vec, int r) { if(vec.size() tmp(vec.end()-r, vec.end()); vec.erase(vec.end()-r, vec.end()); vec.insert(vec.begin(), tmp.begin(), tmp.end()); } void rotate_inplace(vint &num, int k) { //inplace rotation of array o(n) time, o(1) space int size=num.size(); if(size==0) return; //k=-k; //if you want right rotate k=k%size; k=k<0?size+k:k; if(k==0) return; int pos=0, start=0; int initial,buffer; const int offset=size-k; for(int i=0;i the solution above is a generalized version of swap; however since the jump size was constant (=k), once we return back to starting index (after the swap circle) we can just increment the start by 1 to get new start, (i.e, in all elements were not covered already) however for a general swap you cannot do so import os import sys def unsort(array): s,f=0,float('inf') while(s%d,"%(s,f), #s has looped back to start print while s O(n) time with O(1) space #include using namespace std; int circle_number(int n, int k) { int c = 1; int sum = k; while(sum % n != 0) { sum += k; c += 1; } return n/c; } void rotate_arr(int arr[], int n, int k) { k = k % n; if(k == 0) return; int circle_num = circle_number(n, k); int num = n / circle_num ; int tmp, prev, start; for(int i=0; i< circle_num; i++) { start = i; tmp = arr[start]; for(int j=0; j O(n) time with O(1) space! Basically, popout the last element and insert it to the beginning! Do this r times! void rotate(vector arr, int r) { while (r--) { int temp = vector.pop_back(); vector.insert(0, temp); } } Show More Responses http://baibingz.wordpress.com/2012/10/26/rotate-array/ O(n) Time O(1) Space In-place, O(n) time, O(1) space. slightly quicker than the version using replace() as it is iterating the array twice while this version does just once. void rotate_array(vector& s, int r) { if(r == 0 || s.empty() || s.size() < 2) { return; } r %= s.size(); if(r == 0) { return; } int round = 0; int loopCnt = s.size(); while(loopCnt) { int cur_idx = round; int cur_val = s[cur_idx]; while(1) { int to = (cur_idx+r) % s.size(); int tmp = s[to]; s[to] = cur_val; cur_idx = to; cur_val = tmp; loopCnt--; if(to == round) break; } round++; } } I just took an array instead of a vector.. public static void rotateArrayByNPlaces(int oArray[], int places) { int length = oArray.length, destinationIndex = 0, startingIndex = 0, boundaryIndex = 0; int nArray[] = new int[length]; destinationIndex = places % length; boundaryIndex = destinationIndex; if(destinationIndex == 0) { printArray(oArray); } else { do { nArray[destinationIndex] = oArray[startingIndex++]; destinationIndex = (destinationIndex + 1) % length; } while(destinationIndex != boundaryIndex); printArray(nArray); } } I wonder if this would work: http://ideone.com/i2QMBw Perl version which works - http://ideone.com/UKxbqA |

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

Given a list of n objects, write a function that outputs the minimum set of numbers that sum to at least K. FOLLOW UP: can you beat O(n ln n)? 15 AnswersQuestion has some ambiguity. If "minimum set of numbers" means the minimum sum of numbers = K. This can be solved with a type of a greedy algorithm. The maximum(..) function shall take into account that when K is negative maximum should return the distance of the number to 0.(abs() of the element). As this boils down to getting maximum element of an array in order, it can easily be implemented via binary heap. The complexity becomes O(n.logn) and not sure if it can be beated. Partition the array by the target value. if any element is larger than target value, return it. else target value -= largest element and do the partition again. 1) Sort the array in increasing order 2) Start scanning backward from largest to smallest elements in array until we have enough elements that sum to given target sum. ArrayList FindMinSet(int sum, int numbers[]) { int numbers[] = Sort(numbers); // Sort in increasing order of numbers -- O(nlogn) ArrayList minSet = new ArrayList(); for(int i=numbers.length-1; i>=0; i--) { sum = sum - numbers[i]; minSet.add( new Integer(numbers[i]) ); if(sum <=0) { return minSet; } } } Show More Responses @Anonymous: that didn't beat O(n lg n) Construct a max heap out of this list. Keep taking out the max and decrease K accordingly till K becomes less than or equal to zero. Making a heap out of the array is O(n). on average, it could be better than O(logn). I believe the closest answer to the correct one is birdy's. You're supposed to partition around a random element x, and get the sum S of all elements larger than x. if S is larger than K, you recurse on the subarray of the elements that are larger than x. if S is smaller than K, you recurse for S-K on the subarray of elements that are smaller than x. The worst case running time of this algorithm can be O(n^2), but it will be O(n) on the average. The probabilistic proof of that statement is not very easy, but the intuitive idea is that most of the time, the partition will be more balanced than a (1,10) ratio, and this enough to make the subarray sizes bounded by a geometric sequence of ratio less than one, which will guarantee you a linear time algorithm. It is also possible to get a worst case linear time algorithm by adapting the algorithm given here: http://en.wikipedia.org/wiki/Selection_algorithm to the weighted case, but this is really overkill and,in practice, the resulting algorithm will be slower than the randomized algorithm I described. Traverse the array, use minHeap to store the values that > 0 and sum >= K if(newNode.value > 0) { if (heap.sum = K && newNode > heap.root.value) heap.root = newNode; //replace root with newNode; while(heap.sum - heap.root.value >= K) heap.remove(root); } Time = nlogm < nlogn - where m is number is Nodes in heap ~ number of numbers needed to sum to K Sorting + scanning is trivial and O(nlogn) If the input data is integer is also trivial, just use radix sort. O(n), so let's assume the input is float numbers If there is an element a[i] s.t. a[i] > t, where t is the target value, then it's also trivial, so let's assume a[i] =0 for all i If the sum of a[i] is still smaller than or equal to t, then the answer is N/A or the whole set, and this can be checked in O(n), so let's assume the sum of a[i] is larger than t. With the above assumption, let's try to do it in a way similar to qsort: select a[0] as pivot, partition the array using a[0], smaller element appears to the left, and larger to the right. do a sum of all the values to the right of the pivot, say it's s', if s's, answer is found; if still s's, we can focus on the subarray defined as the right of the pivot. Repeat the procedure until the answer is found. I believe there is a math proof similar to the analysis of why median selection can be done in O(nlogn) in average cases, to show this algorithm to run in O(n) in average cases. Any ideas? Please ignore the previous post, cuz I made too many silly mistakes. Sorting + scanning is trivial and O(nlogn) If the input data is integer is also trivial, just use radix sort. O(n), so let's assume the input is float numbers If there is an element a[i] s.t. a[i] > t, where t is the target value, then it's also trivial, so let's assume a[i] =0 for all i If the sum of a[i] is still smaller than or equal to t, then the answer is N/A or the whole set, and this can be checked in O(n), so let's assume the sum of a[i] is larger than t. With the above assumption, let's try to do it in a way similar to qsort: select a[0] as pivot, partition the array using a[0], smaller elements move to the left, and larger to the right. do a sum of all the values to the right of the pivot, say it's s', if s's, answer is found; if still s'+pivots, we can focus on the subarray defined as the right of the pivot. Repeat the procedure on the slimmed-down subarray until the answer is found. I believe there is a math proof similar to the analysis of why median selection can be done in O(n) in average cases, to show this algorithm to run in O(n) in average cases. Any ideas? I'm writing the actual code for this. #include #include #include using namespace std; void recPrintTightestSum(double* a, int from, int to, double s) { if (from >= to) { if (from == to) cout s) recPrintTightestSum(a, right+1, to, s); else if (sumRight == s) for (int i = right+1; i = s) cout = s) { cout 0) { sumA += a[i]; offset[i] = 1; }else offset[i] = 0; } if (sumA > s; while (true) { cin >> input[inputL]; if (998 <= input[inputL]) break; inputL++; } printTightestSum(input, inputL, s); return 0; } /* 99 4 3 5 7 21 43 5 2 5 -8 -1 0 0 0 0 0 0 -3 5 -4 3.5 6.5 7.6 999 -2 1 -3 4 -1 2 1 -5 4 999 1 -41 -51 -5 -2 999 -1 0 999 10 0 2 -3 5 5 -5 999 99 4 3 5 7 2 4 5 2 5 -8 -1 0 0 0 0 0 0 -3 5 -4 3.5 6.5 7.6 4 3 5 7 2 4 5 2 5 -8 -1 0 0 0 0 0 0 -3 5 -4 3.5 6.5 7.6 4 3 5 7 2 4 5 2 5 -8 -1 0 0 0 0 0 0 -3 5 -4 3.5 6.5 7.6 4 3 5 7 2 4 5 2 5 -8 -1 0 0 0 0 0 0 -3 5 -4 3.5 6.5 7.6 4 3 5 7 2 4 5 2 5 -8 -1 0 0 0 0 0 0 -3 5 -4 3.5 6.5 7.6 4 3 5 7 2 4 5 2 5 -8 -1 0 0 0 0 0 0 -3 5 -4 3.5 6.5 7.6 4 3 5 7 2 4 5 2 5 -8 -1 0 0 0 0 0 0 -3 5 -4 3.5 6.5 7.6 4 3 5 7 2 4 5 2 5 -8 -1 0 0 0 0 0 0 -3 5 -4 3.5 6.5 7.6 4 3 5 7 2 4 5 2 5 -8 -1 0 0 0 0 0 0 -3 5 -4 3.5 6.5 7.6 999 */ //java implementation below public int minSum(List vals, int sum, int runningValue){ if(vals.size() == 0) return -1; List less = new ArrayList(); List more = new ArrayList(); int pivot = vals.get(0); for(int i : vals.subList(1, vals.size())){ if(i > pivot) more.add(i); else less.add(i); } int moreListSum = 0; for(int i : more){ moreListSum += i; } if(moreListSum = sum) return more.size() + runningValue + 1; else if(moreListSum + pivot < sum){ return minSum(less, sum - (moreListSum + pivot), runningValue + more.size() + 1); } else { return minSum(more, sum, runningValue); } } import random def minimum_numbers(lst, l, r, k): '''returns list of minimum amount of numbers which sum is greater than k''' if l + 1 == r: return [lst[l]] elif l == r: return [] x = random.randrange(l, r) val = lst[x] lsum = 0 rsum = 0 b = l e = r while b val: e -= 1 t = lst[e] lst[e] = lst[b] lst[b] = t rsum += lst[e] else: lsum += lst[b] b += 1 if lsum + rsum = k: return minimum_numbers(lst, e, r, k) else: return minimum_numbers(lst, l, e, k - rsum) + lst[e:r] #include #include #include using namespace std; int partition(int A[], int begin, int end, int &left_sum, int &right_sum) { int x = rand()%(end-begin+1); x = x + begin; int tmp = A[x]; A[x] = A[end]; A[end] = tmp; int lsum = 0, rsum = 0; int i = begin; for(int j=begin; j= k) { for(int i=begin; i= k) begin = pos + 1; else if(right_sum + A[pos] >= k) { for(int i=pos; i 0) { end = pos - 1; } else if(pos > k; if(get_K(A, 7, k)) { cout << "Found !" << endl; } else cout << "No answer!" << endl; } } Show More Responses You could solve it in deterministic linear time using a combination of linear-time selection (median-of-medians solution) and binary search. At each iteration, find the median of the array being considered and partition around it. If the greater half sums to K, return it. If it sums to less than K, store all elements of the greater half and recurse on the lower half. Otherwise, recurse on the greater half. Once you get down to considering a small enough set, just sort and finish off the problem. We have to perform linear time selection and linear partition on n + 1/2n + 1/4n + 1/8n +... elements, which sums to 2n so O(n) running time. Iterate the list and get the average of the list, suppose the average number is A, then we can assume that the set's number should less than K/A = n. Iterate the list again and keep a max heap for n+1 elements I think this can beat O(n ln n) |

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

Given the daily values of a stock, find how you can lose the most with one buy-sell trading. 14 AnswersOr in other words, find the two points where the difference between the two are the largest in the function. "find the two points where the difference between the two are the largest in the function" - this is incorrect. You can not go back in time when it comes to stock trading :) e.g. {2,1,10} has a maximum loss of 1-2 = -1, but has a maximum difference of -9. [11,20,24,51,10,99,15,1,199,75] list of stock prices in increasing order of time stamps Maintain two variables, min and max. Whenever cur value of array is less than max then upadate min do a diff between min and max and update curloss if it is less than curloss. update max variable if value is greater than or equal to max 11 11 0 11 20 0 11 24 0 11 51 0 10 51 -41 10 99 -41 15 99 -84 1 99 -98 1 199 -198 75 199 -198 Show More Responses Slight error in my previous post given above: [11,20,24,51,10,99,15,1,199,75] list of stock prices in increasing order of time stamps Maintain two variables, min and max. Whenever cur value of array is less than max then upadate min do a diff between min and max and update curloss if it is less than curloss. update max variable if value is greater than or equal to max, dont update curloss variable here. 11 11 0 11 20 0 11 24 0 11 51 0 10 51 -41 10 99 -41 15 99 -84 1 99 -98 1 199 -98 75 199 -124 package asaf; public class MaxLose { public static void main(String[] args) { int[] ticks = {5,7,4,2,77,8,9}; int[] worseSell = new int[ticks.length]; worseSell[worseSell.length-1] = ticks[ticks.length-1]; for (int index=ticks.length-2; index>=0; index--) { worseSell[index] = Math.min(worseSell[index+1], ticks[index]); } int lose = 0; for (int index = 0; index < ticks.length; index++) { lose = Math.max(lose, ticks[index] - worseSell[index]); } System.out.println(lose); } } double WorstSell(double *values, int n) { double maxBuySeenSoFar = 0.0; double minprofit = 0.0; // in-order lose most. we need to buy high and sell low. we can only sell after buying. for (int i = 0; i maxBuySeenSoFar) { maxBuySeenSoFar = values[i]; } else if (maxBuySeenSoFar - values[i] < minprofit) { minprofit = maxBuySeenSoFar - values[i]; } } return minprofit; } Recursive way to solve this in n logn public static int[] findMaxLost(int[] prices) { return rFindMaxLost(prices, 0, prices.length-1); } private static int[] rFindMaxLost(int[] prices, int p, int r) { if (p == r) { int[] ml_pos = new int[2]; ml_pos[0] = p; ml_pos[1] = p; return ml_pos; } int q = (p + r) / 2; int[] l_ml_pos = rFindMaxLost(prices, p, q); int[] r_ml_pos = rFindMaxLost(prices, q + 1, r); /*find the max_min cross the center point q*/ int[] m_ml_pos = new int[2]; m_ml_pos[0] = findMax(prices, p, q); m_ml_pos[1] = findMin(prices, q + 1, r); if ((l_ml_pos[0] - l_ml_pos[1]) >= (m_ml_pos[0] - m_ml_pos[1]) && (l_ml_pos[0] - l_ml_pos[1]) >= (r_ml_pos[0] - r_ml_pos[1])) { return l_ml_pos; } else if ((m_ml_pos[0] - m_ml_pos[1]) >= (r_ml_pos[0] - r_ml_pos[1])) { return m_ml_pos; } else { return r_ml_pos; } } private static int findMax(int[] prices, int p, int q) { int pos = 0; for (int i = p + 1; i prices[i]) { pos = i; } } return pos; } reader writer pointer soution. O(n) public class MaxLose { public static void main(String[] args) { MaxLose m = new MaxLose(); int[] a = new int[]{10, 3, 20, 10, 12, 5, 20, 7, 5, 3}; int max = m.maxLose(a); System.out.println(max); } private int maxLose(int[] a) { int b = 0, max = 0; for (int s = 1; s max ? a[b] - a[s] : max; } return max; } } Most answers here are in correct. Here is the algorithm. You first identify all buy canditaes, and all sell candidates. A buy canditate is: a point which is bigger than everything on its left and also bigger than the next point on its right. A sell candiate is a point that is smaller than everything on its right and also smaller than the point on its left. Then you match buy canditates to sell candidates, for every buy candidate the matching sell canditate is the first sell candidate on its left. (multiple buy candidates can match multiple sell) After they are matched the pair with maximum difference will give you the max loss. O(n) needed to find candidates, les than O(n) neded to match pairs. Most answers here are in correct. Here is the algorithm. You first identify all buy canditaes, and all sell candidates. A buy canditate is: a point which is bigger than everything on its left and also bigger than the next point on its right. A sell candiate is a point that is smaller than everything on its right and also smaller than the point on its left. Then you match buy canditates to sell candidates, for every buy candidate the matching sell canditate is the first sell candidate on its right. (multiple buy candidates can match multiple sell) After they are matched the pair with maximum difference will give you the max loss. O(n) needed to find candidates, les than O(n) neded to match pairs. public static int minPoint(List list){ if (!list.isEmpty()){ int minPoint = list.get(0); return Math.min(minPoint - findMax(list),minPoint(list.subList(1, list.size()-1))); } return 0; } private static int findMax(List list) { int max = list.get(0); for (int i=1; i max){ max = list.get(i); } } return max; } public static void main(String[] args) { int[] a = new int[]{10, 3, 20, 10, 12, 5, 20, 7, 5, 3}; List list = new ArrayList(); for (int i=0; i //Given the daily values of a stock, find how you can lose the most with one buy-sell trading. //A[] -> {5, 8, 6, 3, 9, 3, 2, 7} //B[] -> {0, 3,-2,-3,6,-6,-1, 5} ? diff A[i] = A[i] - A[i - 1] //C[] -> {0, 0,-2,-5,0,-6,-7,-2} -> min(0, B[i - 1] + B[i]) public int[] looseMost(int[] A) { int minRes = 0; int sIdx = 0; int eIdx = 0; int currRes = 0; int csIdx = sIdx; int prevB = 0; int currB; int currC = 0; for (int i = 1; i < A.length; i++) { currB = A[i] - A[i - 1]; currC = Math.min(0, currB + prevB); if (currC < minRes) { sIdx = csIdx; eIdx = i; } else if (currC == 0) csIdx = i; prevB = currB; } return new int[] {sIdx, eIdx}; } If I understand the question correctly, the task is to find the minimum consecutive sum of price differences, which is equivalent to a maximum consecutive sum algorithm (just google it). This can be solved in O(n) using a dynamic programming approach. Show More Responses The solution is here: http://www.geeksforgeeks.org/archives/6463 |

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

Find a sequence with max sum in an array of negative and positive real numbers. 15 AnswersYou construct a sub-sequence within the array where all entries are >= 0.0. Trick question. Given an array a[n], find the subsequence with the greatest sum (without reordering the elements). Let p[i] = the max sum of elements up to and including a[i]. It may or may not include a[i-1], a[i-2], etc. but it must include a[i]. Then p[i+1] = max(a[i+1], p[i] + a[i+1]). The basis is p[0] = a[0]. This recurrence is simple enough to perform in O(n) time and O(1) space. At each step, we need only decide whether to extend the current run or start a new one. float bestsum = sum = a[0]; int i, besti = 0; int len, bestlen = 1; for (i = 1; i bestsum) { bestsum = sum; besti = i; bestlen = len; } } printf("Elements %d through %d sum to %g\n", besti, besti + bestlen - 1, bestsum); function bestSum (array a): size = count of items in array bestsum = a[0] + a[1] //this assumes zero-indexed arrays for (i=0; i bestsum bestsum = sum endfor endfor return bestsum end function Show More Responses lamont, your solution assumes that all elements are positive. No. The (sum < 0) condition accounts for negative elements. My solution does assume that sequences of length 1 are allowed. In the case of ALL negative input, it chooses the single largest element (i.e. the one closest to zero). I tested it against monkeysdown's O(n^2) solution on a variety of mixed positive/negative inputs. They produce the same results except in the case mentioned above. The only error in my solution was the printf. It should read: printf("Elements %d through %d sum to %g\n", besti - bestlen + 1, besti, bestsum); If the minimum sequence length is 2, then it's still possible to solve in O(n). Briefly: float sum = a[0] + a[1]; float bestsum = sum; for (int i = 2; i bestsum) bestsum = sum; } return bestsum; 1) convert the sequence of pos/neg numbers into another sequence of pos/neg numbers where pos/neg numbers are alternating. ie: original sequence 2, -1, 3, 4, -5, -1, 10, 2 into 2, -1, 3+4, -5 + (-1), 10 + 2 ==> 2, -1, 7, -6, 12 with the new sequence, start with first number, as long as next pair of pos/neg number adds together is more than 0, then keep using those numbers in the sub-sequence. The result is O(n) for worst case. It's little more complicated to program. public static double maxSequenceSum(double[] array) { double maxSum = Double.MIN_VALUE; double maxElm = Double.MIN_VALUE; double curSum = 0; for(int i = 0; i maxElm ? array[i] : maxElm; maxSum = curSum > maxSum ? curSum : maxSum; if(curSum + array[i] >= 0) curSum += array[i]; else curSum = 0; } maxSum = maxElm > maxSum ? maxElm : maxSum; return maxSum; } small correction to my previous answer! public static double maxSequenceSum(double[] array) { double maxSum = Double.NEGATIVE_INFINITY; double maxElm = Double.NEGATIVE_INFINITY; double curSum = 0; for(int i = 0; i = 0) { curSum += array[i]; maxSum = curSum > maxSum ? curSum : maxSum; } else { curSum = 0; maxElm = array[i] > maxElm ? array[i] : maxElm; } } maxSum = maxElm > maxSum ? maxElm : maxSum; return maxSum; } I can't believe they would still ask this question - easiest in the book. huh! dynamic programming written all over it! public int computeDP() { int[] V = new int[L.length]; V[0] = L[0]; int max = -1; for(int i = 1 ; i V[i-1] + L[i]) { V[i] = L[i]; } else { V[i] = V[i-1] + L[i]; if(V[i] > max) { max = V[i]; } } } return max; } public void maximumSumSubsequence(int [] array){ int currentMaxSum = 0; int startIndex = 0; int maxSum = 0; int maxStartIndex = 0, maxEndIndex = 0; for (int i = 0; i = maxSum ){ maxSum = currentMaxSum; maxEndIndex = i; maxStartIndex = startIndex; } if ( currentMaxSum < 0 ){ startIndex = i + 1; currentMaxSum = 0; } } System.out.println ("Current max sum " + maxSum ); System.out.println("current start index " + maxStartIndex); System.out.println("End index " + maxEndIndex); } Show More Responses The answer to this problem is the submaxarray algorithm. Find it here: http://en.wikipedia.org/wiki/Maximum_subarray_problem Kadanes algorithm |

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

Phone interview 1 : a) Simulate a Queue with stacks ? b)Find repeated occurrence of character in a string ? Phone interview 2 : a) Given a 2D matrix of numbers find the position of number . Constraints of matrix number always in increasing order left to right and top to bottom . b)When should version control be used . And a tricky discreet math problem ? 13 AnswersWow, a lot of questions: 1. a) Something like this: public class StackBasedQueue { private final Stack store; public StackBasedQueue() { this.store = new Stack(); } public void addToTail(final Integer v) { this.store.push(v); } public Integer popHead() { final Stack temp = new Stack(); while(!this.store.isEmpty()) { final Integer v = this.store.pop(); temp.push(v); } final Integer head = temp.pop(); while(!temp.isEmpty()) { final Integer v = temp.pop(); this.store.push(v); } return head; } public int size() { return this.store.size(); } } 1. b) Something like this: O(n) runtime. public void findRepeats(final String str) { this.map.clear(); final char[] array = str.toCharArray(); for(int i = 0; i < array.length; i++) { final Character c = array[i]; Integer count = this.map.get(c); if(count == null) { this.map.put(c, 1); continue; } count++; this.map.put(c, count); } } For a) further challenge was to simulate a double ended queue , but we ran out of time . you could maintain temp stack as permanent variable and get around doing that. b) Kind of sort of what I wrote I was asked to optimize even further , so I said XOR the array make a note of elements left , remove from original list and you have set of repeated elements . Show More Responses 2a. My idea is to first identify the column that might contain our element, then use binary search to see if our element is in that column. The column that might contain our element is the rightmost column where the first row's element is less than or equal to our target element. int[] matrixSearch(int[][] m, int numRows, int numCols, int target){ int[] firstRow = m[0][]; // not sure this works, can just use for loop to populate int targetCol = findWhichCol(firstRow, 0, numCols-1, target); int targetRow = findWhichRow(m[][targetCol], 0, numRows-1, target); if (targetRow == -1) { return null; // Element not found } return new int[] { targetRow, targetCol}; } int findWhichColumn(int[] a, int low, int hi, int target) { int midIndex = (hi+low)/2; int mid = a[midIndex]; if (mid > target) { return findColumn(a,low,midIndex-1,target); } while (mid <= target && midIndex < a.length-1) { midIndex++; mid = a[midIndex]; } return midIndex--; } int findWhichRow(int[] a, int low, int hi, int target){ int midIndex = (low+hi)/2; if (midIndex == target) { return midIndex; } if (hi-low == 0) return -1; // Element is not in the matrix if (midIndex < target) { return findWhichRow(a,midIndex+1,hi,target); } return findWhichRow(a,low,midIndex-1,target); } Average: O(log n) Worst: O(n/2) = ~ O(n) This isn't very elegant. How would you do it? @above: I think the run time is log(n)*log(m) Sorry, Log m + log n for 2a you had to describe the properties of the matrix , the diagonal elements have some unique properties which you can recognize . So a good start is initialize the search from of the corners of the non leading diagonal . and yes iterative or divide and conquer from thereon after. @Anonymous That's correct, but this part: while (mid <= target && midIndex < a.length-1) { midIndex++; mid = a[midIndex]; } makes it O(n) in the worst case. Right? @Interviewee Thank you for the additional explanation. You seem quite qualified. Is there a particular reason you think you weren't given a offer? Did any one interview go poorly? It's a little worrying to look through these interview reports and see so many apparently intelligent people not receive offers. I recently passed my phone interview and am waiting to schedule my on-site. As much as I agree with hiring only the best, I'm finding it difficult to feel optimistic in light of the evidence on this site. Thank you for sharing your experience. Why I didn't get it ? don't know I am still in school , I applied for an internship and they said I am qualified enough for full time since I work along with school . I think I answered everything well (they said so themselves ... ) but there is the economy , a bit of this http://valleywag.gawker.com/5392947/googles-broken-hiring-process and the fact that I am not a states resident and I guess they didn't see any quality in me which they couldn't find locally . Big school names also count for a bit more at a place like Google . Do your best , and be calm and composed , being nervous won't help. For the program 2a you want to manipulate both indices at the same time to get a (logN) running time. Why I didn't get it ? don't know I am still in school , I applied for an internship and they said I am qualified enough for full time since I work along with school . I think I answered everything well (they said so themselves ... ) but there is the economy , a bit of this http://valleywag.gawker.com/5392947/googles-broken-hiring-process and the fact that I am not a states resident and I guess they didn't see any quality in me which they couldn't find locally . Big school names also count for a bit more at a place like Google . Do your best , and be calm and composed , being nervous won't help. For the program 2a you want to manipulate both indices at the same time to get a (logN) running time. @Interviewee: Did they ask you any work culture questions? Why google, etc? I think they see a culture fit too. Did they ask you any work culture questions? Why google, etc? I think they see a culture fit too. I guess they evaluate that over questions in lunch . Answer to 1b in C++11: list findDupes(string s) { list ret; map m; for(char c : s) { m[c]++; if(m[c] == 2) { ret.push_back(c); } } return ret; } |

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

Given an array of numbers, replace each number with the product of all the numbers in the array except the number itself *without* using division. 26 AnswersCreate a tree, where the leaf nodes are the initial values in the array. Given array A[1..n] create array B[1..n]= {1} // all elements =1 ; for (i=1; ij) B[i] *=A[j]; } } A=B; To husb: Your answer will work, but it's O(n^2) solution. Can you do better? Show More Responses Am I missing something? It can't be this easy: given array[0..n] int total = 0; for(int i=0; i<=n; i++) { total += array[i]; } for(int i=0; i<=n; i++) { array[i] = total-array[i]; } Ah yes.. I was. The question is PRODUCT, not sum. That will teach me to read the question too fast ;) Create a tree, where the leaf nodes are the initial values in the array. Build the binary tree upwards with parent nodes the value of the PRODUCT of its child nodes. After the tree is built, each leaf node's value is replaced by the product of all the value of the "OTHER" child node on its path to root. The pseudo code is like this given int array[1...n] int level_size = n/2; while(level_size != 1){//build the tree int new_array[1...level_size]; for ( int i=0; i left = array[i*2]; (and also from child to parent) new_array[i] -> right = array[i*2+1] new_array[i] = new_array[i] -> right* new_array[i] -> left; (take the product) } array= new_array; level_size /=2; } for(int i=0; iparent; if( parent->left == node){//find the other node under the parent brother = parent->right; } else{ brother = parent->left; } p *= brother; node = parent; } return p; } btw, it's O(n*logn) It seems to me that for any number array[i], you're looking for PRODUCT(all array[j] where j i]) we can simply precompute these "running products" first from left-to-right, then right-to-left, storing the results in arrays. So, leftProduct[0] = array[0]; for j=1; j = 0; j-- rightProduct[j] = rightProduct[j+1]*array[j]; then to get our answer we just overwrite the original array with the desired product array[0] = rightProduct[1]; array[n-1] = leftProduct[n-2]; for j=1; j < n-1; j++ array[j] = leftProduct[j-1] * rightProduct[j+1] and clearly this solution is O(n) since we just traversed the data 3 times and did a constant amount of work for each cell. betterStill, I think you have the answer the interviewer wanted.. But... if the array is google sized, don't we have to worry about overflows? it looks to me can be done in order n time given the following relation: product[n] = product[n-1]*array[n-1]/array[n] for example we have array 2 3 4 5 6 product[0]=3*4*5*6 product[1]=2*4*5*6 array[0] = 2; array[1]=3 product[1]=product[0]*array[0]/array[1] Here are my 2 cents to do this in memory without creating temporary arrays. The simple solution , if division was allowed, was multiple all the elements of the array i.e. tolal = A[0]*A[1]]*....*A[n-1] now take a loop of array and update element i with A[i] = toal/A[i] Since division is not allowed we have to simulate it. If we say X*Y = Z, it means if X is added Y times it is equal to Z e.g. 2*3 = 6, which also means 2+2+2 = 6. This can be used in reverse to find how mach times X is added to get Z. Here is my C solution, which take pointer to array head A[0] and size of array as input void ArrayMult(int *A, int size) { int total= 1; for(int i=0; i< size; ++i) total *= A[i]; for(int i=0; i< size; ++i) { int temp = total; int cnt = 0; while(temp) { temp -=A[i]; cnt++; } A[i] = cnt; } } Speed in O(n) and space is O(1) narya trick is good but really useful as it might take more iterations depending on values... eg. 2,3,1000000000000000 so if you have 3 numbers and if you are trying for the first one it will go for 500000000000000 iterations, hence as the overall product value wrt to the value matters a lot... try something else.... narya, your solution is not O(n). You have to also account for how many times you will run through the inner loop - which will be a lot. You can do it in O(n) time and O(n) space. In one pass, populate B[i] with the product of every number before i. In the second pass, multiply this with the product of every number after i. Can't think of a way to do it without the second array. void ArrayMult(int *A, int size) { runningProduct = 1; int *B = new int[size]; for(int i = 0; i = 0; --i) { B[i] *= runningProduct; runningProduct *= A[i]; } for(int i = 0; i < size; ++i) { A[i] = B[i]; } } Show More Responses <strong>Brutefoce Method : </strong> The brute-force method suggests that if we take each element, multiply all elements and store the product in the array B[i], then it would take O(n^2) time. <strong>Other Solution : </strong> The other solution to this problem can be we multiply all the elements of the array "A" and store the product in a variable (say product.), and then divide the product by each element, then we will get the desired array. The C code of the solution can be : #include int main() { int n,i=0; scanf("%d",&n); int arr[n]; int brr[n]; int product = 1; for(i=0;i This solution will take O(n) time. The space complexity of this solution will be O(1). If we have particularly given that "We can't use the *DIVISION* operator, then the solution to this problem will be as follows." polygenelubricants method : Let we have 2 arrays, "A" and "B". Let the length of "A" is 4. i.e. {A[0],A[1],A[2],A[3]} Then we will make two arrays (say temp1 and temp2). One array will be storing the product the array before a particular element and temp2 will store the product of elements after a particular element. temp1 = { 1 , A[0] , A[0]*A[1] , A[0]*A[1]*A[2]} temp2 = {A[1]*A[2]*A[3] , A[2]*A[3] , A[3] , 1} And then we will correspondingly multiply temp1 and temp2 and store in B. B = {A[1]*A[2]*A[3] , A[0*A[2]*A[3] , A[0]*A[1]*A[3] , A[0]*A[1]*A[2]} The C code to this solution will be : #include int main() { int n,i=0; scanf("%d",&n); int A[n],B[n]; int temp1[n], temp2[n]; for(i=0;i=0;i--) { temp2[i] = product; product *= A[i]; } for(i=0;i The time complexity to this solution will be O(n) and the space complexity to this problem will also be O(n). var nums = new[] {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; var newnums = new int[nums.Length]; for (var i = 0; i index != i).Aggregate((a, b) => a*b); } We can fill two arrays: headProduct and tailProduct. Each headProduct[i] == product of A[0..i-1], tailProduct[i] ==[i+1..A.lenght-1]. They can be built in O(n) and the result could be gathered in O(n). Memory demand is O(n) Not commentary nt a[N] = {1, 2, 3, 4}; int products_below[N]; int products_above[N]; int p=1; int p1=1; for (int i=0;i def solve(arr,n): product_arr=[1]*n product=1 for i in xrange(n): product_arr[i]*=product product*=arr[i] product=1 for i in xrange(n-1,-1,-1): product_arr[i]*=product product*=arr[i] return product_arr {{{ If A = {a0, a1, a2, ... an} Construct two arrays called left_p left product and right_p right product: left_p = {1, a0, a0 * a1, a0 * a1 * a2, .... , a0 * a1 * a2 ... * an-1} right_p = {a1*a2*...*an, ....... an-2 * an-1 * an , an-1 * an, an , 1} prod_p[i] = left_p[i] * right_p[i]; }}} O(N) Solution!!! static void Calculate(int[] iArr) { int total = 1; for (int i = 0; i < iArr.Length; i++) { total *= iArr[i]; } for (int i = 0; i < iArr.Length; i++) { iArr[i] = (int)(total * (1 / (double)iArr[i])); } } The answer I post above this uses division. Oops. Here is an answer without division static void Calculate(int[] iArr) { int total = 1; for (int i = 0; i 0) { temp -= iArr[i]; newVal++; } iArr[i] = newVal; } } Sorry, that last one didn't paste properly static void Calculate(int[] iArr) { int total = 1; for (int i = 0; i 0) { temp -= iArr[i]; newVal++; } iArr[i] = newVal; } } Show More Responses p = 1 g = 1 for x in nums: g = g* x + p p = p + x return g Way easy with a simple negative exponent var arr = [2,3,4,5] var prod = arr.reduce((a,b,arr)=>a*b) arr.map((x)=>Math.pow(x,-1)*prod) console.log(arr) //[60,40,30,24] I don't know if this is correct. But i think it is. I have done it with python def multiply(numbers,n): total = 1 for x in numbers: if x != n: total *= x return total a = [10, 3, 5, 6, 2] n = 4 prod = [] for i in a: re = multiply(a,i) prod.append(re) |

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

You are trying to rob houses on a street. Each house has some +ve amount of cash. Your goal is to rob houses such that you maximize the total robbed amount. The constraint is once you rob a house you cannot rob a house adjascent to that house. 14 AnswersNot that difficult to answer. You need to keep track of houses that are marked robbed. You can do some sort of recursion and at everys step evaluate sequence of 3 houses. At each step either you can add the middle house or the two adjascent houses to rob list (provided they are OK to rob.) The cumulative return would be the value of the immediate houses and the value returned by the function when called recursively on the remainder of the houses with the current houses marked robbed. I probably should just paste code here. Explaining it in word is twisted. My complain is I was given all of 2 minutes to think about the question and all of 5-7 minutes to write code for it. I was asked this in 38th minute of a 45 minute interview. this is actually a typical dynamic programming question: int getMaxValue(int[] values) { if (values.length < 3) return max(values[0], values[values.length - 1]); int[] best = new int[values.length]; best[0] = values[0]; best[1] = values[1]; best[2] = values[0] + values[2]; for (int i = 3; i < values.length; i++) { best[i] = max(best[i - 3], best[i - 2]) + values[i]; } return max(best[best.length - 2], best[best.length - 1]); } It is a dp problem and it is typical, but your solution is incorrect. Show More Responses public static int maxRob(int[] amount){ return maxAmount(amount, amount.length-1); } public static int maxAmount(int[] amount, int house){ if(house<=1){ return amount[house]; } return Math.max(amount[house]+ maxAmount(amount, house-2), maxAmount(amount, house-1)); } Here is the working solution!! static public int maxRob(int[] housePoints){ int length = housePoints.length; switch(length){ case 0: return 0; case 1: return housePoints[0]; case 2: return Math.max(housePoints[0],housePoints[1]); } Hashtable> prev, best = new Hashtable>(3); ArrayList scores = new ArrayList(1); scores.add(housePoints[0]); best.put(0,scores); scores = new ArrayList(1); scores.add(housePoints[1]); best.put(1,scores); scores = new ArrayList(1); scores.add(housePoints[0]+housePoints[2]); best.put(2,scores); for(int i=3;i>(3); best.put(i-1,prev.get(i-1)); best.put(i-2,prev.get(i-2)); int tmp = housePoints[i]; scores = new ArrayList(); for(int sc : prev.get(i-3)) scores.add(sc+tmp); for(int sc : prev.get(i-2)) scores.add(sc+tmp); best.put(i,scores); prev = null; } int max = 0; for(int sc : best.get(length-2)) if(sc>max) max = sc; for(int sc : best.get(length-1)) if(sc>max) max = sc; return max; } public int maxRob(int[] W) { int sz = W.length; int[] V = new V[sz]; if(sz == 0) { return 0; } else if(sz == 1) { return W[0]; } else if(sz == 2) { return max(W[0], W[1]); } V[0] = W[0]; V[1] = max(V[0], W[1]); for(int i = 2; i < sz; i++) { V[i] = max(W[i] + V[i-2], V[i-1]); } return V[sz]; } 1. We need an int array same size as house values array to keep track of dp local results. 2. We need the local results to construct path, i.e., which houses we want to rob. Here's Java code with unittest /* * MaxRob(n) = Max(MaxRob(n-2)+value(n), MaxRob(n-1)) */ public class RobHouse { public static void MaxRob(int[] values) { if (values.length==0) { return; } if (values.length==1) { System.out.println("only 1 house to rob. Value: " + values[0]); return; } if (values.length==2) { System.out.println("only 1 house to rob. Value: " + Math.max(values[0],values[1])); return; } int[] maxValues = new int[values.length]; maxValues[0] = values[0]; for (int i=1; i0; i--) { if (maxValues[i]!=maxValues[i-1]){ System.out.println("Rob house " + i + " value: " + values[i]); } } if (maxValues[0]==maxValues[1]){ System.out.println("Rob house 0 value: " + values[0]); } System.out.println("Rob done."); } public static void main(String[] args) { MaxRob(new int[] {5,2,4,1});//1010 MaxRob(new int[] {5,2,9,1});//1010 MaxRob(new int[] {1,2,1,1});//0101 } } If I were interviewer, I would give no hire for everyone above - Only Hee solution above is correct (but waaay overcomplicated). When writing code consider: 1,3,1,3,100 Found solution online, your interviewer must be from CMU: http://www.cs.cmu.edu/afs/cs/academic/class/15451-f10/www/solutions/hw3soln.pdf solve(0,0) //previous indicate whether previous house was looted or not solve(int house, bool previous) { if(house == N) return 0; int &res = dp[house][previous]; if(res != -1) return res; int res = solve(house+1, 0); if(!previous) res = max(res, cash[house]+ solve(house+1, 1)); return res; } A set of data: input: 4 4 3 5 9 output: 13 input: 10 4 3 5 9 2 6 8 1 10 7 output: 31 input: 100 46 62 74 1 88 77 69 92 67 16 83 79 25 22 56 34 14 91 58 64 65 66 89 75 5 17 51 78 8 47 52 41 81 96 95 28 33 35 4 85 70 9 63 7 27 36 71 48 43 94 80 60 26 13 50 90 10 20 39 55 15 49 23 82 29 57 73 68 59 31 18 97 40 93 100 54 38 44 2 84 37 45 99 98 21 86 24 53 3 61 42 6 19 12 30 72 87 76 11 32 output: 2895 public class Solution { public int findMax(int[] houses) { if (houses == null || houses.length == 0) { return 0; } else if (houses.length == 1) { return houses[0]; } else if (houses.length == 2) { return Math.max(houses[0], houses[1]); } int[] res = new int[houses.length]; res[0] = houses[0]; res[1] = Math.max(houses[0], houses[1]); int max = res[1]; for (int i = 2; i max) { max = res[i]; } } return max; } } public static int rob (int[] amounts) { if (amounts == null) return 0; int[] max = new int[amounts.length]; max[0] = amounts[0]; max[1] = Math.max(amounts[0], amounts[1]); for (int i = 2; i < amounts.length; i++) { max[i] = Math.max(max[i-2] + amounts[i], max[i-1]); } return max[max.length - 1]; } Show More Responses public class MaxRob { public static void main(String[] args) { int[] houseValues = new int[]{1, 3, 1, 3, 100}; int[] selfPlusMax = new int[houseValues.length]; int[] selfMinusMax = new int[houseValues.length]; selfPlusMax[0] = houseValues[0]; selfMinusMax[0] = 0; for (int i = 1; i < houseValues.length; i++) { selfPlusMax[i] = selfMinusMax[i - 1] + houseValues[i]; selfMinusMax[i] = Math.max(selfPlusMax[i - 1], selfMinusMax[i - 1]); } System.out.println( "Max Rob : " + Math.max(selfPlusMax[houseValues.length - 1], selfMinusMax[houseValues.length - 1])); } } |

### Software Engineer at Apple was asked...

Find number of ones in an integer. 13 Answers1. Convert the number into bits (we assume that all our bits of size 8) 2. "And" it with 1 3. check if the bit returned is 1 or now. if it is '1' increase some counter. 4. right shift 8 times and perform go to 2 or you can do the following using properties of number. every number when AND'ed with number - 1 it would eliminate one binary number.\ count = 0; while(n) { n &= (n-1); count++; } This doesn't work: 1. Convert the number into bits (we assume that all our bits of size 8) 2. "And" it with 1 3. check if the bit returned is 1 or now. if it is '1' increase some counter. 4. right shift 8 times and perform go to 2 look at the number 11: counter=0; 0x000B, look at the last byte B: 1011 and that with 1, you get 1 counter now equals 1, right shift 8 times and get 0x0000 and with 1, get 0, doesn't increment counter. so the number of 1's in 11 is 1. Show More Responses This doesn't work either: or you can do the following using properties of number. every number when AND'ed with number - 1 it would eliminate one binary number.\ count = 0; while(n) { n &= (n-1); count++; } Look at n=7, which we know has no 1's in it. 7 in binary: 0111 6 in binary: 0110 n=7&6; so n=6; counter=1; loop again: 5 in binary=0101; n=6&5=0110&0101=0100=4; counter=2; We can already see this is wrong answer should be 0; Solutions provided above are used for finding out the number of ones in a binary string. If you Google for such question, both proposed answers would show up. For finding out the number of ones in an integer, I would propose the following. int NumberOfOnes(double number) { int counter = 0; if (number == 0) return 0; if (number == 1) return 1; do { if (number % 10 == 1) counter++; number = number / 10; } while (number); return counter; } Binary ones in python: def findBinOnes(integer): val = integer ones = 0 while val > 0: if val & 1 == 1: ones +=1 val = val >> 1 return ones Decimal ones in python: def findDecOnes(integer): val = integer ones = 0 while val > 0: if val % 10 == 1: ones += 1 val = val / 10 return ones just an idea #!/usr/bin/env ruby 123456718791.to_s.scan(/1/).size int numOfOnes( int n ){ int num = 0; String str = Integer.toString ( n ); for(int i = 0 ; i < str.length() ; i++ ) { if ( str.charAt ( i ) == '1' ) num++; } return num; } In Perl: sub OnesInNum{ my $number = shift; my $count; my @numbers = split //, $number; foreach my $num (@numbers){ next if($num eq '.'); #skip decimal point $count++ if($num == 1); } return $count; } #include #include using namespace std; int CountBits(const int& number){ int test = 1; int count = 0; for (int i = 0; i < (sizeof(number)*8) ; i++){ int filter = number & test; if(filter) count++; test <<= 1; } return count; } int _tmain(int argc, _TCHAR* argv[]){ cout << CountBits(566632145) << endl; return 0; } Convert to binary and iterate. Check last big (increment counter if 1) then bit shift right to drop last bit. repeat. int main(void) { int input, counter = 0; printf("Enter integer: "); scanf("%d", &input); while(input) { if ((input & 0x0001) == 1) {counter++;} input = input >> 1; } printf("No. of 1s are: %d", counter); } Perl read fm stidn: chomp ( my $int = ); my $ones = $int =~ tr/1/1/; say $ones; |

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

Implement a function string balanceParanthesis(string s); which given a string s consisting of some parenthesis returns a string s1 in which parenthesis are balanced and differences between s and s1 are minimum. Eg - "(ab(xy)u)2)" -> "(ab(xy)u)2" ")))(((" -> "" 13 AnswersUse O(n) time and O(1) space. def balanceParanthesis(str) : (bef, aft, left, right) = (0, 0, 0, 0) for i in str : if i == '(' : if right > 0 : bef += right right = 0 left += 1 elif i == ')' : if left > 0 : left -= 1 else : right += 1 if right > 0 : bef += right if left > 0 : aft = left return '(' * bef + str + ')' * aft All we need to do is to delete unnecessary parenthesis. every time we encounter a ')' which has no previous '(' to match with, delete. delete every '(' left when we finished reading the string s. Show More Responses string justify(string str) { string s1 = ""; int l = 0, i; for(i = 0; i 0) { l --; s1 += ')'; } else if(str[i] == '(') { s1 += '('; l++; } } for(i = 0; i < l; i++) s1 += ')'; return s1; } @xemoaya try print balanceParanthesis(")))((("): you solution is wrong!! --> ((()))((())) @hussein try cout ((())) well according to the given examples, this code would do good void balance(char *u) { int n=strlen(u); int i=n-1; //modified string length for(;i>=0;--i) { if(u[i]=='(') --n; else break; } //remove extra right braces int l=0; for(int i=0;i one small change needed for(;l>0;--l,pos++) { output[pos]=')'; } output[pos]='\0'; need to add extra ) at end how about simple balancing with an open count? close any that are unclosed. but before that run a round to delete leading ')' and trailing '(' which are be deemed unnecessary. well in the above code for(;i>=0;--i) { if(u[i]=='(') --n; else break; } part removes trailing '(' then ofcourse we are removing and extra ')' [ones not balanced by a '('] finally if there were more {remember that by our approach we can never have more ')'} '(' then we need to balance them with ')' that is what this part of the code does for(;l>0;--l,pos++) { output[pos]=')'; } output[pos]='\0'; this part compacts the string, so we can do convert it inplace, if a standard technique to delete certain parts of a string is to fill those parts with '\0' and then compact the string that is what this does int pos=0; for(int i=0;i Actually I think there is some mistake in the question itself. If the solution persue minimum difference, ")))(((" should lead to "((()))" since the difference between the input and output is 0. However, in the question ")))((("'s output is "", then the difference is 6. No I think the correct form of ")))(((" is not "((()))" since you are not allowed to change the ordering of elements. You change the ordering of original parenthesis. Even though you can change the ordering the difference between ((())) and )))((( is still 6. import java.util.*; class BalanceParanthesis { static String getBalancedHelper(String input) { int count=0; for(int i=0;i0) //'(' is extra { while(input.charAt(0)=='('&& count!=0) { input=input.substring(1,input.length()); count--; if(input.length()==0) break; } while(count!=0) { input+=")"; count--; } } else if(count0) if(input.charAt(0)=='('&&input.charAt(input.length()-1)==')') input=input.substring(1,input.length()-1); return input; } static String getBalanced(String input) { Stack chars=new Stack(); Stack index=new Stack(); for(int i=0;i0) { System.out.println("in partition"); return getBalancedHelper(input.substring(0,ind+1))+getBalancedHelper(input.substring(ind+1,input.length())); } } return getBalancedHelper(input); } public static void main(String[] st) { String input=")))((("; System.out.print(input+" result: "+getBalanced(input)); } } def removeExtra(s,op,cl): count = 0 out = '' for c in s: if c == op: count += 1 out += c elif c == cl: if count > 0: count -= 1 out += c else: out += c return out def parenBalance(s): return removeExtra(removeExtra(s,'(',')')[::-1], ')', '(')[::-1] |

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

Given an array of integers, now we want to erase all 0's (can be other value), and we want the result array condensed, meaning no empty cell in the array. 16 Answers#include #include void main() { clrscr(); int i,j,k.a[20]; cout>n; cout>a[i]; } cout<<"entered array is"; for(i=0;i Assuming that the array is named iArray and the unwanted number is named delthis. I think this should work: public condense(int[] iArray, int delthis){ ArrayList iList = new ArrayList(); for (int i=0; i Test on Java 6: public Integer[] condense(int[] iArray, Integer delThis){ ArrayList iList = new ArrayList(); for (int i=0; i Show More Responses void erase( int arr[] , int size , int &new_size ) { int p1 = 0, p2 = 0; while ( p1 < size && p2 < size ) { if ( arr[p1] == 0 ) { while ( p2 < size && arr[p2] == 0 ) { ++ p2; } if ( p2 == size ) { break; } arr[p1] = arr[p2]; ++ p1; ++ p2; } else { ++ p1; ++ p2; } } new_size = p1+1; } test on gcc void erase( int arr[] , int size , int &new_size ) { int p1 = 0, p2 = 0; while ( p1 < size && p2 < size ) { if ( arr[p1] == 0 ) { while ( p2 < size && arr[p2] == 0 ) { ++ p2; } if ( p2 == size ) { break; } arr[p1] = arr[p2]; arr[p2] = 0; ++ p1; ++ p2; } else { ++ p1; ++ p2; } } new_size = p1; } // This is erase/remove idiom one liner. Too much code with C. std::vector v; v.erase(std::remove(v.begin(), v.end(), 0), v.end()); #include using namespace std; int main() { int a[] = { 0,2,3,0,4,0,5,0,0,0}; int i,nz = 0; for(i = 0; i<=9 ; i++) { if (a[i] == 0) nz++; else a[i-nz] = a[i]; } for(i = 0; i <=9-nz ; i++) cout << a[i]<<" "; return 0; } Python: ------------- s = [1, 2, 4, 0, 5, 0, 1, 0, 0, 1, 7, 0, 8, 0, 2, 4, 5, 1, 2, 8, 0, 5, 6, 8] for k in xrange(len(s), 0, -1): if not s[k-1]: s.pop(k-1) -------------- after: [1, 2, 4, 5, 1, 1, 7, 8, 2, 4, 5, 1, 2, 8, 5, 6, 8] void erase(int arr[], int sz, int errasedVal) { int i = 0, j = -1; while(i < sz && j < sz) { if(arr[i] == errasedVal && j == -1) j = i; else if(arr[i] != errasedVal && j != -1) { cout << arr[i]<< " " << j << endl; swap(arr[i], arr[j]); j++; while(arr[j] != errasedVal && j < sz) j++; } i++; } } void RemoveZeros(vector& input) { int p1 = 0, p2 = 0; int len = input.size(); while (p1 < len && p2 < len) { while(input[p1] == 0) { ++p1; } input[p2++] = input[p1++]; } input.resize(p2); for (int i = 0; i < p2; ++i) { cout << input[i] << endl; } } @Bikash is my favorite answer because it uses constant space, unlike some of the above answers. Completely trivial in C#. The only thing to note about the solution is that it does not do the replacement "in place" and returns a new array. But that was not specified as a constraint in the question. int[] RemoveZeros(IEnumerable input) { return input.Where(x => x != 0).ToArray(); } Objective-C NSArray *input = @[@2, @3, @1, @2, @0, @2, @0, @1, @3, @1, @2, @0]; input = [input objectsAtIndexes:[input indexesOfObjectsPassingTest:^BOOL(id obj, NSUInteger idx, BOOL *stop) { return ![obj isEqualToNumber:@0]; }]]; ----------------------- output:(2, 3, 1, 2, 2, 1, 3, 1, 2) Show More Responses def eraseDigit(aList, aDigit): theResult = [int(''.join([x for x in str(X) if x != str(aDigit)])) for X in aList] return theResult theList = [432, 4409, 85, 6887, 87, 1386] theDigit = 8 print eraseDigit(theList, theDigit) import java.util.Arrays; public class facebook1 { public static void main(String[] args) { int [] givenArray = new int[] {3,4,45,5,0,3,0,32,4,5,40,23,0,43,0,0,43,2,4}; int rightPointer = givenArray.length -1; for(int leftPointer = 0; leftPointer 0; i--){ if(givenArray[i] == 0){ int [] tempArray = new int[givenArray.length-1]; System.arraycopy(givenArray, 0, tempArray, 0, givenArray.length-1); givenArray = tempArray; } } System.out.println(Arrays.toString(givenArray)); } } Here is a short python solution: a = [1, 2, 4, 0, 5, 0, 1, 0, 0, 1, 7, 0, 8, 0, 2, 4, 5, 1, 2, 8, 0, 5, 6, 8] a = [x for x in a if x != 0] |

**11**–

**20**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