[sirsar]

This doesn't sound much like a trick[0] question to me, it just takes working out a few examples by hand to guess that it's `n-1`, and the proof isn't hard either. And the result shouldn't be surprising: if sorting can be done in O(n log n) comparisons, it should be easier than `n log n` to just find the maximum/minimum element.

Even without doing any math, or proofs, or having any algorithmic background, it shouldn't take "fumbling about on some recursive goose chase" to write the function from first principles:

    >>> def games(players):
    ...   if players <= 1: return 0
    ...   if players == 2: return 1
    ...   return 1 + 2 * games(players // 2)
    ...
    >>> games(8)
    7

If your interviewer couldn't come up with that, I wonder how well they do with real-world recursive algorithms on the job. It bears some resemblance to real-world problems I've had: groups of IPs combining into groups-of-groups-of-groups for addressing, computing permissions for teams-of-teams on the org chart, etc.

[0] To me, trick questions involve some hard-to-come-by "aha" moment, like the XOR trick to swap two variables without a temp. This one doesn't seem to have that.

[0x445442]

It's even easier than that... return players - 1. The trick is knowing in any single elimination tournament in order for there to be one winner there must be n - 1 losers.

edit: Also, I'm not sure your solution works for 13 players.

[sirsar]

I wrote that it was `n-1` in my comment. Doesn't seem like much of a trick to me.