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.
Contents
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.
32bit signed integer:
MAX = 0x7fffffff # 2147483647 == (1<<31)1
MIN = 1 << 31 # 2147483648
Using float:
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 userdefined 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:
scala> assert(5/2 == 2)
scala> assert(5/(2) == 2)
However, in Python, the negative division rounds away from zero:
>>> assert(5//2 == 3)
>>> assert(5//2 == 3)
This causes us some trouble when we convert bases:
Bit Manipulation
Left shift may cause the int
being converted to long
automatically.
To prevent this, use a mask
>>> 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.
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:
edges = [(1, 0), (1, 2)]
neighbors = collections.defaultdict(set)
for start, end in edges:
neighbors[start].add(end)
[collections.Counter
](https://docs.python.org/3.5/library/collections.html#collections.Counter) is used to count things.
It is a subclass of dict
,
with some additional methods.
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.
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 doubleended 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.
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:
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:
class ListNode():
def __init__(self, value):
self.val = value
self.next = None
tree
A node in a binary tree can be defined as:
class TreeNode():
def __init__(self, value):
self.left = None
self.right = None
self.val = value
Buildin functions
Proper use of the builtin functions can produce more readable code.
map
can apply the same function for a list, return a list of result.
strs = ['hello', 'world']
total = sum(map(len, strs))
reduce
reduce(lambda x,y:x*y,range(1,4)) == 6
filter(function, iterable)
is equivalent to (item for item in iterable if function(item))
.
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()
:
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:
m = max(a, b, c)
m = max([a, b, c])