Software Engineering Interview Questions in San Jose, CA | Glassdoor

# Software Engineering Interview Questions in San Jose, CA

6,130

Software engineering interview questions shared by candidates

## Top Interview Questions

Sort: RelevancePopular Date

Aug 8, 2011
 Implement a function rotateArray(vector 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 vecprivate 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 Responsespublic 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 spacehttp://ideone.com/Gv6Lo A very nice O(n) solution with O(n) spaceUsing 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;ithe 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 sO(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; jO(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 Responseshttp://baibingz.wordpress.com/2012/10/26/rotate-array/ O(n) Time O(1) SpaceIn-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/i2QMBwPerl version which works - http://ideone.com/UKxbqA

Apr 1, 2011

Nov 26, 2011

Nov 7, 2010
 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 functionShow More Responseslamont, 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 ResponsesThe answer to this problem is the submaxarray algorithm. Find it here: http://en.wikipedia.org/wiki/Maximum_subarray_problemKadanes algorithm

Nov 20, 2009

Jul 13, 2009

Oct 19, 2010
 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 Responsespublic 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,100Found solution online, your interviewer must be from CMU: http://www.cs.cmu.edu/afs/cs/academic/class/15451-f10/www/solutions/hw3soln.pdfsolve(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: 2895public 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 Responsespublic 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...

Oct 15, 2011
 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 2or 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 ResponsesThis 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 onesjust an idea #!/usr/bin/env ruby 123456718791.to_s.scan(/1/).sizeint 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;