Google Interview Question for Software Engineer / Developers


Country: Switzerland
Interview Type: Phone Interview




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

The key question is if it is a single or multiple query. If multiple queries are expected than I would propose @zsalloum's solution with a hash map:
OFFLINE:
(i) Create a hash map, key - numeronym, val - List of strings, full words
(ii) For each word from dictionary, comute its numeronym and use it as a key
and add it to the hash map.
ONLINE:
(i) use the given numeronym as a key
(ii) return a list of words from hash map.

Offline O(N) time complesity, online O(1) amortized.

- autoboli April 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Theres a few ways to do this, and a question like this is begging to be elaborated on. Do you want words that actually exist? Do you have a given set of words which are valid, or do you have the set of all possible combinations of letters?

Let's say, for start, that you do not have a dictionary of words to work with initially, so any values that match the given length are valid (i.e. a2e -> {aaae, aabe, abae, abbe....}) which creates an incredibly slow solution (O(26^n) where n is length of string minus first and last char)

I doubt that's what they meant initially, but the solution in this case is to use a recursive function to create to permutations, then apply the first and last char to each prior to returning.

In python:

def getStringFromNumeronym(numeronym):
    alphabet = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k',
                'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v',
                'w', 'x','y', 'z'  ]
    internal_length = int(numeronym[1:-1])
    permutations = permutate(alphabet, internal_length)
    for i in range(0,len(permutations)):
        permutations[i] = numeronym[0] + permutations[i] + numeronym[-1]
    return permutations

def permutate(chars, length):
    if length == 1 :
        return chars
    x = permutate(chars, length - 1)
    output = []
    for c in chars:
        for b in x:
            output.append(c + b)
    return output

As stated before, though, this a pure bruteforce answer.

If, however, you are given a dictionary of acceptable response terms, you can simply create an empty set and process through the dictionary, getting the numeronym for each word and comparing it to the input.

In python:

#assume we have a dictionary available
def get_string_with_dict(numeronym,dictionary):
    output = []
    for x in dictionary:
        if makeNumeronym(x) == numeronym:
            output.append(x)
    return output

This runs O(n) where n is size of the dictionary. This assumes your makeNumeronym function is O(1)

Some versions of the answer use a pre-processing into a hash table, but really this doesn't save any time or space as in both cases you still have to run through the ENTIRE dictionary input and process every word into a numeronym.

- Javeed April 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I see a straight forward solution.
If you have a dictionary or a list of words. You scan them make numeronym of each word. If the numeronym matches the given parameter or will be added to the result list.
At the end you return the result list.

Of course you can optimize by precomputing the numeronym of the dictionary for faster search.

- zsalloum April 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Another solution would be to use a trie:
Dictionary is represented as a trie. Than you traverse trie from 'h' at three levels down and than to 'e' in order to find complete words matching the numeronym. This method may be not optimal for large dictionaries.

- autoboli April 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Why to use only one structure (tree/dict/whatever)? Why not use one per length? It can improve the searching a lot.

- Selmeczy, P├ęter April 28, 2015 | Flag Reply


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