Python questions asked at Women Who Code's Interview workshop

gistfile1.py

unsorted_list = [1, 4, 12, 3, 0, 4, 1, 16, 20, 20, 19, 7, 4, 0]

# Terrible solution that only works small integers, but it is O(n) in both
# space and time
max_int = max(unsorted_list)
entries = [0] * (max_int + 1)

for x in unsorted_list:
    entries[x] += 1

result = [index for index, entry in enumerate(entries) if entry]
print result

# Naive solution O(n^2)
result = []
for x in unsorted_list:
    already_in = False
    for y in result:
        if x == y:
            already_in = True
            break
    if not already_in:
        result.append(x)
print result

# Naive solution O(n^2)
result = []
for x in unsorted_list:
    if x not in result:
        result.append(x)
print result

# Naive O(n * logn) solution with 2 * O(n) space
result = []
for x in sorted(unsorted_list):
    if not result or x != result[-1]:
        result.append(x)
print result

# Better O(n) solution with 1 * O(n) space
result = set()
for x in unsorted_list:
    if x not in result:
        result.add(x)
print list(result)

# Even better O(n) solution with 1 * O(n) space
print list(set(unsorted_list))

"""
Questions:
 1. Why are the solutions where result is a set faster than the solutions
    where result is a list?
    
    It's because set lookup is O(1) while list lookup is O(n). That 
    cuts down on the duplicate check.

    http://wiki.python.org/moin/TimeComplexity
    In Python, sets are implemented as hash maps/dictionaries

 2. What properties do integers have to allow for the set solution?
    Integers are hashable. You can not use the set solutions with
    non-hashable types such as lists.

 3. Instead of a set, what other data structure can you use in solutions
    faster than O(n^2)?

    You can replace the set with any data structure that has better
    than O(n) lookup. That can be a binary search tree, a hash map,
    a heap, whatever.

 4. Which of those data structures work with unhashable types like lists?
    Those that do not hash the values for lookup. Sets and hash maps use
    hashes for comparison, so they can not be used.
    
    Binary search trees and heaps use equality comparison to compare elements.
    Such data structures can be used for all types that can be compared.
    The trade-offis that a solution for non-hashable types using a tree or a
    heap is O(n logn) Instead of O(n).
"""