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. |
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. |
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? 12 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 How does the first one not contradict this: https://math.stackexchange.com/questions/982797/prove-that-the-product-of-two-positive-semidefinite-and-symmetric-matrices-has-n It doesn’t. It provides an alternative way of establishing that the eigenvalues must be nonnegative. In fact, if you read the proof, all that’s established is that AB is similar to a positive semidefinite matrix and therefore must be positive semidefinite. It says nothing about whether or not AB is symmetric (which is also required for AB to be a covariance matrix). |
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 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). |
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 |
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. |
25 racehorses, no stopwatch. 5 tracks. Figure out the top three fastest horses in the fewest number of races. 11 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. 0 Races. Ask the jockeys to rate the 10 fastest horses and take the average of the top 3. Nobody knows the horses that are fast better than the jockeys. Race results can vary from race to race but the jockeys truly know the fastest and besides because race results vary anyway you will not find the fastest horses with the least races you will find the fastest on that day. Either way your results will not be accurate without a larger dataset. The jockeys however already have a deeper dataset. Better yet find the local bookie for the track and ask for the odds on the horses. Why solve a problem that has already be solved. |
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. |
Senior Software Engineer at Microsoft was asked...
Given a set of people, one of them is a celebrity. You have a 2D array which describes which people know each other, that is [N, M] is true if N knows M. The celebrity will not know anyone (except them self) and everyone will know the celebrity. Find an order N algorithm to find the celebrity. 6 AnswersDon't think there is an O(n), but O(n*m) yes. The key here is that the celebrity knows nobody AND everybody knows the celebrity. So for each iteration, you can rule out 1 person. [Notation: A->B -- A knows B] If A->B then A is not the celebrity .. rule out A Next check would skip B->A since we don't care if B->A etc It is not so simple. You can construct a matrix of relationships to defeat this algorithm. For example, start with A knows B. Then check if B knows C, and say answer is false. Then check B -> D, answer is false. And so on. That's O(N) operations. B looks like a good candidate. But then you check B-> A, you get true, so after all that work B is ruled out. Need to examine C now. Same thing. You end up checking perhaps half of all possible pairs, that's O(N^2). Show More Responses How about constructing a graph with edges between who know each other.. and then checking if target is reachable.. http://courses.cs.vt.edu/~cs5114/spring2010/notes.pdf Please correct me if I've made some incorrect assumptions here. It seems like the matrix is an adjacency matrix, so M is always equal to N. The solution is to follow the diagonal. If A is the celebrity then following are the patterns possible along the diagonal. If A is the first element in the matrix, i.e. i=0 and j=0 then [0,0] = 1, [0,1]=0, [1,1]=1, [1,0]=1. If A is the last element in the matrix, i.e. i=M and j=M then [M,M]=1, [M-1,M-1]=1,[M,M-1]=0,[M-1,M]=1 The third case is when A is an element somewhere other than the above cases. In this case, you're looking for the following pattern [i,j]=1,[i-1,j]=1,[I+1,j]=1,[i,j+1]=0,[i-1,j]=0. Looking at the time complexity, it is going to be a tad higher than O(N) but certainly not O(M^2). |