Interview Question
Country: United States
This problem will be divide in 3 sub problem.
1) find same length word in dictionary
2) First char must be equal
3) last char must be equal
If any dictionary word match with this condition than word NOT unique.
Complexcity: O(n) n= dictionary word list
static void Main(string[] args)
{
Dictionary<string,string> dict = new Dictionary<string, string>()
{
{"internationalization", "i18n"},
{"localization","l10n"},
{"dog","d1g"},
{"accessibility","a11y"}
};
Console.WriteLine(IsAbbrUnique(dict, "dig"));
Console.WriteLine(IsAbbrUnique(dict, "digger"));
Console.ReadLine();
}
static bool IsAbbrUnique(Dictionary<string,string> dict, string word)
{
return !dict.Values.Any(value => value == word[0] + (word.Length - 2).ToString() + word[word.Length - 1]);
}
A large part of this problem complexity depends upon the structure of the Dictionary. if the Dictionary is a list of Strings, then the complexity would be dependent upon the length of the list. If the content is a Trie or some other tree like structure, then you'd have to iterate and find possible solutions.
Assuming the dictionary is a List of Strings and you will run this operation once
public static boolean isOverloaded(List<String> dictionary, String word){
char first = word.charAt(0);
char last = word.charAt(word.length() -1);
int totalSize = word.length();
for(String str : dictionary){
if(str.length() == totalSize
&& str.charAt(0) == first
&& str.charAt(str.length() -1) == last
&& !word.equals(str) ){
return true;
)
)
return false;
}
If string is tree, you have to travel the tree (each node once) and check length. if length equal than you will match first and last char. What extra complexity you are thinking.
- Aerofoil.kite December 11, 2014