6
\$\begingroup\$

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
        username = name + str(memo[name])
        users.append(username)
        copy_u.remove(name)
        return username_system(copy_u, memo, users)
    else:
        username = name
        users.append(username)
        memo.update({name: 0})
        copy_u.remove(name)
        return username_system(copy_u, memo, users)
    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?

\$\endgroup\$
9
\$\begingroup\$

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']
res1 = username_system(names)
print(res1)    # ['john', 'john1', 'tom', 'john2']

lst = ['a']
res2 = username_system(names, users=lst)
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

# def username_system(...)
names = ['john', 'john', 'tom', 'john']
cProfile.run('username_system(names)')

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

def get_unique_usernames(user_names):
    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
\$\endgroup\$
  • 1
    \$\begingroup\$ Thank you so much! That was of great help! \$\endgroup\$ – Andressa Cabistani Nov 11 at 21:36
  • \$\begingroup\$ This fails for get_unique_usernames(['john', 'john', 'john1']) (it returns ['john', 'john1', 'john1']). \$\endgroup\$ – Florian Brucker Nov 12 at 8:04
  • \$\begingroup\$ @FlorianBrucker, such a condition (if relevant) should be stated in the OP's question as a specific edge case \$\endgroup\$ – RomanPerekhrest Nov 12 at 8:09
4
\$\begingroup\$

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
        username = name + str(memo[name])
        users.append(username)
        copy_u.remove(name)
        return username_system(copy_u, memo, users)
    else:
        username = name
        users.append(username)
        memo.update({name: 0})
        copy_u.remove(name)
        return username_system(copy_u, memo, users)
    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
        username = name + str(memo[name])
    else:
        memo.update({name: 0})
        username = name
    users.append(username)
    copy_u.remove(name)
    return username_system(copy_u, memo, users)
    return users

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

Try/catch instead of if/else

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.

Be careful about remove()

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
        username = name + str(memo[name])
    else:
        memo.update({name: 0})
        username = name
    users.append(username)
    del u[0]
    return username_system(u, memo, users)

And now the subtle bug

If you call your function multiple times there is some persistence

print("given:", names)
print("returns:", username_system(names.copy()))
print("given:", names)
print("returns:", username_system(names.copy()))

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

def username_system(u, memo=None, users=None):
    memo = memo or Counter()
    users = users or []
    # [...]
    if name in memo:
        username = name + str(memo[name])
    else:
        username = name
    memo[name] += 1
\$\endgroup\$
  • \$\begingroup\$ You have an extra return in your second code block under "Code Repetition" \$\endgroup\$ – Gloweye Nov 12 at 7:55
  • 1
    \$\begingroup\$ @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'. :-) \$\endgroup\$ – stefan Nov 12 at 12:12
  • \$\begingroup\$ Ah, ok. Perhaps I read a bit to quickly :) \$\endgroup\$ – Gloweye Nov 12 at 12:19
  • \$\begingroup\$ Thank you! That was an amazing answer! \$\endgroup\$ – Andressa Cabistani Nov 12 at 17:18
2
\$\begingroup\$
  • defaultdict gives you a major headstart on this one.
  • Include some """python docstring"""
  • decompose into a neat single username method and a list-comprehension to apply this to an input list.

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


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


def username_system(names):
    return [new_username(n) for n in names]  # list comprehension


names = ['john', 'john', 'tom', 'john']
print(username_system(names))
\$\endgroup\$
  • \$\begingroup\$ This fails for username_system(['john', 'john', 'john1']) (it returns ['john', 'john1', 'john1']). \$\endgroup\$ – Florian Brucker Nov 12 at 8:05
  • 1
    \$\begingroup\$ Interesting. Given the input is a "list of names" I'm going to assume the only missed code here is to validate input name is only alphabetical characters - john1 is not a name (unless you're a rapper) \$\endgroup\$ – drekbour Nov 12 at 11:31
  • \$\begingroup\$ Yes, it was just a list of names. \$\endgroup\$ – Andressa Cabistani Nov 12 at 17:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.