The question was roughly this: given a set of ballots, where each ballot is a candidate preference ranking, like [A, B, C, D] or [B, A, C, D], representing a voter's priority order over the candidates. Part one was actually pretty direct — just look at the first candidate on each ballot and count who appears most often. If there's a tie, pick the smallest one in lexicographic order. This part was basically simple counting and I finished it quickly.
Part two was a variation on top of that, similar to instant runoff voting. In each round, you only tally the first choice among candidates who are still alive. If someone gets over 50 percent, they win outright. If not, you eliminate whoever currently has the fewest votes, then move to the next round and keep tallying. The key thing here is the tie-breaking. If multiple candidates are tied for fewest votes, you need to eliminate the one that's lexicographically largest, i.e. try to keep the lexicographically smallest one. If this rule isn't handled correctly, basically all the results afterward come out wrong.
For the implementation, I didn't modify the ballots themselves — instead I used a set to track which candidates had already been eliminated. When scanning a ballot each round, I went front to back to find the first still-active candidate to count. Writing it this way is cleaner and avoids the complexity of repeatedly modifying the array.
The difficulty was mostly in the details. This kind of multi-round-update simulation is very easy to get wrong, because each round's result affects the next round. A ballot might need to skip over several already-eliminated candidates, and if the counting or break condition isn't written rigorously enough, it's easy to break on certain cases. I spent a lot of time afterward thinking about test cases and debugging — things like everyone tied in the first round, several consecutive rounds of ties, an incomplete ballot, or needing to skip multiple positions after an elimination, and so on. But testing this kind of problem is inherently time-consuming, because you have to work through the result round by round, and it's not easy to verify quickly.
With about 10 minutes left, the interviewer ran a set of tests for me, around ten or so. I had one case fail, and was given a few minutes to fix it, but by that point things were already a bit of a mess in my head and I couldn't fix it in time. In the end I failed.
Looking back on it now, the problem itself isn't conceptually complex, but the implementation demands are very rigorous, and getting all the edge cases right in one shot under time pressure is genuinely hard. It felt a bit like gambling on whether your test cases would cover everything. I guess this time I just wasn't prepared enough.
Discussion
Loading comments…