Python QuickRef
This quick reference assumes that you already know Python and just want a refresher of some common techniques, particularly for tech interviews.
Contents
- Common Stuff
- Data Structures
- Algorithms
Common stuff
Python 3
Python 3 - a major, backwards-incompatible release - was released in December 2008. Both Python versions (2.7.x and 3.x) work well if the libraries you want to use are supported. However, Python 2.7 will only be supported till 2020 and users should move to 3.x as soon as possible. With this in mind, this page is written for Python 3.x.
len()
Python has a global function len() that can be used to get the length (or size) of any data structure: lists, tuples, dictionaries, etc.
l1 = [1, 2]
l2 = []
len(l1) # = 2
len(l2) # = 0
Indexing with negative numbers
In Python, you can use negative numbers to index into a list from the end.
l1 = [10, 20, 30, 40]
l1[-1] # = 40
l1[-2] # = 30
Slicing
Slicing is a great tool in Python but can be tricky to remember and always get right. There are basically three parts to it, the start, the stop and the step (or stride). First, looking at the entire thing in one go:
# somelist[start:stop:step]
[10, 20, 30, 40, 50, 60, 70][1:5:2] # = [20, 40]
Breaking that down, this means: give me a slice
- starting from index 1, which is the number 20 (because Python is zero-indexed)
- till (but excluding) index 5, which is the number 60
- with a step of 2 - which is like saying
i+=2inforloops, or saying go forward 2 elements at a time
All 3 parts are optional and have defaults: start = 0, stop = len(), step = 1 and can be left blank as in the following examples.
[10, 20, 30][1:] # = [20, 30] (start = 1 and implies stop = len() = 3, step = 1)
[10, 20, 30][:2] # = [10, 20] (stop = 2 and implies start = 0, step = 1)
[10, 20, 30, 40, 50][::2] # = [10, 30, 50] (step = 2 and implies start = 0, stop = len() = 5)
You can also use negative indices in slices.
[10, 20, 30, 40, 50][-2:] # = [40, 50]
[10, 20, 30, 40, 50][:-2] # = [10, 20, 30]
[10, 20, 30, 40, 50][::-1] # = [50, 40, 30, 20, 10], list in reverse
[10, 20, 30, 40, 50][::-2] # = [50, 30, 10], list in reverse with step = 2
Lists
# creating a list
l1 = [1, 2, 3, 4]
l2 = []
# appending to a list, O(1)
l2.append(42)
l2.append(7)
# accessing an element
l2[0] # = 42
# iterating through the elements
for item in l2:
item # = 42, 7
# deleting the last element, O(1)
l1.pop() # returns 4
l1 # = [1, 2, 3]
# deleting element at an index and returning it, O(n)
l1.pop(1) # returns 2
l1 # = [1, 3]
# deleting first occurrence of a value
l1.remove(3)
l1 # = [1]
Python’s lists can also be used as stacks.
Tuples
Tuples are similar to lists, but they are immutable, that is, their size and elements cannot be changed.
t1 = (10, 20)
t1[0] # = 10
t1[1] # = 20
for item in t1:
item # = 10, 20
t1[0] = 5 # TypeError: 'tuple' object does not support item assignment
(However, this immutability is shallow - items inside a tuple can be changed. For example, you can append to a list that is inside a tuple.)
Dictionaries (dict)
Dictionaries are key-value pairs.
# initialization
d1 = {2: 4, 3: 9}
# access, average case O(1), worst case O(n)
d1[2] # = 4
# set item, average case O(1), worst case O(n)
d1[4] = 16
# iteration
for key in d1:
key # = 2, 3, 4
d1[key] # = 4, 9, 16
# deletion by key
d1.pop(2) # returns 4, removes {2: 4}
Stacks
Stacks are LIFO (last in first out) containers.
# we're using a list as a stack, so initialization is the same as for lists
s1 = [12, 24]
# push operation, O(1)
s1.append(36)
# peek/top (see last pushed element), O(1)
# using a -ve index means counting from the end
s1[-1] # = 36
# pop operation, O(1)
s1.pop() # return 36
len(s1) # = 2
Queues (and deques)
Queues are FIFO (first in first out). Deques (generally pronounced “decks”) are double-ended queues, meaning you can push and pop from both sides.
from collections import deque
# creation
d1 = deque([4, 9, 16])
# iteration
for elem in d1:
elem # = 4, 9, 16
d1.append(25) # append/push to the end, or the right side
d1.appendleft(1) # append/push to the beginning, or the left side
d1 # = 1, 4, 9, 16, 25
# pop from the end, or the right side
d1.pop() # returns 25
# pop from the start, or the left side
d1.popleft() # returns 1
Sorting
There are two ways of sorting lists in Python: an in-place version using .sort() or a version that returns a sorted list using the global sorted() function.
The sorting algorithm used is Timsort and it runs in worst case O(n log n) time and O(n) space.
l = [5, 10, 1, 20]
sorted(l) # returns [1, 5, 10, 20]
l # = [5, 10, 1, 20], still unchanged
l.sort()
l # = [1, 5, 10, 20]
l.sort(reverse=True) # same works for sorted()
l # = [20, 10, 5, 1]
You can also sort a list of more complex things such as tuples or objects by providing a key function. Lambda functions are very useful here.
l = [("Banana", 22), ("Apple", 10), ("Orange", 11)]
# sort by the second element of the tuple
sorted(l, key = lambda item: item[1])
# returns [('Apple', 10), ('Orange', 11), ('Banana', 22)]
Heap (Priority Queue)
The heapq module allows you to easily maintain a min-heap (which can be used as a priority queue). This module doesn’t provide you a heap class or object but instead provides functions that operate on a standard list (using the standard approach of a heap backed by an array).
import heapq
l = [50, 30, 10, 20]
# turn l into backing for a heap, in-place
heapq.heapify(l)
l # = [10, 20, 50, 30]
# The list's ordering can't be used directly,
# but the 0th element will always be the smallest!
l[0] # = 10, the smallest element
heapq.heappop(l) # pops and returns 10
l # = [20, 30, 50]
heapq.heappush(l, 40)
heapq.heappush(l, 5)
l # = [5, 20, 50, 40, 30]
heapq.heappop() # returns 5
heapq.heappop() # returns 20