Page 1 of 1

Convert word1 to word2 interview question

Posted: Mon Apr 06, 2009 11:12 pm
by sparrrow
The following code problem is one of the Amazon sample interview questions. I think it is written poorly which may be why I don't understand it. I also can't find any posted solutions with a google search. If anyone can help that would be great. Either just elaborate if you think you understand it, or posting some code is good too.

You are given a dictionary of all valid words. You have the following 3 operations permitted on a word: delete a character, insert a character, and replace a character. Now, given two words, $word1 and $word2, write a script to convert $word1 to $word2 using the minimum number of steps required. (One operation counts as 1 step).

Re: Convert word1 to word2 interview question

Posted: Tue Apr 07, 2009 1:21 am
by requinix
Ever played one of those word games where you have to turn one word into another, like "bear" into "claw", by changing one letter at a time? Except each change has to be a real word?
BEAR -> BEAT -> SEAT -> SLAT* -> SLAW* -> CLAW
(* narrow strip of wood; basically a salad, like coleslaw)

Here you can also add and remove letters.
WHITE -> WHIT* -> WIT -> LIT -> LIE
(* a small amount)

Given two words (bear, claw; white, lie) find the shortest path between the two.

Re: Convert word1 to word2 interview question

Posted: Tue Apr 07, 2009 6:48 pm
by sparrrow
Seems difficult to impossible to write with just what is provided though. They don't provide the dictionary or the words being converted. I would just be tempted to str_split the words to character arrays, parse through each element one at a time beginning to end, then delete any extra letters at the end. That would mean the words in the middle of the operation wouldn't be real words though. You could remove all of the non-shared characters, then insert the missing ones where needed, but that seems like a stretch.

Re: Convert word1 to word2 interview question

Posted: Tue Apr 07, 2009 7:41 pm
by John Cartwright
You could use pspell_check to check the word permuations, but thats not very efficient :banghead:. This one has me stumped.

Re: Convert word1 to word2 interview question

Posted: Tue Apr 07, 2009 8:48 pm
by requinix
Just pretend you have a hash/dictionary/lookup array that you can use to check if a word exists. Like

Code: Select all

if (isset($dictionary[$word])) {
    // $word is a word
} else {
    // $word is not a word
}
There's a "simple" way to do this, but it's really horrible: you brute-force it.

Start systematically doing stuff.
- Too few letters: add a letter
- Too many letters: remove a letter
- Same number of letters: replace a letter
Remember, each new string has to be a word.
Problem is, you're trying to find the shortest path, not any path at all. Which means you have to run all these possibilities at the same time.

Code: Select all

WHITE
(remove a letter (5), and replace a letter (5*25))
HITE, WITE, WHTE, WHIE, WHIT, AHITE, BHITE..., YHITE, ZHITE, WAITE, WBITE..., WHATE..., WHIAE..., WHITA
(filter to remove only the words that exist and haven't been tried. according to firefox's spellcheck:)
WHIT, WAITE, WRITE, WHILE, WHINE, WHITS
(and repeat. one line per word)
HIT, WIT, WHT, WHI, AHIT..., WAIT..., WHAT..., WHIA...,
AITE, WITE, WATE, WAIE, WAIT, AAITE...,
RITE...,
HILE...,
HINE...,
HITS...
Eventually you'll find LIE. But you have to keep track of the path taken. More complexity.