Given a Dictionary with a word and the weight (frequency, higher is better) of a word, like so -
var words = new Dictionary<string, int>();
words.Add("amazon", 10);
words.Add("amock", 10);
words.Add("amuck", 10);
words.Add("am", 8);
words.Add("as", 20);
words.Add("ant", 4);
words.Add("amazing", 7);
words.Add("ambiguous", 12);
words.Add("be", 10);
words.Add("bee", 3);
words.Add("bed", 12);A. Design an API that given a prefix, gets the word with the highest weight that matches the prefix.
So, prefix "a" returns "as", since weight is 20, prefix "am" returns "ambiguous", weight of "12" and not "amazon" which has weight 10.
- Preprocess as much as you like, the important thing is the runtime for the search.
//Generate all prefixes for the given words and then store the best based on weight in a Dictionary<string,string>
//and the lookup is now constant time.
//Did not use Trie, since I was able to get constant time lookup and runtime for GetWord was the biggest concern.
Dictionary<string, string> lookUp = new Dictionary<string, string>();
//Runtime - O(N*L) - N - number of words, L - avg word length.
public void GenerateLookUpDictionary(Dictionary<string, int> words)
{
foreach (var word in words)
{
for (int i = 1; i <= word.Key.Length; i++)
{
var prefix = word.Key.Substring(0, i);
var currWeight = word.Value;
if (lookUp.ContainsKey(prefix))
{
var oldWeight = words[lookUp[prefix]];
if (currWeight > oldWeight)
lookUp[prefix] = word.Key;
}
else
lookUp[prefix] = word.Key;
}
}
}
//API Method, this is constant time lookup
public string GetWord(string prefix)
{
if (lookUp.ContainsKey(prefix))
return lookUp[prefix];
return string.Empty;
}B. On the same API, now design a method, that given a prefix and a number k, returns the top "k" words that match the prefix. The order of words returned should be their weights (descending).
So, given prefix "a" and k = 6, the list returned is - "as", "ambiguous", "amazon", "amock", "amuck", "am" - no ordering needed when weights are the same.
- Like before, preprocess as much as you like, the important thing is the runtime for the search.
I think this is where things went wrong for me, I used a SortedDictionary to store the words, by weight and then retrieve the top k words.
Dictionary<string, SortedDictionary<int, List<string>>> lookUp = new Dictionary<string, SortedDictionary<int, List<string>>>();
//Worst case runtime - O(N*L*logN) - N - number of words, L - avg word length.
public void GenerateLookUpDictionary(Dictionary<string, int> words)
{
foreach (var word in words)
{
for(int i=1;i<=word.Key.Length;i++)
{
var prefix = word.Key.Substring(0, i);
var weight = word.Value*-1; //-1, since default ordering is ascending and I need weights sorted descending
if (lookUp.ContainsKey(prefix))
{
var dictVal = lookUp[prefix];
if (dictVal.ContainsKey(weight))
dictVal[weight].Add(word.Key);
else
dictVal.Add(weight, new List<string> { word.Key });
}
else
{
lookUp[prefix] = new SortedDictionary<int, List<string>>();
lookUp[prefix].Add(weight, new List<string> { word.Key });
}
}
}
}
//API Method, this lookup is now O(k)
public List<string> GetWord(string prefix, int k)
{
var output = new List<string>();
if(lookUp.ContainsKey(prefix))
{
var childDict = lookUp[prefix];
foreach (var key in childDict.Keys)
{
var val = childDict[key];
var take = Math.Min(val.Count, k);
output.AddRange(val.Take(take).ToList());
k -= take;
if (k == 0)
break;
}
}
return output;
}Is the SortedDictionary the best datastructure to use in this case, or is there something better?
I'm guessing that there must be something far better, since I was rejected post this interview.