Code Review Stack Exchange is a question and answer site for peer programmer code reviews. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I've recently applied to a backend position and I was asked to complete a take-home interview question. I thought the question was rather simple and I completed in about an hour although I was told it could take up to 4 hours.

I got a response back recently stating that my answer does not demonstrate the necessary skill-level required. Looking back at my answer, I am not exactly sure where I should improve.

Please take a look a look and see what you would have done differently.

The orignal question:

Description:

A supervisor is using the TaskManagementSystem to manage tasks for his workers. The system can add users, assign tasks to users, and get task(s) that belong to a specific user.

Restriction:

You can not modify user or task class. self.users and self.tasks in TaskManagementSystem has to remain as lists. You can introduce new methods and class variables. Goals:

  1. Fix the syntax and semantic bugs that prevent the program from running correctly.

  2. Change get_user_tasks() to return list of task names instead of task objects.

  3. Add error handling to add_user(), add_task(), and get_user_tasks() methods

  4. Optimize TaskManagementSystem to handle large number of users and tasks

Code provided at interview:

#!/usr/bin/env python2.7
# encoding: utf-8

class user(object):

    def __init__(self, user_id, name):
        '''
        Task object.  This code can not be modified.
            @ user_id: int
            @ name: string
        '''
        self.user_id = user_id
        self.name = name


class task(object):

    def __init__(self, user_id, task_name):
        '''
        Task object.  This code can not be modified.
            @ user_id: int
            @ task_name: string
        '''
        self.user_id = user_id
        self.task_name = task_name

class TaskManagementSystem(object):

    def __init__(self):
        self.users = []  # stores a list of user objects
        self.tasks = []  # stores a list of task objects


    def add_user(self, user_name):
        '''
        Add a new user
            @ user_name: string

        Condition:
            Every user should have a unique name
            Every user should have a unique id
        '''

        unique_id = 0
        for user in self.users:
            if user.user_id > unique_id:
                unique_id = user.id

        self.users.append(user(unique_id, user_name))


    def add_task(self, user_name, task_name):
        '''
        Add a task for a user
            @ user_name: string
            @ task_name: string

        Condition:
            The user should not have two or more tasks with the same name
        '''

        for user in self.users:
            if user.name = user_name:
                user_id = user.user_id

        self.users.append(task(user_id, task_name))


    def get_user_tasks(self, user_name):
        '''
        Get task(s) that belongs to the specified user name
            @ user_name: string
        '''

        user_tasks = []

        for user in self.users:
            if user.name == user_name:
                for task in self.tasks:
                    if task.user_id == user.user_id:
                        user_tasks.append(task)

        return user_tasks


if __name__ == "__main__":

    tms = TaskManagementSystem()
    tms.add_user('Bob')
    tms.add_task('Bob', 'laundry')
    tms.add_task('Bob', 'grocery')
    tms.add_task('Bob', 'daycare')

    print tms.get_user_tasks('Bob')
    # should print: ['laundry', 'grocery', 'daycare']

Here is the code I handed in as my answer:

#!/usr/bin/env python2.7
# encoding: utf-8
from random import choice


class user(object):

    def __init__(self, user_id, name):
        '''
        Task object.  This code can not be modified.
            @ user_id: int
            @ name: string
        '''
        self.user_id = user_id
        self.name = name


class task(object):

    def __init__(self, user_id, task_name):
        '''
        Task object.  This code can not be modified.
            @ user_id: int
            @ task_name: string
        '''
        self.user_id = user_id
        self.task_name = task_name


class TaskManagementSystem(object):

    def __init__(self):
        self.users = []  # stores a list of user objects
        self.tasks = []  # stores a list of task objects

    def add_user(self, user_name):
        '''
        Add a new user
            @ user_name: string

        Condition:
            Every user should have a unique name
            Every user should have a unique id
        '''

        # Create a unique id based on current user list.
        if self.users:
            unique_id = max([_user.user_id for _user in self.users]) + 1

        # There are no current users.
        else:
            unique_id = 1

        # Check that user_name is not taken.
        if [_user for _user in self.users if _user.name == user_name]:
            print 'That user name is taken.'
        else:
            self.users.append(user(unique_id, user_name))


    def add_task(self, user_name, task_name):
        '''
        Add a task for a user
            @ user_name: string
            @ task_name: string

        Condition:
            The user should not have two or more tasks with the same name
        '''

        user_id = self.get_user_id(user_name)
        if not user_id:
            return

        if task_name in self.get_user_tasks(user_name):
            print 'The user has already been asigned this task.'

        else:
            self.tasks.append(task(user_id, task_name))


    def get_user_id(self, user_name):
        '''
        Get a users id.
        Prints error if not found.
            @ user_name: string
        '''

        try:
            return [_user.user_id for _user in self.users
                    if _user.name == user_name][0]
        except(IndexError):
            print 'User not found.'


    def get_user_tasks(self, user_name):
        '''
        Get task(s) that belongs to the specified user name
            @ user_name: string
        '''

        user_id = self.get_user_id(user_name)

        if not user_id:
            return

        return [_task.task_name for _task in self.tasks
                if _task.user_id == user_id]


def test_add_users(n):
    '''
    Test by adding n users.
        @ n: int
    '''

    print 'adding users...'
    for x in xrange(n):
        user_name = ''.join([chr(choice(range(97, 123))) for c in range(4)])
        tms.add_user(user_name)

    n_added = len(tms.users)
    print '{} users added. {} user names rejected.'.format(n_added, n - n_added)

def test_add_tasks(n):
    '''
    Test by assigning random users tasks.
        @ n: int
    '''

    print 'adding tasks...'
    for x in xrange(n):
        user_name = choice(tms.users).name      # Grabs a random user's name
        task_name = ''.join([chr(choice(range(97, 123))) for c in range(4)])
        tms.add_task(user_name, task_name)

    n_added = len(tms.tasks)
    print '{} tasks added. {} task rejected.'.format(n_added, n - n_added)


if __name__ == "__main__":
    tms = TaskManagementSystem()

    # Test with lots of users.
    # test_add_users(10000)
    # test_add_tasks(10000)

    tms.add_user('Bob')
    tms.add_task('Bob', 'laundry')
    tms.add_task('Bob', 'grocery')
    tms.add_task('Bob', 'daycare')

    print tms.get_user_tasks('Bob')
    # should print: ['laundry', 'grocery', 'daycare']
share|improve this question
2  
Are you allowed to post the interview question publicly? Haven't you signed an agreement not to do this? It's easier to delete your question now than later after you have received answers with votes – janos Mar 14 at 20:19
1  
I didn't sign anything, nor was there anything remotely mentioning not posting the question/answer – DGDD Mar 14 at 20:29
    
Out of curiosity, is this a copy-paste? That is, were the grammatical mistakes present in the original text of the question they posed? – Josh Caswell Mar 14 at 20:31
    
Yes, copy and paste. Actually there was a whole bunch of quirks. The 1 thing I didn't add was that every class and method was separated by a long #--------- spanning the whole page. I removed it because it was a nightmare to fit in to the Stackoverflow code presentation. – DGDD Mar 14 at 20:33
    
What is the point of question 4 when the most obvious and effective optimization is arbitrarily forbidden by the rules ? – b0fh Mar 15 at 10:11
up vote 14 down vote accepted

Let’s tackle the four points in turn:

  • Syntax and semantic bugs. I assume this was the indentation problems, which you seem to have fixed correctly.

  • Change get_user_tasks() to return a list. This is pretty good.

    But you return None if the user isn’t found – that’s not a list, and could be interpreted as meaning that the user exists, and doesn’t have any tasks assigned, which is wrong. You should throw a UserNotFound exception (see below).

    And this is a good use of list comprehensions, but will be slow if you have lots of tasks (again, see below).

  • Add error handling. Your approach to error handling is wrong – rather than printing messages to stdout (which are very hard for calling programs to hook into, viz. try … except), you should throw suitable exceptions.

    For example: your add_user method could throw a DuplicateUser exception if I try to add a user who already exists. This is much more useful for control flow.

    And your error messages could be more specific – although it’s obvious which user I’m trying to re–add in a small script, it that shows up in a massive log file, it would be nice to know which user was added twice. That’s useful for debugging.

  • Optimise the class for lots of tasks and users. This seems to be the key task, and it doesn’t seem like you’ve done anything in this area. I’d have swapped out the two attributes for more appropriate data structures (probably dicts), but apparently that’s against the rules.

    You could have protected attributes _users and _tasks that contain your proper data structures, and add properties users and tasks that return the correct lists. That way the public interface is preserved, but you have a more efficient implementation.

    You’d need to use the @property and @foo.setter decorator for that – not completely trivial, but not impossible either.

I wasn’t on this interview panel, but the key mistakes seem to be the error handling (use exceptions, not printing) and the lack of meaningful changes to improve scalability.

And a few other small things I spotted:

  • Read PEP 8, the Python style guide. The names of the user and task classes should be CamelCase.

  • The docstring of the user object is incorrect. Was that a deliberate mistake you were meant to catch?

  • Your add_user() method assigns a user ID based on the existing user IDs. This might be a problem if you later add a delete_user() method – for example:

    create user 'alice' (id 1)
    create user 'bob' (id 2)
    delete user 'bob' (id 2)
    create user 'carol' (id 2)
    

    At different points in time, I had two users with the same ID – that might cause confusion. It would be nice if IDs were reasonably unique. Maybe use hash(name)?

  • This isn’t wrong, but it’s a bit unusual:

    except(IndexError):
    

    except is a statement, not a function.

  • I know you’re not allowed to modify the user or task objects, so this is an aside: those two objects could be replaced by namedtuples with multiple benefits:

    • Reduced occupancy
    • Nicer repr()’s
    • Equality/comparison semantics
share|improve this answer
    
Thanks for your input. The raise exception seems so obvious now that you point it out. I'm not sure what I was thinking. – DGDD Mar 14 at 23:18
1  
Concerning the ID remark: at least something like hash(name + some_time_dependent_stuff) would be in order to not create the same ID for distinct, but identically named users. Or bring out the UUID cannon. – ojdo Mar 15 at 11:37

The code is full of linear searches \$O(N)\$ and other sub-optimal operations that could have been \$O(1)\$, especially when the assignment specifically asked for optimization.

add_user

What is the time complexity of this operation?

unique_id = max([_user.user_id for _user in self.users]) + 1

A linear search for the maximum user id, making it an \$O(N)\$ operation to add users.

Note that if all users are added using this add_user function, then they will have increasing ids, so you could find the same maximum value simply by taking the id of the last user.

Or, to avoid reusing ids as @alexwlchan suggested, the TaskManagementSystem class could keep a counter.

What is the time complexity of this operation?

if [_user for _user in self.users if _user.name == user_name]:
    print 'That user name is taken.'

Iterating over a entire collection is linear, so that's another \$O(N)\$ operation.

For one thing, it would have been better to stop after finding the first matching name. It would still be an \$O(N)\$ operation, but look a bit better.

To make this operation fast for large numbers of users, you would need to index the users by name, for example by using a set.

add_task

What is the time complexity of this operation?

if task_name in self.get_user_tasks(user_name):
    print 'The user has already been asigned this task.'

That depends on the type of the return value of get_user_tasks. It's a list, so this is again \$O(N)\$. The reality is actually a bit worse, because get_user_tasks also has another linear search in it.

get_user_id

By now I imagine you might be getting tired of the "what is the time complexity" question. But you have to ask this question always, and it's a good question to ask. There's another linear search in this method that could have been faster.

Conclusion

There's a lot more to writing good code than something that works. Even if optimization for large inputs wasn't one of the main objectives, it's important to keep time complexity down as a good habit. The issues pointed out by @alexwlchan are serious too, and I wouldn't be surprised if a small subset of these issues was enough for a rejection.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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