[alisey]

The question starts with: "Consider a finite checkerboard of unknown size", which means you don't know the value of size-squared. Bitmap requires O(n) space, while the Carpenter's solution requires only O(1) space. And both require O(n) time. If an interviewee failed to see the difference, honestly I doubt I would want to pursue it further.

[Jare]

"size" is perfectly known in the code. Before shooting off into functional rearchitecture land, a simple common sense question like "by unknown you mean arbitrary, right?" would have been more sensible. In addition, the candidate thinks "being asked to whiteboard code was an excuse to have a technical conversation with a future colleague" but spends the entire time having a monologue rather than a conversation, and seems pleased about it.

[zaroth]

Time and space complexity is obvious, and I agree I would want the interviewee to understand that. Like I said, the worst case is always the number of squares (just imagine the path of arrows walks through the entire board) so you can achieve O(1) space, O(n) time with just a move counter.

What I missed is the requirement that you ignore the known upper bound, even though it's right there in the code, and so you can't use the move counter technique to achieve O(1)/O(n), you have to use the cycle-finding algorithm, which is slower but at least still not quadratic.

  "Your code should not presume anything about the gameboard’s size
  or contents, only that it is given an arrow every time though the
  while loop."

It's not a bad question, but I think starting it off by asking them to write code inside the game function is a red herring. The function should be boxed off to return the sequence of arrows to start with, and then let the game begin. That way the requirements are clearly defined up-front.

However, in my experience 0% of interviewees I've ever sat with, given such a function, ES6Fiddle and nothing else, would actually be able to implement Floyd's cycle finding from memory. Unless of course the recruiter prompted them to study it the night before.

If you're adverse to providing full internet access during interviews (which I always do) then at least you would have to provide an excerpt from a relevant textbook or Wikipedia to set them on the right path.

[alisey]

I gave this question to a friend and she came up with what I think is a beautiful answer. Remember min and max X and Y coordinates seen so far, and count the number of steps. When this number gets larger than (maxX - minX)*(maxY - minY) we know we're in a cycle.

It's an extension of your idea of counting the total number of visited positions. What I like most about it is that it can work with streamed data.

[defen]

That's a really cool solution. One potential problem is that it doesn't find the loop as soon as possible (e.g. if it's going around the perimeter of a square, the cycle is detectable after 4N steps, but the algorithm will take N^2 steps to realize that)

[jongraehl]

That's nice (and can be easily fixed to handle negative coordinates), but extremely slow (imagine a simple square cycle with side length N. Her solution takes N^2 steps.

[zaroth]

Perfection! A beautiful hack around not knowing the size of the board, and even faster detecting cycles to boot.

[Udik]

I think it's the best answer so far!