# Technical Interview Questions

interview questions shared by candidates

## Technical Interview Questions

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

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

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

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

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

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

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

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

You are given a random binary tree 5 / \ 4 9 / \ / \ 3 5 6 8 Write code to print it out in order level ie 5 4 9 3 5 6 8 The tree need not be balanced. Write all the datastructures for the tree and make sure that you print newlines after each level. Also write test cases to test your code. 4 AnswersSolution is to do a BFS on the binary tree. Now in order to print newlines, the datastructure inserted in the BFS queue also needs to contain level information which must be correctly updated while doing an insert in the queue. Here's a Java implementation (skipping imports etc.): public class Pair { F first; S second; public Pair(F first, S second) { this.first = first; this.second = second; } } public class Node { public int value; public Node left; public Node right; public Node() { } public Node(int value, Node left, Node right) { this.value = value; this.left = left; this.right = right; } public static void printTreeLevels(Node root) { Queue> q = new LinkedList>(); q.add(new Pair(root, 1)); int level = 1; while(!q.isEmpty()) { Pair pair = q.remove(); Node node = pair.first; if(pair.second > level) { System.out.println(""); level = pair.second; } System.out.print(node.value + " "); if(node.left != null) q.add(new Pair(node.left,(pair.second+1))); if(node.right != null) q.add(new Pair(node.right,(pair.second+1))); } } } package com.google.interview2; import java.util.LinkedList; import java.util.Queue; public class BinaryTree { public int value; public BinaryTree left; public BinaryTree right; public int distance; public BinaryTree(int value, BinaryTree left, BinaryTree right){ this.value = value; this.left = left; this.right = right; } public void printTree(){ Queue q = new LinkedList(); q.add(this); this.distance = 0; int currDistance = 0; while (!q.isEmpty()){ BinaryTree head = q.poll(); if (head.left != null){ head.left.distance = head.distance+1; q.add(head.left); } if (head.right != null){ head.right.distance = head.distance+1; q.add(head.right); } if (head.distance != currDistance){ System.out.println(); ++currDistance; } System.out.print(head.value); } } public static void main(String[] args){ //test with a full tree BinaryTree b3 = new BinaryTree(3, null,null); BinaryTree b5 = new BinaryTree(5, null,null); BinaryTree b6 = new BinaryTree(6, null,null); BinaryTree b8 = new BinaryTree(8, null,null); BinaryTree b4 = new BinaryTree(4, b3,b5); BinaryTree b9 = new BinaryTree(9, b6,b8); BinaryTree head = new BinaryTree(5, b4,b9); head.printTree(); System.out.println(); //test with not full and balanced tree BinaryTree b7 = new BinaryTree(7, null,null); BinaryTree b10 = new BinaryTree(10, null,null); BinaryTree b8sec = new BinaryTree(8, b7,b10); BinaryTree b9sec = new BinaryTree(9, null,b8sec); BinaryTree b5sec = new BinaryTree(5, null,null); BinaryTree b4sec= new BinaryTree(4, null,b5sec); BinaryTree head2 = new BinaryTree(5, b4sec,b9sec); head2.printTree(); } } Show More Responses Instead of storing level information use 2 queues Q1 for level i Q2 for level i + 1 |

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

Reverse a string in-place. 4 Answersfor(i = 0; i < strlen(str); i++) { temp = str[i]; str[i] = str[strlen(str) - 1 - i]; str[strlen(str) - 1 - i] = temp; } @Rahul, Wouldn't the for condition be i < strlen(str)/2? that way if you had a string of length 5, it would run for i=0 and i=1, but it wouldn't bother doing i=2 since that is the middle element and doesn't need switching. Without the /2, you will reverse it, then re-reverse it again. For an even length (like 6) you'd want it to do swaps on i=0, i=1, and i=2, but not i=3 public static String reverseString(String s){ int len = s.length(); int temp = len; StringBuffer sb = new StringBuffer(); try { for(int i=1;i<len;i++){ sb.append(s.substring(temp-1,temp)); temp = temp -1; } }catch (Exception e){ System.out.println("Error: " + e); } return sb.append(s.substring(temp-1,temp)).toString(); } Show More Responses void reverse(char* str) { int len = strlen(str); char* end = str + len - 1; for(char* start = str; start > end; ++start, --end ) { char ch = *start; *start = *end; *end = ch; } } |