Reference Problem :-
http://www.geeksforgeeks.org/flipkart-interview-set-6/
Problem statement
Given a Alien language, we have the dictionary of that language , but we have only very few words, but they are all arranged in the lexicographical order. We need to first find whether we will be able to get a alphabetical order or not, if yes explain approach
Eg:
http://www.geeksforgeeks.org/flipkart-interview-set-6/
Problem statement
Given a Alien language, we have the dictionary of that language , but we have only very few words, but they are all arranged in the lexicographical order. We need to first find whether we will be able to get a alphabetical order or not, if yes explain approach
Eg:
abc
acd
bcc
bed
bdc
dab
The order of letters for the given example would be
a->b->c->e->d
My approach
Answer :-
Process is divided
in two parts.
PART 1 ) CREATE
SEQUENCE
Visit every string and create a sequence of their initial
character.
Also we will populate a map (character and list of
strings). Those strings which started with this character (key of map) will be
considered. We will enlist substring after initial character.
So for strings,
abc
acd
bcc
bed
bdc
dab
After visiting all strings, sequence is
a->b->d
So Map will be
a [bc,cd]
b [cc,ed,dc]
d [ab]
Now for each we will call same procedure
1) So for map
“a [bc,cd]” list is [bc,cd]
Sequence will be
b ->c
And map will be
b [c]
c [d]
As each list has only one string; there is no use of
calling method those lists
2) ) So for map
“b [cc,ed,dc]” list is [cc,ed,dc]
Sequence will be
c->e->d
And map wil be
c [c]
e [d]
d [c]
As each list has only one string; there is no use of
calling method for those list
PART 2) RECONCILE
SEQUENCE
After part 1, we have three sequences
a->b->d
b ->c
c->e->d
Now we need to reconcile these sequences.
Till we have more
than one sequence we need to try all combination of sequences
Reconcile two sequences
Check if t2 is completely
present in t1 (directly or indirectly)
Example 1). t1 =
a->b->c t2 = b->c
So t2 is present. Remove t2 from list
Example 2) If t1 = a->b->d->x->c t2 = b->c
Root of t2 i.e. “b” is present is present in t1.
Next of root of t2 i.e. “c” is present downward in sequence.
So it sequence is b->c indirectly present in t1. So
remove t2 from list
Check if t2 is partially
present in t1.
“Leaf node of t1”
case
t1 = a->b->c t2 = b->c->m->n
b->c part is already present.
“c” is leaf node so attach remaining part to t1
t1 == = a->b->c->m->n
So remove t2 from list.
“Non leaf node of
t1” case
t1 = a->b->d ->c->p t2 = b->c->m->n
b->c part is already present.
“c” is non leaf node of t1.
So remove redundant part of t2. t2 == c->m->n
t1 remain as it is
As sequence are modified by one of the above condition,
try again reconciling till there remains only one sequence.
Java implementation
It is also shared at http://ideone.com/W7NMpN
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Set;
class Dictionary {
public static void main(String[] args) {
ArrayList<String> dictionary = new ArrayList<String>();
dictionary.add("abc");
dictionary.add("acd");
dictionary.add("bcc");
dictionary.add("bed");
dictionary.add("bdc");
dictionary.add("dab");
ArrayList<CharNode> treeList = new ArrayList<CharNode>() ;
buildDictionaryTree(dictionary,treeList);
System.out.println("Printing trees");
for(CharNode lst:treeList){
System.out.println(lst);
}
reconcileTrees(treeList);
System.out.println("Final tree is ");
System.out.println(treeList.get(0));
System.out.println("done");
}
public static void reconcileTrees(ArrayList<CharNode> treeList){
while(treeList.size()>1){
for(int i =0;i<treeList.size();i++){
for(int j =i+1;j<treeList.size();j++){
mergeOrModifyTwoTrees(treeList,i,j,true);
// if list is not modified call reverse way
if(i<treeList.size() && j<treeList.size()){
mergeOrModifyTwoTrees(treeList,j,i,true);
}
}
}
}
}
public static void mergeOrModifyTwoTrees(ArrayList<CharNode> treeList , int first , int secodnd,boolean firstCall){
CharNode t1 = treeList.get(first);
CharNode t2 = treeList.get(secodnd);
// Check if root of t2 is found in tree of t1
CharNode currOfT1 = t1;
CharNode currOfT2 = t2;
CharNode lastMatchingNodeOfT1 =null,lastMatchingNodeOfT2=null;
while(currOfT2!=null){
while(currOfT1 != null && currOfT1.value !=currOfT2.value ){
currOfT1 = currOfT1.nextNode;
}
if(currOfT1 != null){
// loop ended when currOfT1 so match for t2 found in t1
// So go for next of t2
lastMatchingNodeOfT1 = currOfT1;
lastMatchingNodeOfT2 = currOfT2;
currOfT2 = currOfT2.nextNode;
}else{
// no match found for current node
break;
}
}
if(lastMatchingNodeOfT1 == null && lastMatchingNodeOfT2 == null){
return;
}
if(currOfT2==null){
// t2 is completely present in t1 directly or indirectly
// So remove from arrayList
treeList.remove(t2);
}else{
// There is part of t2 that is not present in t1
if(lastMatchingNodeOfT1 != null && lastMatchingNodeOfT1.nextNode ==null){
// lastMatchingNodeOfT1 was a leaf node then you can append remaining of t2 there
lastMatchingNodeOfT1.nextNode = currOfT2;
treeList.remove(t2);
}else{
// lastMatchingNodeOfT1 is not present or NOT leaf.
// Do reverse way. Check if next of lastMatchingNodeOfT1 is present t2
// e.g. t1==a->b->d t2 == b->c->e->d
// lastMatchingNodeOfT1 == b->d
// lastMatchingNodeOfT2 == b->c->e->d
// So check if lastMatchingNodeOfT1.nextNode i.e. "d" is present in lastMatchingNodeOfT2
CharNode temp = lastMatchingNodeOfT2.nextNode;
CharNode nodeBeforeTemp = lastMatchingNodeOfT2;
while(temp !=null && temp.value != lastMatchingNodeOfT1.nextNode.value){
nodeBeforeTemp = temp;
temp = temp.nextNode;
}
// t1== a->b->d->n t2 == b->c->e->d->m
// them lastMatchingNodeOfT1=lastMatchingNodeOfT2= b
// lastMatchingNodeOfT1.next = d->n
// temp = d->m
// nodeBeforeTemp = e->d->m
//
if(temp !=null ){
nodeBeforeTemp.nextNode = lastMatchingNodeOfT1.nextNode; // e->d->n
lastMatchingNodeOfT1.nextNode = lastMatchingNodeOfT2.nextNode; // a->b->c
// together it became a->b->c->e->d->n
if(temp.nextNode !=null){
treeList.remove(t2);
treeList.add(secodnd, temp); // d->m added as separate string
}else{
// t2 is completely consumed
treeList.remove(t2);
}
}
}
}
// do the same for reverse
}
public static void buildDictionaryTree(ArrayList<String> dictionary, ArrayList<CharNode> treeList){
//System.out.println("Input strings are");
//System.out.println(dictionary);
if(dictionary.size()>1){
CharNode currentNode = null;
HashMap<Character, ArrayList<String>> charStringMap = new HashMap<Character, ArrayList<String>>();
for(String str : dictionary){
char firstChar = str.charAt(0);
ArrayList<String> strlst = charStringMap.get(firstChar);
if(strlst==null){
//first time this character was visited
strlst = new ArrayList<String>();
charStringMap.put(firstChar,strlst);
}
// If this string is more than one character add substring to this list
if(str.length()>1){
strlst.add(str.substring(1));
}
if(currentNode==null){
// First time creating tree in this call. So create node and also add it in input tree list
currentNode = new CharNode(firstChar);
treeList.add(currentNode);
}else{
if(currentNode.value==firstChar){
// We are still processing strings starting with same character so no need to add in tree
}else{
currentNode.nextNode=new CharNode(firstChar);
currentNode= currentNode.nextNode;
}
}
}
// All first character done. Now call same process for substrings one by one
// Each call will create a separate tree
Set<Character> charCovered = charStringMap.keySet();
for(char ch:charCovered){
buildDictionaryTree(charStringMap.get(ch),treeList);
}
}else{
//System.out.println("Only one string. No use");
}
}
}
class CharNode{
char value;
CharNode nextNode;
public CharNode(char value) {
this.value=value;
}
@Override
public String toString() {
if(nextNode!=null){
return value+"->"+nextNode.toString();
}else{
return value+"";
}
}
}
No comments:
Post a Comment