4 ms·

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 numbe

by 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!).
Someone 14y ago
"I vaguely recall counting lattice paths in 3-space being a wickedly hard problem with no known polynomial time solution." I think you can easily write the recursion: p(x,y,z) = p(x-1,y,z) + p(x,y-1,z) + p(x,y,z-1) Leave out the term with x-1, y-1, or z-1 for the edge cases for x, y, and/or z equal to zero. With that in hand, it is easy to compute all values bottom up, starting with those where x+y+z = 0, 1, 2, etc. Definitely fewer than (x+y+z)^3 values to compute, all of them in O(1) (disregarding cases where the numbers become bignums) Generalization to any number of dimensions seems easy, too. A closed form solution, that might be harder.
- pjscott 14y ago
  You're assuming that all movement must be in one of three directions, but in general, you can go in six directions -- forward or backward along the x, y, and z axes. Your cubic-time DP algorithm doesn't solve the self-avoiding walk problem, which I think is what jsolson vagely recalls. http://en.wikipedia.org/wiki/Self-avoiding_walk http://en.wikipedia.org/wiki/Self-avoiding_walk
  - jsolson 14y ago
    So, the professor in question was Dana Randall. I believe she was talking about this topic: http://en.scientificcommons.org/42983059 http://en.scientificcommons.org/42983059 Basically, yes, self-avoiding paths. This was basically a brief aside in her honors undergrad algorithms course, so the topic was a bit beyond what I was prepared for at the time :)
  - Someone 14y ago
    I wasn't assuming, I was following what the OP wrote: "by going only up or right one point with each move (that is, each move is either (0,1) or (1,0)))" for 3D. Counting self-avoiding walks is hard in 2D, too (http://oeis.org/A007764 http://oeis.org/A007764)

by jsolson 14y ago

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!).

Someone 14y ago

"I vaguely recall counting lattice paths in 3-space being a wickedly hard problem with no known polynomial time solution." I think you can easily write the recursion: p(x,y,z) = p(x-1,y,z) + p(x,y-1,z) + p(x,y,z-1) Leave out the term with x-1, y-1, or z-1 for the edge cases for x, y, and/or z equal to zero. With that in hand, it is easy to compute all values bottom up, starting with those where x+y+z = 0, 1, 2, etc. Definitely fewer than (x+y+z)^3 values to compute, all of them in O(1) (disregarding cases where the numbers become bignums) Generalization to any number of dimensions seems easy, too. A closed form solution, that might be harder.

pjscott 14y ago
You're assuming that all movement must be in one of three directions, but in general, you can go in six directions -- forward or backward along the x, y, and z axes. Your cubic-time DP algorithm doesn't solve the self-avoiding walk problem, which I think is what jsolson vagely recalls. http://en.wikipedia.org/wiki/Self-avoiding_walk http://en.wikipedia.org/wiki/Self-avoiding_walk
- jsolson 14y ago
  So, the professor in question was Dana Randall. I believe she was talking about this topic: http://en.scientificcommons.org/42983059 http://en.scientificcommons.org/42983059 Basically, yes, self-avoiding paths. This was basically a brief aside in her honors undergrad algorithms course, so the topic was a bit beyond what I was prepared for at the time :)
- Someone 14y ago
  I wasn't assuming, I was following what the OP wrote: "by going only up or right one point with each move (that is, each move is either (0,1) or (1,0)))" for 3D. Counting self-avoiding walks is hard in 2D, too (http://oeis.org/A007764 http://oeis.org/A007764)