Technical (Leetcode-style) Interview Cheat Sheet (Python)
Beyond the basics — Tips & tricks to ace your next technical interview
As I prepared for my interviews, I noticed that there wasn’t a single resource that made solving leetcode questions easier. More often than not, there are some “tricks” (or very niche algorithms) involved when solving certain type of problems and not obvious to anyone who hasn’t encountered similar questions before.
As such, I’ve consolidated this list of “tips and tricks” as I’d call it, to help others (and perhaps my future self when I do apply for another job) prioritize what should be learnt and the tricks involved with each data structure.
Disclaimer: This article does NOT walk through each individual data structure and algorithm (DS&A). It is meant to supplement basic knowledge of these DS&A by providing insight/tips/tricks into how they can be used to solve leetcode questions.
💡 Note: Topics are not listed in order of importance. For starters, focus on topics with an importance of 8 and above (indicated on a scale of 1–10).
Table of Contents
1. Arrays
- Sliding Window
- Prefix and Postfix Arrays
2. Palindromes
3. Sorting
- Bucket Sort
4. Binary Search
5. Linked Lists
- Sentinel (Dummy) Nodes
- Tortoise and the Hare
6. Intervals
7. Graphs
- Breadth-first-search (BFS) / Depth-first-search (BFS)
- Adjacency Lists/Matrices
- Union Find algorithm
- Dijkstra's (Shortest Path) algorithm
- Bellman-Ford's (Shortest Path) Algorithm
- Prim's (Minimum Spanning Tree) algorithm
8. Trees
- Recursive DFS
- Binary Trees
- Heaps
- Tries
9. Dynamic Programming
10. Bit Manipulation
11. Miscellaneous (Tips & Tricks)
Arrays
Arrays form the bread of butter of leetcode-style interviews. Be comfortable with all methods that come with this data structure, including stacks and queues.
With arrays come pointer manipulation — the sliding window technique is a very common and fundamental technique used to traverse an array.
Sliding Window
Sliding window questions typically require the use of some other data structure (such as a hash map or hash set) to keep track of seen characters.
Size of sliding window = right — left+1
→ e.g. if left=2
and right=5
, the window size would be 5-2+1=4
.
There are typically two different syntax that you can use for sliding windows:
# 1. Initialize both left and right pointers to 0 and use a while loop
l, r = 0, 0
while r < len(nums):
# increase l here based on some condition
r += 1
# OR 2. Initialize left to 0 and iterate right pointer from 0 using a for loop
l = 0
for r in range(len(nums)):
# increase l here based on some condition
Both methods are synonymous and mostly a matter of preference (and sometimes readability).
Related LeetCode Questions: Longest Substring Without Repeating Characters, Longest Repeating Character Replacement Importance: 10/10
Prefix & Postfix Arrays
Calculating running sums (or product or any other operator for the matter) is a fairly common sense technique, but it is important to conceptualise it in your head with the official terms “prefix” and “postfix” as it helps with verbalising your solution. In essence, it is a technique used to cache calculations of subarrays and re-using it later on.
Related LeetCode Questions: Product of Array Except Self Importance: 10/10
Palindromes
Palindromes deserves a section on its own because there are so many string-related questions that involve palindromes. For the purpose of this article, we’ll look at various methods on how to determine if a string is a palindrome.
s = "racecar"
# Method 1: Slicing
# Comments: Not ideal as this method uses linear space O(k) where `k` is the
# length of the sliced string
def is_palindrome(s):
return s == s[::-1]
# Method 2: Using two pointers from outside in
# Comments: Improvement over method 1 as it uses constant space
def is_palindrome(s):
l, r = 0, len(s)-1
while l <= r:
if s[l] != s[r]:
return False
return True
# Method 3: Using two pointers from inside out
# Comments: Particularly useful for `Longest Palindromic Substring`
def is_palindrome(s):
mid = len(s) // 2
while l >= 0 and r < len(s):
if s[l] != s[r]:
return False
return True
Sorting
Generally, interviewers will not require you to code out any sorting algorithm (e.g. merge sort, quick sort, etc) from scratch. However, you should still be aware of how they work on a low-level (i.e. you can psuedocode it out if required) and their differences in terms of average and worst case time complexities. I will not be going through those sorting algorithms as they can be found all over the web.
Bucket Sort
Also known as counting sort, bucket sort isn’t a sorting algorithm per se, but makes use of “buckets” to count elements, either using another data structure to store them or by simply keeping a counter.
Each index in the array is used to represent the ith
value, while the array itself stores the count of each occurrence. For example, to represent the counts of the lowercase English characters in a string, we have at most 26 characters and hence our bucket array will be of size 26.
# e.g. lowercase alphabats start from ord 97
buckets = [0] * 26
for i in range(len(s)):
buckets[ord(s[i]) % 97] += 1
Related LeetCode Questions: Top K Frequent Elements, Find Players With Zero or One Losses Importance: 7/10. More often than not, bucket/counting sort is used to optimize a solution. Coming up with a slightly more inefficient solution using another algorithm/data structure is usually sufficient.
Binary Search
When questions provide an input array that is already sorted, binary search should come to your mind as it can likely be used to optimize your brute force solution. It is one of the few ways we can improve a linear scan of an array (i.e. from O(n)
→ O(log n)
).
A textbook binary search follows the below structure. However, questions are typically not so straightforward but require some form of customization to this original template.
def find_index(values: List[List[int]], target) -> int:
"""
Binary search to finds the exact or approximate match of `target`
given a list of `values`. Returns the index of match.
"""
n = len(values)
left, right = 0, n-1
while left <= right:
mid = left + (right-left) // 2 # prevent int overflow
if target == values[mid]:
return mid
if target < values[mid]:
right = mid - 1
elif target > values[mid]:
left = mid + 1
return mid
Related LeetCode Questions: Koko Eating Bananas, Find Minimum In Rotated Sorted Array Importance: 9/10.
Linked Lists
ListNode
class defined as (used in below examples):
class ListNode:
def __init__(self,):
self.prev = prev # only for nodes in doubly linked list
self.next = next
self.val = val
Sentinel (Dummy) Head Nodes
When dealing with linked list questions, the main crux of these questions involve pointer manipulation. With pointer manipulation comes the dreaded error that comes from messing up our node’s next/prev pointers. To deal with this, we simply add a dummy head node and a dummy tail node. [Example question: Merge Two Sorted Lists]
# E.g. head=[1]
dummy = ListNode(0, next=head)
curr_node = dummy
curr_node.next = curr_node.next.next # avoids NoneType error
The Tortoise and the Hare
This is a technique used to find a certain node within the linked list. The gist of this technique is to maintain two pointers: a slow
and fast
pointer. The slow
pointer is behind the fast
pointer and they each can move at the same or different speeds, depending on its purpose. Below are some variants of this implementation:
- Finding the middle element of linked list — To do so, the
slow
pointer moves one node at a time while thefast
pointer moves two at a time. By the time thefast
pointer reaches the end of the linked list, theslow
pointer will be at the middle. [Example question: Reorder List]
# Given a head of a linked list, we can find the middle.
slow, fast = head, head.next
while fast and fast.next:
slow = slow.next
fast = fast.next.next
# `slow` pointer is now in the middle
- Finding the Kth element from the end of linked list — To do so, we first move the
fast
pointerk
elements ahead from the head. After which, we initialise theslow
pointer at the head and move both pointers one at a time. By the time thefast
pointer reaches the end, theslow
pointer would be at theKth
element from the end. [Example question: Remove nth node from end of list]
dummy = ListNode(0, next=head)
slow, fast = dummy, head
# move `fast` k+1 elements ahead
while k < 0:
fast = fast.next
k -= 1
# move both pointers to the end at the same time
while fast:
slow, fast = slow.next, fast.next
Related LeetCode Question: See above. Importance: 9/10. Although vanilla linked lists questions are less common, practical questions like LRU cache require this data structure for an optimal solution.
Intervals
Intervals are typically time-based questions, which means that order matters. As such, sorting should always come to mind when dealing with interval-based questions. Here are some approaches to consider:
- Sort based on start times (i.e. first index of interval array). Example: Meeting Rooms I
- Separate start and end intervals into separate arrays and sort them separately. Example: Meeting Rooms II
It is also extremely helpful to draw a diagram to visualize start/end times to see how they intersect.
Related LeetCode Questions: See above. Importance: 8/10
Graphs
Breath First Search (BFS) / Depth First Search (DFS)
These two should be pretty straightforward and fundamental for other algorithms used below.
TL;DR: Use a stack for DFS and queue for BFS.
# Iterative DFS
stack = [(0,0)] # example
visited = set()
while stack:
x, y = stack.pop()
# some logic here...
for dx, dy in [(1,0), (0,1), (-1, 0), (0, -1)]:
xx, yy = dx + x, dy + y
if (xx, yy) not in visited:
stack.append((xx,yy))
visited.add((xx,yy))
# Iterative BFS
queue = deque()
while queue:
curr = queue.popleft() # only difference is to popleft() instead
# same as iterative approach
Gotcha: Always maintain a
visited
set to prevent being stuck in an infinite loop! Note: Some people prefer updating thevisited
set after popping, but I personally like adding it after appending neighbours to the stack/queue. Both works but the latter approach avoids some duplicate iterations and hence more efficient.
Related LeetCode Questions: Number of Islands, Walls And Gates Importance: 10/10
Adjacency Lists/Matrices
Typically, when given a list of edges, you are required to convert them it into an adjacency list or matrix in order to perform BFS/DFS on it.
Adjacency list
# E.g. Input edges: [[1,2], [2,3], [0,1], [3,4]]
adj_list = defaultdict(list)
for parent, child in edges:
adj_list[parent].append(child)
Adjacency matrix
# E.g. Input edges: [[1,2], [2,3], [0,1], [3,4]]
# Let `n` be the size of the adjacency matrix
adj_mat = [[0 for _ in range(n)] for _ in range(n)]
for parent, child in edges:
adj_mat[parent][child] = 1
There are pros and cons of using either data structure, but I’ll leave that as a homework for you. Generally speaking however, adjacency lists should be sufficient for leetcode-style of questions.
Union Find
A niche but useful algorithm that is mostly used to detect number of connected components (disjoint sets) in a graph. It can also be used to detect for “cycles” in an undirected graph.
# Union Find template. Given `edges`: List[List[int]] = [[1,2],[2,3],[4,5]]
parents = [i for i in range(len(edges))]
rank = [1] * len(edges)
n_connected_components = len(edges)
def find(node):
# Used to find the ultimate parent of that node
while node != parents[node]:
parents[node] = parents[parents[node]] # graph compression
node = parents[node]
return node
def union(node1, node2):
p1, p2 = find(node1), find(node2)
# Same parent, already connected.
if p1 == p2:
return 0
# Not connected, determine which component to merge into which based on rank.
if rank[p2] > rank[p1]:
rank[p2] += rank[p1]
parents[p1] = p2
else:
rank[p1] += rank[p2]
parents[p2] = p1
return 1
# Iterate through edges. Reduce count whenever we find a union
for n1, n2 in edges:
n_connected_components -= union(n1, n2)
Related Leetcode Questions: Number of Connected Components in an Undirected Graph, Redundant Connection, Graph Valid Tree Importance: 6/10. There usually isn’t much variations to union find questions. You either know it or you don’t, hence it’s not very common for interviewers to ask these type of make-or-break questions.
Dijkstra’s (Shortest Path) Algorithm
Dijkstra’s algorithm is used to find the shortest path on a positively weighted directed graph. It uses a combination of BFS and a priority queue (min heap) to determine which path should be explored at each iteration.
Intuition: Since this is a shortest path algorithm, we want to find the path (sum of all the weighted edges) that is the smallest. Using a heap, we can choose the path at each iteration that has the smallest weight. Note that this aforementioned weight is the running weight of the current edge plus all other edges that come before it from the start. Hence, using BFS, we are guaranteed to find out which is the shortest path.
Time Complexity: O(E log V)
, where E
represents number of edges and V
represents number of vertices
# Solution to Network Delay Time
def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
# Create adjacency list
adj = defaultdict(list)
for start, dest, w in times:
adj[start].append((dest, w))
heap = [(0, k)]
visited = set()
t = 0
while heap: # start BFS
curr_w, n1 = heapq.heappop(heap)
if n1 in visited: continue
visited.add(n1)
t = max(t, curr_w)
# add neighbours to heap
for neighbour, w in adj[n1]:
if neighbour not in visited:
heapq.heappush(heap, (curr_w+w, neighbour))
return t if len(visited) == n else -1
Related Leetcode Questions: Network Delay Time Importance: 7/10. Although yet another niche algorithm, this algorithm makes use of BFS and a priority queue — two very important algorithms/data structures — making it more useful to learn compared to union find (above).
Bellman-Ford (Shortest Path) Algorithm
Bellman-Ford’s algorithm is similar to Dijkstra’s algorithm in that its purpose is also to find the shortest path between two vertices. However, this algorithm is more flexible because it also works with negative edges and also in an unweighted graph. The tradeoff is that the time complexity is greater than Dijkstra’s because this algorithm actually traverses ALL nodes in the graph.
Intuition: Bellman-Ford performs a BFS starting from the source node and with each iteration, updates each node’s weight if we encounter a path that is shorter up to that point. We simply return the weight (price) of the destination node once BFS is complete.
Time Complexity: O(EV)
, where E
represents number of edges and V
represents number of vertices.
# Solution to `Cheapest Flight Within K Stops`
def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
prices = [float("inf")] * n
prices[src] = 0
for i in range(k+1):
tmp_prices = prices.copy()
for s, d, p in flights:
if prices[s] == float("inf"):
continue
if prices[s] + p < tmp_prices[d]:
tmp_prices[d] = prices[s] + p
prices = tmp_prices
return -1 if prices[dst] == float("inf") else prices[dst]
Related LeetCode Questions: Cheapest Flights Within K Stops Importance: 6/10
Prim’s (Minimum Spanning Tree) Algorithm
Prim’s is a textbook algorithm that doesn’t really have much utility besides finding the MST of a weighted undirected graph. It uses BFS and a priority queue (min heap) to add the edge with the minimum cost at each iteration.
Wait, that sounds like Dijkstra’s algorithm… If this thought came across your mind, let me clear up the confusion. Besides the fact that Dijkstra’s works on directed graphs while Prim’s works on undirected graphs, the main difference algorithm-wise is that when adding (weight, node)
to the heap in Prim’s, the weight
is simply the edge’s weight but in Dijkstra’s, this weight
is the total cost from source node to the vertex in question (see below).
# Dijkstra's algorithm
heapq.heappush(heap, (curr_weight + prev_weight, neighbour))
# Prim's algorithm
heapq.heappush(heap, (curr_weight, neighbour))
💡 Note! Use a visited
hash set to prevent an infinite loop!
Related LeetCode Questions: Min Cost to Connect All Points Importance: 6/10
Trees
Recursive Depth-First-Search
An extremely handy technique that can be used to solve not only tree problems, but other problems that can be visualized in a tree-based structure. It is also used in backtracking and some dynamic programming questions (together with memoization).
There are many ways to implement a recursive DFS solution, but I personally like to follow a nested structure as follows:
# Example of using recursive DFS to solve a typical tree-based problem
def calculate_max_depth(root: TreeNode) -> None:
max_depth = 0
# nested DFS function
def dfs(node):
nonlocal max_depth # include this variable into scope
# base case(s)
if not node:
return
# main logic implemented here
# call to recursive DFS function
dfs(root)
return max_depth
More often than not, I would simply write out the above structure first and focus on coding out the main logic within the DFS function itself. This shows the interviewer that you are aware of how to write recursive functions and now you can work together with the interviewer to implement the main logic.
Related LeetCode Questions: Subsets, Subsets II, Combination Sum, Combination Sum II, Word Search, Most binary tree questions Importance: 10/10
Binary Trees
For binary trees, you should be familiar with the three traversal techniques, namely:
- Preorder traversal
- Inorder traversal
- Postorder traversal
For brevity of this article and other resources out there, you can refer to this article for details on each traversal technique.
Questions that test your knowledge on traversal techniques often provide nodes based on two different traversal technique and asking you to solve for a particular thing.
A subset of binary trees are binary search trees (BST). BSTs have a unique property in that a node’s left child will always hold a smaller value than itself and the node’s right child will always hold a larger value than itself. This means that an inorder traversal of a BST will yield a sorted order of node values.
Related LeetCode Questions: There are too many variations of binary tree-related questions. Importance: 10/10
Heaps
Heaps should always come to mind when questions ask for:
- Top-K smallest/largest elements
- Min/max elements
For top-K largest elements, use a min heap. Intuition: Use a min heap data structure with size K to store top-K largest elements. When initializing a min heap with a set of values, either heapq.heappush
until size K or heapq.heapify
the first-K elements. After which, heapq.heappushpop
the remaining elements.
When adding a new element, use heapq.heappushpop
or heapq.heapreplace
method to add the new element. This ensures that the size of the heap is always maintained at K
and additional elements are added only if they are bigger than the smallest element in the heap.
# Initializing a min heap given a set of vals: List[int]
heap = vals[:k]
heapq.heapify(heap)
for i in range(k, len(vals)):
heapq.heappushpop(heap, vals[i])
# Adding new element `ele` to heap
if len(heap) < k:
heapq.heappush(heap, ele)
elif ele > heap[0]:
heapq.heapreplace(heap, ele)
For top-K smallest elements, use a max heap. Intuition: Same as above but for max heaps.
Heaps can not only store integers tuples as well. Tuples that are added to the heap will be sorted based on not only the first index of the tuple but subsequent indexes as well.
# Example
import heapq
min_heap = []
heapq.heappush(min_heap, (2,10))
heapq.heappush(min_heap, (2,5))
heapq.heappop(min_heap)
>> (2,5) # 5<10 hence we get (2,5) back
💡 Note: As with all data structures, be aware of the time complexity of each method implemented (e.g. heapify
, heappush
, etc) as you’ll need it to evaluate your code’s complexity.
Related Leetcode Questions: Kth Largest Element in a Stream Importance: 9/10
Tries
Tries are unique tree-based data structure that’s mainly used to store word prefixes and used in real-world applications like auto-complete.
There are two main ways to implement a trie:
- Object oriented (using a
TrieNode
class) - Nested dictionaries
Here’s how each of the implementations look like:
# 1. Object oriented method
class TrieNode:
def __init__(self, letter):
self.letter = letter
self.is_end_of_word = False
self.children = {}
class Trie:
def __init__(self):
self.root = TrieNode("*")
def add_word(self, word):
curr_node = self.root
for letter in word:
if letter not in curr_node.children:
curr_node.children[letter] = TrieNode(letter)
curr_node = curr_node.children[letter]
curr_node.is_end_of_word = True
def does_word_exist(self, word):
if word == "":
return True
curr_node = self.root
for letter in word:
if letter not in curr_node.children:
return False
curr_node = curr_node.children[letter]
return curr_node.is_end_of_word
# 2. Nested dictionaries
class Trie:
def __init__(self):
self.root = {"*": "*"}
def add_word(self, word):
curr_node = self.root
for letter in word:
if letter not in curr_node:
curr_node[letter] = {}
curr_node = curr_node[letter]
curr_node["*"] = "*"
def does_word_exist(self, word):
curr_node = self.root
for letter in word:
if letter not in curr_node:
return False
curr_node = curr_node[letter]
return "*" in curr_node
Related LeetCode Questions: Implement Trie Prefix Tree, Design Add And Search Words Data Structure Importance: 6/10
Dynamic Programming
Everyone’s “favourite” topic — dynamic programming (DP).
DP questions come in two forms: 1-dimensional or 2-dimensional. If it’s your first time learning about DP, it is crucial to familiarize yourself with the concept of subproblems, otherwise identifying a DP problem in the first place can be tough. After which, you’d want to identify if it is a 1-D or 2-D DP problem.
You also need to be fairly comfortable with recursion as most DP solutions are easier (and typically requires fewer lines of code) when solved recursively (rather than iteratively).
Also, recursive DFS is a fairly common technique used to solve DP problems and commonly paired with memoization (caching).
Related LeetCode Questions: Climbing Stairs, Palindromic Substrings, House Robber I, House Robber II, Coin Change, Longest Increasing Subsequence Importance: 7/10. Even though DP is fairly important, it is less common than array/tree/graph/string based questions. If you’re strapped for time, you can skip DP and pray that it won’t be asked.
Bit Manipulation
To be honest, I prepared for this topic the least.
<Placeholder: to furnish with more details in the future>
# XOR operation: ^
x ^ y
# Logical and
x & 1
# Bitshift left/right by 1
x >> 1
x << 1
Importance: 1/10. Honestly, I’ve not encountered any interview that touched on this topic, and neither has anyone I know.
Miscellaneous (Tips & Tricks)
- Removing an element from an array at a known index can be done in constant O(1) time. How? Swap the element you want to remove with last element in the array and then pop it off the array.
E
number of edges → O(n²);V
number of vertices → O(n)- Use
defaultdict
instead of built-in dictionary wherever possible. This allows to skip handling keys that are not currently present in the dictionary and also assigning default values/data structures.
from collections import defaultdict
d = defaultdict(int) # useful when assigning values with default 0
d = defaultdict(list) # useful for creating adjacency lists
- Create a 2D matrix of zeros (e.g. DP matrix)
n_rows, n_cols = len(grid), len(grid[0])
dp = [[0 for _ in range(n_cols)] for _ in range(n_rows)]
- Array slicing is
O(k)
wherek
is the length of the sliced array - Be familiar with Python’s inbuilt
sorted
function. For example to sort a dictionaryd
based on its value in descending order:
sorted(d.items(), reverse=True, key=lambda item: item[1])
- Convert unicode characters to code point:
ord(<CHAR>)
- Convert unicode code point to unicode characters:
chr(<CODE>)
- When keeping track of a max/min variable, use this one-liner as your update statement:
max_depth = 0
# some code here (...)
# update statement
max_depth = max(max_depth, var1, var2)
- Use multi-variable assignments to avoid the use of temporary variables. This is particularly useful (and not to mention a lot neater) for linked list questions where pointers often get reassigned.
# Single variable assignment
tmp = left
left = right
right = tmp
# Multi-variable assignment
left, right = right, left
Finals Words
Want to find out how I prepared for my interview and how I used these resources to land a job offer? Read more at my personal blog page here!
Also, leave a comment to let me know which areas you find useful or want more information about!
Support me! — If you like my content and are not subscribed to Medium, do consider supporting me and subscribing via my referral link here (NOTE: a portion of your membership fees will be apportioned to me as referral fees). Otherwise, leaving a 👏🏻 clap or 💬 comment helps with the algorithm too!