3 ms·

> Given a cube with sides length n, write code to print all possible paths from the center to the surface. What is a path through a cube? This seems like some

> Given a cube with sides length n, write code to print all possible paths from the center to the surface. What is a path through a cube? This seems like some weird combination of graph theory and geometry.

seiko55 14y ago
you are a googler, right? i think we've seen your posts.
- haberman 14y ago
  Yes (I don't keep this a secret, it's right on my userinfo page). How does that pertain to this thread?
Zenst 14y ago
Indeed, sometimes the question is silly and you should not be afriad to question it. I was once asked about video conferencing in detail for some task and explained that recording via VCR and sending the output via tape would be more suitable and cost effective for what they were trying to use it for. You have to look at the initial question and peel of the layers until you find the reason for the question and then you can address the true problem. Sometimes somebody will ask how to computerise this and you will ook at it and sometimes find yourself asking how does it work now and again sometimes saying that what they have is already better or as good as a computerised system to that problem. In this cube land question you can answear, how are you defining the centre and just revering that process will already give you the code you require. What they are doing you don't know so you have to ask, may be they are trying to reinvent a wheel and with that the best answear may be how to draw a circle as there question is flawed. This is the problem with made up interview questions, if they are based upon real world experience then you get a good question that you can truely answear. You may have a better answear or approach which with them having lived it, makes enough sence to know you would of saved them 2 days debugging that problem and thats from a quick chat walking of the street. If it is a made up question then your approach and alternative answear can be missed and ignored and your genius is not appreicieated.
jsolson 14y ago
Perhaps they're assuming that the cube is a set of integral points and they want you to count lattice paths. This is trivial in 2-space (e.g., give me the number of paths that go from (0,0) to (5,5) by going only up or right one point with each move (that is, each move is either (0,1) or (1,0))). However, I vaguely recall counting lattice paths in 3-space being a wickedly hard problem with no known polynomial time solution. Could be completely wrong on that, though, and don't feel like looking it up just now. You could of course write a program that would solve it (trivially), but it might take exponential time :) Of course, the phrasing doesn't say they have to be lattice paths, so perhaps we can say a countably infinite number of paths of we're only considering integral (or rational) points and have no direction invariant. Uncountably many if we're allowing the reals. Still uncountably many if we allow the reals and have a directional invariant. We reach the realm of a finite solution if it's a finite set of points and we have a directional invariant or another constraint (e.g., the path might be prohibited from visiting any given point more than once). Most of these are still completely intractable as far as I know :)
- Symbol 14y ago
  Glad I'm not the only one who thought this problem statement must be missing constraints if they expect a code solution on a whiteboard.
  - Bakkot 14y ago
    I assumed it was intentionally ambiguous (like a lot of problem statements in practice), to see how the interviewees respond. There are a few interesting interpretations, some of which are obviously exponential time, infinite time, or impossible (ie uncountably many solutions).
- deleted 14y ago
  [deleted]
- jules 14y ago
  In n-space the problem is almost as easy as in 2-space if you can only go in forward in each dimension. If you can go in both directions and you want to find the number of non self intersecting paths, the problem is hard even in 2-space (as far as I can tell). If you allow paths to be self-intersecting, then the count is obviously infinite. Note that the actual interview question asks you to list all paths, not count them. To count paths in 2-space from (0,0) to (5,6), you have the operations "X++" and "Y++" which go right and up, respectively. Each increasing path from (0,0) to (5,6) has to be some permutation of 5 times X++ and 6 times Y++. So the count is (5+6)!/(5!6!) where the exclamation mark denotes factorial. This extends to higher dimensions by adding an additional operation "Z++". Then the count to go from (0,0,0) to (5,6,7) is (5+6+7)!/(5!6!7!).
Whodi 14y ago
If you follow the links, this was asked to someone interviewing for a job on the Windows team who then posted it to an interview question aggregator, so it's likely that the actual phrasing of the question was lost. But as best as I can tell, they're considering each 1x1x1 space to be a node like a Rubix cube, and they want a list of all possible paths from the center node to the surface. I imagine that half of the question is making sure that the interviewee presses for details, because there's plenty of problems I see with the question right off the bat. If n is even, there's no single center node, so where does the algorithm start? Can the algorithm traverse diagonally by edges, or only by adjacent faces? Not to mention that there's an infinite number of possible paths for some values of n, assuming paths can cross themselves, for the same reason that there's an infinite number of paths from my front door to my car if I feel like walking in circles for a while.
arjn 14y ago
The first thing I thought was , this may be a trick question, since there are an infinite number of paths from the center to the surface. I think the problem statement needs a bit more detail.

seiko55 14y ago

you are a googler, right? i think we've seen your posts.

haberman 14y ago
Yes (I don't keep this a secret, it's right on my userinfo page). How does that pertain to this thread?

Zenst 14y ago

Indeed, sometimes the question is silly and you should not be afriad to question it. I was once asked about video conferencing in detail for some task and explained that recording via VCR and sending the output via tape would be more suitable and cost effective for what they were trying to use it for. You have to look at the initial question and peel of the layers until you find the reason for the question and then you can address the true problem. Sometimes somebody will ask how to computerise this and you will ook at it and sometimes find yourself asking how does it work now and again sometimes saying that what they have is already better or as good as a computerised system to that problem. In this cube land question you can answear, how are you defining the centre and just revering that process will already give you the code you require. What they are doing you don't know so you have to ask, may be they are trying to reinvent a wheel and with that the best answear may be how to draw a circle as there question is flawed. This is the problem with made up interview questions, if they are based upon real world experience then you get a good question that you can truely answear. You may have a better answear or approach which with them having lived it, makes enough sence to know you would of saved them 2 days debugging that problem and thats from a quick chat walking of the street. If it is a made up question then your approach and alternative answear can be missed and ignored and your genius is not appreicieated.

jsolson 14y ago

Perhaps they're assuming that the cube is a set of integral points and they want you to count lattice paths. This is trivial in 2-space (e.g., give me the number of paths that go from (0,0) to (5,5) by going only up or right one point with each move (that is, each move is either (0,1) or (1,0))). However, I vaguely recall counting lattice paths in 3-space being a wickedly hard problem with no known polynomial time solution. Could be completely wrong on that, though, and don't feel like looking it up just now. You could of course write a program that would solve it (trivially), but it might take exponential time :) Of course, the phrasing doesn't say they have to be lattice paths, so perhaps we can say a countably infinite number of paths of we're only considering integral (or rational) points and have no direction invariant. Uncountably many if we're allowing the reals. Still uncountably many if we allow the reals and have a directional invariant. We reach the realm of a finite solution if it's a finite set of points and we have a directional invariant or another constraint (e.g., the path might be prohibited from visiting any given point more than once). Most of these are still completely intractable as far as I know :)

Symbol 14y ago
Glad I'm not the only one who thought this problem statement must be missing constraints if they expect a code solution on a whiteboard.
- Bakkot 14y ago
  I assumed it was intentionally ambiguous (like a lot of problem statements in practice), to see how the interviewees respond. There are a few interesting interpretations, some of which are obviously exponential time, infinite time, or impossible (ie uncountably many solutions).
deleted 14y ago
[deleted]
jules 14y ago
In n-space the problem is almost as easy as in 2-space if you can only go in forward in each dimension. If you can go in both directions and you want to find the number of non self intersecting paths, the problem is hard even in 2-space (as far as I can tell). If you allow paths to be self-intersecting, then the count is obviously infinite. Note that the actual interview question asks you to list all paths, not count them. To count paths in 2-space from (0,0) to (5,6), you have the operations "X++" and "Y++" which go right and up, respectively. Each increasing path from (0,0) to (5,6) has to be some permutation of 5 times X++ and 6 times Y++. So the count is (5+6)!/(5!6!) where the exclamation mark denotes factorial. This extends to higher dimensions by adding an additional operation "Z++". Then the count to go from (0,0,0) to (5,6,7) is (5+6+7)!/(5!6!7!).

Whodi 14y ago

If you follow the links, this was asked to someone interviewing for a job on the Windows team who then posted it to an interview question aggregator, so it's likely that the actual phrasing of the question was lost. But as best as I can tell, they're considering each 1x1x1 space to be a node like a Rubix cube, and they want a list of all possible paths from the center node to the surface. I imagine that half of the question is making sure that the interviewee presses for details, because there's plenty of problems I see with the question right off the bat. If n is even, there's no single center node, so where does the algorithm start? Can the algorithm traverse diagonally by edges, or only by adjacent faces? Not to mention that there's an infinite number of possible paths for some values of n, assuming paths can cross themselves, for the same reason that there's an infinite number of paths from my front door to my car if I feel like walking in circles for a while.

arjn 14y ago

The first thing I thought was , this may be a trick question, since there are an infinite number of paths from the center to the surface. I think the problem statement needs a bit more detail.