About Technical Interview Questions
Technical interview questions in a placement paper are about how much work a program does: the comparisons a search makes, the swaps a sort makes, the depth a recursion reaches, the keys that must collide in a hash table, the times a nested loop runs, the connections between n machines, the multiplications in a matrix product and the number of subsets of a set. This topic covers that ground on one page, with the counting that decides the answer.
What you need to understand
- Big O describes how the work grows with the size of the input, not how long it takes on one machine. A constant factor is ignored, so an algorithm that takes twice as long but scales better is still the better choice for large inputs.
- The common growth rates in order are constant, logarithmic, linear, n log n, quadratic, cubic and exponential. Moving one place down that list matters more than any constant factor.
- An array gives constant time access to any element and is the best structure when the size is known and the data is read more than written. Inserting at the front of an array costs a move of everything else.
- A linked list inserts and removes in constant time once the position is known, but it has to be walked from one end to reach that position, so a search is linear.
- A stack is last in, first out and a queue is first in, first out. Both do their work in constant time, and both appear constantly in interview questions about parsing, scheduling and searching.
- A hash table gives average constant time lookup and insertion. Its worst case is linear, and that happens when every key lands in one slot.
- The pigeonhole principle guarantees collisions: with n keys in m slots, some slot holds at least the keys divided by the slots, rounded up. That is why a load factor above about three quarters makes a table slow.
- A balanced binary search tree gives logarithmic search, insertion and removal, and it keeps the data in order, which is what a hash table cannot do.
- A linear search makes about half as many comparisons on average as in the worst case: (n + 1) / 2 against n.
- A binary search makes about the logarithm to base two of n comparisons, but it needs the data to be sorted in the first place - and sorting costs more than the search saves unless the list is searched many times.
- Sorting by comparing every pair takes n (n - 1) / 2 comparisons, which is quadratic. The good comparison sorts, such as merge sort and heapsort, take of the order of n log n, which is far less for a long list.
- Counting pairs is the single most useful formula in these questions: n items have n (n - 1) / 2 pairs, and it counts the comparisons in a pair-by-pair sort, the handshakes in a room and the cables in a fully connected network.
- Two nested loops over the same n give n squared operations, because the inner loop runs in full for every trip of the outer. That is the difference between an approach that scales and one that does not.
- A recursive function that halves its input reaches the base case in the logarithm to base two of n steps, so it copes with a million items in about twenty levels.
- A set of n elements has two to the power of n subsets, because each element is independently in or out. That is what makes an exhaustive search over subsets impossible beyond a few dozen elements.
How to work through these questions
- Say the size of the input out loud and name the variable. Almost every one of these questions is a count of operations in terms of n, and writing n down makes the count obvious.
- Count the pairs before anything else: n (n - 1) / 2 comes up for comparisons, handshakes, cables and connections, and recognising it saves the whole derivation.
- For nested loops, ask how many times the inner loop runs for one trip of the outer, and multiply. Adding the two counts instead of multiplying is the commonest error.
- For a recursion, ask how much smaller the input gets at each call. Halving gives logarithmic depth, subtracting one gives linear depth, and that single question decides the complexity.
- For a hash table question, divide the keys by the slots and round up - the guarantee is a ceiling, not a floor.
- Check the answer against the growth rate. A quadratic algorithm on a thousand items runs about a million operations, and a question whose answer is a hundred is describing something else.
Mistakes that cost marks
- Using the sum formula n (n + 1) / 2 where the pair formula n (n - 1) / 2 is wanted. An item is never paired with itself, so the count is the sum up to n - 1, not to n.
- Adding the two loop counts instead of multiplying them, which turns a quadratic algorithm into a linear one on paper.
- Quoting the worst case of a linear search as the average, which doubles the figure. The average is (n + 1) / 2 and the worst case is n.
- Rounding the collision count down instead of up. The guarantee is that some slot holds at least the ceiling, not the floor.
- Forgetting that a binary search needs sorted data, and quoting its logarithmic cost without the cost of the sort that made it possible.
- Confusing constant time with fast. A constant time operation can still be slow, and a linear operation on a short list can still beat a logarithmic one with a large constant.
- Counting the levels of a halving recursion as n / 2 rather than the logarithm. Doubling the input adds one level, not twice as many.
- Leaving the matrix product as rows times columns and forgetting the shared dimension, which is the one that decides how many multiplications each entry takes.
Worked example
A list holds 100 items and a linear search is used. How many comparisons does it make on average? A bubble sort is run on the same list: how many comparisons does it make?
- For the search, the item is equally likely to be anywhere. One comparison if it is first, a hundred if it is last, so the average is half of (100 + 1).
- That is 50.5 comparisons on average. The worst case is 100, which is worth quoting alongside - interviewers usually want both figures.
- For the sort, count the pairs in a list of 100 items: 100 x 99 / 2 = 4950 comparisons.
- Notice how much larger that is than the search. A quadratic sort on a hundred items does about five thousand comparisons, while on a thousand items it does about half a million - which is why the n log n sorts are used in practice.
- The two answers together are the whole of the topic: a search is linear or logarithmic, and a comparison sort is at best n log n. Everything else is a detail of the structure being used.
Answer: 50.5 comparisons on average for the search; 4950 comparisons for the bubble sort
Practice questions with answers
A few Technical Interview Questions questions with the full solution shown, so you can see
how the method is applied before you attempt the timed set.
Question 1
A list holds 100 items and a linear search is used to look for one of them. On average, how many comparisons does it take, assuming the item is in the list?
-
A
50
-
B
99/2
-
C
100
-
D
101/2
Answer: Option D — with explanation
A linear search looks at the first item, then the second, and so on. If the item is equally likely to be anywhere in the list, the number of comparisons is one for the first position, two for the second, and n for the last, and the average of those is (n + 1) / 2.
For 100 items that is (100 + 1) / 2 = 101/2 comparisons.
The worst case is n comparisons, which happens when the item is the last one or is not in the list at all. Quoting the worst case as the average is the usual slip, and it makes the algorithm look twice as slow as it is.
Common mistakes
- 50 is not the answer: 50
- 99/2 is not the answer: 99/2
- 100 is not the answer: 100
Question 2
A bubble sort is run on a list of 50 items. How many comparisons does it make before the list is sorted?
-
A
2500
-
B
1225
-
C
1275
-
D
2450
Answer: Option B — with explanation
Each pass of a bubble sort compares neighbouring pairs from one end of the list to the other, and it puts one more item in its final place. Counting the comparisons is therefore counting the number of pairs in a list of n items, which is n (n - 1) / 2.
For 50 items that is 50 x 49 / 2 = 1225 comparisons.
The sum n (n + 1) / 2 counts the numbers from one to n, and it appears in the other answers because it is the formula people remember. The pair formula is that sum with n replaced by n - 1, because an item is never compared with itself.
Common mistakes
- 2450 is not the answer: 2450
- 1275 is not the answer: 1275
- 2500 is not the answer: 2500
Question 3
A recursive function calls itself on half the input each time until the size is one. Starting with an input of 32, how many levels deep is the recursion?
Answer: Option C — with explanation
Each level of the recursion halves what is left, so the depth is the number of times the size can be halved before it reaches one - which is the power of two that the size is, or the logarithm to base two of it.
32 is 2 to the 5, so the recursion goes 5 levels deep.
This is why a halving algorithm is described as logarithmic: doubling the size of the input adds exactly one level, rather than doubling the work. A recursive function that halves its input therefore copes with a million items in about twenty levels.
Common mistakes
- 10 is not the answer: 10
- 6 is not the answer: 6
- 4 is not the answer: 4
Question 4
With 225 keys in a hash table of 100 slots, what is the least number of keys that have to end up in the same slot?
Answer: Option B — with explanation
This is the pigeonhole principle. If every slot held at most one fewer than the answer, the table could hold fewer keys than it does, so some slot must hold at least the number found by dividing the keys by the slots and rounding up.
Here 225 keys divided by 100 slots is 2.25, and rounding up gives 3 keys in some one slot.
The rounding up is the whole of it. Dividing and rounding down gives the number that every slot holds on average, and the guarantee is one more than that whenever the division is not exact.
Common mistakes
- 100 is not the answer: 100
- 2 is not the answer: 2
- 125 is not the answer: 125
Question 5
A piece of code has an outer loop that runs 200 times and an inner loop that also runs 200 times, with the work done inside the inner loop. How many times is that work done?
-
A
40000
-
B
400
-
C
200
-
D
20000
Answer: Option A — with explanation
The inner loop runs in full each time the outer loop goes round, so the work is not added but multiplied: n times n is n squared.
That is 200 x 200 = 40000 executions of the body.
It is the difference between a linear and a quadratic algorithm, and it is why an approach that works for a few hundred items can be hopeless for a few hundred thousand. Doubling the size of the input multiplies the work by four, and multiplying the size by ten multiplies it by a hundred.
Common mistakes
- 400 is not the answer: 400
- 200 is not the answer: 200
- 20000 is not the answer: 20000
Frequently asked questions
Why is n (n - 1) / 2 so important?
Because it counts the pairs in a collection of n things, and a great many questions are really questions about pairs: comparisons in a sort, handshakes in a room, cables between computers and comparisons between all pairs of items. Recognising the shape saves deriving it each time.
What is the difference between the average case and the worst case?
The average case assumes the input is typical - for a linear search, that the item is equally likely to be anywhere - while the worst case assumes the input is as unfavourable as possible. Interviewers usually want both, and the worst case is the safer figure to design to.
Why is a hash table not always better than a tree?
Because a hash table keeps no order. It answers questions about exact keys in constant time but cannot answer range queries or give you the items in sorted order, and a balanced tree can do both in logarithmic time.
How deep can a recursion safely go?
Only as deep as the call stack allows, which is usually a few thousand frames in a language with a fixed stack. That is why a recursion that halves its input is safe and one that reduces by a single step is not - the first is logarithmic and the second is linear.
Does the order of multiplying a chain of matrices matter?
Enormously. The cost of each step is rows times shared dimension times columns, so putting the smallest shared dimension in the middle of the chain can cut the work by orders of magnitude. That is why a library reorders the product rather than working left to right.
What does it mean for an algorithm to be exponential?
That the work doubles every time the input grows by a fixed amount, as with the two to the power of n subsets of a set. Such an algorithm is fine for twenty elements and hopeless for a hundred, and recognising that early is what saves a lot of wasted effort.
