Amazon Interview Question
Country: India
Interview Type: Phone Interview
1. Pick all combinations of words one by one. if diff in there size is 1, then find edit distance between two words[consider only deletion scenario]
Now we will create graph and find longest path
2. If Edit distance is 1 between two words then add one directed edge between two words in the Graph.
3. Now we can find the longest path
1. Pick all combinations of words one by one. if diff in there size is 1, then find edit distance between two words[consider only deletion scenario]
Now we will create graph and find longest path
2. If Edit distance is 1 between two words then add one directed edge between two words in the Graph.
3. Now we can find the longest path
public class DictionaryChain {
public static StringGraph startingPoint = null;
public static int highestDepth = 0;
public static void main(String[] args) {
String[] w = {"a", "b", "ba", "bca", "bda", "bdca"};
System.out.println(biggestWordChain(w));
String[] w2 = {"a", "b", "ba", "bca", "bda", "bdca", "bdcaf", "f", "bdcafg", "g", "asdsddsdsa", "xyzxyzyxyz"};
System.out.println(biggestWordChain(w2));
}
public static String biggestWordChain(String[] words) {
Map<Integer, ArrayList<StringGraph>> wordSet = new HashMap<Integer, ArrayList<StringGraph>>();
int maxLength = Integer.MIN_VALUE, minLength = Integer.MAX_VALUE;
for(String word : words) {
if(!wordSet.containsKey(word.length())) {
wordSet.put(word.length(), new ArrayList<StringGraph>());
}
StringGraph newString = new StringGraph(word);
wordSet.get(word.length()).add(newString);
maxLength = Math.max(maxLength, word.length());
minLength = Math.min(minLength, word.length());
}
for(int i=minLength+1; i<=maxLength; i++) {
findEveryNeighbors(wordSet, i);
}
return printStringGraph();
}
public static void findEveryNeighbors(Map<Integer, ArrayList<StringGraph>> wordSet, int index) {
List<StringGraph> wordLists = wordSet.get(index);
int depth;
if(wordLists == null) {
return;
}
for(StringGraph wordList : wordLists) {
depth = addNeighbors(wordList, wordSet.get(index-1));
if(depth > highestDepth) {
highestDepth = depth;
startingPoint = wordList;
}
}
return;
}
public static int addNeighbors(StringGraph wordGraph, ArrayList<StringGraph> neighborLists) {
int currentDepth = -1;
if(neighborLists == null) {
return currentDepth;
}
for(StringGraph neighborList : neighborLists) {
if(!isDictionaryChain(wordGraph.strName, neighborList.strName)) {
continue;
}
if(neighborList.strDepth > currentDepth) {
currentDepth = neighborList.strDepth;
wordGraph.longestString = neighborList;
}
}
wordGraph.strDepth = (currentDepth > -1)?currentDepth+1:0;
return wordGraph.strDepth;
}
public static boolean isDictionaryChain(String source, String target) {
boolean alreadyDeleted = false;
for(int i=0; i<target.length(); i++) {
if(source.charAt(i) != target.charAt(i)) {
alreadyDeleted = source.substring(i+1).equals(target.substring(i))?true:false;
return alreadyDeleted;
}
}
return true;
}
public static String printStringGraph() {
StringBuilder result = new StringBuilder();
StringGraph finalGraph = startingPoint;
while(finalGraph != null) {
result.append(finalGraph.strName);
result.append(" -> ");
finalGraph = finalGraph.longestString;
}
return result.toString();
}
}
class StringGraph {
String strName;
int strDepth;
StringGraph longestString;
public StringGraph(String name) {
strDepth = 0;
strName = name;
longestString = null;
}
}
/*
Output:
bdca -> bca -> ba -> a ->
bdcafg -> bdcaf -> bdca -> bca -> ba -> a ->
*/
public class DictionaryChain {
public static StringGraph startingPoint = null;
public static int highestDepth = 0;
public static void main(String[] args) {
String[] w = {"a", "b", "ba", "bca", "bda", "bdca"};
System.out.println(biggestWordChain(w));
String[] w2 = {"a", "b", "ba", "bca", "bda", "bdca", "bdcaf", "f", "bdcafg", "g", "asdsddsdsa", "xyzxyzyxyz"};
System.out.println(biggestWordChain(w2));
}
public static String biggestWordChain(String[] words) {
Map<Integer, ArrayList<StringGraph>> wordSet = new HashMap<Integer, ArrayList<StringGraph>>();
int maxLength = Integer.MIN_VALUE, minLength = Integer.MAX_VALUE;
for(String word : words) {
if(!wordSet.containsKey(word.length())) {
wordSet.put(word.length(), new ArrayList<StringGraph>());
}
StringGraph newString = new StringGraph(word);
wordSet.get(word.length()).add(newString);
maxLength = Math.max(maxLength, word.length());
minLength = Math.min(minLength, word.length());
}
for(int i=minLength+1; i<=maxLength; i++) {
findEveryNeighbors(wordSet, i);
}
return printStringGraph();
}
public static void findEveryNeighbors(Map<Integer, ArrayList<StringGraph>> wordSet, int index) {
List<StringGraph> wordLists = wordSet.get(index);
int depth;
if(wordLists == null) {
return;
}
for(StringGraph wordList : wordLists) {
depth = addNeighbors(wordList, wordSet.get(index-1));
if(depth > highestDepth) {
highestDepth = depth;
startingPoint = wordList;
}
}
return;
}
public static int addNeighbors(StringGraph wordGraph, ArrayList<StringGraph> neighborLists) {
int currentDepth = -1;
if(neighborLists == null) {
return currentDepth;
}
for(StringGraph neighborList : neighborLists) {
if(!isDictionaryChain(wordGraph.strName, neighborList.strName)) {
continue;
}
if(neighborList.strDepth > currentDepth) {
currentDepth = neighborList.strDepth;
wordGraph.longestString = neighborList;
}
}
wordGraph.strDepth = (currentDepth > -1)?currentDepth+1:0;
return wordGraph.strDepth;
}
public static boolean isDictionaryChain(String source, String target) {
boolean alreadyDeleted = false;
for(int i=0; i<target.length(); i++) {
if(source.charAt(i) != target.charAt(i)) {
alreadyDeleted = source.substring(i+1).equals(target.substring(i))?true:false;
return alreadyDeleted;
}
}
return true;
}
public static String printStringGraph() {
StringBuilder result = new StringBuilder();
StringGraph finalGraph = startingPoint;
while(finalGraph != null) {
result.append(finalGraph.strName);
result.append(" -> ");
finalGraph = finalGraph.longestString;
}
return result.toString();
}
}
class StringGraph {
String strName;
int strDepth;
StringGraph longestString;
public StringGraph(String name) {
strDepth = 0;
strName = name;
longestString = null;
}
}
/*
Output:
bdca -> bca -> ba -> a ->
bdcafg -> bdcaf -> bdca -> bca -> ba -> a ->
*/
Solution with O(max{nlogn, nk}) time complexity (k is length of longest word)
1. sort word by ascending order of lengths.
2. init hash table, to store (word, max_chain_length)
2. for a word w:
- set tmp max_chain_length(w) to 1
- for every char c in w, remove c from w, and call it w'. check in the hash table if w' exists - if yes, set tmp max_chain_length of w to max{tmp_max_chain_length, max_chain_length( w' + 1).
- insert (w, tmp max_chain_length) to hash table.
complexity analysis: we iterate over N words, for each one we iterate over its chars, and perform hash operations in O(1). thus total O(nk). (not including sorting)
JavaScript implementation. Let's say the longest words is K and we got N words the worst case will be:
1. Sorting O(NlogN)
2. for each word we work on every sub word length k-1 so it's O(K^2) and we do it for all the words so it's O(N*K^2)
Together it's O(NlogN + N*K^2) I add them because we don't know if K^2 > logN.
But in an actual dictionary it will run much faster because I added some optimisation so I don't check substrings if it won't be longer than the current maximum. But there are cases that the running time will still be that of O(NlogN + N*K^2)
/*
Sort an array of strings from longest to shortest
*/
let reverseSort = (a, b) => {
return -( a.length - b.length);
};
/*
Build a dictionary: String to Object
{
visited: boolean - Did we already visit this word
length: number - the length of the maximum chain
nextWord: string - the index for the next word in the dictionary
}
*/
let buildDictionary = (arr) => {
let dictionary = {};
arr.forEach((item)=> {
dictionary[item] = {
visited: false,
length: 1,
nextWord: null
};
});
return dictionary;
};
let findChainForWord = (originContext, originWord, dictionary) => {
let originWordCharArray = originWord.split('');
for(let i = 0; i < originWordCharArray.length ; i++){
//remove char
let tmpCharArray = originWordCharArray.splice(i,1);
let currentWord = originWordCharArray.join('');
let currentContext = dictionary[currentWord];
// this is a valid word in the dictionary
if(currentContext){
//build subchain
if(!currentContext.visited){
findChainForWord(currentContext, currentWord, dictionary);
}
// Change the current maximum to the new one if it's longer
if(currentContext.length + 1 > originContext.length){
originContext.length = currentContext.length + 1;
originContext.nextWord = currentWord;
}
}
//put the char back
originWordCharArray.splice(i,0, tmpCharArray[0]);
}
originContext.visited = true;
};
/*
Build a string from a chain node
*/
let buildResultChain = (dictionary, word) => {
let current = dictionary[word];
let res = `Length: ${current.length}: ${word} `;
while(current.nextWord){
res += ` -> ${current.nextWord}`;
current = dictionary[current.nextWord];
}
return res;
};
/*
This is the main method. It will return a string representation of the longest chain
*/
function findLongestChain(words) {
// Sort the words from the longest word to the shortest
words.sort(reverseSort);
//
let dictionary = buildDictionary(words);
let current = null;
words.forEach((word) => {
let wordObj = dictionary[word];
// we need to check only unvisited words. If I visit it already it must be part of a chain,
// meaning it won't be longer than the current longest
// Also, if current found word is longer than the word length, no need to check. The chain will never be as long
if (!wordObj.visited && !(current && dictionary[current].length >= word.length)) {
findChainForWord(wordObj, word, dictionary);
if(!current || dictionary[current].length < wordObj.length){
current = word;
}
}
});
return buildResultChain(dictionary, current);
}
let words = ['a', 'b', 'bca', 'ba', 'bda', 'bdca'];
console.log(findLongestChain(words));
//print Length: 4: bdca -> bca -> ba -> a
words = ['a', 'b', 'bca', 'bcdef', 'ba', 'abcd', 'bda', 'bdca', 'abcdef', 'cdef','cde','de','d', 'qqqqq'];
console.log(findLongestChain(words));
//print Length: 6: abcdef -> bcdef -> cdef -> cde -> de -> d
words = ['a'];
console.log(findLongestChain(words));
// print Length: 1: a
words = ['ba', 'agd', 'liuf','lkjda'];
console.log(findLongestChain(words));
// print Length: 1: lkjda (because we sort the dictionary this is the first word)
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
public class Chain {
static HashMap<String, ArrayList<String>> adjecentNode = new HashMap<>();
static{
ArrayList adjecentNodeList= new ArrayList<>();
adjecentNodeList.add("bda");
adjecentNodeList.add("bca");
adjecentNode.put("bdca",adjecentNodeList);
ArrayList adjecentNodeList_ = new ArrayList<>();
adjecentNodeList_.add("ba");
adjecentNode.put("bca", adjecentNodeList_);
ArrayList adjecentNodeList__ = new ArrayList<>();
adjecentNodeList__.add("ba");
adjecentNode.put("bda", adjecentNodeList__);
ArrayList adjecentNodeList_1 = new ArrayList<>();
adjecentNodeList_1.add("b");
adjecentNode.put("ba", adjecentNodeList_1);
ArrayList adjecentNodeList_2 = new ArrayList<>();
adjecentNodeList_2.add("a");
adjecentNode.put("ba", adjecentNodeList_2);
}
public static void main(String[] str){
System.out.println(findLongestChain("bdca"));
}
static ArrayList<String> findLongestChain(String word){
if(adjecentNode.get(word) == null){
ArrayList<String> a = new ArrayList<String>();
a.add(word);
return a;
}
int previousLength = 0;
ArrayList<String> prevList = new ArrayList<String>();
for(String adjecentNode : adjecentNode.get(word)){
ArrayList<String> list = findLongestChain(adjecentNode);
if( list.size() > previousLength ){
previousLength = list.size();
prevList = list;
}
}
prevList.add(word);
return prevList;
}
}
public class BiggestWordChain {
public static void main(String[] args) {
String[] w = {"a", "b", "ba", "bca", "bda", "bdca"};
System.out.println(biggestWordChain(w));
String[] w2 = {"a", "b", "ba", "bca", "bda", "bdca", "bdcaf", "f", "bdcafg", "g", "asdsddsdsa", "xyzxyzyxyz"};
System.out.println(biggestWordChain(w2));
}
public static int biggestWordChain(String[] w) {
int max = 1;
Map<String, Integer> wordCount = new HashMap<>();
for (int i = 0; i < w.length; i++) {
wordCount.put(w[i], wordCount.containsKey(w[i]) ? wordCount.get(w[i]) + 1 : 1);
}
// sort by size - start from bigger strings first - greedy aproach
Arrays.sort(w, new Comparator<String>() {
@Override
public int compare(String o1, String o2) {
return o1.length() > o2.length() ? -1 : o1.length() < o2.length() ? 1 : 0;
}
});
for (int i = 0; i < w.length; i++) {
String s = w[i];
if (s.length() > max) {
int currMax = biggestWordChain(wordCount, new StringBuilder(s));
max = Math.max(max, currMax);
}
}
return max;
}
public static int biggestWordChain(Map<String,Integer> words, StringBuilder s) {
int max = 0;
char[] c = s.toString().toCharArray();
for (int i = 0; i < c.length; i++) {
// try removing char
String newStr = null;
if (i == 0) {
newStr = s.substring(i+1);
} else if (i == c.length-1) {
newStr = s.substring(0, c.length-1);
} else {
newStr = s.substring(0, i) + s.substring(i+1);
}
if (newStr.equals("")) {
return 1;
}
if (words.containsKey(newStr)) {
max = 1;
if (words.get(newStr) > 1) {
words.put(newStr, words.get(newStr) - 1);
} else {
words.remove(newStr);
}
int newMax = 1 + biggestWordChain(words, new StringBuilder(newStr));
max = Math.max(max, newMax);
// put back attempted string - backtrack
words.put(newStr, words.containsKey(newStr) ? words.get(newStr) + 1 : 1);
}
}
return max;
}
}
/*
output:
4
6
*/
- create a map of word length and words.
- Initiate possible chain size 0 for all the words.
- For every word of length l starting from biggest word, see if they are able to form a chain with words of length l-1.
- if w1 of length l is chainable with word w2 of length l-1, assign possible_chain_size(w2) = possible_chain_size(w1)+1.
- Return maximum of chain size of all words.
For k, the length of the maximum word and n, number of words. It takes O(n^2) comparsions. Each comparision is O(k). So worst case scenario is O(k* n^2).
1) sort all words by length (if not)
- Sergey September 16, 20162) sort each word by chars. e.g:
{a, b, ba, bca, bda, bdca} -> {a, b, ab, abc, abd, abcd}
3) dynamic: add each word and check longest chain for all previous words chain
f(n+1 word) = max {f(n) f(n-1) ... f(1)} + 1
{a} - {1, 1}
{a, b} - {1, 1}
{a, b, ab} - {1, 1, 2}
{a, b, ab, abc} - {1, 1, 2, 3}
{a, b, ab, abc, abd} - {1, 1, 2, 3, 3}
{a, b, ab, abc, abd, abcd} - {1, 1, 2, 3, 3, 4}
complexity in worst case is O(n^2 k) there n is number of words and k is max len of longest word