find a string in a grid

[puzzlecracker]

Hi guys,

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

 

[red floyd]

Hi guys,

[way OT redacted]

That's nice. And your C++ question was?

 

[puzzlecracker]

That's nice. And your C++ question was?

answer it in C++, what a gleeful venture!

 

[Jerry Coffin]

puzzlecracker wrote:

[ ... ]

answer it in C++, what a gleeful venture!

Apparently you take glee in recursion?

 

[Ioannis Vranos]

Apparently you take glee in recursion?

What recursion? Why recursion?

 

[Karl Heinz Buchegger]

answer it in C++, what a gleeful venture!

Why should we?
Besides: it is relatively simple to do. No challenge
in that. A quick estimate: less then one hour, probably
more in the range of half an hour (with testing).

 

[puzzlecracker]

Why should we?
Besides: it is relatively simple to do. No challenge
in that. A quick estimate: less then one hour, probably
more in the range of half an hour (with testing).

IT IS NOT SO SIMPLE TO COME UP WITH EFFICIENT SOLUTION

 

[Karl Heinz Buchegger]

IT IS NOT SO SIMPLE TO COME UP WITH EFFICIENT SOLUTION

First make it work, then make it work fast.
Do you have a working solution?

 

[Mike Smith]

IT IS NOT SO SIMPLE TO COME UP WITH EFFICIENT SOLUTION

Since when does Microsoft care about efficient solutions? The MS
interviewer will grade the solution based on:

1) whether it has a catchy, trademarkable name

2) whether you implemented a pop-up Clippy window to ask for help
running the program

3) how many service packs can be released for the program, and whether
or not MS might be able to charge for them

4) whether there are any ridiculously simple algorithms in the program
that MS can patent, then use the patents to sue other companies

Actually working *at all* will be #5 on the list at best, and working
*efficiently* won't be anywhere near the list, or anywhere near the town
of Redmond for that matter.

 

[puzzlecracker]

Since when does Microsoft care about efficient solutions? The MS
interviewer will grade the solution based on:

1) whether it has a catchy, trademarkable name

2) whether you implemented a pop-up Clippy window to ask for help
running the program

3) how many service packs can be released for the program, and whether
or not MS might be able to charge for them

4) whether there are any ridiculously simple algorithms in the program
that MS can patent, then use the patents to sue other companies

Actually working *at all* will be #5 on the list at best, and working

*efficiently* won't be anywhere near the list, or anywhere near the town
of Redmond for that matter.

so much prejudice about microsoft. I know people that work there -
really top class in the field.... and they DO care about the
efficiency...

 

[Karl Heinz Buchegger]

Since when does Microsoft care about efficient solutions? The MS
interviewer will grade the solution based on:

1) whether it has a catchy, trademarkable name

2) whether you implemented a pop-up Clippy window to ask for help
running the program

3) how many service packs can be released for the program, and whether
or not MS might be able to charge for them

4) whether there are any ridiculously simple algorithms in the program
that MS can patent, then use the patents to sue other companies

5) can a COM object be made from it and how hard would it be to generate HTML
output from it.

6) How often during startup can the program emit the error: 'DLL not found'.

7) can gets() be used with it? (Important for opening the virus-loopholes)

8) How high is the potential for changing the GUI and nothing else in the next
few years, such that the whole thing can be sold again as the best since the
invention of the wheel.

9) Is it possible to integrate features that nobody asks for or needs.

10) Does it take more then 10 MB on the hard disk or in memory when loaded?

Actually working *at all* will be #5 on the list at best, and working

****

Make that number bigger. Much bigger!

 

[Karl Heinz Buchegger]

so much prejudice about microsoft. I know people that work there -
really top class in the field.... and they DO care about the
efficiency...

Personally I believe, that most of the worst programmers on this
planet work for MS.