# Engineering Interview Questions in San Jose, CA

Engineering interview questions shared by candidates

## Top Interview Questions

How would you design a recommendation system (like amazon)? 2 AnswersUse collaborate filtering to compare personal preference with others. If A and B are similar, we can recommend preferred items in B to A. Why downvote on other answer? He/she is right. Collaborative filtering is the most common strategy for recommendation systems. You see user A buys these things and user B also bought those things but user B bought this other thing too so let's show that thing to User A. |

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

### Software Engineer Intern at eBay was asked...

Questions related to data structures like "What data structure would you use for a browser's BACK & FORWARD ability" 6 AnswersMay be Stack , any one please correct me if I am wrong. This can be implemented by using two different stacks, one for back and one for forward. Command Pattern Show More Responses I would use doubly link list Doubly linkedList Use two stacks. Every time you visit a site, push its address in stack1. When you press back, pop from stack1 and also push in stack2. When user presses forward, pop from stack2 and also push in stack1. |

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

Given a matrix print it clockwise from the first element to the very inner element. 6 AnswersNeed to design the program first and then implement it very carefully yet fast! void PrintMatrix(int** a, int n) { for (int i = 0; i = i; j--) { printf("%d ", a[n - i -1][j]); } } void PrintColInc(int** a, int n, int i) { for (int j = i; j = i; j--) { printf("%d ", a[j][i]); } } struct point { point(int a, int b) { row = a; col = b; } int row; int col; }; void printMatrixSpiral(int a[][5], int r, int c) { int direction = 1; // 1 - right // 2 - down // 3 - left // 4 - up point upper_left = point(0,0); //point upper_right = point(0,c-1); point lower_right = point(r-1, c-1); //point lower_bottom = point(r-1, 0); while(true){ if(direction==1){ int row = upper_left.row; for(int i=upper_left.col; i= upper_left.col;--i){ cout= upper_left.row;--i){ cout lower_right.row) || (upper_left.col > lower_right.col)){break;} } } Show More Responses int matrix[][3] = { {1, 2, 3}, { 4, 5, 6}, {7, 8, 9} }; void PrintMatrix() { int start = 0; int end = 2; while(end >= start) { for(int col = start; col = start; col--) cout start; row--) cout << matrix[row][start] << " "; start++; end--; } } int main() { int m, n; cin >> m >> n; int matrix[m][n]; for (int i = 0; i > matrix[i][j]; int l = 0, r = n, t = 0, b = m; while (l = l; i--) cout = t; i--) cout << matrix[i][l] << ' '; l++; } return 0; } ^ Above anon, your solution is almost correct. But for the 3rd and 4th for loops you first need to check whether you've already printed the corresponding previous for loop. Ok I didn't explain that too clearly. Here's an example: Matrix: {{1,2,3,4},{5,6,7,8},{9,10,11,12}} will print 1 2 3 4 8 12 11 10 9 5 6 7 6 That last 6 is because of the 3rd for-loop. You don't need to run that opposite for-loop (R-L) once you've already printed 6 from L-R. Just use an if-loop to rectify this. Same for the 4th loop. |

### Software Engineer Intern at PayPal was asked...

n= 20 for (i=0;i<n; i--) print i the question was to change or replace a only one character in for loop to print 20 times. 5 Answersit has to do with decrement or condition clause in for loop n= 20 for (i=0;-i n= 20 for (i=0;i Show More Responses add 4 in front of the 0 (in i=0); so it becomes i=40; i < n (which is 20); i-- changing i-- to n-- is a correct answer. adding 4 in front of i=0 would work, but does not satisfy the condition "change or replace a character" as it adds a character instead. |

Create a 8 input AND gate using 3 4:1 muxes 7 AnswersWithout an enable bit on at least one of the mux's the maximum inputs would be 7. Not so. You only need 2 4:1 muxes. Have the output of the first be the select to the second. 8 input and gate. tie 3 0's to the three inputs of initial 2 4x1 mux, the 3rd input be an actual input, 2 sel be 2 inputs. feed the output of the results of the two muxes as sel to the 3rd mux and tie the last inputs to actual inputs and top two inputs to 0's. Show More Responses I can only make it 7 bits with that explenation. I don't see it being possible with three standard 4-1 muxes... Using 4, this question is straight forward... The two selects of each mux are your 8 inputs... tie out put of each mux to the (11) case input to the mux. We need 3 4:1 MUX and a And gate. Are we allowed to use 'and' gate? A to H are the 8 inputs. For the first 2 muxes we can have GH as select bits with all their inputs tied to 0. Connect output of these muxes to the first 2 input lines of third mux. Tie the third input to 0. Now we care only about the 4th input line when EH are both 1s. We can derive an expression and connect it to the 4th input line of third mux. job done. |

### Test Engineer at Qualcomm was asked...

Talk about how to verify if an RF amplifier is operating in its linear mode? 4 AnswersObserve the IM3. Back off input by 1dB and see how much IM3 changes. hi, did you applied for system test engineer? If yes, can I ask some detailed question? Thank you! Yes. Show More Responses hi, can you send me your email address? Mine is dayuallen@gmail.com, thank you. |

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

Write a probability formula to tell how many bits will be changed when 1 is added to a 32 bit binary number. 11 AnswersThe probability of N bits being changed is (1/2)^N. The reason: the number of bits that will change depends on the position of the first zero that appears in the number. If the first zero is at the LSB, only one bit changes; if it is in the third position, the three bits upto the first zero change. Now, it boils down to the probability of finding the first zero. Assuming that the zeros and ones appear with equal probability in a given number, the probability of finding the first 0 in the Nth position is (1/2)^N. For more, look up the Geometric Random Variable. I think that you need to take into account that if you want to toggle 2 bits, you can only do if you flip bits from position 0..30. Toggling bit 31 is only going to toggle this bit no matter what. Therefore, you need to multiply (33-N)/32 to your proposed result, to keep this into account. @Mythreya's analysis is correct but incomplete. To get the expected value, you have to multiply the number of bits by their probability. Answer is Sigma{k/(2^k)} for k = 1 to 32. Show More Responses Using this approach, the answer is 2 bits will change on an average: https://answers.yahoo.com/question/index?qid=20110413165236AAU9tmO @Henry David Thoreau: The question is not asking for expected value, just the discrete density function. Also P(k=32) needs special handling. @Henry, no ... probability that at least 1 bit will change is (k/2^k); but, probability for all k bits to change, I guess, would still be 1/2^k. Right? And, k=0 to 31 !! k=1-32 p=k/2^(k-1) E(n) = 1 + E(n-1) / 2 where E(n) is the expected number of bit changes when 1 is added to an n-bit integer. E(1) = 1. E(2) = 1 + E(1) / 2 = 1.5. E(3) = 1 + E(2) / 2 = 1.75 We can verify it for n = 3. The possible values are as follows 000 -> 1 change 001 -> 2 change 010 -> 1 change 011-> 3 change 100-> 1 change 101-> 2 change 110-> 1 change 111-> 3 change Total changes: 14 Expected change = 14 / 8 = 1.75; answer is (2^1+2^2+2^3....2^32)/(32*(2^32)) If we just look at two bits - (b1,b2) f(b1) = { 1 b1=0; f(b2) if b1=1}, the probability of one bit changing is half. The probability of two bits changing is half * f(b2), which is half*half if b2=0 and half*half*f(b3) if b2=1. Therefore, for k=1-31 p(k) = 1/2^k and for p(k=32) = 1/2^k because when the 32nd bit flips there is nothing more to be done and the recursion stops |

### Software Engineer at PayPal was asked...

Consider the following function: int f (int num) { int out = 0; for (; num > 0; num /= 10) { int d = num % 10; out *= 10; out += d; } return out; } 1) What does it do? 2) Write the same algorithm using recursion 5 AnswersThere is a trick that need global variable or static variable to record the temper sum. so the function declaration cannot be same as loop version if don't use global or static variable. the output parameter b will be the reverse result. void rev(int d, int& b) { b *= 10; if (d/10 == 0) b += d; else { b += d%10; rev(d/10, b); } } You can do it without the golbal or static variables: int f(int num) { if((num/10) == 0) return num; else return ( 10(num%10) + f(num/10) ); } Sorry my answer previously posted was wrong. Here is the correct one without golbal or static variables, which is basically the same as the first one by Paul. inf f(int num, int car=0) { car *=10; if((num/10) == 0) return ( car + num ); else return f(num/10, car+(num%10) ); } Show More Responses private static int reverse(int n, int r) { if (n == 0) return r; return reverse(n/10, 10*r+n%10); } public static int reverse(int n) { return reverse(n, 0); } Simple method without using global variable. static int reverseRecursive(int number, int sum) { if (number != 0) { int temp = number % 10; sum = sum * 10 + temp; return reverseRecursive((number / 10), sum); } else return sum; } |

### Engineering at Google was asked...

Write a code to find out if two string words are anagrams 4 Answersdifferrent ways: 1. sort them and strcmp() 2. hash them ( function should be independent of characte sequence) and if they map to same value they are anagrams. 3. assign primary numbers to each letter of the word. get the product. do the same with target. if product matches then they are anagrams. not a big deal, but make sure to check the lengths for #3 (or for really any of the solutions). 1. sorting and strcmp is straightforward and no extra memory, but n log n. 2. not too bad for memory. O(n) 3. could get nasty with super long strings. O(n) #2 and #3 are basically the same thing. the first thing in any algorithm here is to check lengths. the next thing i would do it make an array of ints the length of the range of input. then, i would read the first one in, incrementing the corresponding integer for its position. then compare this list of character frequency with the second string for a match. if you do not know the range of the input, or it is otherwise prohibitive, you can do a has from each character object to the integer keeping record of its frequency. Show More Responses more clearly: boolean areAnagrams?( String s1, String s2) { int[] frequencies = new int[128]; //assuming ascii. make a hash table for unicode for( int i = 0; i < frequencies.length; i++) { frequencies[ i ] = 0; } for(int i = 0; i < s1.length(); i++) { frequencies[ (int)s1.charAt(i) ]++; }//now we have an int array corresponding to letter frequencies for(int i = 0; i < s2.length(); i++) { frequencies[ (int)s2.charAt(i) ]--; }//now, if they are anagrams, all will be zero for(int = 0; i < s1.length(); i++) { if( frequencies[ (int)s1.charAt(i) ] ) { return false; } } return true; } |

**1**–

**10**of

**3,129**Interview Questions

## See Interview Questions for Similar Jobs

- Software Engineer
- Machine Learning Engineer
- Machine Learning Scientist
- Intern
- Software Developer
- Data Scientist
- Software Engineer Intern
- Associate Systems Engineer
- Software Development Engineer
- QA Software Engineer
- Senior Software Engineer