4 ms·
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 (
by 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 agoI 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 agoI think it's the best answer so far!
- zaroth 12y agoPerfection! A beautiful hack around not knowing the size of the board, and even faster detecting cycles to boot.
- defen 12y agoThat'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 agoThat'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.