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

Data Structures & Algorithms (DSA) Module 5

Sorting and selection interview questions

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

7 questions: 2 warm-ups and 5 with model answers · Levels: Fresher to senior

Warm-up questions

Short questions with short answers, each answered in full.

Fresher to mid

What do stable, in-place and adaptive mean for a sort?

Answered in the lesson Sorting: stability, in-place and adaptivity
Fresher

Which of selection, bubble and insertion sort are stable, and what makes selection sort unstable?

Answered in the lesson Selection, bubble and insertion sort

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 data table sorts its rows again each time a user clicks a column header. A user clicks City, then Name. What order should they see, and what breaks if the table's code switches from a stable sort to an unstable one?
What it tests

Predicting the order that successive stable sorts build, knowing which library sorts are stable, and making the order deterministic without relying on stability.

First step

Name the order the clicks build. The last click is the primary key, so rows are in name order, and rows with the same name stay in city order only because the second sort is stable. Then say what an unstable sort does to those ties.
Follow-ups
- How do you keep the same order after a page reload, when only the last click was saved?
- The table has a million rows. What does each click cost?
- How does the feature look when the sorting moves to SQL on the server?
From the lesson Sorting: stability, in-place and adaptivity
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 3 minutes
Mid to senior

A service receives 10⁶ events as 20 chunks, each already sorted by time, joined end to end in arrival order. About how many comparisons does Python's sort need to put all events in time order, against the same events shuffled, and why?
What it tests

Understanding an adaptive merge sort: finding runs, the cost of merging k sorted runs, and estimating comparisons with n log₂ k against log₂(n!).

First step

Notice that the input is 20 sorted runs. An adaptive merge sort finds them in about n comparisons and then merges them, and merging k runs costs about n log₂ k comparisons. Estimate n + n log₂ 20 and compare it with log₂(10⁶!) ≈ 1.85 × 10⁷ for shuffled input.
Follow-ups
- What changes if the chunks cover separate stretches of time?
- Would heapq.merge be the better tool, and when?
- What happens if every chunk arrives newest first?
From the lesson Sorting: stability, in-place and adaptivity
Model answer, Pro.
In the answer:
- Model answer
- Follow-up answers
- Common mistakes
- Rubric
- Variants
- about 3 minutes
Fresher to mid

A device sends 50,000 sensor readings almost in time order: network delays move each reading at most 3 places from where it belongs. You must sort them on a microcontroller with no spare memory. Which elementary sort do you use, and how much work does it do?
What it tests

Linking insertion sort's cost to inversions, bounding the inversions from a displacement limit, and respecting a memory limit.

First step

Bound the disorder first: work out how many out-of-order pairs one reading can belong to when it is at most 3 places from its final position, and multiply by 50,000. Then use the cost of a sort that does one move per out-of-order pair and needs no extra memory.
Follow-ups
- One reading arrives 40,000 places late. What happens to the cost?
- Would bubble sort with an early exit do as well?
- The delay limit is not known in advance. What do you do?
From the lesson Selection, bubble and insertion sort
Model answer, Pro.
In the answer:
- Model answer
- Follow-up answers
- Common mistakes
- Rubric
- Variants
- about 3 minutes
Fresher to mid

Selection sort is not stable. Change it so that it is, and say what the change costs on an array of n items and on a linked list.
What it tests

Seeing that the long-distance swap breaks stability, repairing it by shifting or relinking, and counting the writes each version makes.

First step

Find where the order breaks: trace one pass on two equal items and a smaller one, and see which item the swap moves and how far. A fix must bring the smallest item to the front without letting any item jump over an equal one.
Follow-ups
- How many writes does the stable version make on reversed input of 1,000 items?
- Why is the linked-list version cheap?
- Can you keep the swap and still get a stable result?
From the lesson Selection, bubble and insertion sort
Model answer, Pro.
In the answer:
- Model answer
- Follow-up answers
- Common mistakes
- Rubric
- Variants
- about 3 minutes
Mid to senior

You must sort 1,000 records of 4 KB each in flash memory, where writing a record costs 100 times as much as comparing two keys. Compare selection sort and insertion sort on shuffled records in that cost model, and choose.
What it tests

Building a weighted cost model from exact comparison and write counts, and then questioning the model, for example by sorting small keys instead of moving records.

First step

Write the cost as comparisons plus 100 × record writes. Selection sort makes n(n − 1)/2 comparisons and about n swaps of two writes each; insertion sort makes about n²/4 comparisons and about n²/4 shifts, each one write. Put in n = 1,000.
Follow-ups
- What if the records are already nearly sorted?
- Could you avoid moving the records during the sort at all?
- How does wear on the flash memory change the choice?
From the lesson Selection, bubble and insertion sort
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

What do stable, in-place and adaptive mean for a sort?

Which of selection, bubble and insertion sort are stable, and what makes selection sort unstable?

Questions with model answers

A data table sorts its rows again each time a user clicks a column header. A user clicks City, then Name. What order should they see, and what breaks if the table's code switches from a stable sort to an unstable one?

A service receives 10⁶ events as 20 chunks, each already sorted by time, joined end to end in arrival order. About how many comparisons does Python's sort need to put all events in time order, against the same events shuffled, and why?

A device sends 50,000 sensor readings almost in time order: network delays move each reading at most 3 places from where it belongs. You must sort them on a microcontroller with no spare memory. Which elementary sort do you use, and how much work does it do?

Selection sort is not stable. Change it so that it is, and say what the change costs on an array of n items and on a linked list.

You must sort 1,000 records of 4 KB each in flash memory, where writing a record costs 100 times as much as comparing two keys. Compare selection sort and insertion sort on shuffled records in that cost model, and choose.