6 ms·

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, wh

by alisey 12y ago

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 12y ago
"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.
- deleted 12y ago
  [deleted]
zaroth 12y ago
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 12y ago
  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.
  - Udik 12y ago
    I think it's the best answer so far!
  - zaroth 12y ago
    Perfection! A beautiful hack around not knowing the size of the board, and even faster detecting cycles to boot.
  - defen 12y ago
    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 12y ago
    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.

by alisey 12y ago

Jare 12y ago

"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.

deleted 12y ago
[deleted]

zaroth 12y ago

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 12y ago
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.
- Udik 12y ago
  I think it's the best answer so far!
- zaroth 12y ago
  Perfection! A beautiful hack around not knowing the size of the board, and even faster detecting cycles to boot.
- defen 12y ago
  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 12y ago
  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.