Name Prefixes

This was an interview question that I had. I’ll this as easy since it can be brute force pretty easily.

Intuition

Pattern: Looking for repeatition, duplication, or similarity between more than one string

You’re given two list of names. One of the list (Let’s call them prefixes) contains names that act as, well, prefixes. The other list (let’s call them names) contains the full list of names.

Brute Force

One way of doing this is by interating through both lists. Based on the length of prefixes, iterate through every name in names. For each name, slice the name according to the length of the prefix at the current index. If the sliced name is the same as the prefix, increment the count.

Return the list of count, where each count was decrement by 1

HashMap

Iterate through names once. For every name, generate all possible prefixes and use them as keys.

Code

Brute Force

result = [0] * len(prefixes)
for index in range(len(prefixes)):
  for name in names:
      temp_name = name[:len(prefixes[index])]
      if temp_name == prefixes[index]:
          result[index] += 1
return result - 1

HashMap

hash_prefix = {}
for name in names:
    for i in range(len(name)):
        hash_prefix[name[:i]] = hash_prefix.get(name[:i], 0) + 1
return [hash_prefix[prefix] for prefix in hash_prefix]