1. 37
  1.  

  2. 12

    I got this problem when interviewing for my first programming job. I brillantly solved it by arguing that a winning board in tictactoe is equivalent to having 3 numbers from 1-9 that add up to 15, and then summing all of each player’s 3-subsets.

    I did not get the job.

    1. 2

      Could you elaborate on how the positions on the board map to the numbers? The following layout doesn’t seem correct, since 1+2+3=6 but that’s still a win for X.

      123      XXX
      456  =>  O
      789      OO
      
      1. 6

        You map it to a magic square instead:

        276
        951
        438
        
        1. 1

          Nice! Did you come up with it on the spot?

          1. 1

            This is the key to that solution. As someone responsible for giving technical interviews (not at google lol), you would have passed as far as I’m concerned.

          2. 1

            You can change rows by adding/subtracting 9, and change columns by adding subtracting 3. This is equivalent to shifting the row/col towards/away from the center. The property that the numbers add to 15 only holds around the center.

            But still, this doesn’t solve the question how to avoid flagging e.g. 3, 4, 8 as a winning position.

        2. 9

          Did this awhile back in Erlang relying on pattern matching.

          https://git.sr.ht/~statianzo/sevenlangs/tree/master/item/erlang/tictactoe.erl

          1. 7

            To my surprise, fully half the candidates were unable to finish this simple task… Either they weren’t cut out to be programmers or their education was not serving them well at all.

            This is a false dichotomy. A third possibility is that the interview is flawed. Writing software either as a student or as a professional is almost never conducted in an interrogation setting like this. Perhaps to some it comes naturally, but for others it’s a trick one has to train and re-train to perform on command. If they fail, I’d give them the benefit of the doubt and say simply that they did not pass the interview.

            Sounds like Google still has plenty of candidates to burn. All the more for the rest of us.

            A couple seemed unable to use a whiteboard to sketch out a solution… I wanted to see how the candidate organized his thoughts.

            The thoughts of others are unknowable. If one trains to solve problems for a skeptical audience at a whiteboard, the act is reflexive, not a genuine intimacy afforded to a supposedly benign and merely curious onlooker. Even as a student in an exam setting, one is at least afforded the privacy of one’s thoughts before turning in one’s solution.

            1. 5

              Not a single candidate tried to abstract over the low-level array manipulation.

              I always interpreted these kind of questions as “do something simple/understandable that solves the problem” not “do something as clever/general as possible”. Yes, you can solve this with some bit magic, and you can abstract over rows/columns, but why would you if there are only 8 possible configurations which let you win.

              Without context, there’s no way to know if what you’re doing makes sense. The interviewer might have a particular nice solution in his mind, but good luck trying to guess it if you haven’t encountered the problem before.

              That’s also my view on ‘prepping’ for these kind of interviews: it’s just going though heaps of potential interview questions in the hope that you’ll encounter the same or a similar question.

              1. 4

                I immediately thought that I’d trip up the loops and gave up on that, so my next thought was to store them in an array of ints as e.g. 0b111, 0b1001001 etc, and first & them with the position of all the Xs and then Os, which is kinda like the hashing solution. I think I did something similar during this year’s Advent of Code. Maybe I should try getting an interview at google :P

                1. 7

                  Yeah, there are only 8 win states & you can “and” those with the current board state & test for equality. Job done. (You’d have to do this twice; once for each player.)

                  Much faster than faffing about looping over the current board state.

                  1. 2

                    How would you encode the board? My immediate naive thought was to use the low 9 bits of two 16-bit integers, one for each player. To play, you toggle a bit in your board from 0 to 1, after checking that it is not already 1 in either version. Your win check is then just 8 bitwise and operations (which, if you’re lucky, your compiler will splat the board into a 128-bit vector register and do in parallel). I wonder if there’s a better way of encoding the tri-state logic in the game though. A 9-square grid that has three states per grid has just over 14 bits of information in it, so in theory you can encode the entire state of the game in a single 16-bit integer with some space left over, but I don’t immediately see a way of doing so that makes testing for winning states easy.

                    1. 1

                      Personally I’d just use an array of an enum of Empty | X | O and then reduce it to those two ints. If you wanna do something more complex maybe use 18 bits for both the board and the win states and use 0b00 for Empty, 0b01 for X and 0b10 for O, and either have two win state tables or just encode the win states for X and right shift by 1 when checking for O.

                      1. 1

                        9 bits to record if a specific space is occupied, 9 bits to denote who is occupying.

                        for example, lower 9 are for occupancy, upper 9 are for ownership:

                        0b000000000000000000
                        0│1│2
                        ─┼─┼─
                        3│4│5
                        ─┼─┼─
                        6│7│8
                        
                        0b100100100101101101
                        O│1│X
                        ─┼─┼─
                        O│4│X
                        ─┼─┼─
                        O│7│X
                        
                        0b100100100110101100
                        0│1│X
                        ─┼─┼─
                        O│4│X
                        ─┼─┼─
                        6│O│X
                        

                        https://gist.github.com/justintout/736b51e6e5dd655c87d91cbab6773c5e

                        1. 1

                          If I was going to use logical operators, then two bits per location seems reasonable. Board state fits easily into a 32-bit word, Everything fits in cache & the test takes a whole 16 machine cycles or so, since the CPU will pipeline the reads from cache.

                          But, given the size of the problem, you could just use an array of chars & it wouldn’t make that much difference.

                        2. 1

                          Yeah, that’s the algorithm I was trying to describe. I’d just woken up with a bit of a hangover so I guess I wasn’t clear enough.

                      2. 3

                        I use to give junior candidates similar types of questions — things that weren’t really difficult, but nontrivial and had a few gotchas. One of them was to look at the cards the dealer’s been dealt in Blackjack and determine whether the dealer should hit or stand or if they’ve busted. (The duality of aces counting either 1 or 11 is the tricky part.)

                        I was always surprised that some seemingly qualified people just got stuck. In some cases it seemed to be nerves, but others just had trouble translating a high level task into code.

                        1. 3

                          So you had to explain the rules of blackjack before people can start working on this question? I can’t make sense of it, to be honest.

                          1. 1

                            Recently I was asked to implement the chess game in system design exercise. I am not too familiar with the rules so I kept abstracting away the actual moves bit gave a pretty good description of how a state can be verified. I failed the interview. Why are interviews so specific on a game/rules? Not everybody would have known how to play it.

                            1. 1

                              I understand, and I tried not to make the question dependent on knowing the game. I gave the information up front:

                              • There are two or more playing cards
                              • Number cards count as themselves, face cards are 10, aces are either 1 or 11, your choice
                              • If the total is 15 or less, the result is “hit” (take another card)
                              • If the total is 16-20, the result is “stand” (don’t take a card)
                              • If the total is 21, the result is “blackjack!” (win)
                              • If the result is > 21, the result is “busted” (lose)
                          2. 3

                            interesting solution is to consider “winning states” as strides over the 1d array

                            1. 2

                              Strides and starting points: [[0,1], [3,1], [6,1], [0,3], [1,3], [2,3], [0,4], [2,2]]

                            2. 3

                              For fun, I thought I’d give this problem to my kids on Easter Sunday. Coded up a challenge / arbitrator program in Haskell that would generate random valid noughts+crosses boards & gave them the scaffold of a python program to interact with it. They had to complete the challenge of correctly judging 10 boards in order to get their Easter eggs :)

                              They went straight for the “test all possible win states” option & coded it up fairly quickly. After fixing all the (inevitable) syntax errors their code worked first time, which is a lot more than I could say for a lot of my code!

                              1. 2

                                isnt a single dimension array already enough for this?

                                1. 4

                                  I’m learning programming and literally code tictactoe up for fun about 6 months ago and did exactly that… Just kept a 2 dim array with winning moves and it was done

                                  1. 2

                                    I was thinking about something like this:

                                      type TicTacToeAtom = X | O | None
                                    
                                      type TicTacToeState = list<TicTacToeAtom>
                                    
                                      let exampleGameStateNone : TicTacToeState =
                                        [X; O; None; None; None; None; None; None; None]
                                    
                                      let exampleGameStateX : TicTacToeState =
                                        [X; O; None; X; O; None; X; None; None]
                                    
                                      let didAnyBodyWin (gameState:TicTacToeState) =
                                        match gameState with
                                        | [ X; X; X; _; _; _; _; _; _; ] -> X
                                        | [ _; _; _; X; X; X; _; _; _; ] -> X
                                        | [ _; _; _; _; _; _; X; X; X; ] -> X
                                        | [ X; _; _; X; _; _; X; _; _; ] -> X
                                        | [ _; X; _; _; X; _; _; X; _; ] -> X
                                        | [ _; _; X; _; _; X; _; _; X; ] -> X
                                        | [ X; _; _; _; X; _; _; _; X; ] -> X
                                        | [ _; _; X; _; X; _; X; _; _; ] -> X
                                        | [ O; O; O; _; _; _; _; _; _; ] -> O
                                        | [ _; _; _; O; O; O; _; _; _; ] -> O
                                        | [ _; _; _; _; _; _; O; O; O; ] -> O
                                        | [ O; _; _; O; _; _; O; _; _; ] -> O
                                        | [ _; O; _; _; O; _; _; O; _; ] -> O
                                        | [ _; _; O; _; _; O; _; _; O; ] -> O
                                        | [ O; _; _; _; O; _; _; _; O; ] -> O
                                        | [ _; _; O; _; O; _; O; _; _; ] -> O
                                        | _                              -> None
                                    

                                    The Erlang version is shorter because you can just say A,A,A instead of spelling out X and O. You can also collapse the cases to A|B|C…. -> X.

                                2. 1

                                  Setting aside the efficacy of this challenge in in-person interviews, Tic Tac Toe is a really interesting lens through which to view various programming languages. I tried using TypeScript’s tuples as a poor person’s parametric type. It’s not nearly as elegant as this solution in Idris I found on GitHub, which makes me want to redouble my efforts to learn the language. Like some of the other commenters here, I think this challenge makes a strong case for algebraic pattern matching.

                                  1. 1

                                    that is super interesting… I didn’t think to hash it but that would be a better solution. I must be getting off my game