## Directi Interview Question for Interns

Country: India
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
1
of 1 vote

Backtracking with branch-and-bound.

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

Comment hidden because of low score. Click to expand.
0

Please, could you explain in details how to apply branch and bound approach.

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Can you please post code for this problem ?

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.