# Computer science interview questions: state the assumptions first

> Five original computer science interview problems on complexity, recursion, binary search and data representation, with what each tests and how to reason.

[Formatted version of this page](https://www.frontiervue.com/interviews/questions/computer-science)

A computer science interview is not only about whether you can write code. It is about whether you can say why a solution works, what it costs, and where it breaks. These five problems are **original practice**; each approach starts with assumptions before the algorithm.

## Key takeaways
- Ask about input size and constraints before choosing an algorithm.
- Being able to state time and space costs counts for more than elegant code.
- Offer a counterexample to show you know where your solution breaks.

### Computer science interviews at a glance

| Item | Value |
| --- | --- |
| Format | Verbal design, changing constraints |
| Question style | Algorithms, data structures, edge cases |
| What matters | Assumptions, complexity, correctness |
| How to prepare | Name the cost and a counterexample |

> You may be asked to write pseudocode on paper or a shared whiteboard. State the input, output and edge cases first.

> What the format looks like: The interview usually grows one problem in stages: first a naive solution, then can you make it faster, then what happens when the input or the memory limit changes. Whether you write code varies, but explaining complexity aloud is almost always part of it.

## Contents
1. What a computer science interview is testing
2. How to use these five problems

## 1. What a computer science interview is testing

The interviewer rarely expects the optimal solution immediately. They start with a small example, ask for a naive method, then tighten the constraints: what if there are a million items? What if you can only read sequentially? What if it does not fit in memory?

The real test is formalising the problem: what is the input, what is the output, which operations are allowed, and what is the worst case. Once those are clear, the algorithm often suggests itself.

> A reliable opening: **“I will assume the input is …, and if that assumption fails, the approach changes to …”** Interviewers notice when you know an assumption is there.

## 2. How to use these five problems

1. **Start with the naive solution**
Do not reach for the optimum first. Give a solution you know is correct, then say where it is slow.

2. **Label the cost** (Must say)
State the time and space cost of each step, and which one becomes the bottleneck first.

3. **Find a counterexample**
Empty input, duplicates, already sorted, very large or very small: try at least two.

4. **Improve by one step**
Usually one data-structure change or one invariant is enough. You rarely need to start over.

## 5 Computer Science interview problems

Every problem below is original practice written for this site, not a past paper. Read the question, try it aloud, then compare your reasoning with the approach.

### Question 1

**Prompt:** You have a sorted list of one million integers. To decide whether a value is present, how many comparisons does binary search need at most? What changes if the list is stored as a linked list?

**What this tests：** This tests logarithmic complexity and the hidden precondition of binary search. Many candidates can recite O(log n) but cannot say that the method depends on random access.

**How to work through it：**
1. Since 2²⁰ = 1,048,576, which is just over a million, at most about 20 comparisons are needed.
2. A linked list cannot find the middle in O(1). Walking to the midpoint costs O(n) each time, so the binary-search structure degrades to O(n) or worse.
3. Alternatives: convert to an array first, or use a balanced tree or skip list that supports ordered search. State the extra space and preprocessing cost.

**The likely follow-up:** If the data sits on a hard drive and is read in blocks, is binary search still the right choice?

### Question 2

**Prompt:** Describe an algorithm that finds the first character that appears twice in a string. What are its time and space complexity? How would you test it?

**What this tests：** This tests hash sets and edge cases. The problem is simple, but “first” and “repeated” both need precise definitions, and the test design reveals engineering habits.

**How to work through it：**
1. Scan left to right and keep a set of characters seen so far. Return a character when it is already in the set; otherwise add it.
2. The time cost is O(n) and the space cost is O(k), where k is the alphabet size. For a fixed alphabet this is O(1).
3. Test the empty string, no repeats, a repeat at the start, a repeat at the end, case differences and Unicode. Decide first whether “repeated” is case-sensitive.

**The likely follow-up:** If the string contains only 26 lowercase letters, can you do it with O(1) extra space?

### Question 3

**Prompt:** What does this function compute? `f(n) = 1` when `n = 0`, otherwise `f(n) = n × f(n − 1)`. Rewrite it without recursion. If n is very large, what breaks first?

**What this tests：** This tests recursion, the call stack and numeric growth. The interviewer wants to see that recursion depth and integer overflow are two different limits.

**How to work through it：**
1. It computes the factorial, f(n) = n!. Use a loop from 1 to n and keep the result in one variable.
2. The recursive version hits the call-stack limit first. The iterative version avoids that, but the result overflows a fixed-width integer much sooner.
3. If you only need the last digit or a value modulo some number, reduce at every step and avoid big integers entirely.

**The likely follow-up:** Without computing 2026!, how would you find its last digit?

### Question 4

**Prompt:** Two people each hold a sorted list of 1,000 numbers. You may only ask “what is the k-th number in your list?”. Using as few questions as possible, find the median of the combined 2,000 numbers.

**What this tests：** This tests binary search over a partition and invariants. The point is not to merge the lists, but to see that the median is determined by a split point.

**How to work through it：**
1. The combined length is 2,000, so the median is the average of the 1,000th and 1,001st values.
2. Binary-search a split i in A and take j = 1000 − i in B, so the left side has 1,000 values. Check that max(left) ≤ min(right).
3. Once the condition holds, the median comes from the largest left value and the smallest right value. Each question halves the range, so about ten are enough.

**The likely follow-up:** If the two lists have different lengths, how does the partition condition change?

### Question 5

**Prompt:** A census records the exact age in years of 50 million people, from 0 to 120. How would you store the data if memory is tight? How would you answer “how many people are aged 30 to 40?” quickly?

**What this tests：** This tests data representation and the insight that aggregate questions do not require storing every individual. The first instinct is often 50 million records, which ignores that only counts are needed.

**How to work through it：**
1. If you only need the distribution, use 121 counters of 32 bits each: under 500 bytes in total. Increment one counter per person.
2. If individual records must be kept, each age needs only 7 bits (2⁷ = 128), far less than a 32-bit integer.
3. For range queries, build prefix sums over the 121 counters. Any interval is then the difference of two prefix values, answered in O(1).

**The likely follow-up:** If you also need the age distribution by region, how does the shape of the counter array change?

## Questions
**Do I need to be able to write code?**

Most interviews focus on verbal design and pseudocode rather than complete runnable code. You do need to write loops, conditions and data-structure operations clearly, and explain what each one costs.
**Am I disadvantaged without a competition background?**

Competition experience helps but is not required. Interviewers care more about whether you can break a problem down, test your assumptions and improve with a hint. Those skills can be built through repeated practice aloud.

## Official sources
- [University of Oxford: a guide to undergraduate interviews](https://www.ox.ac.uk/admissions/undergraduate/applying/guide-for-applicants/interviews)
- [University of Oxford: admissions timeline (decisions on 12 January 2027)](https://www.ox.ac.uk/admissions/undergraduate/applying/admissions-timeline)
- [University of Cambridge: interviews (main period 7 to 18 December 2026)](https://www.undergraduate.study.cam.ac.uk/apply/after/cambridge-interviews)
- [University of Cambridge: how to prepare for your interview](https://www.undergraduate.study.cam.ac.uk/apply/after/interview-preparation)

## Related pages
- [All subject interview questions](https://www.frontiervue.com/interviews/questions)
- [Mathematics interview questions](https://www.frontiervue.com/interviews/questions/mathematics)
- [Engineering interview questions](https://www.frontiervue.com/interviews/questions/engineering)
- [Oxford interviews](https://www.frontiervue.com/interviews/oxford)
- [Cambridge interviews](https://www.frontiervue.com/interviews/cambridge)
- [How to read a TMUA score](https://www.frontiervue.com/results/tmua)
