## Google Interview Question for Software Engineer / Developers

• 0

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.

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 + 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.

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.

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.

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.

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.

### 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.