Amazon Interview Question SDE-2s
Country: India
Interview Type: In-Person
By tour approach, It seems you are using to much of space.. If we already know that we have to HashMap then I do not think so we should with suffix approach as this will adds up extra space overhead.
One way which came to my mind is :
Maintain Map<Char, Set<WoldWrapper>> ...
where WordWrapper is wrapper classes for Actual String and Idx of the char which is present in the key..
The code will look like this :
public class DicWithHashmap
{
private static class WordWrapper
{
StringBuffer stringBuffer;
int idx;
WordWrapper(StringBuffer sb, int idx)
{
stringBuffer = sb;
this.idx = idx;
}
public boolean equals(Object ob)
{
if(ob instanceof WordWrapper)
return ((WordWrapper) ob).stringBuffer.equals(this.stringBuffer) &&
((WordWrapper) ob).idx == this.idx;
return false;
}
public int hashCode()
{
return 17*stringBuffer.hashCode()*idx;
}
}
static HashMap<Character,Set<WordWrapper>> map = new HashMap<Character, Set<WordWrapper>>();
public static void insertWord(StringBuffer world)
{
for(int i=0;i<world.length();i++)
{
Set<WordWrapper> set = map.get(world.charAt(i));
if(set == null)
{
set = new HashSet<WordWrapper>();
map.put(world.charAt(i),set);
}
set.add(new WordWrapper(world,i));
}
}
public static List<StringBuffer> getWorlds(char ch)
{
Set<WordWrapper> set = map.get(ch);
if(set == null)
return null;
List<StringBuffer> lst = new ArrayList<StringBuffer>();
for(WordWrapper wordWrapper : set)
{
if(wordWrapper.idx == 0)
lst.add(wordWrapper.stringBuffer);
}
return lst;
}
public static void main(String args[])
{
insertWord(new StringBuffer("bed"));
insertWord(new StringBuffer("able"));
insertWord(new StringBuffer("bell"));
insertWord(new StringBuffer("bore"));
insertWord(new StringBuffer("abore"));
insertWord(new StringBuffer("gbore"));
List<StringBuffer> sb = getWorlds('a');
for(StringBuffer s : sb)
System.out.println(s);
}
}
Let me know If I am thinking wrong...
Hi Khadar, I tried your code and it is working.. the ideea is ok.. like you have max 26 elements in the map with each element having a set of words/index. Performance wise i compared it with a simple HashSet<String> dictionary. Searching for 1 character in 100k word dictionary is much faster.. 16 ms compared to 3 ms. The only problem you have is when you need to search for words starting with String like "ab". It is somehow really hard to extend and get an optimal result. You need something like an iteration for the searched word for each character but in the same time.
Maintain the map with the following structure:
- Khadar Basha September 09, 2014key: String
value: LinkedList of indexes
While insertion:
Read the string and get all the suffixes and for every suffix, check if the current suffix is there in the map, if yes then retrieve it and add the current string's index to the list.
Example:
apple, apron, ape
apple:
(a,[1])
(ap,[1])
(app,[1])
(appl,[1])
(apple,[1])
apron:
(a,[1,2])
(ap,[1,2])
(apr,[2])
(apro,[2])
(apron,[2])
ape:
(a,[1,2,3])
(ap,[1,2,3])
(ape,[3])
Now to show the suggestions:
Read the string, and retrieve the list from the map, show the strings at the indexes as in list as suggestions:
For example:
Input:
ap
Output:
[1,2,3]
Input:
ape
Output:
[3]
Let me know if there exists any better approaches.