# Technical Interview Questions

interview questions shared by candidates

## Technical Interview Questions

I was asked the basic process of O&P sample from start to finish. 1 AnswerProcess sample, build sample, mix samples, centrifuge sample for 5 mins on 1500 rpm, float sample for 10 mins, read sample then release. |

### Housekeeper at Wyndham Vacation was asked...

How many rooms at your old job did you clean. 1 AnswerAround 1 every half hour |

Why does one use MSE as a measure of quality. What is the scientific/mathematical reason for the same? 2 AnswersMean-Square error is an error metric for measuring image or video quality it is popular video and image quality metric because the analysis and mathematics is easier with this L2-Norm metric. Most video and image quality experts will agree that MSE is not a very good measure of perceptual video and image quality. The mathematical reasoning behind the MSE is as follows: For any real applications, noise in the readings or the labels is inevitable. We generally assume this noise follows Gaussian distribution and this holds perfectly well for most of the real applications. Considering 'e' follows gaussian distribution in y=f(x) + e and calculating the MLE, we get MSE which is also L2 distance. Note: Assuming some other noise distribution may lead to other MLE estimate which will not be MSE. |

### Maintenance Technician at Tesla was asked...

I was asked to describe what is a router, like the one used in the home for the internet. 1 AnswerSwitches create a network. Routers connect networks. A router links computers to the Internet, so users can share the connection. A router acts as a dispatcher, choosing the best path for information to travel so it's received quickly. |

### Sales Strat Intern at Goldman Sachs was asked...

Suppose we hire you, and you and the rest of the new interns decide to go buy a cup of coffee. Each intern purchases one cup of coffee. One of the interns suggests everyone play a game. Everyone will flip a fair coin, dividing the group of interns into two subgroups: those that got heads and those that got tails. The game is this: whichever group is smaller evenly splits the cost of everyone's cup of coffee (i.e. if there are 5 interns, 3 get H, 2 get T, then the two interns that got tails each buy 2.5 cups of coffee). However, nothing says you need to play this game. You can choose to buy your own cup of coffee and not play the game at all. The question: Should you play this game? (Note: You may assume that there is an odd number of interns, so there are no ties, and that if everyone gets H or everyone gets T, then everyone loses and just buys their own cup of coffee). 18 AnswersHint: Despite its look, this is not a math question. I dont get it, Would you please provide more hints? Assume each coffee costs $1, for simplicity. So this is effectively a choice between two outcomes: paying $1 with probability 100%, or paying $0 with some probability and paying more than $0 with some probability. So you ask yourself: what is your expected cost in the second case? Give that a try and see if you can figure it out. However, I want to remind you that the question is "should you play this game?" The answer to this question isn't just a math question. If you only work out expected values, you've missed the point. For example, a separate question (with the same kind of flavor as the direction I'm trying to lead you) is this: suppose I give you a choice of two outcomes. Either you get $1 with 100% probability or I give you $500,000,000 with probability 1/100,000,000 and 0 otherwise. Which would you pick? Now what if it was the same first choice, but the second choice was $50 with prob 1/10 and 0 otherwise? Now which would you pick? These are the kinds of things you want to think about while answering this kind of question. Let me know if you have anymore questions. And if you want me to post the answer, just let me know. Show More Responses I think I get it. It's about investor's risk appetite. Investors is likely to take guaranteed gains, here is $1. Well yes and no. This is indeed a risk aversion question. If you work it out, you'll find that the EV in each case is exactly the same (your EV is -1 cup of coffee in both scenarios) but that's not the end of it. It's also really a question for them to test your risk aversion. You can really support either answer, and *should* comment on the validity of either answer. My answer was to go with buying my own cup of coffee, and followed it up with a story where a friend of mine had tried to get us to play credit card roulette (which is similar in spirit to this game) and I told him that I did, in fact, say no in that instance and why I said no. However, traditionally people are risk-averse when faced with gains and risk-seeking when faced with losses, so many would probably choose to play the game. But this is as much a question about your psychology as it is about your math skills. And that's why this is such an awesome question, and is probably a question that kills most people they ask it to. Would you please explain to me how do you get -1 for the second scenario? There are 50% H and 50% T. Therefore players have 50% opportunity in the winning group. Given 5 interns, there are two combination of lossing group (4 vs. 1 and 3 vs. 2). EV=0.5*0 + 0.5*(0.5*-5 + 0.5*-2.5) = -1.875. The probability of winning isn't 50%. It's actually slightly above 50%, but that's not the way to look at it. The total number of coffees that need to be bought is n, where n is the number of interns. Going into this game, every intern is the same so they each have the same expected value, and the sum of the expected values must equal -n. So everyone has an EV of -1 as claimed. Thank you very much. I finally got it. I'm still not sure why you said no if the EV is the same? It's a matter of risk preference. See the example I gave in my Mar 19 posting: "Suppose I give you a choice of two outcomes. Either you get $1 with 100% probability or I give you $500,000,000 with probability 1/100,000,000 and 0 otherwise. Which would you pick? Now what if it was the same first choice, but the second choice was $50 with prob 1/10 and 0 otherwise? Now which would you pick? These are the kinds of things you want to think about while answering this kind of question." You would probably not play in the first instance and consider possibly playing in the second. (And those instances even have the risky game with a HIGHER EV). This coffee game is the same kind of game, and even if the EV is the same in each case, the volatility is not the same. It is usually a good rule of thumb to take the lower volatility outcome if the EV is the same (think Sharpe Ratio here! Or think efficient frontier here! Both get the point across I think.). Does that help? I say yes. To play the game. Only because I'm prepared if I lost. The fact that I can afford to loose, makes me want to try my chance at wining I would play the game. Consider the expected price with n total interns splitting a total cost of P. That is P/2*E[1/(N)|you're paying]. This is simply equal to P/2*E[1/(N+1)] where n is a binomial now corresponding to n-1 interns. Notice that 1/n+1 is a concave function. That means that P/2*E[1/(N+1)] <= P/2*(1/E[N]+1)=P/2 * 1/( (n-1)/2 + 1)) = P / (n +1). So it pays to play on average Apologies, but both of the above answers are incorrect. The EV of playing is the same as the EV of not playing. Show More Responses No way would I play! The most money I save is a dollar the most money I can lose ( in the case of five interns) is 4 dollars... That's a 400 percent downside verse a 100 percent upside ( kind of you cannot technically compute your return on zero dollars invested). Plus, I do not even drink coffee! Stupid...I don't have time to play games at work. The EV in both scenarios are not the same: it's clear when think about the case where there are n = 3 interns. I've already explains why they are the same. In either scenario there will be n cups of coffee bought (3 in your case) so total EV is -n (-3 in your case). In the game each person is the same as any other so their EV must all be the same. That is why in the game the EV is -1 (same as if they buy their own cup of coffee). To argue otherwise is to argue that either the total EV is not the number of coffees purchased or that someone has an unfair advantage in the game. Incidentally, if you are going to claim that someone who has given you the answer is wrong, you should provide more of a response than "go think about it." if v = pay by game -1 . Then all have five intern have same distributed V by symmetry 5EV=0 It's zero sum. |

### Software Engineer at Dropbox was asked...

Given an array of integers eg [1,2,-3,1] find whether there is a sub-sequence that sums to 0 and return it (eg 1,2,-3 or 2,-3,1) Checking every sub-sequence is O(n^2) which is too inefficient 12 AnswersShould do a running sum, storing previous sum values in a hash table along with array index if you ever get a sum value you’ve already seen, return the array indices (1+the index in the hash table, and the current index) This solution is O(n) Although the above algorithm runs in O(N) time, will it cover all cases? What about if the input array is [1,2,1,-3,-4]? In this case, the subsequence would be [2,1,-3]. I feel though that the algorithm described above will miss this subsequence since you are only keeping a running sum from the start of the array. Do you mean a subsequence (can be discontinue) or a sub array (continue)? Show More Responses Yes, the solution by Interview Candidate (do a running sum and return when you see a sum already seen) works for all cases. If the list is [1, 2, 1, -3, -4], S1 = 1; S2 = 3 (1 + 2); S3 = 4 (1 + 2 + 1) S4 = 1 (1 + 2 + 1 -3) ... since we have already seen this sum at index 1. the answer is list of numbers at [old_sums_index + 1, new_sums_index] = [2, 1, -3] [100 7 1 2 -3] the above method will not work for this array, It will work for [100 7 1 2 -3]. Index: 0, Sum = 100 (put in hashtable) Index: 1, Sum = 100 + 7 = 107 (put in hashtable) Index: 2, Sum = 107 + 1 = 108 (put in hashtable) Index: 3, Sum = 108 + 2 = 110 (put in hashtable) Index: 4, Sum = 110 + (-3) = 107 107 already exists in hashtable with index = 1. Hence we return (1+1, current index) meaning (2, 4) Doesn't work for [-1,-1,-3,4]. This looks like a classical NP-complete problem: http://en.wikipedia.org/wiki/Subset_sum_problem. And generating all sub sequences is not O(n^2) but O(n!) which is the cost to generate all permutations. It works for [-1 -1 -3 4] too. The subset sum problem allows discontinuous subsets, but this question asks for a subsequence implying no discontinuity. Here is a solution using Python 3: def findZeroSequence(list): hash = {} sum = 0 startIndex = -1 hash[sum] = startIndex # a sum of zero later in the list means the sequence starts at index 0 (== -1 + 1) for i, v in enumerate(list): sum = sum + v # print(i, ' has sum ', sum) try: startIndex = hash[sum] return list[startIndex+1:i+1] except KeyError: hash[sum] = i return [] # no subsequence print(findZeroSequence([1,2,-3,1])) print(findZeroSequence([1,2,1,-3,-4])) print(findZeroSequence([-1,-1,-3,4])) print(findZeroSequence([100, 7, 1, 2, -3])) print(findZeroSequence([-7, -3, -2, 5, 8])) Checking every sub-sequence is O(2^n) not O(n!), which is the cost for generating all subsets. Contrary to what the previous poster said, sub-sequence implies both continuity and discontinuity: http://en.wikipedia.org/wiki/Subsequence and the algorithm fails for this case: [2, 2, 1, -4]. How about these: [1,2,-3,4] or [-3,3,1] ? May be user should check for zero also? |

Implement a power function to raise a double to an int power, including negative powers. 11 AnswersCould be implemented many ways. I got the feeling that the interviewer wanted to see you approach the problem in multiple ways and demonstrate confidence in your math and recursive skills. #include #include #define MAX_ARRAY_LENGTH 256 double power(double, unsigned int); int main(int argc, char** argv) { double a = atof(argv[1]); int b = atoi(argv[2]); double result = power(a, b >> 31 == 0 ? b : -b); if ((unsigned int) b >> 31 == 1) { result = 1 / result; } printf("%f\n", result); return 0; } double power(double a, unsigned int b) { switch (b) { case 0: return 1.0; case 1: return a; default: return (b & 1) == 0 ? power(a * a, b >> 1) : power(a * a, b >> 1) * a; } } c implementation of the above (no recursion): int ipow(int base, int exp){ int result = 1; while(exp){ if(exp & 1) { result *= exp; } exp >>= 1; base *= base; } return result; } Show More Responses int power(double n, int exp) { bool npower = (exp < 0) ? true : false; double result = 1; exp = abs(exp); // get the absolute value for (int i = 0; i < exp; i++) { if (npower) { result = result/n; } else { result = result*n; } } return result; } C# code verified: static double Power(double d, int exp) { if (d == 0 || exp == 0) { if (exp >= 0) { return 1; } else { return double.PositiveInfinity; } } int expAbs = Math.Abs(exp); double res = d; for (int i = 1; i 0) ? (res) : (1 / res); } double power(double x, int y) { if(y == 0) return 1; int sign = 1; if(y < 0) sign = -1; y = abs(y); double d = power(x, y/2); if(y%2 == 0) d = d*d; else d = x*d*d; if(sign == -1) return 1.0/d; else return d; } I am surprised that not a single person here had noticed that the guy asked to raise a DOUBLE to a given power. Men, double are not integers. Their exponent is stored in a part of their binary representation. If you multiply n times a double you will make n times a rounding error and n useless calculations. Just changed the binary part of the double that is related to its exponent, and here it is, your double has been raised to a given power, a you absolutely lost no precision, and you've made 0 calculations. This is basic stuff, every university teaches that to its students... floating numbers representation... I believe interviewer is expecting for this public static double Power(double x, int y) { double result = 1; bool isNegative = y 0) { if ((y & 1) > 0) { result *= x; } y = (y >> 1); x *= x; } if (isNegative) result = 1 / result; return result; } Verified C# static double Pow(double b, double exp) { if (exp == 0) return 1; else if (exp > 0) return b * Pow(b, exp - 1); else return 1 / Pow(b, -exp); } Does it get more compact? TD's answer is interesting, but not very useful. If you actually try it you'll find that since the double's base is 2, any changes to the exponent portion approximately multiply (or divide) numbers by a power of two. I say approximately here, since TD forgot to mention that the number itself isn't stored in float point numbers, only the digits after the implied 1. So yes, it's important to know how floating point numbers work, but modifying the exponent portion of a floating point number is a fundamentally incorrect solution. public double power(double num, int exp) { if(exp == 0) return 1; double res = 1; for(int e=Math.abs(exp);e>0;num*=num,e>>=1) { if( (e&1) == 1) res *= num; } return (exp>0)?res:1.0/res; } |

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

Write a function that divides two numbers without using the divide '/' operator. 10 AnswersI had to use recursive subtraction or addition. But, I think I took too long a time to figure out the fastest code and I was typing it out in google docs while the interviewer was on the phone with me. I was nervous. It was my first ever interview. But, it was a heck of a experience. X * Y^(-1) One way is to iteratively count the number of times Xn = Xn-1 - Y >= Y. No recursion needed. Also, if Y is a power of 2, you can use a right-shift to get the answer...even faster. If the number space is sufficiently small, you can use a lookup table. Show More Responses int positionOfFirstAndOnlyBitSet(int m) { int pos = -1; int x = 0; for (; x > x) & 1) if (pos == -1) pos = x; else return -1; // found more than one bit } return pos; } int divide(int n, int m) { if (m == 1) return n; if (m == n) return 1; if (m > n) return 0; int pos = positionOfFirstAndOnlyBitSet(m); if (pos != -1) return n >> pos; // how manny times one can multiply m before going over n int x = 1; int mm = m; while (mm <= n) { mm += m; x++; } return x - 1; } assuming you want to be able to handle doubles, I like the idea of x * pow(y,-1.0); ... why make the answer more difficult for yourself than it needs to be? I got this question in facebook interview as well. You usually are not allowed to use floats, or pow(), or % And also you have to consider both +, - integers, so Steve M answer is not valid. public static int divide(int a, int b) { if(a < b) return 0; int div = b; int k = 1; while((div<<1) <= a) { div = div<<1; k = k<<1; } return k + (div == a ? 0 : divide(a-div,b)); } int num; int div; int rem; // assume only positive numbers for(i=0; num>=0 ; num-=div) { i++; rem=num; } printf("\ni: %s%d rem:%d", i, rem ); Victor, whats the complexity of your solution ? Binary search will work ? Let's say you need x/y. And only integral solution is needed i.e. 10/3 = 3 , not 3.33. This won't work if we need float as a result Pseudocode If x > 2) if mid*y == x : return mid if mid*y > x : hi = mid - 1 else: lo = mid + 1 return lo -------------------- |

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

List all anagrams in a file. Assumptions: case-insensitive, a-z characters only, one word per line. For example, if the file contains dog, cat, ddd, goo, act, god -- output dog, god, act, cat 10 AnswersThankfully I was taking a theory course and one trick used in the course was "encoding" programs as a large natural number using product of primes. 1. Adapt the encoding as follows -- generate the first 26 primes and assign a prime to each letter 2a. For each word, take the product of each letter's prime. So #(act) = 2*5*prime(t) 2b. As you can see, #(cat) = 5*2*prime(t) = #(act) 3. Insert a handwavey argument about inserting the number/word pairing into a HashMap> Sort the words. Anagrams appear next to each other in the sorted list. Sorry, sort the letters in each word, then sort the words. Anagrams appear next to each other in the list. For example the sorted list for the input would be: act act ddd dgo dgo goo Show More Responses Thanks for sharing Bill For this set of input, the expected output should contain only [cat, act, god, dog]. I'm curious to see what "next steps" your algorithm will perform to provide this expected output You keep track of the mapping from the sorted word to the actual word in a pair, for example: [act, cat] [act, act] [ddd, ddd] [dgo, god] [dgo, dog] [goo, goo] Then you go through this list and count if you have a duplicate entry or not. If you do, like for act, you print out those duplicate entries: cat, act. Bill, your algorithm is O(n*log(n)) while the candidates would be O(n) - provided he uses a decent hash function donutello, bills algo is not n log n it is n*log(k) where as candidates algo is n * k again (multiplications for each word) where k = length of the longest word on top of that calculating primes is expensive anyway I would go with bills answer Bills algo is nlogk + nlgn. After sorting the k letters for n times you also have to sort the n words. #Get inputs a = [] f = open('input.txt','r') for line in f: line = line.strip() a.append(line) #Sort letters in a word def sort_letter(s): r = [] for i in s: r.append(i) t = sorted(r) v = ''.join(t) return v #Find anagrams d = {} for v in a: sv = sort_letter(v) if sv in d: d[sv].append(v) else: d[sv] = [v] #Print results for k,v in d.items(): if len(v) > 1: for s in v: print s think of each line as a set of characters, not a word, then create set of sets of characters which you fill from the input. then print the set (order does not matter as its not specified) |

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

find 3 elements in an array that sum to 0. 6 AnswersI would construct a hash of all entries in the array and then iterate through a 2d product of all elements in the array and see if that sum was in the hash as first mentioned. Any comments ? @Richard no, that's not the way to do it actually. Your naive solution would take a N^3 / 2 complexity. A N^2 lgN complexity can be achieved if you first sort the array. A pair a[i] and a[j] is part of a triple that sums to 0 if and only if the value -(a[i]+ a[j]) is in the array(and not a[i] or a[j]). You need to sort the array, then do N (N - 1)/ 2 binary searches that each take time proportional to log N, for a total running time proportional to N^2 log N. Here's an example in java : http://algs4.cs.princeton.edu/14analysis/ThreeSumFast.java Thanks for the comment. However, I'm not sure how I am that far off.. If you just replace my hash with an ordered array, then essentially it's the same algorithm. How did I get to n^3 though .. I take it on board that a hash array take longer to construct than an ordered list in which to do a binary search - is that the additional order of magnitude? Show More Responses Richard, The solution using a Hashtable is better, because its time complexity would be O(N^2). public void sumIsZero(int[] a){ int n = a.length; for(int i=0; i<n-1; i++) for(int j=i+1; j<n; j++) { int num1 = a[i]; int num2 = a[j]; for(int k=j+1; k<n; k++){ int num3 = a[k]; int sum = num1 + num2 + num3; if(sum == 0){ System.out.println("a["+i+"]="+num1+", a["+j+"]="+num2+", a["+k+"]="+num3); } } } } More elegantly, RIchard is correct. Compute the 2sum (N^2/2 +N/2 operations) and store it in a has table (potentially O(1)) or sort the answer (potentiall O(n\lg n)). For each element in the list, look up the negation in this list (O(n) for has tables, O(nlg(n)) for sorted arrays). |