100 hard software engineering interview questions
by Jerome Kehrli
Posted on Friday Dec 06, 2013 at 04:11PM in Computer Science
For some reasons that I'd rather keep private, I got interested in the kind of questions google, microsoft, amazon and other tech companies are asking to candidate during the recruitment process. Most of these questions are oriented towards algorithmics or mathematics. Some other are logic questions or puzzles the candidate is expected to be able to solve in a dozen of minutes in front of the interviewer.
If found various sites online providing lists of typical interview questions. Other sites are discussing topics like "the ten toughest questions asked by google" or by microsoft, etc.
Then I wondered how many of them I could answer on my own without help. The truth is that while I can answer most of these questions by myself, I still needed help for almost as much as half of them.
Anyway, I have collected my answers to a hundred of these questions below.
For the questions for which I needed some help to build an answer, I clearly indicate the source where I found it.
1. You are given a the source to a application which is crashing when run. After running it 10 times in a debugger, you find it never crashes in the same place. The application is single threaded, and uses only the C standard library. What programming errors could be causing this crash? How would you test each one?
2. You have a stream of infinite queries (ie: real time Google search queries that people are entering). Describe how you would go about finding a good estimate of 1000 samples from this never ending set of data and then write code for it.
3. Given a large network of computers, each keeping log files of visited urls, find the top ten of the most visited urls.
(i.e. have many large <string (url) -> int (visits)> maps, calculate implicitly <string (url) -> int (sum of visits among all distributed maps)>, and get the top ten in the combined map)
The result list must be exact, and the maps are too large to transmit over the network (especially sending all of them to a central server or using MapReduce directly, is not allowed)
4. Merge two sorted linked lists
When you merge two "linked" lists, there tend to be problems with "conflicts" between the lists (because they have a specific order to them and you are messing with the order).
6. If we had a list of n nodes, what are the maximum number of edges there can be for a directed acyclic graph?
You have to draw lines between nodes, but never have a clear path of returning to the original node regardless of where you're starting.
10. Write a program to compute if one string is a rotation of another
For example, "strings" usually refer to lines of letters, words or something that is meant to be printed and seen. But they can also refer to matrices (a two-dimensional object) and other kinds of objects.
You have to check if you can rotate them and check them against existing strings
17. You are given a number of identical balls and a building with N floors. You know that there is an integer X < N such that the ball will break if it is dropped
from any floor X or higher but will remain intact if dropped from a floor below X.
Given K balls and N how would you compute the minimum number of ball drops that are required to determine X in the worst-case?
25.c. Given an array, find the longest (non necessarily continuous) increasing subsequence.
Not to be confused with problem 66.c which adds a "continuous" constraint.
30.a. The probability of a car passing a certain intersection in a 20 minute windows is 0.9. What is the probability of a car passing the intersection in a 5 minute window? (Assuming a constant probability throughout)
34. Tree search algorithms. Write BFS and DFS code, explain run time and space requirements. Modify the code to handle trees with weighted edges and loops with BFS and DFS, make the code print out path to goal state.
37.b. You have 5 jars of pills. Each pill weighs 10 gram, except for contaminated pills contained in one jar, where each pill weighs 9 gm. Given a scale, how could you tell which jar had the contaminated pills in just one measurement?
37.c. You have 12 balls. All of them are identical except one, which is either heavier or lighter than the rest - it is either hollow while the rest are solid, or solid while the rest are hollow. You have a simple two-armed scale, and are permitted three weighings. Can you identify the odd ball, and determine whether it is hollow or solid.
38. There is an array A[N] of N numbers. You have to compose an array Output[N] such that Output[i] will be equal to multiplication of all the elements of A[N] except A[i]. For example Output will be multiplication of A to A[N-1] and Output will be multiplication of A and from A to A[N-1]. Solve it without division operator and in O(n).
39. Find or determine non existence of a number in a sorted list of N numbers where the numbers range over M, M>> N and N large enough to span multiple disks. Algorithm to beat O(log n) bonus points for constant time algorithm.
40. How do you put a Binary Search Tree in an array in a efficient manner.
Hint : If the node is stored at the ith position and its children are at 2i and 2i+1(I mean level order wise) Its not the most efficient way.
41. How do you find out the fifth maximum element in an Binary Search Tree in efficient manner.
Note: You should not use use any extra space. i.e sorting Binary Search Tree and storing the results in an array and listing out the fifth element.
53. Given an array whose elements are sorted, return the index of a the first occurrence of a specific integer. Do this in sub-linear time. I.e. do not just go through each element searching for that element.
[Binary Search algo]
63. You are given with three sorted arrays ( in ascending order), you are required to find a triplet (one element from each array) such that distance is minimum.
Distance is defined like this : If a[i], b[j] and c[k] are three elements then distance=max(abs(a[i]-b[j]),abs(a[i]-c[k]),abs(b[j]-c[k])).
Please give a solution in O(n) time complexity.
66.b. Given an array, find the longest continuous(!) increasing subsequence.
Not to be confused with problem 25.c which releases the "continuous" constraint.
70. There are 4 men who want to cross a bridge. They all begin on the same side. You have 17 minutes to get all of them across to the other side. It is night. There is one flashlight. A maximum of two people can cross at one time. Any party who crosses, either 1 or 2 people, must have the flashlight with them. The flashlight must be walked back and forth, it cannot be thrown, etc. Each man walks at a different speed. A pair must walk together at the rate of the slower mans pace.
Man 1: 1 minute to cross
Man 2: 2 minutes to cross
Man 3: 5 minutes to cross
Man 4: 10 minutes to cross
79. A character set has 1 and 2 byte characters. One byte characters have 0 as the first bit. You just keep accumulating the characters in a buffer.
Suppose at some point the user types a backspace, how can you remove the character efficiently.
(Note: You can't store the last character typed because the user can type in arbitrarily many backspaces)
89. You have five pirates, ranked from 5 to 1 in descending order. The top pirate has the right to propose how 100 gold coins should be divided among them. But the others get to vote on his plan, and if fewer than half agree with him, he gets killed.
How should he allocate the gold in order to maximize his share but live to enjoy it? (Hint: One pirate ends up with 98 percent of the gold.)
90. Every man in a village of 100 married couples has cheated on his wife. Every wife in the village instantly knows when a man other than her husband has cheated, but does not know when her own husband has. The village has a law that does not allow for adultery. Any wife who can prove that her husband is unfaithful must kill him that very day. The women of the village would never disobey this law. One day, the queen of the village visits and announces that at least one husband has been unfaithful. What happens?
94.a. Implement a special type of integer iterator. It will be a wrapper over a regular integer iterator, except that this iterator will only iterate over negative numbers.
Show how you'd write the next() and hasNext() functions to work with the next negative integer instead of just the next integer.
95. You need to check that your friend, Bob, has your correct phone number, but you cannot ask him directly. You must write the question on a card which and give it to Eve who will take the card to Bob and return the answer to you. What must you write on the card, besides the question, to ensure Bob can encode the message so that Eve cannot read your phone number?
97. Write a function (with helper functions if needed) called toExcel that takes an excel column value (A,B,C,D,...,AA,AB,AC,...,AAA,..) and returns a corresponding integer value (A=1,B=2,...,AA=26,...)?
99. How Old Are My Children? Knowing:
A) The product of their ages is 72 and the sum of their ages is the same as your birth date.
B) ... I still don't know .
A) My eldest kid just started taking piano lessons.
B) Now I know :-)
Don't hesitate to leave a comment or contact me should you see any error in here, or any improvement, better solution, etc. and I'll update the post accordingly.