‡ Piero24 ¯ pietrobonandrea Œ hashto.

net

Data Structures
Arrays Strings Binary Trees

Collection of items of some data type stored one after another. A string is a sequence of characters. Many tips that apply to arrays also Is a tree like data structure where every node has at most two children.
Optimal for indexing; bad at searching, inserting, and deleting (except apply to strings. Common string algorithms: Rabin Karp (using a Trees are undirected graphs in which any two vertices are connected by
at the end). Linear arrays, Dynamic arrays, Multi dimensional arrays. rolling hash) and KMP: for searching of substring. exactly one edge and there can be no cycles in the graph.
- Neighbor: Parent or child of a node.
Things to look out for during interviews: Things to look out for during interviews: - Ancestor: A node reachable by traversing its parent chain.
- Understanding time and space complexity - Input character set and case sensitivity. (lowercase, uppercase, English - Descendant: A node in the node’s subtree.
- Knowing common array algorithms (like sorting) letters etc...) - Degree: N° of children of a node.
- Familiarity with dynamic arrays and their benefits - Degree of a tree: Maximum degree of nodes in the tree.
Techniques: Corner cases: - Distance: N° of edges along the shortest path between two nodes.
Techniques: Corner cases: - Counting characters - Empty string - Width: N° of nodes in a level.
- Sliding window - Empty sequence - String of unique characters - 1 or 2 characters - Full binary tree: Every node has exactly 0 or 2 children.
- Two pointers - Sequence with 1 or 2 elements - Anagram - Repeated characters - Perfect binary tree: Every node have 2 children.
- Traversing from the right - Sequence with repeated elements - Palindrome - Only distinct characters - Complete binary tree: All levels are fully filled, except possibly the
- Sorting the array - Duplicated values in the sequence last, with nodes as far left as possible.
- Precomputation - Balanced binary tree: Height difference between left and right
Helpful Resources:
- Index as a hash key subtrees is at most 1.
Tech Interview Handbook
- Traversing the array more than once - Level/Depth: N° of edges from the root to the node.
Python Cheat Sheet
- Height: N° of edges from its root to the furthest leaf.
- Degenerate tree: An unbalanced tree, which if entirely one-sided,
Helpful Resources: Stacks
(essentially a linked list).
Interview Cake Stores items in a last-in, first-out (LIFO). Made with linked lists/arrays.
- Number of nodes in a level 2h − 1 where h is the height of the level.
Tech Interview Handbook
Python Cheat Sheet Things to look out for during interviews:
- In-order traversal : Lef t → Root → Right :[2, 7, 5, 6, 11, 1, 9, 5, 9]
TICS - Familiarity with dynamic arrays and their benefits
- Pre-order traversal : Root → Lef t → Right :[1, 7, 2, 6, 5, 11, 9, 9, 5]
- Post-order traversal : Lef t → Right → Root :[2, 5, 11, 6, 7, 5, 9, 9, 1]
Linked List/Double Linked List
Techniques: Corner cases:
Stores data with nodes that point to other nodes. Designed to optimize - Dynamic Resizing - Popping from an empty stack Things to look out for during interviews:
insertion and deletion, slow at indexing and searching. Singly linked - Stack Reversal - Stack with one item - Sometimes interviewers ask candidates for the iterative approach.
list, Doubly linked list, Circularly linked list. - Stack with two items - Familiar with: Insert value, Delete value, Count nodes, If value is in
the tree, Calculate height
Common routines:
Helpful Resources:
- Counting the number of nodes in the linked list
Interview Cake Techniques: Corner cases:
- Reversing a linked list in-place
Tech Interview Handbook - Use recursion - Empty tree
- Finding the middle node using two pointers (fast/slow)
TICS - Algorithm Wiki - Traversing by level - Single node
- Merging two linked lists together
- Summation of nodes - Two nodes
- Very skewed tree (like a linked
Queues / Double Ended Queues
Techniques: Corner cases: list)
- Sentinel/dummy nodes - Empty linked list Stores items in a first-in, first-out (FIFO) order (Queue) or allows
- Two pointers - Single node insertion and removal from both ends (Deque).
- Using space - Two nodes Depht: 0
Helpful Resources:
- Elegant modification operations - Linked list has cycles Things to look out for during interviews:
Interview Cake
- Many languages lack efficient built-in Queues. Inform the interviewer
Tech Interview Handbook Depht: 1
Helpful Resources: and assume an efficient queue structure is available (or use deque).
TICS
Interview Cake - Deques can handle both stack and queue operations efficiently. Height: 3

Tech Interview Handbook Depht: 2

Python Cheat Sheet Techniques: Corner cases:

TICS - Use deque in Python for both - Empty Queue/Deque
Depht: 3
Algorithm Wiki queue and deque use cases. - Queue/Deque with one item
- Implement circular queues for - Queue/Deque with two items
space-efficient fixed-size queues.

Helpful Resources:
Interview Cake
Tech Interview Handbook
TICS - Algorithm Wiki
 ‡ Piero24 ¯ pietrobonandrea Œ [Link]
Binary Search Trees Hash Tables Matrices

A (BST) is a binary tree where every node’s left subtree contains only A hash map maps keys to values using a hash function to compute an A 2-dimensional array. Can be used to represent graphs where each
nodes with values less than the node’s key, and every node’s right index into an array, where the corresponding value is stored. During node is a cell on the matrix which has 4 neighbors (except those cells on
subtree contains only nodes with values greater than the node’s key. lookup, the key is hashed to find the value’s location. You likely won’t the edge and corners).
Balanced vs. Unbalanced: be asked about collision resolution in detail during interviews.
- In a balanced tree, operations are O(log n). - Separate chaining: Collided values are stored in a linked list at each Things to look out for during interviews:
- In an unbalanced tree (e.g., degenerate trees), can degrade to O(n). bucket. - Questions involving matrices are usually related to dynamic program-
Note: Some properties are the same as the one for the trees. - Open addressing: All values are stored in the array, probing for the ming or graph traversal.
next available slot when collisions occur.
- In-order traversal, Pre-order traversal, Post-order traversal: Same of Techniques: Corner cases:
those for the Binary Tree Things to look out for during interviews: - Creating an empty N x M matrix - Empty matrix
- - Transposing a matrix - 1 x 1 matrix
Things to look out for during interviews: - Only one row or column
- The same as those for the Binary Trees Techniques: Corner cases:
- How to maintain the properties after insertion and deletion - - Helpful Resources:
- Implement search, insert, and delete iteratively
Tech Interview Handbook
Helpful Resources: Apple Mango
Techniques: Corner cases: Interview Cake Avocado
- Use recursion - Empty tree Tech Interview Handbook
- Deletion, focus on understanding - Single node Python Cheat Sheet Graphs
the three different cases. - Two nodes TICS
- Balance a tree with AVL or Red- - Very skewed tree (like a linked A structure with nodes (vertices) and edges, which can be directed or
Algorithm Wiki
Black trees. list) undirected, and may have weights (a weighted graph).
- Minimum Spanning Tree: Finds the cheapest edges needed to
Trie
connect all nodes in a weighted graph.
Helpful Resources: A special tree that can compactly store strings. Be familiar with
- Directed: edges have a direction (from one node to another).
Interview Cake implementing from scratch, a Trie class and its add, remove and search
- Undirected: edges connect nodes without direction.
Tech Interview Handbook methods.
- Cyclic: Contains at least one cycle (a path that loops).
TICS
- Acyclic: No cycles.
Algorithm Wiki Things to look out for during interviews:
- Weighted: Edges have a “weight” (e.g., distance, cost, time)
- Space-efficient when storing many words with shared prefixes.
- Unweighted: Edges are simply connections between nodes.
- Efficient for prefix queries (e.g., “How many words start with. . . ”).
- Legal Coloring: Assigning colors to nodes such that no adjacent
- Often space-inefficient compared to storing strings in a set.
nodes share the same color.
- Not a standard data structure—requires custom implementation.
Heaps - Topological Sort: Orders nodes in a directed acyclic graph based on
dependencies. (e.g. scheduling tasks with prerequisites.)
A tree-based data structure that is complete and satisfies the heap
Techniques: Corner cases:
property:
- Reduces word search time from - Searching string in an empty trie Common graph representations are: Adjacency matrix, Adjacency list,
- Max heap: Each node’s val. is the largest in its subtree (recursively).
O(n) to O(k), where k is the word - Inserting empty strings into a trie Hash table of hash tables (simplest approach during interviews).
- Min heap: Each node’s val. is the smallest in its subtree (recursively).
length.
Heaps and priority queues are often treated as the same and are useful
Things to look out for during interviews:
for repeatedly removing the highest or lowest priority object with
Helpful Resources: - In interviews, graphs are often 2D matrices; ensure boundary checks
interspersed insertions. Note: Some properties are the same as the one
Interview Cake and track visited nodes.
for the trees.
Tech Interview Handbook - A tree-like diagram might be a graph with cycles, so naive recursion
can fail. Track visited nodes to avoid infinite loops.
Things to look out for during interviews:
- Be prepared to explain heap operations’ time complexities (O(log n)).
- Be aware of the space complexity for storing a heap. Graph search algorithms: Corner cases:
- Common: BFS, DFS - Empty graph
- Uncommon: Topological Sort, - Graph with one or two nodes
Techniques: Corner cases:
Dijkstra’s - Disconnected graphs
- Mention of k - Empty or Small (k = 1 - 2) heap.
- Never: Bellman-Ford, Floyd- - Graph with cycles
- Duplicate values in heaps.
Warshall, Prim’s, Kruskal’s

Helpful Resources:
Helpful Resources:
Interview Cake
Interview Cake
Tech Interview Handbook
Tech Interview Handbook
Algorithms Wiki
 ‡ Piero24 ¯ pietrobonandrea Œ [Link]

Code for Data Structures

Arrays Strings Queues / Double Ended Queues (DE-Q)

nums . append (1) # Appends 1. text . split ( ’ ’) # Splits a string into a list . from collections import deque
nums . copy () # Returns a copy of the list . l = list ( s ) # Converts a string to a list . q = deque ()
copy . deepcopy ( nums ) # A real copy of the list . message . count ( ’p ’) # Counts rep of a substring . q . append ( x ) # Enqueue x to the queue
nums . count (1) # Counts occurrences of 1. s . isnumeric () # Checks if all chars are num q . popleft () # Dequeue the front item
# Extends list with another list . message . find ( ’ fun ’) # Index of substring or -1. q [0] # Peeks at the front item
nums . extend ( otherList ) name . isalnum () # Checks if are alphanumeric . len ( q ) == 0 # Checks if the queue is empty
# Removes and returns the last item . name . isalpha () # Checks if chars are alphabets . q . appendleft ( x ) # Enqueue x to the front ( DE - Q )
nums . pop () # . pop ( index ) string . upper () # Converts to uppercase . q . pop () # Dequeue the last item ( DE - Q )
nums . reverse () # Reverses the list . string . lower () # Converts to lowercase .
nums . sort () # Sorts the list ( in place ) . string . islower () # Check if chars are lowercase . Binary Trees/Binary Search Trees
arr . insert (x , y ) # Inserts x at index y . string . isupper () # Check if chars are uppercase .
a [ start : stop ] # Slice from start to stop -1. string . isdigit () # Checks if chars are digits .
a [ -1] # Last item . txt = " aabac " # Removes leading " a ". class TreeNode :
a [:: -1] # List reversed . txt . lstrip ( " a " ) # result -> " bac " def __init__ ( self , val =0 , l = None , r = None ) :
" " . join ([ " h " , " i " ]) # O (1) , with += is O ( n ˆ2) self . val = val
Linked List/Double Linked List self . left = l
Hash Tables self . right = r

class ListNode : Tries

def __init__ ( self , val =0 , next = None ) : # prev hs = { ’a ’: 1 , ’b ’: 2} # Dictionary Methods
= None hs . keys () # List of keys : [ ’ a ’, ’b ’]
self . val = val hs . values () # List of values : [1 , 2] class TrieNode :
self . next = next hs . items () # List of pairs : [( ’ a ’, 1) , ( ’ b ’, 2) ] def __init__ ( self ) :
# self . prev = prev hs . pop ( ’a ’) # Pops key ’a ’ self . children = {}
hs . popitem () # Pops the most recent item self . is_end_of_word = False
def delete_after ( self , node : ListNode ) : # Elem . added have a default value
node . next = node . next . next hs = defaultdict ( int ) # int , list , set , str etc .. class Trie :
# prev for the double linked list . OR use deque def __init__ ( self ) :
from collections import Counter self . root = TrieNode ()
Heaps l1 = [ ’x ’ , ’y ’ , ’x ’]
cnt = Counter ( l1 ) # Counter ({ ’ x ’: 2 , ’y ’: 1}) # Insert a word into the Trie
cnt . most_common (1) # [( ’ x ’, 2) ] def insert ( self , word ) :
import heapq # Min - Heap by default cnt [ ’y ’] += 1 # Increment ’y ’ node = self . root
nums = [5 , 7 , 9 , 1 , 3] del cnt [ ’y ’] # Remove ’y ’ for char in word :
heapq . heapify ( nums ) # Convert list to heap if char not in node . children :
heapq . heappush ( nums , element ) # Push element st = {1 , 2 , 3} # Set Methods node . children [ char ] = TrieNode ()
heapq . heappop ( nums ) # Pop element st . add ( item ) # Add item node = node . children [ char ]
# k largest elements st . remove ( item ) # Err if not present node . is_end_of_word = True
heapq . nlargest (k , iterable , key = fun ) st . discard ( item ) # No Err if not present
# k smallest elements st . isdisjoint ( otrSet ) # True if no common # Search for a word in the Trie
heapq . nsmallest (k , iterable , key = fun ) elements def search ( self , word ) :
# View the next element without popping st . issubset ( otrSet ) # True if set is a subset of node = self . root
if nums : next_element = nums [0] otrSet for char in word :
# Max - Heap ( use min - heap ) : Multiply values by -1 st . difference ( otrSet ) # Elements only in st if char not in node . children :
to simulate max - heap , then pop and multiply st . intersection ( otrSet ) # Common elements return False
by -1 again to restore st . symmetric_difference ( otrSet ) # Non - common node = node . children [ char ]
elements of both sets return node . is_end_of_word
Graphs st . union ( otrSet ) # Combine sets
st . update ( otrSet ) # Add otrSet without duplic # Check if any word in the Trie starts with
the given prefix
from collections import defaultdict def starts_with ( self , prefix ) :
Stacks
class Graph : node = self . root
def __init__ ( self ) : for char in prefix :
self . adj_list = defaultdict ( list ) s . append ( x ) # Pushes x onto the stack if char not in node . children :
s [ -1] # Peeks at the top item return False
def add_edge ( self , u , v ) : s . pop () # Removes and returns the top item node = node . children [ char ]
self . adj_list [ u ]. append ( v ) len ( s ) == 0 # Checks if the stack is empty return True
 ‡ Piero24 ¯ pietrobonandrea Œ [Link]

Algorithms
Binary Search DFS for Trees BFS for Graphs

Binary Search is an efficient algorithm to find an element’s position in a Depth-First Search (DFS) is a traversal algorithm that explores as far Traverses the graph level by level, starting from a given source node. It
sorted array by repeatedly dividing the search interval in half. It works down a branch as possible before backtracking. Common DFS strategies visits all neighboring nodes before moving on to nodes at the next level
on sorted sequences and has O(log n) time complexity. include pre-order, in-order, and post-order traversal for binary trees. of distance. The time complexity is O(V + E), where V is the number
The time complexity is O(V + E) where V is vertices and E is edges, of vertices and E is the number of edges.
Things to look out for during interviews: making it efficient for tree and graph traversals.
- Ensure the input is sorted (works on sorted sequences) Things to look out for during interviews:
Things to look out for during interviews: - For directed graphs, ensure edges are traversed correctly.
def binarySearch ( nums : List [ int ] , target : int ) - Choose the correct traversal type (pre-order, in-order, post-order) - For undirected graphs, mark nodes as visited to avoid revisiting.
-> int : - Commonly used for shortest path algorithms in unweighted graphs.
l , r = 0 , len ( nums ) - 1 def inorder_traversal ( self , root ) :
while l <= r : if not root : return from collections import deque
m = l + ( r - l ) // 2 inorder_traversal ( root . left ) def bfs ( root ) :
if nums [ m ] < target : print ( root . value , end = " " ) queue = deque ([ root ])
l = m + 1 inorder_traversal ( root . right ) visited = set ([ root ])
elif nums [ m ] > target :
r = m - 1 def preorder_traversal ( self , root ) : while queue :
else : if not root : return node = queue . popleft ()
return m print ( root . value , end = " " ) print ( node ) # Example operation
return -1 preorder_traversal ( root . left )
preorder_traversal ( root . right ) # Iterate over the neighbors of the node
Helpful Resources:
for neighbor in get_neighbors ( node ) :
Algorithm Wiki
def postorder_traversal ( self , root ) : # Skip already visited neighbors
Zero To Mastery
if not root : return if neighbor in visited :
postorder_traversal ( root . left ) continue
BFS for Trees
postorder_traversal ( root . right )
print ( root . value , end = " " ) queue . append ( neighbor )
Breadth-First Search (BFS) for trees traverses the tree level by level, visited . add ( neighbor )
visiting all nodes at the current depth before moving to the next level.
Helpful Resources:
It uses a queue to manage the nodes to be explored next. BFS has a
Zero To Mastery Helpful Resources:
time complexity of O(V ), where V is the number of nodes in the tree.
Algorithm Wiki Algo Master
Zero To Mastery
Things to look out for during interviews:
- Requires additional memory for the queue, which can grow large for
wide trees

DFS for Graphs

from collections import deque
def level_order ( root : TreeNode ) -> None : Explores as far along a branch as possible before backtracking. Has a Relaxation
if not root : time complexity of O(V + E), where V is the number of vertices and E
Relaxation is the process of updating the shortest path estimate for a
return is the number of edges.
vertex by checking whether a shorter path is found via an adjacent edge.
It is a core concept in many graph algorithms, including Dijkstra’s,
q = deque ([ root ]) Things to look out for during interviews:
Bellman-Ford, and the Floyd-Warshall algorithm. Relaxation is done
- Ensure visited nodes are tracked to prevent infinite loops.
by comparing the current shortest path estimate to a newly found path
while q : - Detects cycles, finds components, or solves mazes.
and updating it if the new path is shorter.
node = q . popleft () - Recursive DFS may overflow; iterative is safer.
print ( node . val , end = " " ) - For directed graphs, pay attention to the direction of edges.
Things to look out for during interviews:
if node . left : - Relaxation is repeated for every edge during algorithms like Bellman-
def dfs ( root , visited ) :
q . append ( node . left ) Ford.
for neighbor in get_neighbors ( root ) :
if node . right : - It’s crucial for updating shortest paths in graphs with weighted edges.
if neighbor not in visited :
q . append ( node . right ) - Ensure that relaxation is performed correctly to avoid incorrect shortest
visited . add ( neighbor )
path results.
dfs ( neighbor , visited )
Zero To Mastery
Helpful Resources:
Zero To Mastery
Helpful Resources:
Algorithm Wiki
AlgoMaster
Zero To Mastery
 ‡ Piero24 ¯ pietrobonandrea Œ [Link]
Bellman-Ford Dijkstra Merge Sort

Finds the shortest paths from a source node to all other nodes in a Finds the shortest path from a source node to all other nodes in a A divide-and-conquer algorithm that recursively splits the sequence in
graph, even with negative edge weights. It works by repeatedly relaxing weighted graph with non-negative edge weights. The time complexity half until each sub-sequence has one element. It then merges them back
edges and has a time complexity of O(V · E), where V is the number of is O((V + E) log V ), where V is the number of vertices and E is the together in sorted order. It is efficient for large data sets and guarantees
vertices and E is the number of edges. The algorithm can also detect number of edges. O(n log n) time complexity.
negative weight cycles.
Things to look out for during interviews: Things to look out for during interviews:
Negative edge weights in a graph can complicate the shortest path - Works only with non-negative weights. - Recursive depth and potential for stack overflow in languages without
problem, as they allow for potential decreases in path length when - Ensure priority queue or min-heap is implemented efficiently. tail recursion optimization
traversing edges. Algorithms like Dijkstra’s fail in graphs with negative - Can be adapted for shortest path in graphs with specific constraints
edge weights, but others, like Bellman-Ford, can handle them effectively. (e.g., one-to-all, all-to-all). def merge_sort ( arr : List [ int ]) -> None :
Negative weights can also lead to negative weight cycles, which can if len ( arr ) <= 1: return
result in infinitely shorter paths. import heapq
def dijkstra ( graph , n , start ) : mid = len ( arr ) // 2
Things to look out for during interviews: adj = {} left_half = arr [: mid ]
- Handles negative edge weights. for i in range (1 , n + 1) : right_half = arr [ mid :]
- Slower than Dijkstra’s algorithm. adj [ i ] = []
- Can detect negative weight cycles, which Dijkstra cannot. # Recursively sort each half
- Ensure edge relaxation is done V − 1 times for correctness. # Source , Destination , Weight left_sorted = merge_sort ( left_half )
for s , d , w in graph : right_sorted = merge_sort ( right_half )
def bellman_ford ( graph , start ) : adj [ s ] = [( d , w ) ]
# Initialize distances to all nodes as # Merge the sorted halves
infinity shortest = {} return merge ( left_sorted , right_sorted )
distances = { node : float ( ’ inf ’) for node in minHeap = [(0 , start ) ]
graph } def merge ( left : List [ int ] , right : List [ int ]) ->
distances [ start ] = 0 while minHeap : List [ int ]:
w1 , n1 = heapq . heappop ( minHeap ) sorted_array = []
# Relax edges | V | - 1 times i = j = 0
for _ in range ( len ( graph ) - 1) : if n1 in shortest :
for node in graph : continue # Merge elements from both halves in sorted
for neighbor , weight in graph [ node ]: shortest [ n1 ] = w1 order
if distances [ node ] + weight < while i < len ( left ) and j < len ( right ) :
distances [ neighbor ]: for n2 , w2 in adj [ n1 ]: if left [ i ] < right [ j ]:
distances [ neighbor ] = if n2 not in shortest : sorted_array . append ( left [ i ])
distances [ node ] + weight node = ( w2 + w1 , n2 ) i += 1
heapq . heappush ( minHeap , node ) else :
# Check for negative weight cycles return shortest sorted_array . append ( right [ j ])
for node in graph : j += 1
for neighbor , weight in graph [ node ]: Helpful Resources:
if distances [ node ] + weight < # Append remaining elements , if any
Zero To Mastery
distances [ neighbor ]: sorted_array . extend ( left [ i :])
Algorithm Wiki
print ( " Graph contains a negative sorted_array . extend ( right [ j :])
weight cycle " ) return sorted_array
return None
Helpful Resources:
return distances Algorithm Wiki
Sparse Graphs
Zero To Mastery
Helpful Resources:
Zero To Mastery

Helpful Resources:
Zero To Mastery
Zero To Mastery
 ‡ Piero24 ¯ pietrobonandrea Œ [Link]
Quick Sort Insertion Sort Bottom Up (Dynamic Programming)

A divide-and-conquer algorithm that partitions the array around a pivot Builds the sorted array one element at a time by comparing each new Technique in dynamic programming that solves subproblems first and
element, sorting elements before and after the pivot recursively. Average element with those already sorted. It’s efficient for small or nearly builds up to the final solution. It typically uses a table (usually an array
time complexity of O(n log n), (worst-case is O(n2 )) when already sorted. sorted datasets and has a time complexity of O(n2 ) in the worst case, or list) to store the results of subproblems in a bottom-up manner.
but O(n) in the best case (when the array is already sorted).
Things to look out for during interviews: Things to look out for during interviews:
- Randomize Pivot selection to improve performance Things to look out for during interviews: - Carefully define the state.
- In-place sorting but uses O(log n) stack space for recursion depth - Performs well on small or partially sorted data - Determine the base cases.
- Often used in hybrid sorting algorithms for small arrays (e.g., as part - Define how to calculate the value for a cell based on previous cells.
def quickSort ( nums : list [ int ]) -> list [ nums ]: of Timsort) - Ensure is filled in the correct order (usually iteratively).
if len ( nums ) < 2: return nums
def insertion_sort ( arr : List [ int ]) -> List [ int ]: def fib_tabulation ( n ) :
pivot = nums [0] n = len ( arr ) if n <= 1:
l , e , r = [] , [ pivot ] , [] return n
for i in range (1 , n ) : # Create list to store results of
for i in range (1 , len ( nums ) ) : key = arr [ i ] subproblems
if nums [ i ] < pivot : j = i - 1 dp = [0] * ( n + 1)
l . append ( nums [ i ]) # Define base cases
elif nums [ i ] == pivot : # Move elements of the sorted part that dp [0] , dp [1] = 0 , 1
e . append ( nums [ i ]) are greater than the key
else : # to one position ahead of their current # Fill the list using the prev results
r . append ( nums [ i ]) position for i in range (2 , n + 1) :
return quickSort ( l ) + e + quickSort ( r ) while j >= 0 and key < arr [ j ]: dp [ i ] = dp [ i - 1] + dp [ i - 2]
arr [ j + 1] = arr [ j ] return dp [ n ]
Helpful Resources:
j -= 1
Zero To Mastery Helpful Resources: AlgoMaster
# Insert the key at the correct position
Algorithm Wiki Zero To Mastery LeetCode
arr [ j + 1] = key
LeetCode Dynamic Programming GeeksforGeeks
Tech Interview Handbook
return arr
Recursion
Selection Sort
Helpful Resources:
Break problems into smaller instances of the same problem. It involves
A sorting algorithm that divides the array into sorted and unsorted Zero To Mastery
two key parts:
parts. It repeatedly selects the minimum element from the unsorted Algorithm Wiki
- A base case to stop recursion
portion and swaps it with the first unsorted element. It’s O(n2 ),
- Recursive calls to solve subproblems
inefficient for large datasets.

Things to look out for during interviews:

Things to look out for during interviews: Caching/Memoization (Dynamic Programming)
- Always define a base case
- Simple but slow on large data sets
Used in dynamic programming to store intermediate results and avoid - Useful for permutations, combinations, and tree problems
- Minimizes number of swaps, useful when write operations are costly
redundant computations, optimizing performance. Often implemented - Uses a stack (risk of stack overflow, e.g. Python limit: 1000)
using data structures like hash tables, arrays, or dictionaries. - Not O(1) space complexity
def selection_sort ( arr : List [ int ]) -> List [ int ]:
- Can have multiple base cases
for i in range ( len ( arr ) ) :
# Find the min elem in the unsorted part Things to look out for during interviews:

minId = i - Techniques: Corner cases:

for j in range ( i + 1 , len ( arr ) ) : - Memoization: improve effi- - n = 0 or n = 1
if arr [ j ] < arr [ minId ]: def fib (n , cache ={}) : # Dict as a cache ciency, reduce time complexity - Adequate base cases
minId = j if n in cache : return cache [ n ]
if n <= 1: return n
# Swap found min elem with the first cache [ n ] = fib ( n - 1 , cache ) + fib ( n - 2 ,
def fib ( n : int ) -> int :
arr [ i ] , arr [ minId ] = arr [ minId ] , arr [ i ] cache )
if n <= 1:
return arr return cache [ n ]
return n
# OR from functools import lru_cache
return fib ( n - 1) + fib ( n - 2)
# @lru_cache ( None ) Auto . handles caching
Helpful Resources:
Zero To Mastery Helpful Resources:
Helpful Resources: AlgoMaster
Algorith Wiki Tech Interview Handbook
Zero To Mastery LeetCode
Zero To Mastery
LeetCode Dynamic Programming GeeksforGeeks
Tech Interview Handbook
 ‡ Piero24 ¯ pietrobonandrea Œ [Link]
Kruskal Bucket Sort

Finds the Minimum Spanning Tree (MST) by sorting edges and Sort an array by dividing it into several buckets, then sorting each
adding them, avoiding cycles with a union-find data structure. Time bucket individually. It’s a comparison-free sorting algorithm. Efficient
complexity: O(E log E) where E is the number of edges. for floating-point numbers. Not suitable for large input ranges.

Things to look out for during interviews: Things to look out for during interviews:
- Works well with sparse graphs (many edges) because of the sorting step. - Requires knowledge of input distribution.
- The union-find data structure is crucial for cycle detection. - Choice of bucket size affects efficiency.
- Optimize union and find with path compression and union by rank. - Optimal when input values are spread evenly.

class UnionFind :
def __init__ ( self , n ) : def bucket_sort ( arr ) :
# Initialize parent and rank arrays if len ( arr ) == 0: return arr
self . parent = list ( range ( n ) )
self . rank = [0] * n # Step 1: Create buckets
num_buckets = len ( arr )
def find ( self , u ) : max_value , min_value = max ( arr ) , min ( arr )
# Path compression : Find the root of u , bucket_range = ( max_value - min_value ) /
with path compression num_buckets
if self . parent [ u ] != u : buckets = [[] for _ in range ( num_buckets ) ]
self . parent [ u ] = self . find ( self .
parent [ u ]) # Step 2: Distribute elements into buckets
return self . parent [ u ] for num in arr :
index = int (( num - min_value ) //
def union ( self , u , v ) : bucket_range )
# Union by rank : Attach the smaller tree if index == num_buckets : # Handle edge
under the root of the larger tree case for max value
root_u = self . find ( u ) index -= 1
root_v = self . find ( v ) buckets [ index ]. append ( num )

if root_u != root_v : # Step 3: Sort each bucket

# Union by rank for bucket in buckets :
if self . rank [ root_u ] > self . rank [ bucket . sort () # Insertion Sort can be
root_v ]: used here for small buckets
self . parent [ root_v ] = root_u
elif self . rank [ root_u ] < self . rank [ # Step 4: Concatenate buckets
root_v ]: sorted_array = []
self . parent [ root_u ] = root_v for bucket in buckets :
else : sorted_array . extend ( bucket )
self . parent [ root_v ] = root_u
self . rank [ root_u ] += 1 return sorted_array
return True
return False Helpful Resources: Geeks for Geeks
Tech Interview Handbook
def kruskal (n , edges ) :
# Sort edges by weight ( smallest first )
edges . sort ( key = lambda edge : edge [2])
uf = UnionFind ( n )
mst , mst_weight = [] , 0

# Process edges in increasing weight order

for u , v , weight in edges :
if uf . union (u , v ) : # If u and v are not
in the same component
mst . append (( u , v , weight ) )
mst_weight += weight
return mst , mst_weight

Helpful Resources: Algorithm Wiki

 ‡ Piero24 ¯ pietrobonandrea Œ [Link]

Big-O Notaion

Big-O Complexity Chart

Horrible
O(n!) O(n^2)

O(2^n)
Bad

Big-O Cheat Sheet

Operations

O(n log n)

Fair
O(n)
Good Data Structure Array Sorting
O(log n), O(1)
Operation Algorithms
Excellent
Elements
Time Complexity Space Complexity Time Complexity Space Complexity

Average Worst Worst Best Average Worst Worst

Access Search Insertion Deletion Access Search Insertion Deletion

Array Θ(1) Θ(n) Θ(n) Θ(n) Θ(1) Θ(n) Θ(n) Θ(n) Θ(n) Quicksort Ω(n log(n)) Θ(n log(n)) O(n^2) O(n log(n))

Stack Θ(n) Θ(n) Θ(1) Θ(1) Θ(n) Θ(n) Θ(1) Θ(1) Θ(n) Mergesort Ω(n log(n)) Θ(n log(n)) O(n log(n)) O(n log(n))

Queue Θ(n) Θ(n) Θ(1) Θ(1) Θ(n) Θ(n) Θ(1) Θ(1) Θ(n) Timsort Ω(n) Θ(n log(n)) O(n log(n)) Θ(n)

Singly-Linked List Θ(n) Θ(n) Θ(1) Θ(1) Θ(n) Θ(n) Θ(1) Θ(1) Θ(n) Heapsort Ω(n log(n)) Θ(n log(n)) O(n log(n)) O(n log(n))

Doubly-Linked List Θ(n) Θ(n) Θ(1) Θ(1) Θ(n) Θ(n) Θ(1) Θ(1) Θ(n) Bubble Sort Ω(n) Θ(n^2) O(n^2) Θ(n)

Skip List Θ(log(n)) Θ(log(n)) Θ(log(n)) Θ(log(n)) Θ(n) Θ(n) Θ(n) Θ(n) O(n log(n)) Insertion Sort Ω(n) Θ(n^2) O(n^2) Θ(n)

Hash Table N/A Θ(1) Θ(1) Θ(1) N/A Θ(n) Θ(n) Θ(n) Θ(n) Selection Sort Ω(n^2) Θ(n^2) O(n^2) Ω(n^2)

Binary Search Tree Θ(log(n)) Θ(log(n)) Θ(log(n)) Θ(log(n)) Θ(n) Θ(n) Θ(n) Θ(n) Θ(n) Tree Sort Ω(n log(n)) Θ(n log(n)) O(n^2) O(n log(n))

Cartesian Tree Θ(log(n)) Θ(log(n)) Θ(log(n)) Θ(log(n)) N/A Θ(n) Θ(n) Θ(n) Θ(n) Shell Sort Ω(n log(n)) Θ(n(log(n))^2) O(n(log(n))^2) O(n log(n))

B-Tree N/A Θ(log(n)) Θ(log(n)) Θ(log(n)) Θ(log(n)) Θ(log(n)) Θ(log(n)) Θ(log(n)) Θ(n) Bucket Sort Ω(n+k) Θ(n+k) O(n^2) Ω(n+k)

1 10 100
Red-Black Tree Θ(log(n)) Θ(log(n)) Θ(log(n)) Θ(log(n)) Θ(log(n)) Θ(log(n)) Θ(log(n)) Θ(log(n)) Θ(n) Radix Sort Ω(n+k) Θ(n+k) Ω(n+k) Ω(n+k)

Splay Tree N/A Θ(log(n)) Θ(log(n)) Θ(log(n)) N/A Θ(log(n)) Θ(log(n)) Θ(log(n)) Θ(n) Counting Sort Ω(n+k) Θ(n+k) Ω(n+k) Ω(n+k)

AVL Tree Θ(log(n)) Θ(log(n)) Θ(log(n)) Θ(log(n)) Θ(log(n)) Θ(log(n)) Θ(log(n)) Θ(log(n)) Θ(n) Cubesort Ω(n) Θ(n log(n)) O(n log(n)) O(n log(n))

KD Tree Θ(log(n)) Θ(log(n)) Θ(log(n)) Θ(log(n)) Θ(n) Θ(n) Θ(n) Θ(n) Θ(n)
 ‡ Piero24 ¯ pietrobonandrea Œ [Link]

Big-O Examples
O(1) O(n ∗ m) O(n ∗ log n)

# Array # Get every pair of elements from two arrays # HeapSort

nums = [1 , 2 , 3] nums1 , nums2 = [1 , 2 , 3] , [4 , 5] import heapq
nums . append (4) # push to end for i in range ( len ( nums1 ) ) : nums = [1 , 2 , 3 , 4 , 5]
nums . pop () # pop from end for j in range ( len ( nums2 ) ) : heapq . heapify ( nums ) # O ( n )
nums [0] # lookup print ( nums1 [ i ] , nums2 [ j ])
nums [1] while nums :
nums [2] # Traverse rectangle grid heapq . heappop ( nums ) # O ( logn )
nums = [[1 , 2 , 3] , [4 , 5 , 6]]
# HashMap / Set for i in range ( len ( nums ) ) : # MergeSort ( and most built - in sorting functions
hashMap = {} for j in range ( len ( nums [ i ]) ) : )
hashMap [ " key " ] = 10 # insert print ( nums [ i ][ j ])
print ( " key " in hashMap ) # lookup O(2n )
print ( hashMap [ " key " ]) # lookup # O ( n ˆ3 )
hashMap . pop ( " key " ) # remove # Get every triplet of elements in array
nums = [1 , 2 , 3] # Recursion , tree height n , two branches
O(n) for i in range ( len ( nums ) ) : def recursion (i , nums ) :
for j in range ( i + 1 , len ( nums ) ) : if i == len ( nums ) :
for k in range ( j + 1 , len ( nums ) ) : return 0
nums = [1 , 2 , 3] print ( nums [ i ] , nums [ j ] , nums [ k ]) branch1 = recursion ( i + 1 , nums )
sum ( nums ) # sum of array branch2 = recursion ( i + 2 , nums )
for n in nums : # looping O(log n)
print ( n ) O(cn )

nums . insert (1 , 100) # insert middle # Binary search

nums . remove (100) # remove middle nums = [1 , 2 , 3 , 4 , 5] # c branches , where c is sometimes n .
print (100 in nums ) # search target = 6 def recursion (i , nums , c ) :
l , r = 0 , len ( nums ) - 1 if i == len ( nums ) :
import heapq while l <= r : return 0
heapq . heapify ( nums ) # build heap m = ( l + r ) // 2 for j in range (i , i + c ) :
if target < nums [ m ]: branch = recursion ( j + 1 , nums )
# sometimes even nested loops can be O ( n ) r = m - 1
# ( e . g . monotonic stack or sliding window ) elif target > nums [ m ]: O(cn )

l = m + 1
O(n2 ) else :
print ( m ) # Get all factors of n
break import math
# Traverse a square grid n = 12
nums = [[1 , 2 , 3] , [4 , 5 , 6] , [7 , 8 , 9]] # Binary Search on BST factors = set ()
for i in range ( len ( nums ) ) : def search ( root , target ) : for i in range (1 , int ( math . sqrt ( n ) ) + 1) :
for j in range ( len ( nums [ i ]) ) : if not root : if n % i == 0:
print ( nums [ i ][ j ]) return False factors . add ( i )
if target < root . val : factors . add ( n // i )
# Get every pair of elements in array return search ( root . left , target )
nums = [1 , 2 , 3] elif target > root . val : O(n!)

return search ( root . right , target ) - Permutations

for i in range ( len ( nums ) ) : else : - Travelling Salesman Problem
for j in range ( i + 1 , len ( nums ) ) : return True
print ( nums [ i ] , nums [ j ])
# Heap Push and Pop
# Insertion sort ( insert in middle n times -> n import heapq
ˆ2) minHeap = []
heapq . heappush ( minHeap , 5)
heapq . heappop ( minHeap )
 ‡ Piero24 ¯ pietrobonandrea Œ [Link]

Solution Map
 ‡ Piero24 ¯ pietrobonandrea Œ [Link]

LeetCode Patterns
Fast & Slow Pointers Breadth First Search Sliding Window

Description: his technique uses two pointers that move at different Description: This pattern involves traversing a tree or graph level by Description: This pattern involves creating a ”window” into the data
speeds within a data structure, typically a linked list. level, visiting all nodes at each depth before moving to the next level. structure and then moving that window to gather specific information
Usage: Commonly used to detect cycles, find middle elements, or solve Usage: Useful when you need to explore nodes layer by layer in a such as finding the longest subarray containing all 1s. Sliding Windows
specific linked list problems. breadth-first manner, such as in shortest path problems or level order start from the 1st element and keep shifting right by one element and
traversals. adjust the length of the window. In some cases, the window size remains
def traverse ( head : ListNode ) -> None : constant and in other cases the sizes grows or shrinks.
if not head : return Note: You can find the code and more information in the section Usage: Primarily used in array or list-based problems, where you need
Algorithms > BFS for Graphs or Algorithms > BFS for Trees. to find a contiguous subset that satisfies certain conditions.
dummy = ListNode (0)
slow , fast = head , head Helpful Resources: Hackernoon # FIXED WINDOW
def fixed_sliding_window ( nums , k ) :
# Move fast ptr twice as fast as the slow Two Pointers window = set ()
ptr s = 0
Description: This pattern involves using two pointers that traverse a
# When the loop ends , slow will be at the
data structure from different positions, either moving toward each other
middle of the list for e in range ( len ( nums ) ) :
while fast and fast . next : or in tandem. The pointers help in efficiently narrowing down potential
if e - s + 1 > k :
slow = slow . next solutions by leveraging the structure’s ordering, such as finding pairs or
window . remove ( nums [ s ])
fast = fast . next . next triplets that satisfy a specific condition.
s += 1
Usage: Commonly used in sorted arrays or linked lists, where it’s ne-
if nums [ R ] in window :
cessary to find elements that meet certain criteria without redundant
Helpful Resources: return True
comparisons.
Hackernoon window . add ( nums [ R ])
return False
Helpful Resources:
In-place Reversal of a Linked List AlgoMaster # FLEXIBLE WINDOW
Description: This pattern involves reversing elements of a linked list Hackernoon def flexible_sliding_window ( nums , target ) :
in-place. s , tot = 0 , 0
Usage: It’s generally used when reversing a sequence without using extra Merge Intervals res = float ( " inf " )
space. Description: This pattern involves merging overlapping intervals.
for e in range ( len ( nums ) ) :
Usage: Often used in problems involving time intervals, ranges, or se-
def reverseList ( self , head : Optional [ ListNode ]) tot += nums [ e ]
quences.
-> Optional [ ListNode ]:
dummy = ListNode (0 , head ) while tot >= target :
def merge_intervals ( intervals : List [ int ]) ->
prev , curr = None , head res = min ( e - s + 1 , res )
List [ int ]:
tot , s = tot - nums [ s ] , s + 1
if not intervals : return []
while curr :
next_node = curr . next return 0 if res == float ( " inf " ) else res
intervals . sort ( key = lambda x : x [0])
curr . next = prev merged = [ intervals [0]]
prev = curr Helpful Resources:
curr = next_node for current in intervals [1:]: AlgoMaster
return prev last = merged [ -1] Hackernoon
if current [0] <= last [1]:
Helpful Resources: last [1] = max ( last [1] , current [1]) Prefix Sum

AlgoMaster else : Description: A technique that precomputes an auxiliary array (the

Hackernoon merged . append ( current ) ”prefix sum array”) where each element P [i] stores the cumulative sum
return merged of the original array’s elements from index 0 up to i.

Depth First Search Helpful Resources: Usage: Primarily used to calculate the sum of any contiguous subarray
AlgoMaster (a ”range sum query”) in constant O(1) time, after an initial O(N) pre-
Description: This pattern involves traversing a tree or graph depth-
Hackernoon processing step to build the prefix sum array. This is highly effective for
wise, exploring children nodes before siblings or neighbors.
problems involving frequent sum calculations over different segments of
Usage: Useful when you need to dive deeper into a tree or graph before
an array.
exploring other paths.

Note: You can find the code and more information in the section Helpful Resources:
Algorithms > DFS for Graphs or Algorithms > DFS for Trees. AlgoMaster

Helpful Resources: Hackernoon

 ‡ Piero24 ¯ pietrobonandrea Œ [Link]
Monotonic Stack Two Heaps Backtracking (Subset)

Description: This pattern involves using a stack to maintain a mono- Description: This pattern utilizes two heaps (a max-heap and a min- Description: Involves exploring all possible subsets or solutions and
tonic (either entirely non-increasing or non-decreasing) order of elements. heap) to divide a set of numbers into two parts. then backtracking to correct the course whenever necessary.
Usage: It’s often used for solving problems where you need to find the Usage: It’s commonly applied in problems involving dynamic median Usage: Used for generating paths or subsets, commonly applied in prob-
next greater or smaller elements. computation or balancing tasks, such as keeping track of the smal- lems like generating all combinations, subsets, or solving puzzles.
lest/largest halves of a dataset.
def mono_stack ( insert_entries ) : def backtracking1 ( nums : List ) : # O ( n * 2ˆ n )
stack = [] import heapq subsets , curSet = [] , []
for entry in insert_entries : class MedianFinder : helper (0 , nums , curSet , subsets )
while stack and stack [ -1] <= entry : def __init__ ( self ) : return subsets
popped_item = stack . pop () self . min_heap = []
# Do something with the popped item self . max_heap = [] def helper (i , nums , curSet , subsets ) :
here if i >= len ( nums ) :
stack . append ( entry ) def add_num ( self , num : int ) -> None : subsets . append ( curSet . copy () )
# Add to max heap ( smaller half ) return
Helpful Resources: heapq . heappush ( self . max_heap , - num )
AlgoMaster
# Decision to include nums [ i ]
# Balance heaps : Ensure all elements in curSet . append ( nums [ i ])
max_heap are <= elements in min_heap helper ( i + 1 , nums , curSet , subsets )
if self . max_heap and self . min_heap and - curSet . pop () # Backtrack
self . max_heap [0] > self . min_heap [0]:
heapq . heappush ( self . min_heap , - heapq # Decision NOT to include nums [ i ]
Cyclic Sort
. heappop ( self . max_heap ) ) helper ( i + 1 , nums , curSet , subsets )
Description: In-place O(N) time, O(1) space algorithm for arrays where
values map to indices (e.g., numbers 1 to n in an array of size n). Cycles # Maintain size property : len ( max_heap ) Helpful Resources:
0<sum<6
[3,5,2]
each element nums[i] to its correct position (nums[i]-1 for 1-based) via == len ( min_heap ) or len ( max_heap ) == AlgoMaster Hackernoon
swaps until nums[i] is correct, then moves i forward. len ( min_heap ) + 1
Usage: It’s useful in situations where the data involves a finite range of if len ( self . max_heap ) > len ( self .
natural numbers (range [1, n] or [0, n-1]). min_heap ) + 1:
heapq . heappush ( self . min_heap , - heapq
def cyclic_sort ( nums : list [ int ]) -> None : . heappop ( self . max_heap ) )
i , n = 0 , len ( nums ) elif len ( self . min_heap ) > len ( self .
while i < n : max_heap ) : Backtracking (Combinations)

# Calculate index where the nums [ i ] * heapq . heappush ( self . max_heap , - heapq Description: Used to generate all combinations of size k from a set of
should * be . heappop ( self . min_heap ) ) n elements. It relies on recursive inclusion and exclusion decisions.
idx = nums [ i ] - 1 Usage: Typically used for generating subsets of fixed sizes, such as team
def find_median ( self ) -> float : selection problems or combinatorial calculations.
# Conditions before swapping : # If odd , median is the top of max_heap
# 1. Is nums [ i ] valid (1 <= x <= n ) ? if len ( self . max_heap ) > len ( self . def combinations (n , k ) : # O ( k * n ˆ2)
# 2. Is its calculated idx within the min_heap ) : combs = []
array bounds (0 to n -1) ? return - self . max_heap [0] helper (0 , [] , combs , n , k )
# 3. nums [ i ] * not * at its correct # If even , median is the average of tops return combs
position ? of both heaps
if 1 <= nums [ i ] <= n and 0 <= idx < n return ( - self . max_heap [0] + self . def helper (i , curComb , combs , n , k ) :
and nums [ i ] != nums [ idx ]: min_heap [0]) / 2 if len ( curComb ) == k :
nums [ i ] , nums [ idx ] = nums [ idx ] , nums combs . append ( curComb . copy () )
[i] Helpful Resources: return
else : Hackernoon if i > n : return
# If already correct , or it ’s out of
range or it ’s a duplicate for j in range (i , n + 1) :
i += 1 curComb . append ( j )
helper ( j + 1 , curComb , combs , n , k )
Helpful Resources: curComb . pop ()
Hackernoon
Helpful Resources:
AlgoMaster
 ‡ Piero24 ¯ pietrobonandrea Œ [Link]
Backtracking (Permutation) Top ’K’ Elements Island (Matrix Traversal)

Description: This recursive approach generates all permutations of a Description: This pattern is used to find the top ’k’ elements in a Description: Pattern for processing connected components (’islands’)
list by building permutations incrementally. Each recursive call works given dataset based on a specified criterion, such as frequency, value, or of cells with a specific in a 2D grid, often surrounded by another value .
on the next element and inserts it into all possible positions of the exist- priority. It is often implemented using sorting techniques or heap data Uses Depth-First Search (DFS) or Breadth-First Search (BFS) for graphs
ing permutations. structures to optimize for time complexity. to explore all parts of an island once its first cell is discovered.
Usage: Commonly used in problems requiring all possible arrangements Usage: Solve problems requiring partial sorting or selective extraction. Usage: It’s generally used in grid-based problems, especially when we
of elements in a list, such as scheduling, generating anagrams, or solving Max-Heap/Min-Heap efficiently maintain the top ’k’ elements. need to group connected elements together
puzzles.
Note: You can find the code and more information in the section
def permutationsRecursive ( nums ) : # O ( n ˆ2 * n !) import heapq Algorithms > DFS for Graphs or Algorithms > BFS for Graphs.
return helper (0 , nums ) from collections import Counter

def helper (i , nums ) : def find_top_k_elements ( nums , k ) : K-way Merge

if i == len ( nums ) : frequency_map = Counter ( nums )
Description: This pattern involves merging ’k’ sorted lists. Usage:It’s
return [[]]
min_heap = [] # ( frequency , element ) typically used in problems involving lists, where merging is required.

resPerms = [] for num , freq in frequency_map . items () :

heapq . heappush ( min_heap , ( freq , num ) ) import heapq
perms = helper ( i + 1 , nums )
if len ( min_heap ) > k : def k_way_merge ( lists : list [ list [ int ]]) -> list [
heapq . heappop ( min_heap ) int ]:
for p in perms :
min_heap , res = [] , []
for j in range ( len ( p ) + 1) :
top_k_elements = [ num for freq , num in k = len ( lists )
pCopy = p . copy ()
pCopy . insert (j , nums [ i ]) min_heap ]
return top_k_elements # Initialize the heap with the first element
resPerms . append ( pCopy )
from each non - empty list
return resPerms
# Store ( val , list_idx , elem_idx_in_list )
Helpful Resources: k=3
for i in range ( k ) :
Helpful Resources: AlgoMaster if not lists [ i ]: continue
AlgoMaster Hackernoon val = lists [ i ][0]
heapq . heappush ( min_heap , ( val , i , 0) )

# Extract the smallest element , add the next

element
0/1 Knapsack (Dynamic Programming)
while min_heap :
Modified Binary Search Description: This pattern deals with problems where you are given a val , list_idx , elem_idx = heapq . heappop (
set of items, each having a weight and a value, and a constraint (e.g., a min_heap )
Description: This is a tweaked version of the standard binary search
weight limit). The goal is to maximize the total value of items selected res . append ( val )
algorithm. It is adapted to fit specific search conditions, such as finding
while staying within the given constraint. This is a classic optimization
the first/last occurrence of an element, searching in rotated sorted ar- # Check if there ’s a next element in the
problem and forms the basis for many real-world scenarios.
rays, or identifying an element based on a condition rather than an exact list
Usage: Optimize resource allocation under constraints. Solve combin-
match. next_elem_idx = elem_idx + 1
atorial problems, portfolio optimization.
Usage: Use when the problem involves sorted data but includes addi- if next_elem_idx < len ( lists [ list_idx ]) :
tional constraints. next_val = lists [ list_idx ][
def knapsack ( weights , values , capacity ) : next_elem_idx ]
def modified_binary_search ( low , high , n = len ( weights ) heapq . heappush ( min_heap , ( next_val ,
condition_fn ) : dp = [[0] * ( capacity + 1) for _ in range ( n list_idx , next_elem_idx ) )
result = -1 + 1) ] return res
while low <= high :
mid = low + ( high - low ) // 2 for i in range (1 , n + 1) : Helpful Resources:
if condition_fn ( mid ) : for w in range (1 , capacity + 1) :
result = mid # update result Hackernoon
if weights [i -1] <= w :
# Decide whether to go left or right dp [ i ][ w ] = max ( dp [i -1][ w ] , dp [i
high = mid - 1 # e . g . , for finding -1][ w - weights [i -1]] + values
first occurrence [i -1])
else : else :
low = mid + 1 dp [ i ][ w ] = dp [i -1][ w ]
return result return dp [ n ][ capacity ]

Helpful Resources:
Helpful Resources:
AlgoMaster
AlgoMaster
Hackernoon
Hackernoon
 ‡ Piero24 ¯ pietrobonandrea Œ [Link]
Bitwise XOR Union Find

Description: This pattern involves the use of Bitwise XOR to solve Description: Union Find, also known as Disjoint Set Union (DSU), is
various array-based problems. a data structure that partitions a set into disjoint subsets and supports
Usage: It’s used when we need to manipulate and compare bits directly. two key operations efficiently:
1. Union: Merge two subsets into one.
# Example 1: Find the single number in an array 2. Find: Determine the root or representative element of a subset.
where every element appears twice except one Usage: Solve problems related to connectivity in graphs, such as de-
. tecting cycles, finding connected components, and checking if two nodes
def find_single_number ( nums ) : belong to the same set.
result = 0
for num in nums : class UnionFind :
result ˆ= num # XOR operation def __init__ ( self , n ) :
return result self . par = (}
self . rank = {}

for i in range (1 , n + 1) :
self . par [ i ] = i
self . rank [ i ] = 0
Topological Sort (Graph)
def find ( self , n ) :
Description: A linear ordering of vertices in a directed acyclic graph
p = self . par ( n ]
(DAG), such that for every directed edge (u, v), vertex u appears before while p != self . par [ p ]:
v in the ordering. self . par [ p ] = self . par [ self . par [ p ]]
Usage: Solve problems involving scheduling, dependency resolution, and p = self . par ( p ]
precedence constraints. return p
Things to Watch:
- Graph must be a DAG for a valid topological sort. def union ( self , x , y ) :
- Handle nodes with multiple dependencies. p1 , p2 = self . find ( x ) , self . find ( y )
- Use Kahn’s algorithm (BFS) or DFS for implementation. if p1 == p2 :
return False
def find_indegree ( graph ) :
indegree = { node :0 for node in graph } if self . rank [ p1 ] > self . rank [ p2 ]:
for node in graph : self . par [ p2 ]= p1
for neighbor in graph [ node ]: elif self . rank [ p1 ] < self . rank [ p2 ]:
indgree [ neighbor ] += 1 self . par [ p1 ] = p2
return indegree else :
self . par [ p1 ] = p2
self . rank [ p2 ] += 1
def topological_sort ( graph ) : return True
q , res = deque () , []
indegree = find_indegree ( graph )
for node in indegree :
if indegree [ node ] == 0:
q . append ( node )
while len ( q ) > 0:
node = q . popleft ()
res . append ( node )
for neighbor in graph [ node ]:
indegree [ neighbor ] -= 1
if indegree [ neighbor ] == 0:
q . append ( neighbor )
return res if len ( graph ) == len ( res ) else
None

Helpful Resources:
Hackernoon
 ‡ Piero24 ¯ pietrobonandrea Œ [Link]

Other
Binary Math Extra Methods

Binary is a base-2 number system that represents values using two Mathematics is foundational in Computer Science, and all programmers
symbols: 0 and 1. Each position represents a power of 2, with the should possess basic mathematical knowledge. map ( func , iter ) # Applies a function to each
rightmost digit representing 20 , the next 21 , and so on. item in the iterable Example : map ( str , [1 ,
Things to look out for during interviews: 2 , 3]) = > [ ’1 ’ , ’2 ’ , ’3 ’]
Things to look out for during interviews: - Division/Modulo: Always check for division or modulo by zero
- Questions involving binary representations and bitwise operations - Overflow/Underflow: Languages like Java or C++, acknowledge the zip ( list1 , list2 ) # Combines two lists into
- Convert from decimal into binary (and vice versa) potential for overflow/underflow and ask if it needs to be handled tuples , stops at shortest list Example : a =
- Negative/Floating Point Numbers: Don’t overlook these cases (" John " , " Charles ") , b = (" Jenny " , " Monica ")
Technique Code zip (a , b ) = > [( ’ John ’, ’ Jenny ’) , ( ’ Charles
Test if k-th bit is set num & (1 << k) != 0 Formula ’, ’ Monica ’) ]
Set k-th bit num |= (1 >> k) Check if a number is even num % 2 == 0
(N +1)·N any ( list ) # True an element is true
Turn off k-th bit num &= ∼(1 << k) Sum of 1 to N 1 + 2 + ... + N = 2
Toggle the k-th bit num ˆ= (1 << k) Sum of Geometric Progr. 20 + 21 + . . . + 2n = 2n+1 − 1 all ( list ) # True all elements are true
N!
Multiply by 2k num << k Permutations of N (N −K)!
enumerate ( list | tuple ) # Adds index to list
Divide by 2k num >> k Combinations of N N!
K!·(N −K)! elements Example : [ ’ a ’, ’b ’] = > [(0 , ’a ’) ,
Check if a number is a (num & (num - 1)) == 0 or (num Fibonacci Sequence F (n) = F (n − 1) + F (n − 2), F (0) =
(1 , ’b ’) ]
power of 2 & (-num)) == num 0, F (1) = 1
filter ( func , list ) # Filters elements that
Swapping two variables num1 ˆ= num2; num2 ˆ= num1;
return true from func
num1 ˆ= num2
Techniques: Corner cases:
- Multiples of a number - Division by 0 import bisect
Corner cases:
- Comparing floats - Multiplication by 1 bisect . bisect ( list , num ) # Returns index to
- Check for overflow/underflow
- Fast operators - Negative numbers insert num to maintain sort O ( log ( n ) )
- Negative numbers
- Floats
bisect . bisect_left () # Insert at left of
Helpful Resources:
existing
# AND # OR bisect . bisect_right () # Insert at right of
n = 1 & 1 n = 1 | 0 Tech Interview Handbook
existing
# XOR # NOT ( negation ) bisect . insort ( list , num ) # Inserts num and
Intervals
n = 0ˆ1 n = ˜n returns sorted list
n = 1 n = n << 1 n = n >> 1 # Bit shifting Interval questions involve an array of two-element arrays (intervals),
where each represents a start and end value, e.g., [[1, 2], [4, 7]]. These ord ( char ) # Returns ASCII value , ord ( ’ a ’) = 97
Helpful Resources: questions can be tricky due to various overlapping cases. chr ( num ) # Returns char from ASCII , chr (97) = ’a ’
Tech Interview Handbook
Things to look out for during interviews: nonlocal val # Refers to a variable in the
Sorting - Are [1, 2] and [2, 3] considered overlapping? nearest enclosing scope that is not global .
- Does [a, b] strictly follow a < b? Used in nested functions to modify a
Sorting rearranges elements in a sequence (numerical or lexicograph-
variable in the outer function
ical) in ascending or descending order. Avoid O(n²) algorithms in
interviews; use your language’s default sorting function for binary search. Techniques: Corner cases:
- Sort intervals by start point. - No intervals, one or two intervals. Geometry

Things to look out for during interviews: - Check for overlapping intervals. - Non-overlapping intervals. Geometry studies properties of space related to distance, shape, size,
- Know the complexity of your language’s default sort (usually O(n log - Merge intervals. - An interval within another. and relative position. Most Computer Science courses focus on 2D
n)) (Timsort in Python) - Duplicate intervals. geometry, as advanced (e.g., 3D) geometry is less common. In algorithm
- Intervals starting where another interviews, geometry typically plays a minor role
arr . sort () # Ascending order ends: [[1, 2], [2, 3]].
arr . sort ( reverse = True ) # Descending order
arr . sort ( key = lambda x : x [0]) # Based on the key Techniques: Corner cases:
function . def is_overlap (a , b ) : - Distance between two points - Zero values. This always gets
return a [0] < b [1] and b [0] < a [1] - Overlapping circles people
Techniques: Corner cases: - Overlapping rectangles
def merge_overlapping_intervals (a , b ) :
- Sorted inputs - Empty sequence
return [ min ( a [0] , b [0]) , max ( a [1] , b [1]) ]
- Sorting an input that has limited - Sequence with 1-2 element Helpful Resources:
range - Sequence containing duplicates Tech Interview Handbook
Helpful Resources:
Helpful Resources: Tech Interview Handbook
Tech Interview Handbook
Zero To Mastery
 ‡ Piero24 ¯ pietrobonandrea Œ [Link]

Other Relevant Sources

Usefull Links - General Usefull Books/Courses Leetcode Constraints

SuperHero Valley Cracking The Coding Interview: Condition (n) Complexity and
Sunil Notebook US - UK - DE - IT - FR - ES - JP Techniques
Tech Interview Handbook Elements Of Programming Interviews: n < 20 2n , n!
Try Exponent US - UK - DE - IT - FR - ES - JP e.g. brute force,
LeetCode Competitive Programmer’s HandBook: - backtracking
interviewBit DataStructures and Algoritms in Python: -
n < 3000 n2
1point3acres Grokking Algorithms:
e.g. dynamic
CodeForces US - UK - DE - IT - FR - ES - JP
programming
HelloInterview Grokking Data Structures:
3000 < n < 106 O(n), O(n log n)
US - UK - DE - IT - FR - ES - JP
e.g. 2 pointers, greedy,
The Software Engineer’s Guidebook:
heap, sorting
Usefull Links - DSA US - UK - DE - IT - FR - ES - JP
n > 106 O(log n), O(1)
Interview Cake Building a Career in Software:
e.g. binary search, math
Zero To Mastery US - UK - DE - IT - FR - ES - JP

Sufferings and Problem Solving Effective Python:

Applications
Awesome Leetcode Resources US - UK - DE - IT - FR - ES - JP

Python Cheat Sheet System Design Interview: Sites to find companies to apply to: LinkedIn, Glassdoor, [Link]
Algo Monster US - UK - DE - IT - FR - ES - JP

Algo Master System Design Interview - Vol.2:

Tech Interview Cheat Sheet US - UK - DE - IT - FR - ES - JP

Algorithm Wiki Grokking the coding Interviews:

LeetCode ALL

CodeInMotion
VisuAlgo Steps for a good Technical Interview

1. Read the problem carefully.

Relevant Exercise 2. Paraphrase the problem back to confirm understanding.

Top Interview 150

3. Ask clarifying questions, even it’s all clear (e.g., input con-
LeetCode 75
straints, edge cases).
Amazon Spring 23 High Frequency
Premium Algo 100 4. Discuss edge cases and constraints.
Top 100 Liked
Google Spring 23 High Frequency 5. Start with a straightforward solution, NOT the optimal one.
Apple Spring 23 High Frequency
Cheatsheet Leetcode A4 6. Outline your plan, algorithm, and data structures.
AlgoMap
NeetCode 7. Begin coding clearly when given the go-ahead.

NeetCode - 150
8. Explain your thought process while coding.

9. Prioritize precision and clarity over speed.

10. Test with example and edge cases.

11. Discuss optimizations if possible.

12. Optimize if appropriate.

13. Be open to feedback and improvements.

14. Keep a positive attitude, even if you make mistakes—show that

you can handle setbacks gracefully.