You sort a slice built from a map[string]int by count, yet equal counts come out in a different order each run. Why?
answer
- the sort only fixes what you compare
- where did the slice's starting order come from
- stability preserves the input order
- and the input order was the random part
- break ties on the unique key
basics
~20 sThe slice was filled by ranging the map, so its starting order is random, and sorting only by count leaves equal counts in that random order. Fix it by making the comparison a total order: break ties on the key.
solid answer
~40 sSorting fixes only what the comparison function looks at. The slice was built by ranging over the map, so it starts in a randomised order; a comparison that returns "equal" for two entries with the same count leaves those two wherever the random input put them. Switching to a stable sort does not help, because stability preserves the *input* order and the input order is exactly the nondeterministic thing. The fix is a total order — compare on count first, then break the tie on the map key with a string comparison, so no two distinct entries ever compare equal. The same reasoning applies to any top-N over a map: without a tie-break, the boundary between position N and N+1 is a coin flip, and a rendered leaderboard or a golden file will churn.
code
go · 17 linestype kv struct {
Word string
Count int
}
pairs := make([]kv, 0, len(counts))
for w, n := range counts {
pairs = append(pairs, kv{w, n})
}
slices.SortFunc(pairs, func(a, b kv) int {
if a.Count != b.Count {
if a.Count > b.Count {
return -1 // higher count first
}
return 1
}
return strings.Compare(a.Word, b.Word) // total order: ties broken on the key
})go deeper
Remember that a sort only orders by what your comparison examines. If two entries compare equal, their relative order is not defined, and anything built from a map starts out randomly arranged.
Explain why a stable sort is not the fix: stability preserves the input order, and the input order came from a randomised map range. Then write the tie-break on the map key.
Show the operational consequence — churning golden files, a top-N whose membership flips at the cut line, pagination that repeats or skips a tied item — and make total-order comparisons a review habit.
Treat tie-breaking as a product decision, not a bug fix: someone must say what "first" means among equals, and that rule belongs in the code and the spec rather than being left to whatever the runtime produced.
## The shape of the bug A counting pass produces a `map[string]int`. To render "top words by frequency" you build a slice of pairs and sort it descending by count. The top of the list looks right, but rerun the program and words that share a count have swapped places. Nothing about the input changed. ## Why sorting did not make it deterministic Two facts combine. **First, the slice starts in a random order.** It was filled by `for w, n := range counts`, and Go randomises the starting position of every map range. So before the sort runs, the slice is in an order that differs on every execution. **Second, the comparison is a partial order.** Comparing only counts means every pair of entries with the same count compares as equal. A sort is only obliged to put the elements in an order consistent with the comparison you gave it; among elements that compare equal it may do anything. ## The stable-sort trap The natural next move — reach for a stable sort — does not fix this, and understanding why is the point of the question. A stable sort guarantees that elements comparing equal keep their **relative order from the input**. That is a real guarantee, and it is useless here, because the input order is the randomised map iteration. Stability faithfully preserves nondeterminism. Stable sorting is the right tool when the input order carries meaning you want to keep — rows already ordered by timestamp, say — and the wrong tool when the input order is itself an accident. ## The fix: make the comparison total Give the comparison a second key so that no two distinct entries can compare equal: ```go slices.SortFunc(pairs, func(a, b kv) int { if a.Count != b.Count { if a.Count > b.Count { return -1 } return 1 } return strings.Compare(a.Word, b.Word) }) ``` Because map keys are unique, comparing on the key is guaranteed to break every remaining tie, and the result is one specific ordering that no longer depends on how the slice happened to be built. Note what this buys you beyond determinism: a reader now knows what "first" means when counts are equal, which is a product decision you made rather than one the runtime made for you. ## Where it hurts most - **Top-N.** Taking the first ten of a list whose eleventh entry ties the tenth means the reported set of items — not just their order — varies between runs. Users notice a leaderboard that reshuffles itself for no reason. - **Golden files and snapshot tests.** A rendered table with tied rows fails intermittently, and the failure rate depends on how many ties the fixture happens to contain, so it looks like an infrastructure problem rather than a bug. - **Pagination.** Two pages produced by two requests over tied data can repeat an item or skip one entirely, because each request re-derives the arbitrary part of the order. - **Diffing two runs.** Any comparison of yesterday's output against today's is full of noise from moved rows. ## A stronger habit Treat every comparison used to produce output as needing to be **total**. The test is simple: can two entries that differ compare as equal? If yes, the tail of the order is undefined, and once the data came out of a map it is not merely undefined but actively randomised. Adding a final tie-break on a unique field — the map key, an id, a name — costs one line and removes a whole class of intermittent failure. The symmetric mistake is worth naming too: sorting on a field that is itself nondeterministic, such as a pointer value or a string built from an address, produces an order that is total but still varies between runs. ## What an interviewer is listening for The candidate should trace the nondeterminism back to the map range rather than blaming the sort algorithm, should explicitly reject stable sorting as the fix and explain why stability preserves rather than removes the randomness, and should land on the total-order tie-break. A very good answer also mentions the top-N boundary effect — that ties change which items appear at all, not only their order.
- Would switching to a stable sort fix the churn?No. A stable sort preserves the relative order of equal elements as they appeared in the input, and the input order here came from ranging the map, which is randomised. Stability would faithfully reproduce a different random arrangement on every run. Only a tie-break in the comparison removes the nondeterminism.
- How does this change which items appear in a top-10, not just their order?If the tenth and eleventh entries have the same count, which of them lands inside the cut is decided by the arbitrary part of the order. So the set of reported items changes between runs, not only their arrangement — which is why users see a leaderboard reshuffle when nothing was recounted.
- Is there any case where the map-derived order is acceptable to leave alone?Yes, when the result is never observed as an ordered thing — an aggregate sum, a membership check, a set written into another map. The rule applies when the order is visible to a person, a file, a hash or an assertion. Sorting everything defensively costs time on hot paths.
Sorting a shuffled deck by rank alone leaves the four suits of each rank in whatever order the shuffle left them. You have to say which suit wins.
saying these in an interview costs you the question
- Blames the sort algorithm rather than the map iteration
- Says switching to a stable sort makes the output deterministic
- Adds a second sort pass instead of a tie-break
- Assumes equal-comparing elements keep some natural order
- Sorts on a pointer or address to break the tie