Convert word1 to word2 interview question

PHP programming forum. Ask questions or help people concerning PHP code. Don't understand a function? Need help implementing a class? Don't understand a class? Here is where to ask. Remember to do your homework!

Moderator: General Moderators

Convert word1 to word2 interview question

Postby sparrrow » Mon Apr 06, 2009 11:12 pm

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).
sparrrow
Forum Commoner
 
Posts: 81
Joined: Mon Oct 20, 2008 12:22 pm

Re: Convert word1 to word2 interview question

Postby requinix » Tue Apr 07, 2009 1:21 am

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.
User avatar
requinix
Spammer :|
 
Posts: 5610
Joined: Wed Oct 15, 2008 2:35 am
Location: WA, USA

Re: Convert word1 to word2 interview question

Postby sparrrow » Tue Apr 07, 2009 6:48 pm

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.
sparrrow
Forum Commoner
 
Posts: 81
Joined: Mon Oct 20, 2008 12:22 pm

Re: Convert word1 to word2 interview question

Postby John Cartwright » Tue Apr 07, 2009 7:41 pm

You could use pspell_check to check the word permuations, but thats not very efficient :banghead:. This one has me stumped.
Code: Select all
if ($toBe || $notToBe) echo 'That is the question'; 

NEW HERE?: Please read the Forum Rules, and take the Forum Tour before posting!
User avatar
John Cartwright
Site Admin
 
Posts: 11470
Joined: Tue Dec 23, 2003 3:10 am
Location: Toronto

Re: Convert word1 to word2 interview question

Postby requinix » Tue Apr 07, 2009 8:48 pm

Just pretend you have a hash/dictionary/lookup array that you can use to check if a word exists. Like
Syntax: [ Download ] [ Hide ]
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.
Syntax: [ Download ] [ Hide ]
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.
User avatar
requinix
Spammer :|
 
Posts: 5610
Joined: Wed Oct 15, 2008 2:35 am
Location: WA, USA


Return to PHP - Code

Who is online

Users browsing this forum: Google [Bot] and 10 guests