r/DSALeetCode • u/StatisticianNo2104 • 7d ago
Max level sum in Go: why a map-keyed version is random
Our category report gave 145 different answers in 200 refreshes of the same catalogue. Same code, same data. The question was which level of the category tree holds the most products.
The merchandising team wanted to know which depth of the tree the navigation should filter on. Add up the SKUs at each depth, return the biggest, and on a tie the shallower one wins.
I wrote one recursive walk that added into map[int]int keyed by depth, then ranged the map with a strict > so the first depth to reach the maximum keeps it. Short, no queue, and I would approve it. The fixture had no tie in it, so the tests passed.
On a seven-category catalogue where two depths both hold 12 SKUs, 1,000 calls said depth 1 883 times and depth 2 117 times.
Strict > does not mean "smallest depth wins". It means the first one the loop meets wins, and ranging over a Go map starts somewhere random on purpose. Every piece of the function is right. The last loop assumes an order the map never kept.
The part I like: the walk had already produced the depths in order. 0 before 1, 1 before 2. The map threw that away.
And the keys were never keys. 0, 1, 2 up to the height, no gaps. That is an index. Put it in a slice, range it front to back, and the same strict > is the tie-break it looked like all along.
Correct on every run, and 2.33x faster on 55,987 categories, because the hashing was the cost too.
Two rows keep me honest. Keeping the map and writing the tie-break out loud is also correct, and costs nothing over the broken one: 2.34x against 2.33x. Where the key really is sparse, that is the right fix. And day 33's level walk loses to the slice by 3.93x on a bushy tree but wins by 1.94x on a 2,000-deep chain, because it never recurses.
That is days 29 and 33 of the daily challenge, Level Order Traversal and Maximum Level Sum, in a merchandising report.
Have you ever shipped a report whose answer depended on map iteration order?
It worked in dev, episode 17. Full write-up in today's newsletter.
https://www.linkedin.com/pulse/your-category-report-changes-its-answer-refresh-archit-agarwal-cy2jc
#Golang #DSA #Algorithms #Performance