# Receive a list of names and return a list of users - HackerRank test

So, few months ago I did a HackerRank test for a company. The problem was to create a function which receive a list of names and returns a list of unique usernames. For example:

For the list of names = ['john', 'john', 'tom', 'john']
The function must return: = ['john', 'john1', 'tom', 'john2']

My code was:

def username_system(u, memo={}, users=[]):
copy_u = u.copy()
try:
name = copy_u[0]
except IndexError:
return users
if name in memo.keys():
memo[name] += 1
copy_u.remove(name)
else:
memo.update({name: 0})
copy_u.remove(name)
return users


I'd like to know, what could I improve in this code? I used memoization to make it faster. Also, I think this code is in O(n), but I'm not sure. Is that right?

I would warn you from using such an approach - it may lead to buggy and unexpected results.
Consider the following situation:

names = ['john', 'john', 'tom', 'john']
print(res1)    # ['john', 'john1', 'tom', 'john2']

lst = ['a']
print(res2)   # ['a', 'john3', 'john4', 'tom1', 'john5']


Looking at the 2nd print result ...
Using a mutable data structures as function default arguments is considered as a fragile approach - Python "memorizes"(retains) that mutable arguments content/value between subsequent function's calls. Furthermore, you use 2 of such.
Though in some cases it may be viable for defining a specific internal recursive functions - I'd suggest a more robust and faster approach.

As you're mentioned about "memoization", "to make it faster", "O(N)" here's a deterministic profiling stats for your initial function:

import cProfile

names = ['john', 'john', 'tom', 'john']


Output:

         27 function calls (23 primitive calls) in 0.000 seconds

Ordered by: standard name

ncalls  tottime  percall  cumtime  percall filename:lineno(function)
1    0.000    0.000    0.000    0.000 <string>:1(<module>)
5/1    0.000    0.000    0.000    0.000 test.py:3(username_system)
1    0.000    0.000    0.000    0.000 {built-in method builtins.exec}
4    0.000    0.000    0.000    0.000 {method 'append' of 'list' objects}
5    0.000    0.000    0.000    0.000 {method 'copy' of 'list' objects}
1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
4    0.000    0.000    0.000    0.000 {method 'keys' of 'dict' objects}
4    0.000    0.000    0.000    0.000 {method 'remove' of 'list' objects}
2    0.000    0.000    0.000    0.000 {method 'update' of 'dict' objects}


As you may observe even for that simple input list of 4 names username_system function is called 5 times.

Instead, we'll rely on supplementary collections.defaultdict object that conveniently provides the initial value.
Then, traversing over a copy of initial user names only entries that occur more than 1 time (within a dict keys view) will be appended with incremented ordinal suffix:

from collections import defaultdict

d = defaultdict(int)
uniq_unames = user_names[:]

for i, name in enumerate(uniq_unames):
if name in d:
uniq_unames[i] += str(d[name])
d[name] += 1

return uniq_unames

if __name__ == "__main__":
names = ['john', 'john', 'tom', 'john']
print(get_unique_usernames(names))    # ['john', 'john1', 'tom', 'john2']


Comparison of Time execution performance:

initial setup:

from timeit import timeit

names = ['john', 'john', 'tom', 'john']


username_system function:

print(timeit('username_system(names)', 'from __main__ import names, username_system', number=10000))
0.027410352995502762


get_unique_usernames function:

print(timeit('get_unique_usernames(names)', 'from __main__ import names, get_unique_usernames', number=10000))
0.013344291000976227

• Thank you so much! That was of great help! – Andressa Cabistani Nov 11 '19 at 21:36
• This fails for get_unique_usernames(['john', 'john', 'john1']) (it returns ['john', 'john1', 'john1']). – Florian Brucker Nov 12 '19 at 8:04
• @FlorianBrucker, such a condition (if relevant) should be stated in the OP's question as a specific edge case – RomanPerekhrest Nov 12 '19 at 8:09

# Recursion

Recursion is a bad idea if a simple loop does the job and if you have little control over recursion depth.

In [1]: import sys
In [2]: sys.getrecursionlimit()
Out[2]: 1000


Of course you can set a higher limit, but you may run into a stack overflow. But lets refactor your code first.

# Code repetition

Code repetition is one of the ugliest things you can do. copy pasted code is a real pitfall when you forget o update the other execution paths. We change

def username_system(u, memo={}, users=[]):
copy_u = u.copy()
try:
name = copy_u[0]
except IndexError:
return users
if name in memo.keys():
memo[name] += 1
copy_u.remove(name)
else:
memo.update({name: 0})
copy_u.remove(name)
return users


to

def username_system(u, memo={}, users=[]):
copy_u = u.copy()
try:
name = copy_u[0]
except IndexError:
return users
if name in memo.keys():
memo[name] += 1
else:
memo.update({name: 0})
copy_u.remove(name)
return users


We immediately see the unreachable code at the end and remove the last line

You misuse exception handling for a simple test. We replace

try:
name = copy_u[0]
except IndexError:
return users


by

if len(copy_u) == 0:
return users
name = copy_u[0]


# Avoid unnecessary copies

Where you iterate over your list you do

copy_u = u.copy()


for no reason. This your absolute performance killer as it is of quadratic complexity. We can delete that line and the code is still working. If we want to save the initial list we do

print(username_system(names.copy()))


in our main function.

list.remove() searches(!) for a value and deletes it from the list. You already know which index to delete, so use del. In your case remove()has no negative impact to complexity as the element is found immediately at the front. However the code is more readable when you use del as this tells everybody that no search is done.

Current status

def username_system(u, memo={}, users=[]):
if len(u) == 0:
return users

name = u[0]
if name in memo.keys():
memo[name] += 1
else:
memo.update({name: 0})
del u[0]


# And now the subtle bug

If you call your function multiple times there is some persistence

print("given:", names)
print("given:", names)


prints

given: ['john', 'john', 'tom', 'john']
returns: ['john', 'john1', 'tom', 'john2']
given: ['john', 'john', 'tom', 'john']
returns: ['john', 'john1', 'tom', 'john2', 'john3', 'john4', 'tom1', 'john5']


How is that? You do default params in your function. This default value is created only once. If you alter the value, which is possible on containers like list the altered value persists. When you call your function the second time memoand users are initialized to the previously used objects and continue the up-count. That can be solved like

def username_system(u, memo=None, users=None):
memo = memo or {}
users = users or []


# Some other python stuff

if name in memo.keys():


can be replaced by

if name in memo:


The default iteration over a dict() gives the keys. Use dict.keys only if you e. g. want to copy keys to a list().

In the module collections there is a class Counter which does exactly what your memo does. We use it like

from collections import Counter

memo = memo or Counter()
users = users or []
# [...]
if name in memo:
else:
memo[name] += 1

• You have an extra return in your second code block under "Code Repetition" – Gloweye Nov 12 '19 at 7:55
• @Gloweye: Right. And I have an extra line in the text that says that 'We immediately see the unreachable code at the end and remove the last line'. :-) – stefan Nov 12 '19 at 12:12
• Ah, ok. Perhaps I read a bit to quickly :) – Gloweye Nov 12 '19 at 12:19
• Thank you! That was an amazing answer! – Andressa Cabistani Nov 12 '19 at 17:18

The below is not self-contained (users resides as a global variable) but solves the problem succinctly.

from collections import defaultdict

users = defaultdict(lambda: -1)  # All names start at -1

"""Generate unique username for given name"""
users[name] += 1
return f"{name}{'' if users[name] == 0 else users[name]}"


• This fails for username_system(['john', 'john', 'john1']) (it returns ['john', 'john1', 'john1']). – Florian Brucker Nov 12 '19 at 8:05