Coding Style in Python

Question

I have been interviewed recently by an eminent silicon valley based firm . I had been asked to write the code for the following question with O(n) time complexity .

Question :

Write a function that is given an array of integers. It should return true if any value appears at least twice in the array, and it should return false if every element is distinct.

The crux to the question was to use hash maps . I wrote the following code in python :

def containsDuplicate(arr):
    hashi={}
    for i in arr:
        try:
            hashi[i]+=1
            return 1
        except KeyError:
            hashi[i]=1
    return 0

Overall interview went well and I was able to figure out the best solutions (efficient solutions) of all the questions asked . Later I got a mail from the company that I was not the best match for the position.When asked the reason for my rejection I was told to work on my coding style .

What does the HR mean when she said that I need to improve on my coding style ? What would be the best way to code the solution to the problem asked above ?

Edit :

After reading the code again I believe it was not even necessary to do hashi[i]+=1 . Just return 1 was sufficient but I don't think that they rejected me solely due to this minor fault in my coding.

Answer 1

A more concise solution to the problem is:

def has_dups(arr):
    return len(set(arr)) != len(arr)

On the set creation any dups would be removed so the count would tell us the result. I think the set creation from an iterator is O(n) so it would fulfill that requirement.

Can't promise that is what they are looking for though!

Answer 2

Check PEP-8

from collections import defaultdict
def is_duplicate(string):
    freq = defaultdict(lambda: 0)
    for c in string:
        freq[c] += 1
    return all(v == 1 for v in freq.values())

Answer 3

you would have used "in" instead of try and except.

def containsDuplicate(arr):
    hashi={}
    res = 0    
    for i in arr:
        if i not in hashi:
           hashi[i]=1
        else:
            res = 1
            break
    return res

Answer 4

It could be that they didn't like the fact that you return 0 or 1 instead of False or True.

Answer 5

Trying to reverse engineer the interview rejection reason is typically a difficult and often meaningless exercise, so let's reform the question to something more fun and continue to improve on your answer, as you would have if you had been given more time.

Write a function that is given an array of integers. It should return true if any value appears at least twice in the array, and it should return false if every element is distinct.

def containsDuplicate(arr):
    hashi={}
    for i in arr:
        try:
            hashi[i]+=1
            return 1
        except KeyError:
            hashi[i]=1
    return 0

Well, python has a style guide that suggests some spacing, so let's do that. (No one would ever reject someone for this, btw)

Python also uses True and False more then the C style 0 and 1s for booleans.

def containsDuplicate(arr):
    hashi = {}
    for i in arr:
        try:
            return True
        except KeyError:
            hashi[i] = 1
    return False

Now, Python officially subscribes to EAFP where you use exceptions rather then checking, but some people disagree. If you used checking, we have:

def containsDuplicate(arr):
    hashi = {}
    for i in arr:
        if i in hashi:
            return True
        else:
            hashi[i] = True
    return False

However, time to get clever. Using sets, we can do:

def containsDuplicate(a):
    return len(set(a)) != len(a)

Answer 6

Here are a few suggestions.

from collections import defaultdict

def contains_duplicates(arr): # PEP recommends not using camel case
    arr_count = defaultdict(lambda: 0) # you should use defaultdict to specify a default value
    for i in arr:
        arr_count[i] += 1
        if arr_count[i] >= 2:
            return True # Python has a boolean type; you shouldn't use 0s and 1s
    return False

Answer 7

Regarding your style, you appear to not know that sets are implemented similarly to dicts in Python, and you were unnecessarily complicated in your code. I would have implemented it like Gavin H did.

Also, other elements of style that you should work on (see PEP8):

• single spaces around assignment operators
• use underscores to separate words in names as opposed to camel-case
• learn dict methods (you could have used the dict.get method instead of try/except)
• return True or False, not 1 or 0

Answer 8

There are a number of coding style issues with your code, but the one I like least is that it will always process the entire array even if the first two elements are the same.

My take on this would be the following it may not be the shortest but going back later would be better:

def has_dups(array):
    """ Return true if there are any duplicates in the array """
    result = False  # Return value
    seen = {}  # Dictionary of values seen
    for val in array:
        if seen.get(val, False):
            result = True  # We have a duplicate
            break  # Return NOW
        else:
            seen[val] = True # Add to seen
     return result

In a commercial organisation you are usually looking for code that:

1. Meets the specification - yours did not as it returns 0/1 rather than False/True
2. Meets the standards - yours has several PEP8 issues
3. Is clear and maintainable - yours lacks comments and relies on exceptions to save time in an interview it is a good idea to at least mark where you would comment the code.
4. Is testable - this means one entry and exit and a low complexity

Edit

The OP has pointed out that their code returns on the first non-exception which I had missed - this emphasises points 3 and 4 above.

Answer 9

In this version, I tried to make the early return obvious.

def contains_duplicates(arr):
    # returns True if a value of arr occurs more than once
    hashi = {}
    for i in arr:
        if i in hashi:
            return True
        hashi[i] = 1
    return False