# Technical Interview Questions

interview questions shared by candidates

## Technical Interview Questions

### Summer Analyst at Goldman Sachs was asked...

13 cubed 6 Answers2197 how long did it take you to answer this? I assume thats what they were testing I did it while doing some chit chat about his day. No longer then two minutes, and then he asked how I did it. So I explained the steps. Show More Responses really easy on paper, in your head, not so easy. In your head, here's how I'd do it: 13 squared is 169- that's easy. then, 10 times 19 is 1690, and 3 times 169 is approx 500, so 2190 is an easy approximation. Only 7 off from the actual answer! 13*13 = 169. Then do 13*170 = 10 * 170 + 3 * 170 = 1700 + 510 = 2210 Then, 2210 - 13 = 2197 Do it on your head. 13*13 = 169. For 169*13 first 3*169 = 507 second 10*169 = 1690 Finally 169*13 = 507 + 1690 = 2197. |

Suppose you have two covariance matrices A and B. Is AB also a covariance matrix? Suppose that, by plain dumb luck, we also have that AB=BA. Is AB a covariance matrix under this additional condition? 10 AnswersI suppose it's clear from how I wrote the question that the answer to the first question is no (for you: why?). For the second question, this is a little bit harder if you aren't experienced in linear algebra. I actually have a PhD in algebra, and the interviewer also had a PhD in algebra, so on some level this question might have been specifically targeting my background. There is a standard result that applies here; see if you can figure it out. 1. no 2. no, give an example where diagonal positivity is not true. 1 is correct, 2 is wrong. Try again. :) Show More Responses 2. Just checked Wikipedia, AB is cov matrix because it is symmetric semi positive definite. Is it right? If AB=BA then yes it is symmetric. So the question boils down to: Is it in fact positive semi-definite? Why or why not? Work through that and you have your answer. My hint: Take a look at some results related to diagonalizing matrices that commute with each other. Hi for your telephone interview with doug, what was the focus for technical interview parts, everything from math, finance, programming? or mainly probability type of question? thanks I remember it being mostly probability and finance. Nothing too terrible. Hi Mr.interview candidate, what were the types of finance questions Doug asked? Thanks! Hi, Mr. interview. Do you remember what kind of data analysis example was for on-site interview? If so, can you share a little bit? What was the level of difficulty? Thanks! 1, no 2, yes |

### Assistant Trader at Five Rings Capital was asked...

You are standing beside a road watching cars pass by. The probability that you see a car pass by in 1 minute is 1/4. What is the probability that you see a car pass by in 30 seconds? 8 Answers1-sqrt(3)/2 why is this let p=probability that you see a car in 30 seconds p(see car in first 30 seconds)=p p(see car in second 30 seconds)=p p(see car in the first 60 seconds)=2p-p^2=1/4 solving you get p=1-sqrt(3)/2 (reject 1+sqrt(3)/2 since it's over 1) Show More Responses I have a question on this solution: 1-(1-p)^2 is the probability of seeing at least one car, not the probability of seeing a car. You can also solve this using exponential distribution. From the question, you can deduce that the distribution has to be memoryless and hence there has to be a constant rate per unit time for the event to occur. Let the probability per unit time of a car passing by be p. Then from the given information 1/4 = 1 - e^{-p*T} The required answer is e^{-p*T/2} which gives the answer as reported above. Minor correction in above. The required answer is 1 - e^{-p*T/2} ans 1/2 as the person sees car in 15 sec of each 1 minute if we divide 1 minute into 4 parts (60/4 = 15 secs) s the probablity of seeing car now we are asked in 30 sec . the rate of moving of car will not change it will still continue to come at a rate of 1 in each 15 sec so the ans for each 30 sec would be 1/2 if we divide 30 into 2 parts . so in 15 sec one car is left .but for next 30 sec no car is going to come then itls probability would be 0 . now the ans is tricky which 30 secs are asked , the 30 sec in which car is seen or in which it is not seen by the man 1 - sqrt(3)/2 is the wrong answer |

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

What are the first 2 integers that, when added together, equal 10 in a "very large" array of unsigned integers? 6 AnswersMy in-interview answer was bad!!! I came up with a better one using a 2d array with 11 rows and 2 columns. First column to hold the first occurrence of each integer 0-10 (conveniently, the indices of each row match a relevent integer) and second column to hold the second occurrence of 5. When you first encounter an integer that can be used to equal 10, add the index to the first column. When encounter 5 for the second time, add it to the second column. Each time you update a value, check to see if both sides of the equation are populated...if so, you have your answer, if not continue on with the original array. Note: Adding the index enables you to keep track of WHERE the integers were in the original array, however if that doesn't matter, you could update it with any value that works for your evaluation logic. It's a specific case of the problem of finding two integers that add up to a given number in a list of integers. In general case, you do need to sort first and use two pointers from start and end and use an elimination to search in O(n). In this case, since sum is already given (a constant) we just need to maintain last unique indices of integrers <= 10. Any time we find two that adds up to 10 is the answer. if it is a "very large" collection, avoid sorting; i think we are creating a time consuming cycle there. i have given a little piece of code for a similar question in this forum itself, which can be used as a starting point for bettering your answers. i got this question few years ago, when i went for an interview, with a bay area network security company.. as a UI developer !! Show More Responses should not sort it. Create an array or length 11 (index of 0-10), call it H, fill it with null (you can use -1 as null) Call original array A. Code is very simple: i = 0 while(i++) complement = 10 - A[i] if(H[complement] == null) H[complement] = i else break at this point A[H[complement]] + A[i] == 10 I'm essentially using H as a hash table where hash(n) = n this solves the problem in O(n) I believe. I think hashing is preferred in this case. @maxzed2k I'm not entirely sure if your solution will cover all cases. What if the complement (i.e. 10-A[i]) is negative? H[ ] will give you a segmentation fault. |

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

Given a series of words written using a scrambled alphabet, figure out what order the letters of the alphabet are in. 7 AnswersUse a graph! More than three words would be helpful. Do what with a graph? How would you build it? How would you search it? Given a ciphertext C, and plaintext P, the problem is to find a key K that converts the ciphertext to plaintext. Without considering the asymptotic complexity, it should be straighforward to generate the key combinations using a backtracking search algorithm. Show More Responses More specifically, you would be given a list of words in the ciphertext which are in alphabetical order. Your job is to determine the alphabetic order of the ciphertext letters. In a graph, each node would represent a letter, the directed edge would indicate ordering of the two letters it connects. Once the graph is built you can do a simple traversal of the graph to generate your alphabetical ordering. Hope that helps! I think I didn't get the question. Could someone elaborate on it a bit please? @Alexander An example of what I believe the question is presenting to the applicant is as follows. Say I knew one of the words was 'CAT'. Now, if I look at the scrambled 3 letter word, and it was ZBS, then I know that C = Z, A = B, and T = S. Essentially, potentially every letter in the alphabet (up to 26 letters in total) are not of the same value. So, if I had another example word, say 'TACS', and the given scrambled word is 'SBCY', then I now know that S = Y as well. This is not an explanation of how to approach the problem, as we're not given any sample words; This is simply my interpretation of how the question is supposed to be interpreted as @Alexander is probably not the only person who does not understand the question. Of course, I could have it wrong too, so who knows. http://www.careercup.com/question?id=19114716 |

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

What is the output? int n = 1; puts(((char*)&n)[0]==1?"Y":"N"); 6 AnswersIt can be Y or N and the answer depends on the "Endianness" yes..depends on the system architecture whether it is big endian or little endian int n = 1; stores it in the following way in 4 bytes 00000000 00000000 00000000 00000001 (increasing memory addresses) (char*)&n will make n de-reference to only 1 byte instead of 4 bytes. For big endian, (char*)&n[0] will be 00000000 and for little endian it will be 00000001 Umm, so &n returns the address of n, we then cast it as a pointer to char, we then dereference the first element at that pointer [0] and read it as a char. the char corresponding to a value of 1 is not the same as the actual value 1. So, the comparison will return false, and we'll print N. Show More Responses uh... int heads = 13; for (int bullets = 0; bullets < heads; bullets++ ) { int n = bullets; puts(((char*)&n)[0]==n?"Y":"N"); } gives: Y Y Y Y Y Y Y Y Y Y int heads = 130; for (int bullets = 0; bullets < heads; bullets++ ) { int n = bullets; puts(((char*)&n)[0]==n?"Y":"N"); } gives: Y Y .... .... N // 128 bullets N // 129 bullets (overflows the signed char) Not even close guys. The code as written is not portable and invokes implementation-defined behavior. The problems involve whether or not a pointer to char corresponds to a pointer to unsigned char or pointer to signed char. char can be either and it is left up to the implementation. It is important because not all bits are value bits. An implementation can encode a signed char with value bits + pad bits + sign bit and conversion between pointer to int to pointer to char is not guaranteed to produce a meaningful value of the destination type. unsigned char has value bits while something like an unsigned int can have both value bits and padded bits. All that means, is that you can't go about mucking around with bit patterns and converting them between pointer types where the pointer type is not an allowable type to be converted to as outlined by the ANSI/ISO/INCITS standard that defines the abstract machine for the C programming language (9899:1990) and (9899:1999). A lot of this is also very similar to the C++ language so it also holds. |

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

Given a stream of integers of unknown (possibly large) length, how would you pick one at random? Now prove its random. 6 AnswersQuestion was not worded very well, however we eventually reached mutual understanding. Answer: Store one integer at most. For each pop, decide whether or not to store it in the one slot with probability 1/N (N is current count of integers encountered). proof is easy: probability of an object appearing (being chosen) to be in some previous slot K starts with 1/K as per the algorithm. To "survive" to the Nth slot, the probability is (let M be distance of K to N: M = N - K or N = K + M) 1/K * K/(K+1) * (K+1)/(K+2) * ... * (K+M-1)/(K+M) , the last denominator simplifies to N All the numerators and denominators cancel except 1/N. Can you explain how you got this? 1/K * K/(K+1) * (K+1)/(K+2) * ... * (K+M-1)/(K+M) Show More Responses You can prove by induction, probably simpler. If the list only contains 1 member, probability is 1/1 = 1, which is correct. For the induction step, consider what happen when k-th member is encountered: case(a): for the k-th member, probability of being picked is 1/k, which is what we want. case(b): for each of the previous (k-1) members, probability of being picked become P(k-th not picked) * P(original, i.e. 1/(k-1)) = (k-1)/k * 1/(k-1) = 1/k, which is what we want. [] It is more fun if we were to picked m members at random, then the prove becomes less trivial (though almost equally as straightforward). Thank you for the clear, concise explanation, Shards! I get everything except for one part: P(being picked) = P(k-th not picked) * P(original) Where does that come from? Is that a probability rule? If you could point me to a link on the web (or even what keywords to search on Google), that would be much appreciated. Thank you! Just run rand() function to get a number for each member, always keep the member with the minimum number associated with it. Need a little extra effort to handle tie case. |

25 racehorses, no stopwatch. 5 tracks. Figure out the top three fastest horses in the fewest number of races. 9 AnswersWe can do it in seven races, we'll call them races A-F. For notation, we'll say that the Nth horse in race X is called X.N. Races A-E: Divide the horses into 5 groups of 5 each such that each horse races only once. We can eliminate the slowest 2 horses in each of the five races because there are definitely 3 horses faster in each case. As a result, we eliminate 5x2 = 10 horses: {A.4,A.5,B.4,B.5,C.4,C.5,D.4,D.5,E.4,E.5} Race F: Race the fastest horses in each race A-E: {A.1, B.1, C.1, D.1, E.1}. To simplify notation, we'll label F.1 as horse A.1, F.2 as horse B.1, and so forth. That means the winner of this race is A.1, and it is the fastest horse of all. We don't have to race A.1 anymore. We can eliminate D.1 and E.1 = 2 horses. Because they are not in the top 3. As a result, we know that all remaining horses from D and E are eliminated. This is D.2,D.3,E.2,E.3 = 4 horses. We know that A.1,B.1, and B.2 are all faster than B.3 (and similar for C.3) so they are not in the top 3.We can eliminate B.3 and C.3 = 2 horses. Finally, we know that A.1 is faster than B.1, which is faster than C.1, and thus C.2, so we can remove C.2 = 1 horse. Race G: We have removed 19 horses from competition and are sure that A.1 is the fastest horse of them all. This leaves just 5 horses: {A.2,A.3,B.1,B.2,C.1}. We race them and select the top 2 to join A.1 as the top 3 fastest horses. just run them all on the one track :) one race, and you get your 3 fastest horses in one go........or am I missing something! 6 races. Divide 25 horses into 5 groups. Each group races and the fastest is selected. The winner of each of the 5 races all race together. Pick Top 1,2 and 3. My only concern: Could the answer be this simple? Show More Responses B, you're mistaken. Imagine the top three fastest horses are Santa's Little Helper, Yojimbo, and I'm Number One. By random luck, in your first race, the five random horses you choose includes all three of those. I'm Number One wins and goes on to the final race; the other two do not. 8 5 top horses from each race of 5 races (25 / 5) 5 top contenders race; 1 wins--that's one top horse (5-1) 4 remaining top horses race, one wins; that's 2 top horses (4-1) 3 remaining top horses contend; winner is #3 That's 3 top horses from 8 races Race#1 Race#2 Race#3 Race#4 Race#5 A1 B1 C1 D1 E1 A2 B2 C2 D2 E2 A3 B3 C3 D3 E3 A4 B4 C4 D4 E4 A5 B5 C5 D5 E5 Race#6 A1 B1 C1 D1 E1 Let's Say ranking 1st 2nd 3rd 4th 5th Eliminate D1 E1 D2 E2 D3 E3 A4 B4 C4 D4 E4 A5 B5 C5 D5 E5 Left with B1 C1 A2 B2 C2 A3 B3 C3 Eliminate C3 as there are more than three faster horses C2, C1, B1, A1 Eliminate C2 as there are three faster horses C1, B1, A1 Eliminate B3 as there are three faster horses B2, B1, A1 Left with 5 horses for Race#7 B1 C1 A2 B2 A3 So 7 races 7 races. put 25 horses in 5 group. and we will have 5 sorted list of horses in each group. put 1st place horse in each group, and we will have a sorted list X. X_1 is the 1st place horse, and X_2 is 2nd place horse's candidate, X_3 is 3rd place's candidate. 2nd place horse in X_1's group is candidate for 2nd place, 3rd place one is candidate for 3rd place. and 2nd place horse in X_2's group is a candidate for 3rd place. that's 5 horses in total, 2 from X_1's group, 2 from X_2's group, X_3. race them, and 1st place is 2nd place, 2nd place is 3rd place horse. 8 the answer is one race as the question doesn't specify all the horses have to run in separate races. |

Asked to implement a function that takes an integer and returns whether or not the number had an odd or even number of 1 bits. 6 AnswersIt started out with an ambiguous set-up so the first thing that needed to be figured out was what kind of number to be taken in. How many bits this value was. I was told to assume it was 32 bits. I mentioned that the number may be in 2's complement, I was told to only expect unsigned integers. The solution is pretty straight forward, it only requires a for loop that counts from 0 to 31 and checks whether the integer masked with 1 is equal to 1. If it is, add one to the accumulator and shift a bit to the right. Then I was told to extend this function to work for an n bit integer. With some hints I figured out that log base 2 of a number gave you the maximum number of bits it would take to store that number so simply replace the loop that went from 0 to 31 with a loop that goes from 0 to log_2(n). If the task is only for positive numbers, then my solution would be: bool is_odd_set_bits(unsigned number) { bool result = false; int n = number; do { result |= ((n % 2) == 1); n /= 2; } while ((n / 2) != 0); return result; } Show More Responses mod and div operators are good, but you could set yourself apart by using a more efficient algorithm. In terms of big O, it will be the same, but it will have a higher throughput since the operations are slightly faster. > bool is_odd_set_bits(unsigned number) { bool result = false; int n = number; while(n != 0) { result |= ((n & 0x01) == 1); n >> 1; } return result; } masking is faster than a mod operator, and bit shifting is faster than divisions i was trying this in java and found kinda small bug... so we should return false if the number is 3 which is 0000000011. I guess changing the line to: result ^= ((n & 0x01) == 1); will do the job... PC, your solution is incorrect. It will always return true if the number has at least one set bit. |

### Software Engineer at TripAdvisor was asked...

Write a program that given 4 coin denominations and a dollar amount finds the best way to express that amount using the coins given. I.e. you have coins with denominations of 1c, 7c, 13c,19c and you have to express $2.12 with the least number of coins. There is always a 1c coin but the other 3 are arbitrary. 6 AnswersTurns out , this problem only has an elegant solution when the coin denominations are divisible by each other, such as the US coins (1, 5, 10, 25). Otherwise, it requires a (slightly optimized) brute force algorithm. I was told so by the interviewer after struggling with it using different approaches for about 40 minutes. If you have a coin of value 1, you can use a greedy algorithm: always select the most valued coin, until you have less money left that this value. Remove the coin, try again with less coins and the money left. Otherwise, just bruteforce and memoization, to implement a simple dynamic programming approach where you want to minimize the number of coins used, caching on the amount of money left to divide. Greedy algorithm is not right at all for general cases. This is a very classical questioin. If you fail on this question, I would say that it is probably your fault. Show More Responses In all my years of giving and receiving interview questions I have never seen this one. It is definitely NOT a classical programming problem. Asking whether a candidate knows of an obscure academic puzzle does not sound like a good interview question. int main() { int currency[] = {19,13,7,1}; int money = 212; int i=0; int div=0; while (money>0) { div = money/currency[i]; money = money%currency[i]; if(div>0) { cout It is a classical programming question that derives from the first fit decreasing algorithm in discrete (decision) mathematics. |