Coupon Dunia Interview Question
SDE-2sCountry: India
Interview Type: Phone Interview
Shouldn't the insertion into the hashTable in the last line of for loop {{hashTable.insert({s,dp[i]});}}
If i am not wrong, it can be solved much easier -
Record < string,string_len> for each word;
Sort the container according to string_len in non-decreasing order.
starting from beginning, search for longest increasing subarray and keep track or maximum length subarray.
return maxlen subarray.
If the words/strings in the library are all subsets of each other, then the longest possible chain will be n.
E.g. If the words are: a, ab, abc, abcd, abcde, abcdef, .... ,abcde..xyz. You have 26 words (n = 26). Start with the last word and remove the char z, it will now be the same as the second last word. Now remove the char y, it will be same as third last word and so on till we reach the first word a. So the longest possible chain is n
can you please suggest a suitable data structure for this.? also time complexity should be as minimum as possible.
Data structure can be as simple as using an array to store all the strings.
Arr1[n] = {a, ab, abc, abcd, ..., abcd..xy, abcd...xyz}
Complexity will be linear ~ O(n). We will walk the array once. At each step select one string, remove last char and compare to the next string.
Can't come up with a more efficient solution than the dynamic programming approach, but as an alternative, you can model the problem as a graph problem. More specifically, by building one or more acyclic directed graphs in this manner:
1. For each word, associate it with a graph node.
2. For each word, generate the list of words that can be derived from it based on the problem's rule (i.e. take one character out from each character position). Compare these to the rest of the words. For each match, link the node together, with the parent being the longer word.
3. Once you've passed through every word in (2), you'll have one or more ADGs and a list of nodes from said ADGs, but no knowledge of "root" nodes. But this doesn't matter.
4. For each node, compute its "longest distance to a leaf node"; you can use a cache of nodes:longest-distance to avoid doing duplicate computation for a given node.
The answer is the biggest number you find while iterating through nodes in step (4).
In Java:
import java.util.*;
/**
* Given a list of words, you can select any one word and remove a character from
* it such that it becomes another word in the library. Selected word is then discarded.
* You can then do the same with the new word in the latter.
*
* Now, given an arbitrary library of words, what is the longest chain of words you can
* play this game with?
*
* e.g.:
* For the library of words: ['a', 'aa', 'bb', 'bbc', 'cbbc'], the longest chain is 3 words
* because 'cbbc' -> 'bbc' -> 'bb' is the longest chain you can make out of the input set.
*
* (NOTE) This solution uses acyclic directed graph build-and-search method, and assumes
* or eliminates duplicate words.
*/
public class WordChainADG {
// the list of input words, in no particular order
private List<String> words;
public WordChainADG() {
}
public int longestChain(List<String> words) {
// initialize our scratch spaces
words = new ArrayList<String>(words);
HashMap<String, Node> nodes = new HashMap<String, Node>(); // mapping each word to a node
HashMap<Node, Integer> chainLengths = new HashMap<Node, Integer>(); // mapping each node to its longest chain length
int n = words.size();
// initialize the maps: create node for each word
for (String word : words) {
nodes.put(word, new Node(word));
}
// and a count of longest-chain-length for each node
for (String word : nodes.keySet()) {
Node node = nodes.get(word);
chainLengths.put(node, 0); // 0 indicates not yet determined
}
// build the (ADG) graphs
for (int i = 0; i < n; i++) {
String word = words.get(i);
int wordSize = word.length();
// try removing each character in the current word, and see if it matches any of the shorter words
for (int j = 0; j < wordSize; j++) {
String tempstr = trimCharacterAt(word, j);
Node node = nodes.get(tempstr);
if (node != null) {
// such a word exists! add the associated node to this word's node children
nodes.get(word).addChild(node);
}
}
}
// now we have 1 or more (ADG) graphs whose edges point from longer words to shorter words
// we need to find the maximum path in each graph, and then find the maximum of those maximum paths
int answer = 0;
// each node can be thought of as the root of a tree/ADG; so all we have to do is to find
// the maximum-path-to-a-leaf of each "root" and record the biggest number seen
HashSet<Node> allNodes = new HashSet<Node>(chainLengths.keySet());
for (Node node : allNodes) {
int longestPath = findLongestPath(node, chainLengths);
chainLengths.put(node, longestPath);
if (longestPath > answer) {
answer = longestPath;
}
}
System.out.println(chainLengths);
return answer;
}
// given a string, and an index within that string, take out
// the character on that index, and return the resulting string
private static String trimCharacterAt(String input, int index) {
if (index < 0 || index >= input.length()) {
throw new IndexOutOfBoundsException();
}
char[] astr = new char[input.length() - 1];
for (int i = 0, j = 0; i < input.length(); i++) {
if (i == index)
continue;
astr[j++] = input.charAt(i);
}
return new String(astr);
}
// a simple graph node in an ADG; associated with a word, and
// can have 0-N children (pointees of its outgoing edges)
private class Node {
private String word;
private ArrayList<Node> children;
public Node(String word) {
this.word = word;
children = new ArrayList<Node>();
}
public List<Node> getChildren() {
return children;
}
public void addChild(Node child) {
children.add(child);
}
@Override
public String toString() {
return "<Node(\"" + word + "\")>";
}
}
// given a node, find the longest path to a leaf;
// since we can assume that, starting from `node` the graph is ADG, we don't have to worry
// about cycles; additionally once the longest path of a node is computed, we can update
// this value in the cache given (`longestPaths`) so that the same computation for a given
// node is not repeated
private static int findLongestPath(Node node, Map<Node, Integer> longestPaths) {
int computed = longestPaths.get(node);
if (computed != 0) {
// already determined
return computed;
}
List<Node> children = node.getChildren();
// base case
if (children.size() == 0) {
longestPaths.put(node, 1);
return 1;
}
// recursive case
int childPath = 0;
for (Node child : node.getChildren()) {
int childLongestPath = findLongestPath(child, longestPaths);
if (childLongestPath > childPath) {
childPath = childLongestPath;
}
}
assert (childPath > 0);
longestPaths.put(node, 1 + childPath);
return 1 + childPath;
}
public static void main(String[] args) {
List<String> words = new ArrayList<String>();
Scanner input = new Scanner(System.in);
while (input.hasNext()) {
String word = input.next();
words.add(word);
}
int answer = new WordChainADG().longestChain(words);
System.out.println("Longest chain: " + answer);
}
}
public static int getLongestChainKLength(String[] words){
List<String> wordList = Arrays.asList(words);
Collections.sort(wordList,new Comparator<String>() {
@Override
public int compare(String str1, String str2) {
return str1.length()-str2.length();
}
});
Map<String ,Integer> map = new HashMap<String ,Integer>();
map.put(wordList.get(0),1);
int[] dp = new int[wordList.size()];
dp[0] =1;
int ans =dp[0];
for(int i=1;i < wordList.size();i++){
dp[i] =1;
String s = wordList.get(i);
int size = s.length();
for(int j=0;j<size;j++){
String newString = s.substring(0, j) + s.substring(j+1);
if(map.containsKey(newString)){
dp[i]= Math.max(dp[i], map.get(newString)+1);
}
}
ans = Math.max(ans, dp[i]);
map.put(s, dp[i]);
}
return ans;
}
public static int getLongestChainKLength(String[] words){
List<String> wordList = Arrays.asList(words);
Collections.sort(wordList,new Comparator<String>() {
@Override
public int compare(String str1, String str2) {
return str1.length()-str2.length();
}
});
Map<String ,Integer> map = new HashMap<String ,Integer>();
map.put(wordList.get(0),1);
int[] dp = new int[wordList.size()];
dp[0] =1;
int ans =dp[0];
for(int i=1;i < wordList.size();i++){
dp[i] =1;
String s = wordList.get(i);
int size = s.length();
for(int j=0;j<size;j++){
String newString = s.substring(0, j) + s.substring(j+1);
if(map.containsKey(newString)){
dp[i]= Math.max(dp[i], map.get(newString)+1);
}
}
ans = Math.max(ans, dp[i]);
map.put(s, dp[i]);
}
return ans;
}
By chain, do you mean the following statement:
If we remove a character from string S1 and it becomes S2, next time do we have to only remove a character from S2 and making another word in the inventory ?
If so, here's my dynamic programming approach:
- Sort words by their size (from smallest to longest).
- then, define dp[i] = The longest chain that can be formed from word[0] up to word[i] and ends at word[i].
- now, dp[i] = max( dp[j]+1) from all j from 0 to i, provided that by removing one character from word[i] we can have word[j].(we can use a hash map for checking this condition)
- final answer is max(dp[i]) 0<=i<N.
- The order is O(N*L*L), which N is the number of words and L is the maximum length of words.
- MehrdadAP July 21, 2015