Amazon Interview Question Senior Software Development Engineers
Team: Echo
Country: United States
Interview Type: Phone Interview
Indeed. In Python, for instance:
import io
import sys
from collections import deque
class Node(object):
def __init__(self, word, prev=None):
assert word
self._word = word
self._prev = prev
@property
def word(self):
return self._word
@property
def prev(self):
return self._prev
def contains(self, word):
"""Return True if this word is contained in this node,
or in any of its parent nodes.
"""
node = self
while node is not None:
if node.word == word:
return True
node = node.prev
return False
def to_chain(self):
"""Return the (reversed) chain of this word, starting from
this node and followed by its parents, as a list of words.
"""
ret = []
node = self
while node is not None:
ret.append(node.word)
node = node.prev
return ret
def __str__(self):
return str(self.to_chain())
def find_word_ladder(word_set, start, end):
"""Given a set of words (the dictionary, or the universe set of words),
a start word and an end word, return a list that represents a "word ladder",
if any exists.
A word ladder is a series of words, each one is one character off from its
previous.
"""
# first things first, sanitize user input
word_set = { word.upper() for word in word_set }
start = start.upper()
end = end.upper()
if not word_set or not start or not end:
return []
if len(start) != len(end):
return []
if start == end:
return [start,]
# reduce the universe set to only be those words with equal lengths
word_set = { word for word in word_set if len(word) == len(start) }
# remove the starting word
word_set.remove(start)
# now, prepare a BFS scratch spaces
q = deque()
q.append(Node(start))
terminus = None
while q:
node = q.popleft()
# generate all possible descendent words in the remaining universe set
# from this node's word
for word in word_set:
# the "children" of this node involve all words that
# have the "diff/distance" of 1 AND not already existing
# in this node's chain of words
if word == node.word:
continue
if _diff(word, node.word) == 1:
# found a child word of this node; create a child node
# based on this word, and linked to the currently examined node
child = Node(word, node)
if word == end:
# this is the earliest time where we can find the terminus!
terminus = child
break
elif not node.contains(word):
# cycle breaker!
q.append(Node(word, node))
if terminus is not None:
break
if terminus is None:
return []
# we found the terminus node! we can work backward from there to
# reconstruct the word ladder
return [word for word in reversed(terminus.to_chain())]
def _diff(word1, word2):
"""Given two words, return the number of differing characters in each
character position.
"""
assert len(word1) == len(word2)
diff = 0
for i, c in enumerate(word1):
if word2[i] != c:
diff += 1
assert diff != 0
return diff
def main(args):
wordfile, start, end = args[1:]
all_words = set()
# prepare a set (unique) of words from a dictionary file;
# make this set of words case-insensitive by transforming
# the input words to all UPPERCASE
with io.open(wordfile, 'r') as f:
for line in f:
for word in line.split():
all_words.add(word.upper())
ladder = find_word_ladder(all_words, start, end)
print repr(ladder)
return 0
if __name__ == '__main__':
sys.exit(main(sys.argv))
# e.g.:
# python wordladder.py /usr/share/dict/words FOOL WARM
# ['FOOL', u'WOOL', u'WOOD', u'WORD', u'WARD', u'WARM']
Naive Solution, representing the dictionary as a set
Runtime: O(n*m*o) where n is the number of steps in the ladder, m is the number of words in the dictionary, and o is the number of letters per word
Assumptions:
1. word length must be the same
2. no duplicate words allowed in a ladder
Done in python-ish
dictWords - an iterable set of all words in a dictionary
steps - an (initially empty) set that holds currently seen steps on the ladder
def main()
current = "..."
steps.add(current)
for x in range(10)
current = ladder(current)
steps.add(current)
print(current+" ->")
## case of end of ladder (no new words within 1 edit distance)
if( current.length == 0)
print("end of ladder")
break
def ladder(inpWord)
for word in dictWords
if word not in steps and distance(inpWord, word) == 1
return word
else
return ""
def distance(word1, word2)
if(len(word1) != len(word2)
return False
diff = 0
for x in range(len(word1))
if word1[x] != word2[x]:
diff += 1
if diff > 1:
return False
if diff == 1:
return True
This is an obvious graph problem. First create a node based on the first word, then add all available words in the dictionary that are off by one letter of the original word. Then add the same thing to those words until you add the antonym. Find the smallest distance between the two nodes.
public static List<String> getWordLadder(String one, String two, Set<String> words){
List<String> ladder = new ArrayList<>();
if(one == null || two == null || one.length()!=two.length())
return ladder;
ladder.add(one);
if(one.equals(two))
return ladder;
Set<Integer> visited = new HashSet<>();
boolean flag = true;
char [] temp = one.toCharArray();
while(flag){
flag = false;
for(int i=0; i<one.length(); i++){
if(!visited.contains(i)){
temp[i] = two.charAt(i);
String str = new String(temp);
if(words.contains(str)){
flag=true;
visited.add(i);
ladder.add(str);
} else {
//last element - restore what was there before we tried out two.charAt(i);
temp = ladder.get(ladder.size()-1).toCharArray();
}
}
}
}
if(!flag && visited.size()==one.length())
return ladder;
return new ArrayList<String>();
}
Hi,
It can be solved following the same steps as taken in BFS.
Here is a simple pseudo-code for the same:
First parameter is 'source' and the second parameter is 'target'
SourceToTarget(String source, String target)
---> Create Stack (stack)
--->Push source(String) to stack
--->while(!isStackEmpty(stack))
newWord=Pop(stack)
if(newWord!=target)
for(i=0;i<length(newWord))
presentChar=newWord.charAt(i)
for(letter= 'A' to 'Z')
if(letter==presentChar)
continue
newWord.charAt(i)=letter
if(existsInDictionary(newWord))
Push(newWord)
else
break;
import java.util.*;
public class WordLadder {
static List<String> finalList = new ArrayList<String>();
public static void main(String[] args) {
String inputString = "FOOL";
List<String> wordList = new ArrayList<String>();
wordList.add("SAGE");
wordList.add("PALE");
wordList.add("POOL");
wordList.add("SALE");
wordList.add("POLE");
wordList.add("POLL");
check(wordList, inputString);
}
private static void check(List<String> wordList , String inputString) {
for(String s : wordList) {
if(match(inputString, s) && !finalList.contains(s) && wordList.size() != finalList.size()) {
finalList.add(s);
System.out.println(s);
inputString = s;
check(wordList, inputString);
}
}
}
private static boolean match(String inputString, String s) {
boolean found = false;
for(int i = 0;i <inputString.length(); i ++) {
if(inputString.charAt(i) == s.charAt(i)) {
continue;
} else {
if(found) {
return false;
}
found = true;
}
}
return found;
}
}
import java.util.*;
public class WordLadder {
static List<String> finalList = new ArrayList<String>();
public static void main(String[] args) {
String inputString = "FOOL";
List<String> wordList = new ArrayList<String>();
wordList.add("SAGE");
wordList.add("PALE");
wordList.add("POOL");
wordList.add("SALE");
wordList.add("POLE");
wordList.add("POLL");
check(wordList, inputString);
}
private static void check(List<String> wordList , String inputString) {
for(String s : wordList) {
if(match(inputString, s) && !finalList.contains(s) && wordList.size() != finalList.size()) {
finalList.add(s);
System.out.println(s);
inputString = s;
check(wordList, inputString);
}
}
}
private static boolean match(String inputString, String s) {
boolean found = false;
for(int i = 0;i <inputString.length(); i ++) {
if(inputString.charAt(i) == s.charAt(i)) {
continue;
} else {
if(found) {
return false;
}
found = true;
}
}
return found;
}
}
import java.util.*;
public class WordLadder {
static List<String> finalList = new ArrayList<String>();
public static void main(String[] args) {
String inputString = "FOOL";
List<String> wordList = new ArrayList<String>();
wordList.add("SAGE");
wordList.add("PALE");
wordList.add("POOL");
wordList.add("SALE");
wordList.add("POLE");
wordList.add("POLL");
check(wordList, inputString);
}
private static void check(List<String> wordList , String inputString) {
for(String s : wordList) {
if(match(inputString, s) && !finalList.contains(s) && wordList.size() != finalList.size()) {
finalList.add(s);
System.out.println(s);
inputString = s;
check(wordList, inputString);
}
}
}
private static boolean match(String inputString, String s) {
boolean found = false;
for(int i = 0;i <inputString.length(); i ++) {
if(inputString.charAt(i) == s.charAt(i)) {
continue;
} else {
if(found) {
return false;
}
found = true;
}
}
return found;
}
}
package com.sec.strings;
public class WordLadder {
String words[] = new String[]{"WARD","COOL","TOOL","POOL","JYOTI","POLL","ROLL","TOLL","TOLE","NAMDEO","POLE","ROLE"};
public static void main(String args[]){
String str = "COOL";
WordLadder wl = new WordLadder();
wl.createWordLadder(str);
}
private void createWordLadder(String str) {
String ladder = "";
for (int i = 0; i < words.length; i++) {
if(str.length() == words[i].length()){
int count = 0;
for (int j = 0; j < str.length(); j++) {
if(str.charAt(j) == words[i].charAt(j)){
count++;
}
if(count == str.length()-1){
ladder = ladder + words[i] +" ";
count = 0;
str = words[i];
}
}
}
else{
continue;
}
}
System.out.println("Word Ladder is : "+ladder);
}
}
//End
#include <stdio.h>
char dict[][5] = { "FOOL", "POOL", "POLL", "POLE", "PALE", "SALE", "SAGE",
"COLD", "CORD", "CARD", "WARD", "WARM" };
int diff(char* s1, char* s2, int length){
int num = 0;
for (int i = 0; i < length; i++)
if (s1[i] != s2[i])
num++;
return num;
}
void ladder_until(char dict[][5], int length, char* start, char* end, struct index *id){
for (int i = 0; i < length; i++){
if (!diff(start, dict[i], 4)) id->s = i;
if (!diff(end, dict[i], 4)) id->e = i;
}
}
int ladder(char dict[][5], int index, char* start, char* end){
if (!diff(start, end, 4)) return 0;
if (diff(start, dict[index], 4) == 1)
return (1 + ladder(dict, index, dict[index], end));
else
return ladder(dict, index + 1, dict[index], end);
}
int main(){
struct index id = { "FOOL", -1, "POOL", -1 };
ladder_until(dict, sizeof(dict)/sizeof(dict[0]), id.start, id.end, &id);
if (id.s != -1 || id.e != -1)
return 0;
if (id.s < id.e)
printf("%d \n", ladder(dict, id.s, id.start, id.end));
else
printf("%d \n", ladder(dict, id.e, id.end, id.start));
return 0;
}
#include <stdio.h>
char dict[][5] = { "FOOL", "POOL", "POLL", "POLE", "PALE", "SALE", "SAGE",
"COLD", "CORD", "CARD", "WARD", "WARM" };
int diff(char* s1, char* s2, int length){
int num = 0;
for (int i = 0; i < length; i++)
if (s1[i] != s2[i])
num++;
return num;
}
void ladder_until(char dict[][5], int length, char* start, char* end, struct index *id){
for (int i = 0; i < length; i++){
if (!diff(start, dict[i], 4)) id->s = i;
if (!diff(end, dict[i], 4)) id->e = i;
}
}
int ladder(char dict[][5], int index, char* start, char* end){
if (!diff(start, end, 4)) return 0;
if (diff(start, dict[index], 4) == 1)
return (1 + ladder(dict, index, dict[index], end));
else
return ladder(dict, index + 1, dict[index], end);
}
int main(){
struct index id = { "FOOL", -1, "POOL", -1 };
ladder_until(dict, sizeof(dict)/sizeof(dict[0]), id.start, id.end, &id);
if (id.s != -1 || id.e != -1)
return 0;
if (id.s < id.e)
printf("%d \n", ladder(dict, id.s, id.start, id.end));
else
printf("%d \n", ladder(dict, id.e, id.end, id.start));
return 0;
}
BFS.
- MehrdadAP July 27, 2015