Google Interview Question
Software Engineer / DevelopersCountry: Switzerland
Interview Type: Phone Interview
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.
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.
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:
- autoboli April 23, 2015OFFLINE:
(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.