## Coupon Dunia Interview Question for SDE-2s

Country: India
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
1
of 1 vote

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.

``````#include <bits/stdc++.h>

using namespace std;

const int maxn=10000;

unordered_map< string,int > hashTable;
int dp[maxn];

int LongestChain(vector<string> V)
{

vector< pair<int,string> > list;
for (auto s:V){
list.push_back({s.size(),s});
}
sort(list.begin(),list.end());

int N=list.size();
hashTable.insert( {list[0].second,0} );
dp[0]=1;

for (int i=1;i<N;i++){
dp[i]=1;
string s=list[i].second;

int size = s.size();
for (int j=0;j<size;j++){

string tmpStr = s;
tmpStr.erase(tmpStr.begin()+j);
auto it = hashTable.find(tmpStr);

if (it!=hashTable.end())
dp[i] = max (dp[i],dp[it->second]+1);
}

hashTable.insert({s,i});

}

}

int main()
{

int N;
cin >> N;
vector<string> V(N);
for (int i=0;i<N;i++)
cin >> V[i];

cout << LongestChain(V) << endl;

return 0;
}``````

Comment hidden because of low score. Click to expand.
0

can you code it in c

Comment hidden because of low score. Click to expand.
0

can you do it in c

Comment hidden because of low score. Click to expand.
0

Shouldn't the insertion into the hashTable in the last line of for loop {{hashTable.insert({s,dp[i]});}}

Comment hidden because of low score. Click to expand.
0

Shouldn't {{hashTable.insert({s,i});}} be {{hashTable.insert({s,dp[i]});}}

Comment hidden because of low score. Click to expand.
0

Shouldn't {{hashTable.insert({s,i});}} be {{hashTable.insert({s,dp[i]});}}

Comment hidden because of low score. Click to expand.
0

do we really need unordered map? can we do with only map(normal)?

Comment hidden because of low score. Click to expand.
1
of 1 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0

can you please suggest a suitable data structure for this.? also time complexity should be as minimum as possible.

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

It's not necessary that they are sorted in the way you want.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.
*/

// the list of input words, in no particular order
private List<String> words;

}

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
}

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
}
}
}

// 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

// 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);

}
}

System.out.println(chainLengths);

}

// 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;
}
}
@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) {
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();
}

}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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;
}``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.