Duck Duck Goose / by Zach Mayer

Create a function that predicts the winner of a game of “duck duck goose.”

This is a deceptively simple question, and solving it requires a careful exploration of the rules of the game. It's a really good test of how well your candidate can gather requirements, understand a problem, and execute an effective solution.

Let's start with the requirements. A game of duck duck goose is played, for our purposes, by progressively eliminating items from a set of "players" until only one is left. The "goose" in our representation of the game will just be an integer representing the number of "skips" taken each round, and the players will be an array of strings. Each round, when a player is eliminated from the game the next round will begin starting with the player just after the removed player.

It's tempting to reach for a stack or queue-like data-structure here because of that last rule; starting each round where we left off last round. With a queue, as the goose skips around the players we can dequeue and re-enqueue until we reach the appropriate number of skips where we dequeue one last time and start the next round. We finish the game when only one player is left in the queue and return that survivor.

While the queue solution works, it requires a hefty number of operations since we have to enqueue and dequeue for each skip every single round. Even when we have a small player set, a huge skip count will force that algorithm will to take an excessively long time.

Fortunately there's an effective way to make the algorithm linear with the player-count instead, and that's by simply recognizing that the eliminated player each round will always be the remaining player-count MOD the skip-count. Once we know that, it becomes obvious that each round is just a math problem, and a concatenation of the end of the array of players (after the eliminated index) with the beginning (before the eliminated index). With this solution we're not bound by the skip count can be arbitrarily large and our only performance variable is the player-count!

Here's the solution with comments showing the result of each round and the player index to be dropped :)