hard puzzle
puzzlecracker
These are some MS questions which i encountered in a recent interview.
Hope it'll be helpfull to some of you.
#1. Given an n X m grid of characters. You are supposed to search for
a string with in this maze. The characters in the string need not be
alligned in a straight line. They just need to be holding adjusent
positiong.
eg
if this is a maze
a b d e f
r n a j u
g y m r l
e t i y u
The string namit should return a found(True "2,2 2,3 3,3 4,3 4,2" They
hold adjucent positions).
nobody
>#1. Given an n X m grid of characters. You are supposed to search for
>a string with in this maze. The characters in the string need not be
>alligned in a straight line. They just need to be holding adjusent
>positiong.
That's not hard at all, your typical search with backtracking.
Matt Timmermans
"nobody" <nob...@here.com> wrote in message
news:p97u119kc13cth55q...@4ax.com...
I would have given them a polynomial time answer.
--
Matt
Farhan
Per Vognsen
> Matt, what is the polynomial time answer?
It's an obvious application of dynamic programming. Each subproblem is
uniquely identified by a starting (x,y) position in the grid as well as
which suffix of the string to match. If the width and height of the
grid is m and n and the length of the string is l, this results in an
algorithm with a run-time of O(l*m*n).