Directi Interview Question
InternsCountry: India
Interview Type: In-Person
Sure.
Consider this example:
a b a e
b c d f
Suppose your first traversal gave the following path:
a b a e f d c b (which is the clockwise walk)
When you try another traversal, like going from the first a to the b just below:
a b
The natural next step would be going to the c (to the right of b), correct? This would give the following partial walk:
a b c
However, by this point you know that "abc..." will be worse than "abaefdcb" regardless of how to finish walking the grid, since c > a at the position 3. Therefore, you can cancel this walk.
This is the branch-and-bound technique.
The case that's really problematic here is where, for example, you have all a's with one b in there. For most of the strings attempted, branch and bound would not short-circuit fast enough and you'd get a worst case O(n^2) complexity.
I think you could improve this by only starting a walk on the lowest characters in the matrix. You then only progress each of these walks if its next valid lowest step is as low as the lowest from all other of these walks. You progress each walk in lock step with each other and trim the losers at every step. You will never progress any walk further then it matches the real lowest walk.
Backtracking with branch-and-bound.
- Victor November 24, 2014Perform every possible way of walking the grid, making sure you only execute valid steps. Store the best walk you've already come across.
At any given step, check if the current partial walk is leading to a better solution (by lexicographically comparing the partial string to the best string so far). If this partial walk is already worse than the best walk you found, no point in continuing, so cut this branch.