I had a 1-hour interview where I was asked two Data Structures and Algorithms (DSA) questions. Both questions were of medium to hard difficulty, comparable to problems typically found on LeetCode.

The focus was on problem-solving efficiency and coding skills.

There are n coins on the table forming a circle, and each coin is either facing up or facing down. Alice and Bob take turns to play the following game, and Alice goes first.

In each operation, the player chooses a facing-up coin, removes the coin, and flips the two coins that are adjacent to it.

• If, before the operation, there are only two coins left, one will be removed and the other won't be flipped (as it would be flipped twice).
• If, before the operation, there is only one coin left, no coins will be flipped.
• If, before the operation, there are no facing-up coins, the player loses.

Decide who will win the game if they both play optimally. It can be proved that the game will end in a finite number of operations, and one of them will win.