Interview Question


Country: United States




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

DICT = {}

def MAKE_ABBR(word):
    L = []
    if (word[0],word[-1]) in DICT:
        L = DICT[(word[0],word[-1])]
    L.append(len(word)-2)
    DICT[(word[0],word[-1])] = list(set(L))


def CHECK(word):
    L = []
    if (word[0],word[-1]) in DICT:
        L = DICT[(word[0],word[-1])]
    
    if((len(word)-2) in L):
        return False
    else:
        return True

DICTIONARY = ['kite','cat', 'cut', 'book', 'body', 'box', 'an']

for x in DICTIONARY:
    MAKE_ABBR(x)

word = 'baby'
print CHECK(word)

- Aerofoil.kite December 11, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Rajesh Kumar December 11, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This solution is not feasible (a bit slow) if we need to find multiple words from the dictionary. This will iterate the dictionary again and again.

- Psycho January 02, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Eugene Mmmmm December 11, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- zortlord December 11, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Rajesh Kumar December 12, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@rajavni-

What I meant by 'problem complexity' is the slowness of the solution. If the dictionary is a Trie, then that might be faster. If the dictionary were a Map<String,Collection<String>> where the key is the translated string, then that solution would be O(1).

- zortlord December 12, 2014 | Flag


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More