Python for Coding Interviews

Coding interviews are more likely to use Java or C++, since they are more likely to be taught in the college and used in the work. However, I would argue that Python is more suitable in algorithm interviews due to its elegant and concise syntax. You do not need to worry about unclosed curly braces, write getters and setter etc.

Most of the following discussions apply to both Python 2 and Python 3, unless stated explicitly.

Basic data types

str

a str has the following methods:

• str.isalpha()
• str.isdigit()
• str.isalnum(): alphabet or number
• str.isspace()

the string module has some nice things:

• string.ascii_uppercase == 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
• string.ascii_lowercase == 'abcdefghijklmnopqrstuvwxyz'
• string.ascii_letters == string.ascii_lowercase + string.ascii_uppercase
• string.digits == '0123456789'
• string.hexdigits == '0123456789abcdefABCDEF'

int

Since Python integer can be arbitrarily large, there is no minimum or maximum integers. If you want to use some placeholder for maximum or minimum, you have two choices, either generate a large enough value for the context, or use float instead.

32-bit signed integer:

1
2

MAX = 0x7fffffff    #  2147483647 == (1<<31)-1
MIN = -1 << 31      # -2147483648

Using float:

1
2

MIN = float('-inf')
MAX = float('inf')

math module provides math.inf starting from Python 3.5, which is equivalent to float('inf').

Python 2 has a long type, which is removed in Python 3.

float

float is hashable (try hash(3.1415926)), thus can be used as dict keys.

bool

What are considered False here.

• None
• False
• zero of any numeric type, for example, 0, 0.0, 0j.
• any empty sequence, for example, '', (), [].
• any empty mapping, for example, {}.
• instances of user-defined classes, if the class defines a __bool__() or __len__() method, when that method returns the integer zero or bool value False.

Proper use of this can simply the code (if nums: pass instead of if len(nums) == 0: pass), but I prefer explicit comparison like if root is None: pass, besides the bool value.

Operations

Comparison Chaining

You can chain the comparison like 1 <= x <= 5, which is equivalent to x >= 1 and x <=5. Not much, but makes the world just slightly better ;)

Integer Division

Python 3 use // for integer division, while Python 2 use /. To be consistent in Python 2.7, add the following import from __future__ import division.

In C++/Java, the negative division rounds towards zero:

1
2

scala> assert(-5/2 == -2)
scala> assert(5/(-2) == -2)

However, in Python, the negative division rounds away from zero:

1
2

>>> assert(-5//2 == -3)
>>> assert(5//-2 == -3)

This causes us some trouble when we convert bases:

python

Bit Manipulation

Left shift may cause the int being converted to long automatically. To prevent this, use a mask

1
2
3
4
5
6

>>> j = 0xffff & (i << 15); type(j); bin(j)[2:].zfill(16)
<type 'int'>
'1000000000000000'
>>> j = 0xffff & (i << 16); type(j); bin(j)[2:].zfill(16)
<type 'int'>
'0000000000000000'

Data Structure

tuple

tuple is not explicitly asked, but is useful for:

• exchange values: a, b = b, a
• tuple is immutable and hashable, and can be used as keys in a map or values in a set.

1
2

visited = set()
visited.add((0,0))

list

Probably the most frequently used data structure in an interview.

• create a list of size n: nums = [0] * n
• create a matrix of size m*n: matrix = [[0*n] for i in range(m)] (DO NOT matrix=[[0*n] * m])
• copy a list: nums_copy = nums[:]
• negative indexing: nums[:-1]

dict

collection.defaultdict provides a dict with default value:

1
2
3
4

edges = [(1, 0), (1, 2)]
neighbors = collections.defaultdict(set)
for start, end in edges:
    neighbors[start].add(end)

collections.Counter is used to count things. It is a subclass of dict, with some additional methods.

1
2
3
4
5
6
7

counter = collections.Counter('abbccc') # Counter({'a': 1, 'b': 2, 'c': 3})
# .elements ignoring any items with less than one count.
list(counter.elements())  # [a, b, c]
# two Counter can be merged
counter + collections.Counter('abc') # Counter({'a': 2, 'b': 3, 'c': 4})

stack

Use the list, common operations:

• push -> nums.append(val)
• peek -> nums[-1]
• pop -> nums.pop()

queue

Usually we can use a list to simulate a queue.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Queue():
    """List implementation of Queue"""
    
    def __init__(self):
        self.l = []
    
    def pop(self):
        self.l.pop(0)
    
    def push(self, val):
        self.l.append(val)
        
    def size(self):
        return len(self.l)

Python also provides queue.Queue class which is synchronized. Common operations qsize(), get(), put(item).

deque

deque is short for double-ended queue, and is a generalisation of stack and queue.

see doc common operations:

• append, appendLeft
• pop, popLeft
• extend, extendLeft

heap

see doc. default is a min heap.

1
2
3
4
5
6
7
8
9
10

import heapq
print(heapq.heapify([3,2,4,1]))
l = []
heapq.heappush(3)
heapq.heappush(2)
print(l[0]) # 2
print(heap.heappop()) # 2
print(heap.heappop()) # 3

A simple heapsort implementation:

1
2
3
4
5

def heapsort(iterable):
    h = []
    for value in iterable:
        heappush(h, value)
    return [heappop(h) for i in range(len(h))]

linked list

An item in a linked list can be defined as:

1
2
3
4

class ListNode():
    def __init__(self, value):
        self.val = value
        self.next = None

tree

A node in a binary tree can be defined as:

1
2
3
4
5

class TreeNode():
    def __init__(self, value):
        self.left = None
        self.right = None
        self.val = value

Build-in functions

Proper use of the built-in functions can produce more readable code.

map can apply the same function for a list, return a list of result.

1
2

strs = ['hello', 'world']
total = sum(map(len, strs))

reduce

1

reduce(lambda x,y:x*y,range(1,4)) == 6

filter(function, iterable) is equivalent to (item for item in iterable if function(item)).

1

b = filter(lambda x: x > 5, a)

any can test whether at least one element in a list is True. all is similar. For example, in Find the Celebrity, we can use any():

1
2

if any(not knows(i, celeb) for i in range(n)):
    return -1

divmod(a, b) is equivalent to (a // b, a % b)

Python min/max accept an iterable like list as well as variable arguments, so both the following syntax are valid:

1
2

m = max(a, b, c)
m = max([a, b, c])

References

• Why Python’s Integer Division Floors