This page needs a newer browser to run its tools. You can still read everything here.

Data Structures & Algorithms (DSA) Module 6

Binary search and searching interview questions

Interview questions on binary search and searching: short warm-ups, then what each harder question tests, the first step of a good answer and its follow-ups.

8 questions: 2 warm-ups and 6 with model answers · Levels: Fresher to senior

Warm-up questions

Short questions with short answers, each answered in full.

Fresher to mid

bisect_left returns 4 for a value that is not in a sorted list. What does that 4 tell you, and what can you do with it?

Answered in the lesson Lower bound, upper bound and first-true search
Fresher to mid

In a rotated sorted array of distinct values, how do a[lo], a[mid] and a[hi] tell you which half is sorted?

Answered in the lesson Binary search on rotated, peaked and 2-D data

Questions with model answers

What each question tests, the first step of a good answer and the follow-ups to expect.

Fresher to mid

A colleague says two bound searches for the first and last position of x waste probes, and proposes one search that stops at any copy, then two short searches inside the range still open at that moment. Compare the probe counts on 10⁶ values, worst case and typical, and say which you would write.
What it tests

Counting the probes of two designs instead of guessing, knowing what C++'s equal_range does, and weighing a measured saving against simpler code.

First step

Count the plain design first: two bounds of at most ⌊log₂ 10⁶⌋ + 1 = 20 probes each, so at most 40. Then trace the proposal on a value that occurs once: when it stops at the copy, how wide is the range left for the two short searches?
Follow-ups
- What does C++'s std::equal_range do, and how many probes does it make?
- x fills half of the list. Which design wins now?
- How would you settle the question with a measurement instead of an argument?
From the lesson Lower bound, upper bound and first-true search
Model answer, Pro. Model answers open with any pass; prices are in the notice on this page.
Opening the model answers with your pass…
Model answers open with any MySmartCoPilot pass.
Pro pass · 1 week₹79$2.99
30 days₹179$5.99
1 year₹1,699$45
One payment; a pass never renews. The price shown is the total you pay: no fees or charges are added at checkout.
Passes can’t be bought right now, so the model answers can’t be opened at the moment. If you have a pass, enter your licence key.
Choose a pass I have a licence key
It also opens every other in-depth part in Learn and every Pro tool. Sales are final, except where the law gives you a right to withdraw, for example in the EU and the UK (refund policy).
In the answer:
- Model answer
- Follow-up answers
- Common mistakes
- Rubric
- Variants
- about 4 minutes
Mid to senior

You search 2,000 commits for the first one that broke a test. Broken commits always fail, but the test also fails on 5 % of runs of good commits, at random. What does a plain first-true search return, and how do you make the answer reliable at a known cost?
What it tests

Seeing that a flaky test breaks the monotone assumption, estimating the error of the search, and choosing a retry rule that bounds it with numbers.

First step

Count the checks first: about ⌈log₂ 2,001⌉ = 11 builds, roughly half of them on good commits. Each good commit looks broken with probability 0.05, and one false failure sends the search to an earlier commit. Work out the chance that none of those good runs fails.
Follow-ups
- How many runs per check bring the error below 0.1 %?
- The flaky failure prints a different message from the real one. What changes?
- Each build takes 20 minutes. How do you cut the waiting time?
From the lesson Lower bound, upper bound and first-true search
Model answer, Pro.
In the answer:
- Model answer
- Follow-up answers
- Common mistakes
- Rubric
- Variants
- about 4 minutes
Fresher to mid

A sorted list holds a day's 10⁵ train departure times in minutes after midnight. For 10⁶ queries, return the first departure at or after time t and the last one strictly before t. Write the searches, handle times before the first and after the last train, and give the total cost.
What it tests

Turning "at or after" and "strictly before" into the right bound, handling both ends of the list, and estimating the cost of a million queries.

First step

Translate the words into bounds: "at or after t" is the lower bound of t, the first time that is at least t, and "strictly before t" is the position just before it. Then list the two edge cases: the lower bound equals the length of the list, or it is 0.
Follow-ups
- After the last train, the first train of the next day should be returned. What changes?
- The queries arrive sorted by time. Can you avoid the searches?
- Which small tests would you write first?
From the lesson Lower bound, upper bound and first-true search
Model answer, Pro.
In the answer:
- Model answer
- Follow-up answers
- Common mistakes
- Rubric
- Variants
- about 3 minutes
Mid to senior

A ring buffer keeps 10⁶ events in time order from a moving start, and its timestamps have one-second resolution, so long runs of equal times are common. Your rotated search for a timestamp sometimes reads every entry. Explain why, show that no algorithm can always avoid it, and say what you would change.
What it tests

Seeing why ties break the sorted-half test, proving a linear lower bound with an adversary, and fixing the data or the access instead of the search.

First step

Find the comparison that stops working: with a[lo] == a[mid] == a[hi], neither half is known to be sorted. Then build a family of valid inputs, a long run of one time with a single different time placed anywhere, and ask what an algorithm learns from each read.
Follow-ups
- Is the search still fast when runs are short?
- The buffer stores its write position. What search is left to do?
- The timestamps get microsecond resolution and rarely repeat. Does the worst case still matter?
From the lesson Binary search on rotated, peaked and 2-D data
Model answer, Pro.
In the answer:
- Model answer
- Follow-up answers
- Common mistakes
- Rubric
- Variants
- about 4 minutes
Fresher to mid

Hourly prices of a product over 10⁵ hours are in an array. A teammate reports the highest price with the uphill binary search for a peak. When is the answer right, when is it wrong, and what does each correct approach cost?
What it tests

Telling a peak from the maximum, knowing which shapes of data guarantee a single peak, and costing a scan against a search.

First step

Write down what the uphill rule guarantees: a position at least as large as its neighbours, nothing more. Then draw a price series with two hills of different heights and trace the search: which hill does it climb, and why?
Follow-ups
- The prices are known to rise and then fall exactly once. Is the search enough now?
- The series has long flat stretches. What can go wrong?
- You must answer the maximum of many ranges of hours. What do you build?
From the lesson Binary search on rotated, peaked and 2-D data
Model answer, Pro.
In the answer:
- Model answer
- Follow-up answers
- Common mistakes
- Rubric
- Variants
- about 3 minutes
Mid to senior

A table of two-dimensional prefix sums of non-negative counts has 50 rows and 2 × 10⁶ columns, so it is sorted along every row and every column. Compare the staircase, a binary search in every row, and copying the table into one sorted array for 10⁴ queries "is p in the table?", by reads and memory, and choose.
What it tests

Costing three matrix searches from the shape, seeing that the staircase is linear in the long side, and weighing a one-off copy and sort against per-query work.

First step

Write each cost from the shape before choosing: the staircase reads up to r + c − 1 cells; a binary search in each of the r rows reads about r × (⌊log₂ c⌋ + 2); one sorted array of all r × c values must be built and sorted first. Put numbers on all three.
Follow-ups
- The queries ask how many cells are at most p instead. What changes?
- The table is 2 × 10⁶ rows by 50 columns instead. Does the choice change?
- The memory allows only the table itself. Which design is ruled out?
From the lesson Binary search on rotated, peaked and 2-D data
Model answer, Pro.
In the answer:
- Model answer
- Follow-up answers
- Common mistakes
- Rubric
- Variants
- about 3 minutes

All Data Structures & Algorithms (DSA) interview questions · The Data Structures & Algorithms (DSA) track

Warm-up questions

bisect_left returns 4 for a value that is not in a sorted list. What does that 4 tell you, and what can you do with it?

In a rotated sorted array of distinct values, how do a[lo], a[mid] and a[hi] tell you which half is sorted?

Questions with model answers

A colleague says two bound searches for the first and last position of x waste probes, and proposes one search that stops at any copy, then two short searches inside the range still open at that moment. Compare the probe counts on 10⁶ values, worst case and typical, and say which you would write.

You search 2,000 commits for the first one that broke a test. Broken commits always fail, but the test also fails on 5 % of runs of good commits, at random. What does a plain first-true search return, and how do you make the answer reliable at a known cost?

A sorted list holds a day's 10⁵ train departure times in minutes after midnight. For 10⁶ queries, return the first departure at or after time t and the last one strictly before t. Write the searches, handle times before the first and after the last train, and give the total cost.

Hourly prices of a product over 10⁵ hours are in an array. A teammate reports the highest price with the uphill binary search for a peak. When is the answer right, when is it wrong, and what does each correct approach cost?