# 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 doesNOTwalk 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

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.*i*th

```
# 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

class defined as (used in below examples):**ListNode**

```
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 the`fast`

pointer moves two at a time. By the time the`fast`

pointer reaches the end of the linked list, the`slow`

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**— To do so, we first move the*Kth*element from the end of linked list`fast`

pointer`k`

elements ahead from the head. After which, we initialise the`slow`

pointer at the head and move both pointers one at a time. By the time the`fast`

pointer reaches the end, the`slow`

pointer would be at the

element from the end. [*Kth**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`set to prevent being stuck in an infinite loop!`

visitedNote: Some people prefer updating the`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.`

visited

**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**:

, where **O(E log V)**

represents number of edges and **E**

represents number of vertices**V**

```
# 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**:

, where **O(EV)**

represents number of edges and **E**

represents number of vertices.**V**

```
# 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 `(`

to the heap in Prim’s, the **weight**, node)

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).**weight**

```
# Dijkstra's algorithm
heapq.heappush(heap, (curr_weight + prev_weight, neighbour))
# Prim's algorithm
heapq.heappush(heap, (curr_weight, neighbour))
```

💡 **Note**! Use a

hash set to prevent an infinite loop!**visited**

**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

class)**TrieNode** - 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.

number of edges → O(n²);**E**

number of vertices → O(n)**V**- Use

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.**defaultdict**

```
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

where**O(k)**

is the length of the sliced array**k** - Be familiar with Python’s inbuilt

function. For example to sort a dictionary**sorted**

based on its value in descending order:**d**

`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!