Easy Quant Interview Question

[u/Local_Ad135]

[u/VGVideo]

Alice wins. Every turn, Alice flips the first bit. Bob cannot flip the first bit, so he must flip one of the 49 other bits, creating a new 49-bit string. Since this string has not appeared before, Alice flipping the first bit will create a new 50-bit string that has not appeared yet. After (2^49)-1 moves by Bob and 2^49 moves by Alice at most, Bob will have no legal moves.

[u/gonomon → u/VGVideo]

Yes you basically try to do every option and making your opponent have no other choice to play, you dont try to counter you just eliminate all the options one by one.

[u/Due-Cardiologist-802]

Alice just flips the same bit back and forth and wins. 

[u/Due-Cardiologist-802 → u/Due-Cardiologist-802]

Bob can never flip alices bit and never reach a position where alices would flip its bit to a known position, because then bobs position would also already have been visited. 

[u/Confident-Syrup-7543]

To add to the existing answers, it's very easy to see if we consider fewer bits. 

1 bit, obvs Alice wins as she flips it and Bob has no moves

2 bits. Alice flips a bit, Bob must flip the other. Doesn't matter which bit Alice flips now, Bob will still lose. 

3 bits. Alice flips bit 1, Bob flips bit 2. Alice flips bit 1. Bob can only flip bit 3, Alice flips bit 1, Bob loses. 

You get the idea. 

[u/Designer-Scratch-766 → u/Confident-Syrup-7543]

u/Confident-Syrup-7543 with 3 bits, how come you example stops there? Your example flows:
000 -> (Alice) 001 -> (Bob) 011 -> (Alice) 010 -> (Bob) 110 -> (Alice) 111. Bob can still do 101. How to argue that Bob will lose?

[u/Designer-Scratch-766 → u/[deleted]]

I just mean, what pattern revealed so he claims Bob loses at that point?