# Technical Interview Questions

interview questions shared by candidates

## Technical Interview Questions

### Velocity Software Engineer at Cerner was asked...

very straight forward questions already present on glassdoor 6 AnswersCan you tell me when did you have your final interview (Experience Cerner Day)? Its been more than a week and I have not heard from them. Thanks Hey can you tell me how was you interview experience and what king of questions where you asked..?? I had it on feb 15. You will hear from them shortly All the best. Show More Responses http://mohitsamant.blogspot.com/search?updated-min=2012-01-01T00:00:00-08:00&updated-max=2013-01-01T00:00:00-08:00&max-results=13 this is a good place. Thanks for the info. And can you tell me when did you get the call for the offer? Thanks I appreciate your help. i got it last wednesday |

### Software Developer at Microsoft was asked...

Why is a manhole cover round? 6 AnswersSo it won't fall into the manhole. i dont believe all this , i have been to interviews and nobody asks these questions, its usually 1 question per person you talk to and thats it .. not all such questions please. its something that was asked 20 years ago. Now its simple and everything depends on how you are liked as a person ... its a very biased process, i was offered and i declined its a bad place now. for easy transport.... rofl it ... oh sorry roll it Show More Responses I think everyone has seen this in Parade magazine at least once. If someone really asked me this in an interview I think I would suggest that it was time for them to retire. http://en.wikipedia.org/wiki/Manhole_cover Reasons for the shape include: * A round manhole cover cannot fall through its circular opening, whereas a square manhole cover may fall in if it were inserted diagonally in the hole (A Reuleaux triangle or other curve of constant width would also serve this purpose, but round covers are much easier to manufacture.) In reality, however, the existence of a "lip" holding up the lid means that the underlying hole is smaller than the cover, so that other shapes might suffice. * Round tubes are the strongest and most material-efficient shape against the compression of the earth around them, and so it is natural that the cover of a round tube assume a circular shape. * Similarly, it's easier to dig a circular hole and thus the cover is also circular. * The bearing surfaces of manhole frames and covers are machined to assure flatness and prevent them from becoming dislodged by traffic. Round castings are much easier to machine using a lathe. * Circular covers do not need to be rotated to align them when covering a circular manhole. * Human beings have a roughly circular cross-section. * A round manhole cover can be more easily moved by being rolled. * Tradition. * Supply. Most manhole covers are made by a few large companies. A different shape would have to be custom made. So it rolls off your toes after you drop it |

I have a log that consists of more than 100 million lines. Each line is just a data about user login, login time, etc. I want to sort them based on user login, and then if there is a tie based on login time, etc. However, I have limited memory, so don't think of storing all of them in an array. The memory can only hold n data where n is much smaller than 100 millions. You can access the disk though although it is much slower. How will you do it so that it is as efficient as possible? 5 Answershint: the memory can only hold n data, use them wisely. we can solve this problem using n^2 complexity time we scan the whole enters to find the smallest value and we do that in a for loop its complexity is bad, n square anyone knows better answer? how about using hash table? Show More Responses Use an external mergesort http://en.wikipedia.org/wiki/External_sorting hash table |

Suppose you have 100 GB of data that you want to sort, but you only have 1 GB of memory. How would you sort this data? 8 AnswersHint: This isn't really a difficult question (just was an unexpected one for me). You don't really need to know the answer to figure this out. As it turns out, the obvious thing actually works here (and it is a known sorting algorithm). Can you expand on this? What is sorting algorithm? Sorting algorithm = a computer algorithm to sort a list of objects. Well pretend you just have 2 GB of data (for simplicity, assume they are integers) and 1 GB of memory, since the technique is the same. And pretend you want to sort these integers in increasing order. What would you do? Like, what's the first idea that comes to your mind? Show More Responses You do an on disk merge sort, bring chunks in to memory and sort using quick sort, then had the sorted data in to buckets (files). When your done merge them using a merge sort. Yep, exactly. External sort bucket sort. Sort each bucket, then merge. Mark |

### 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. |

Consider an X x Y array of 1's and 0s. The X axis represents "influences" meaning that X influences Y. So, for example, if $array[3,7] is 1 that means that 3 influences 7. An "influencer" is someone who influences every other person, but is not influenced by any other member. Given such an array, write a function to determine whether or not an "influencer" exists in the array. 12 AnswersThis was a tough one that forces you to consider how best to traverse the array and eliminate possibilities as soon as possible. Not_Influencers[n] = 0; //Make all elements 0 for (i = 0 ; i< n ; i++){ if(Not_Influencers[i] == 1) continue; row_sum = find_row_sum(a[i]); if(row_sum == n-1 && find_col_sum(i) == 0) return Found; for(j = i; j < i; j++) if (a[j] == 1) Not_Influencers[j] = 1; } X should be equal to Y, right? Show More Responses //if vec[i][j] == 0 then i is not an influence //if vec[i][j] == 1 then j is not an influence //so time complexity is O(n) bool find_influences(vector > &vec) { int n = vec.size(); vector not_influence(n); for (int i = 0; i = 0; --j) { if (!vec[i][j]) { break; } not_influence[j] = 1; } if (j < 0) { return true; } } not_influence[i] = 1; } return false; } Run a BFS or DFS. For each node keep going to influencer. Find a node which can be reach by all nodes. Sort of finding sink node. public static int influencer(final int[][] jobs, final int r, final int c) { int[] degree_in = new int[jobs.length]; int[] degree_out = new int[jobs.length]; for (int i = 0; i < r; ++i) { for (int j = 0; j < c; ++j) { if(jobs[i][j] == 1) { // i influences j degree_out[i]++; degree_in[j]++; } } } for (int i = 0; i < r; ++i) { if (degree_out[i] == r - 1 && degree_in[i] == 0) { return i; } } return -1; } Consider the input as Graph given in adjaceny matrix representation. Find whether a semi-eulerian path is present in the graph or not. Take the XOR product of the original matrix with the transposed matrix and sum by row. If any row counts equal the rank then they are influencers. private static boolean hasInfluencer(int[][] matrix) { if (matrix == null) return false; if (matrix.length == 0) return false; boolean result = false; for (int i=0; i the XOR suggestion I think is incomplete. The condition sum(row_influencer) = 1 and sum(column_influencer) = N so a simple matrix multiplication with the transposed should give for the vector v[influencer] = N and v[N-influencer] = 1. I assume influencer influences himself. def find_influencer(matrix): for row in range(len(matrix)): following_none = not any(matrix[row]) if not following_none: continue all_following = True for r_no in range(len(matrix)): if not row == r_no: continue if not matrix[r_no][row]: all_following = False break if all_following: return row return -1 Here is a different view. Please comment if you find any issues with the logic. 1st. condition: An influencer can not be influenced by any one. Let's say the in a matrix of [x.y], there is an influencer with index 2. So, the column=2 (3rd column) in the matrix must be all 0s, since the influencer can not be influenced. Step 1: Find a column with all 0s. If found, remember the column index or there is no influencer. Let's say, it is m Second condition: An influencer must have influenced everyone. So, in our example: row=2 (third row) must be all 1s except for column=2, since influencer can not even influence self. Step 2: Check row=m and find that all values are 1 except for [m][m]. If found, we have an influencer. |

### Systems Software Engineer at NVIDIA was asked...

Given a page size and a number, align the number with the nearest page. (Note: This was a phone interview question. The interviewer and I used an online document to share ideas about this problem. 5 Answers//naive solution: int getAlignedValue(int pageSize, int valueToAlign) { int index = valueToAlign/pageSize; return index * pageSize; } //faster solution: int getAlignedValue_Fast(int pageSize, int valueToAlign) { return valueToAlign & !(pageSize-1); } I think that at the faster solution you mean int getAlignedValue_Fast(int pageSize, int valueToAlign) { return valueToAlign & ~(pageSize-1); } Note: There is a difference between !(pageSize-1) and ~(pageSize-1) ~(0x11) is 0xee !(0x11) is 0 @The Dude Good catch! I didn't think about that. (Fortunately, I didn't have to execute the code in the interview--I just typed it in a program similar to Google Docs.) Thanks! Show More Responses I just wanted to point out that the "faster solution" only works if the pageSize is assumed to be a power of 2. For example, suppose pageSize = 10 (or 01010 in binary), and valueToAlign = 24 (or 11000 in binary), then the fast method would give 16, but it should be 20. Anyways, thanks for posting the question and solution. @observer I see how the mask works out for the alignment, why it is works mathematically? Thanks |

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

If you want to distribute a large file (gigabytes) in a large (100+ machines) park how do you do it? 5 AnswersFirst I mentioned rsync, then shell scripts with lists of machines that copy the file via FTP or SFTP. Also dividing the network into a tree of machines that copy their file on to child-nodes would be possible. You could also split the files into smaller pieces and speed up the process this way. The problem may be nodes that are down or slow. Finally you could send the small pieces to random nodes until the big file has arrived everywhere. Bittorrent! Or via some gossip algo Since you have control over these machines and their network, you can impose the requirement of multicast support. Multicast file distribution is not uncommon. There will be some overhead for retries, but it should otherwise scale well. Show More Responses You distribute the file in tree-like fashion and keep the total number of copying tasks at any moment under a threshold because otherwise you slow down the network to a halting point. Assuming you did not reserve a VLAN for the purpose of isolating your regular activities.. I would schedule the whole process at a good time (middle of night?). Use multicast if possible. And pace the data rate to a minimum. But, why the hack didn't you isolate your regular internal network traffic from service update traffic using VLAN? |

If you have a deck of cards split into 4 piles and was offered 1:1 odds to draw a face card (J Q K A) from at least one of the piles, would you take the game? Why or why not? 4 AnswersNo, basic statistics I'm no expert but I don't see it that way. You lose the game if you draw non-face cards from all 4 piles. The probability of that is 39/52*38/51*37/50*36/49 = 30%. So you have a 70% chance of winning the game. Yes, play the game at 1:1 odds. There are 16 face cards and 4 equal piles of 13 cards. By adding the probabilities of drawing a face card from at least 1 pile, you get 16/13. (1/13 + 1/13 + 1/13 + 13/13, or 4/13 + 4/13 + 4/13 + 4/13, and so on)...Doesn't matter how the face cards are arranged in the 4 piles. Thus, you would be willing to play the game at 1:1 odds. Show More Responses If there are 4 piles and you can look at all of them then it's obvious that you're going to take it - all the cards are there. If the question is to take the top card of each of the piles, then it's equivalent to finding the probability of a face card in 4 cards dealt. That is equal to 78.25%. So you would take the bet. (Total = 52 choose 4, Not Wanted = 36 choose 4, P(A face card) = 1-Total/Not Wanted) This is different from the answer given by the previous person because the numerator is wrong: he started at 39 when there are in fact 36 non-face cards (16 face cards - 52-16=36) If, however, the question is to pick one of the piles and then see if it has a face card, it is equivalent to randomly shuffling the deck and seeing if there is at least one face card in the first 13 cards. The probability of not having a face card is 0.363% and thus, the probability of having a face card is 99.637% - this means you should take the bet. So while the question can be interpreted in different ways, you should find it that taking the bet is a good proposition. Another way to look at it is as follows: if we assume sampling with replacement, to make calculations easy, we basically have 4 (or 13, depending on how you view it), chances to pick at least one card with probability 4/13 of the deck. This means that the probability of what is asked is almost equal to 1-(9/13)^4=77.04% (really close to the first case) or almost equal to 1-(9/13)^13=99.16% (also really close to the first number). |

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

Write a function that finds the square root of a decimal number. 4 AnswersA binary search with a constraint for precision. We should also take care of the interval (0.00, 1.00). // iterative (function(n){ var lo=0; var hi=n; var tries=500; var prev; while(tries--){ var curr=hi-((hi-lo)/2); var prd=curr*curr; if(prd===n || prev==curr){ break; } prd>n ? hi=curr : lo=curr; prev=curr; } console.log(curr, curr*curr, 500-tries) })(64) // recursive with closure use (function(n){ var lo=0; var hi=n; var tries=500; var prev; function rec(){ var curr=hi-((hi-lo)/2); var prd=curr*curr; if(prd===n || prev==curr || !tries--){ return curr; } prd>n ? hi=curr : lo=curr; prev=curr; return rec() } var result = rec(); console.log(result, result*result, 500-tries) })(25) Show More Responses For the above, I would set my high to be the max(x, 1), Let say's one call any of your functions with 1/4, or with any 0 epsilon) && (epsilon 100) return; return guess; }) |