Coding

Flip Game

Asked at

Microsoft

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

You are playing a Flip Game with your friend.

You are given a string currentState that contains only '+' and '-'. You and your friend take turns to flip two consecutive '++' into '--'. The game ends when a person can no longer make a move, and therefore the other person will be the winner.

Return all possible states of the string currentState after one valid move. You may return the answer in any order. If there is no valid move, return an empty list [].

Input: currentState = "++++++" Output: ["--++++", "+--+++", "++--++", "+++--+", "++++--"]

Input: currentState = "++--++" Output: ["--.--++", "++----"]

Input: currentState = "-++-"

1 <= currentState.length <= 500
currentState[i] is either '+' or '-'.

cpp

class Solution {
public:
    vector<string> generatePossibleNextMoves(string s) {
        // Your code goes here
    }
};

java

class Solution {
    public List<String> generatePossibleNextMoves(String s) {
        // Your code goes here
    }
}

python

class Solution:
    def generatePossibleNextMoves(self, s: str):
        # Your code goes here

javascript

class Solution {
    generatePossibleNextMoves(s) {
        // Your code goes here
    }
}

csharp

public class Solution {
    public IList<string> GeneratePossibleNextMoves(string s) {

    }
}

func generatePossibleNextMoves(s string) []string {

}

Stuck? Show a way to structure it+

01Clarify whether this is the one-move or two-player version
02Enumerate every consecutive ++ pair
03For game play, recurse after a flip and negate the child result
04Memoize states and restore mutable state after each trial

Reference answer

Start by restating the input contract for Flip Game and testing the smallest boundary case before choosing the algorithm. For the common Flip Game II version, model each move as replacing a consecutive '++' with '--'. Recursively try every legal move and memoize whether the current string is winning: a state wins if it has a move to a losing child. For the one-move variant, simply enumerate indices containing '++'. Explain the invariant while coding, then show how each update preserves it. For Flip Game II, the memoized state search is exponential in the string length, O(2^n * n) time and space when states are stored as strings; the one-move variant is O(n). Walk through one nontrivial example aloud so the interviewer can see why the method reaches the intended result. Finally, call out input assumptions and failure cases rather than silently relying on them. A clean implementation should keep state local, use descriptive names, and avoid work that the invariant makes unnecessary.

Then expect these follow-ups

Can you optimize with Sprague-Grundy theory?
Tests: follow-up reasoning
What is the complexity of the memoized search?
Tests: complexity analysis

Free to read · better with Enzo

Practice this out loud with Enzo

Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.

Continue with Enzo Sign up free

Next question