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 has the following methods:
str.isalnum(): alphabet or number
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'
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:
math module provides
math.inf starting from Python 3.5, which is equivalent to
Python 2 has a
long type, which is removed in Python 3.
float is hashable (try
hash(3.1415926)), thus can be used as dict keys.
What are considered
- zero of any numeric type, for example,
- any empty sequence, for example,
- any empty mapping, for example,
- instances of user-defined classes, if the class defines a
__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.
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 ;)
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:
However, in Python, the negative division rounds away from zero:
This causes us some trouble when we convert bases:
Left shift may cause the
int being converted to
long automatically. To prevent this, use a mask
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.
Probably the most frequently used data structure in an interview.
- create a list of size n:
nums =  * 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:
collection.defaultdict provides a dict with default value:
collections.Counter is used to count things. It is a subclass of
dict, with some additional methods.
list, common operations:
- push ->
- peek ->
- pop ->
Usually we can use a list to simulate a queue.
Python also provides
queue.Queue class which is synchronized. Common operations
deque is short for double-ended queue, and is a generalisation of stack and queue.
see doc common operations:
see doc. default is a min heap.
A simple heapsort implementation:
An item in a linked list can be defined as:
A node in a binary tree can be defined as:
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.
filter(function, iterable) is equivalent to
(item for item in iterable if function(item)).
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
divmod(a, b) is equivalent to
(a // b, a % b)
min/max accept an iterable like list as well as variable arguments, so both the following syntax are valid: