PHP Developers Network

A community of PHP developers offering assistance, advice, discussion, and friendship.
 
Loading
It is currently Mon Dec 22, 2014 9:59 pm

All times are UTC - 5 hours




Post new topic Reply to topic  [ 5 posts ] 
Author Message
PostPosted: Mon Apr 06, 2009 11:12 pm 
Offline
Forum Commoner

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


Top
 Profile  
 
PostPosted: Tue Apr 07, 2009 1:21 am 
Offline
Spammer :|
User avatar

Joined: Wed Oct 15, 2008 2:35 am
Posts: 5710
Location: WA, USA
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.


Top
 Profile  
 
PostPosted: Tue Apr 07, 2009 6:48 pm 
Offline
Forum Commoner

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


Top
 Profile  
 
PostPosted: Tue Apr 07, 2009 7:41 pm 
Offline
Site Admin
User avatar

Joined: Tue Dec 23, 2003 3:10 am
Posts: 11470
Location: Toronto
You could use pspell_check to check the word permuations, but thats not very efficient :banghead:. This one has me stumped.


Top
 Profile  
 
PostPosted: Tue Apr 07, 2009 8:48 pm 
Offline
Spammer :|
User avatar

Joined: Wed Oct 15, 2008 2:35 am
Posts: 5710
Location: WA, USA
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.


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 5 posts ] 

All times are UTC - 5 hours


Who is online

Users browsing this forum: Bing [Bot], Google [Bot] and 7 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Jump to:  
Powered by phpBB® Forum Software © phpBB Group