When I was working at Google I had to interview a lot of candidates. Most often the interview was general in nature. I wasn't evaluating a candidate for a particular position, I was determining whether a candidate was all around "Google material".
Although Google is known for its challenging interview questions, I found the simple questions gave me the most information about a candidate. One of my favorite interview questions was this: “Given the state of a tic-tac-toe game (naughts and crosses), determine if someone has won the game. Code this up however you'd like.”
This isn't a very hard problem. (Pause a moment and think how you'd do it, or even take a moment to write it up.) The straightforward solution is to check the rows, the columns, and the two diagonals. I was less interested in whether the candidate would come up with this solution or something more clever than I was in seeing exactly how the candidate worked his way from an informal word problem towards a formal solution in code. I wanted to see how the candidate organized his thoughts. I wanted to see how proficient the candidate was in programming when he was allowed to use the language he was most comfortable with.
I expected most candidates to whip off a solution in a few minutes and then we'd move on to the next interview question. To my surprise, fully half the candidates were unable to finish this simple task. A couple seemed unable to use a whiteboard to sketch out a solution. A large number dove right in and started coding up the obvious nested loop only to get confused at handling the flow control. (There is a hidden trap in this problem: if you choose the nested loop solution, you want to abort the inner loop early when you determine a solution is not possible on the current row or column you are checking, but you want to abort the outer loop early when you determine a solution is possible.) It was often that a candidate did not at first realize that a cell in the tic-tac-toe board has three possible states, not two. One candidate used 4x4 arrays to represent the board so he could use 1-based indexing. Not a single candidate tried to abstract over the low-level array manipulation.
Interviews are highly stressful for candidates, so I didn't judge them too harshly. If it looked like they were on the right track and they successfully noticed and repaired a bug or two in their solution I'd call it a win. If they got hopelessly lost, I'm afraid I couldn't recommend them. It was sad because many seemed very nice people and they were trying their best. Either they weren't cut out to be programmers or their education was not serving them well at all.
I do have to mention one candidate who knocked this question out of the park. He observed that there really aren't that many tic-tac-toe game positions, so you can just hash the game position and look up the winner in a table. I didn't even ask him to code this up.
7 comments:
Interesting. The first thing that came to my mind after reading the second paragraph is to represent each cell as 2 bits, enumerate the solutions, and check.
A minute later, I thought hey, the winning states of the two players are the same, so why not use 1 bit per cell and just check each player separately. You only need to have 1s in the cells that indicate a win. You check using (= WIN-STATE (LOGAND PLAYER-STATE WIN-STATE)).
I didn't code this up, except for writing stuff like #b100100100 in some emacs buffer... but I think it'll work :)
That was nearly exactly the answer that came to my mind... basically there are only 16 possible winning bit patterns, which means at most 18 XORs of a 32-bit word to check against zero.
On the other hand, that ignores the possibility of an invalid board state.
I've implemented tic-tac-toe a few times and I just checked the eight winning positions with code that was simple enough that I could tell from looking at it whether it was right or wrong. Plenty of room for optimization but no need to bother in an actual implementation. Would be fun to do it on the whiteboard, but I like that kinda thing. : )
P.S. I am a Google employee but just a lowly PM. : )
There are nine positions and eigth possible winning lines (a 72 elem matrix). Maybe you can create a predefined 2-d linked list and just iterate through the positions, checking for every possible winning line. It looks as a data structure problem to me.
as @hacksoncode points out, the author seems to have left out validity checks either from the original problem, or from his description of candidate responses. there are a limited number of "valid" game states but there are many more invalid ones.
interestingly, for-loop answers will struggle more with validity checks than hash-based ones, especially if candidates are being directed to "bail early" when they find a winning combo. For example a full board of x's will have winning solutions but not be a "winning" board since it is invalid.
i find that simpler problems like this are good in that they encourage "bad" solutions and quick answers, but it's the interviewer's job to ask if there are major problems with the proposed solution.
i'm always struck by the fact that in programming the 90% solution usually needs to be rewritten from scratch to accommodate the last 10%, if the last 10% isn't accounted for from the beginning.
In the tic-tac-toe example, a validity check (like x.len == o.len || x.len == o.len + 1) before the for-loop would probably suffice, but in larger systems, these lost details come back to invalidate entire edifices
class TicTacToe {
constructor() {
this.turns = []
this.board = new Array(9).fill(0)
this.winner
this.wins = {
0: { 1: { 2: true }, 3: { 6: true }, 4: { 8: true } },
1: { 4: { 7: true } },
2: { 5: { 8: true }, 4: { 6: true } },
3: { 4: { 5: true } },
6: { 7: { 8: true } },
}
this.cellMap = {
0: '_',
1: 'X',
2: 'O',
}
}
print() {
console.log('v'.repeat(7), 'turn', this.turns.length)
this.board
.map(c => this.cellMap[c])
.join('')
.match(/.{3}/g)
.forEach(r => console.log(r))
}
takeTurn(t) {
if (this.winner) {
throw new Error('game is over')
} else if (![1, 2].includes(t.state)) {
throw new Error('invalid state')
} else if (t.state === this.turns.slice(-1)[0]?.state) {
throw new Error('not your turn')
} else if (t.x < 0 || t.x > 2 || t.y < 0 || t.y > 2) {
throw new Error('out of bounds')
} else if (this.turns.find(turn => turn.x === t.x && turn.y === t.y)) {
throw new Error('cell occupied')
}
this.board[t.x * 3 + t.y] = t.state
const marks = this.board.reduce(
(a, v, i) => (v === t.state ? [...a, i] : a),
[],
)
const combos = combine(marks, 3)
for (let i = 0; i < combos.length; i++) {
const [a, b, c] = combos[i]
if (this.wins[a] && this.wins[a][b] && this.wins[a][b][c]) {
this.winner = this.cellMap[t.state]
break
}
}
this.turns.push(t)
this.print()
if (this.winner) return console.log('WINNER', this.winner)
}
}
function combine(n, k) {
let set
if (typeof n == 'object') {
set = n
n = n.length
}
const result = []
const combos = []
const recurse = start => {
if (combos.length + (n - start + 1) < k) {
return
}
recurse(start + 1)
combos.push(start)
if (combos.length === k) {
result.push(
set
? combos
.slice()
.map(c => set[c - 1])
.sort()
: combos.slice(),
)
} else if (combos.length + (n - start + 2) >= k) {
recurse(start + 1)
}
combos.pop()
}
recurse(1, combos)
return result
}
const t = new TicTacToe()
t.takeTurn({ state: 1, x: 0, y: 0 })
t.takeTurn({ state: 2, x: 1, y: 0 })
t.takeTurn({ state: 1, x: 2, y: 2 })
t.takeTurn({ state: 2, x: 1, y: 2 })
t.takeTurn({ state: 1, x: 0, y: 2 })
t.takeTurn({ state: 2, x: 1, y: 1 })
Unfortunately, Google strips the leading whitespace in the comments section.
Post a Comment