Data Structures and Algorithms Cheat Sheet
What is this?
This repository serves as a continuously updated reference for fundamental data structures, providing concise implementations for each. While it is not meant to be exhaustive, considerable effort has been put into ensuring the presented methods are as comprehensive and neat as possible. Given that these structures often form the cornerstone of many coding interviews, having such a reference at your disposal can significantly aid your preparations. Please note that all the code contained herein is written in Python 3.
Recursion and Iteration
def factorial(number):
'''
This function calculates the factorial of a number using recursion.
Args:
number (int): The number of which to find the factorial.
Returns:
int: The factorial of the number. If the number is negative, it returns None.
Time complexity: O(n), where n is the input number.
Space complexity: O(n), due to the stack space required for the recursive calls.
'''
if number < 0:
print('Invalid entry! Cannot find factorial of a negative number')
return None
if number == 0 or number == 1:
return 1
return number * factorial(number - 1)
def factorial_without_recursion(number):
'''
This function calculates the factorial of a number using iteration.
Args:
number (int): The number of which to find the factorial.
Returns:
int: The factorial of the number. If the number is negative, it returns None.
Time complexity: O(n), where n is the input number.
Space complexity: O(1), as it uses a constant amount of space.
'''
if number < 0:
print('Invalid entry! Cannot find factorial of a negative number')
return None
fact = 1
for i in range(1, number + 1):
fact *= i
return fact
Tries
class TrieNode:
"""
A node in the trie structure.
Attributes:
char (str): The character stored in this node.
is_end (bool): Whether this can be the end of a word.
counter (int): A counter indicating how many times a word is inserted.
children (dict): A dictionary of child nodes. Keys are characters, values are nodes.
"""
def __init__(self, char):
self.char = char
self.is_end = False
self.counter = 0
self.children = {}
class Trie:
"""
The trie object.
Attributes:
root (TrieNode): The root node of the trie.
"""
def __init__(self):
self.root = TrieNode("")
def insert(self, word):
"""
Insert a word into the trie.
Args:
word (str): The word to be inserted.
Time complexity: O(m), where m is the length of the word.
Space complexity: O(m), in the worst case newly inserted key doesn't share a prefix with the keys already inserted in the trie.
"""
node = self.root
for char in word:
if char in node.children:
node = node.children[char]
else:
new_node = TrieNode(char)
node.children[char] = new_node
node = new_node
node.is_end = True
node.counter += 1
def dfs(self, node, prefix):
"""
Depth-first traversal of the trie.
Args:
node (TrieNode): The node to start with.
prefix (str): The current prefix, for tracing a word while traversing the trie.
Time complexity: O(n), where n is the total number of nodes in the trie.
Space complexity: O(h), where h is the height of the trie.
"""
if node.is_end:
self.output.append((prefix + node.char, node.counter))
for child in node.children.values():
self.dfs(child, prefix + node.char)
def query(self, prefix):
"""
Given an input (a prefix), retrieve all words stored in the trie with that prefix,
sort the words by the number of times they have been inserted.
Args:
prefix (str): The prefix to be queried.
Returns:
list: A list of tuples where each tuple contains a word and its frequency.
Time complexity: O(m + n), where m is the length of the prefix and n is the total number of nodes in the trie.
Space complexity: O(h), where h is the height of the trie.
"""
self.output = []
node = self.root
for char in prefix:
if char in node.children:
node = node.children[char]
else:
return []
self.dfs(node, prefix[:-1])
return sorted(self.output, key=lambda x: x[1], reverse=True)
Sorting
def mergeSort(myList):
"""
Sorts a list in ascending order using the merge sort algorithm.
Time complexity: O(n log n)
Space complexity: O(n)
"""
# If the list is a single element list or empty, it's already sorted.
if len(myList) <= 1:
return myList
# Split the list into two halves
mid = len(myList) // 2
left_half = myList[:mid]
right_half = myList[mid:]
# Recursively call mergeSort on each half of the list
# Then merge the sorted halves
return merge(mergeSort(left_half), mergeSort(right_half))
def merge(left, right):
"""
Helper function for mergeSort: merges two sorted lists into one.
"""
merged = []
left_index = 0
right_index = 0
# Compare elements from the two halves and add smaller one to the result
while left_index < len(left) and right_index < len(right):
if left[left_index] <= right[right_index]:
merged.append(left[left_index])
left_index += 1
else:
merged.append(right[right_index])
right_index += 1
# If there are leftover elements in the left half, add them to the result
while left_index < len(left):
merged.append(left[left_index])
left_index += 1
# If there are leftover elements in the right half, add them to the result
while right_index < len(right):
merged.append(right[right_index])
right_index += 1
# Return the merged list
return merged
def QuickSort(arr):
"""
Sorts a list in ascending order using the quick sort algorithm.
Best case time complexity: O(n log n)
Worst case time complexity: O(n^2)
Best case space complexity: O(n log n)
Worst case space complexity: O(n^2)
"""
# If the list is a single element list or empty, it's already sorted.
if len(arr) < 2:
return arr
# Take the first element as pivot
pivot = arr[0]
# Create two new lists, one with elements less than pivot and one with elements greater than pivot
less = [x for x in arr[1:] if x <= pivot] # Elements less than pivot
greater = [x for x in arr[1:] if x > pivot] # Elements greater than pivot
# Recursively quick sort the 'less' and 'greater' lists, then combine them with the pivot to get the final sorted list
return QuickSort(less) + [pivot] + QuickSort(greater)
Linked Lists
class ListNode:
"""
A node in a singly-linked list.
"""
def __init__(self, data=None, next=None):
self.data = data # Assign data
self.next = next # Initialize next as null
def __repr__(self):
return repr(self.data) # Returns a string containing a printable representation of an object
class SinglyLinkedList:
def __init__(self):
"""
Create a new singly-linked list.
Takes O(1) time.
"""
self.head = None # Initialization of Singly Linked List
def __repr__(self):
"""
Return a string representation of the list.
Takes O(n) time.
"""
nodes = [] # Define an empty list
curr = self.head
while curr: # Traverse through the list and append each node's data in the list
nodes.append(repr(curr))
curr = curr.next
return '[' + ', '.join(nodes) + ']'
def prepend(self, data):
"""
Insert a new element at the beginning of the list.
Takes O(1) time.
"""
self.head = ListNode(data=data, next=self.head) # New node points to the old head
def append(self, data):
"""
Insert a new element at the end of the list.
Takes O(n) time.
"""
if not self.head: # If the list is empty, new node is the head
self.head = ListNode(data=data)
return
curr = self.head
while curr.next: # Traverse to the end of the list
curr = curr.next
curr.next = ListNode(data=data) # Add the new node
def find(self, key):
"""
Search for the first element with `data` matching
`key`. Return the element or `None` if not found.
Takes O(n) time.
"""
curr = self.head
while curr and curr.data != key: # Traverse the list till you find the key or reach the end of the list
curr = curr.next
return curr # Will be None if not found
def remove(self, key):
"""
Remove the first occurrence of `key` in the list.
Takes O(n) time.
"""
curr = self.head
prev = None
while curr and curr.data != key: # Find the key while keeping track of the previous node
prev = curr
curr = curr.next
# Unlink it from the list
if prev is None: # If the key is found at the head of the list
self.head = curr.next
elif curr: # If key is found after head
prev.next = curr.next # Skip the node
curr.next = None # Isolate the node
def reverse(self):
"""
Reverse the list in-place.
Takes O(n) time.
"""
curr = self.head
prev_node = None
next_node = None
while curr: # Traverse the list
next_node = curr.next # Keep track of the next node
curr.next = prev_node # Have the current node point to its previous node
prev_node = curr # Move to the next node
curr = next_node
self.head = prev_node # Reset the head to the last node in the original list
Hash Tables and Sets
def create_set():
"""
A function that creates a set.
Time complexity: O(1) for add operation, O(n) for initialization
Space complexity: O(n) where n is the number of elements in the set
"""
return {"apple", "banana", "cherry"}
def create_dict():
"""
A function that creates a dictionary.
Time complexity: O(1) for get and set operations, O(n) for initialization
Space complexity: O(n) where n is the number of elements in the dictionary
"""
return {'Dave' : '001' , 'Ava': '002' , 'Joe': '003'}
def access_dict_entry(my_dict, key):
"""
A function that accesses an entry using a key in a dictionary.
Time complexity: O(1)
Space complexity: O(1)
"""
return my_dict[key]
def print_dict_keys(my_dict):
"""
A function that prints all keys in a dictionary.
Time complexity: O(n) where n is the number of keys in the dictionary
Space complexity: O(1)
"""
print("All keys")
for x in my_dict:
print(x)
def print_dict_values(my_dict):
"""
A function that prints all values in a dictionary.
Time complexity: O(n) where n is the number of values in the dictionary
Space complexity: O(1)
"""
print("All values")
for x in my_dict.values():
print(x)
def print_dict_items(my_dict):
"""
A function that prints all key-value pairs in a dictionary.
Time complexity: O(n) where n is the number of key-value pairs in the dictionary
Space complexity: O(1)
"""
print("All keys and values")
for x, y in my_dict.items():
print(x, ":", y)
my_set = create_set()
my_dict = create_dict()
print(access_dict_entry(my_dict, 'Dave')) # Prints the value associated with 'Dave', which is '001'
print_dict_keys(my_dict)
print_dict_values(my_dict)
print_dict_items(my_dict)
Stacks and Queues
def stack_operations():
"""
A function that demonstrates stack operations.
Time complexity: O(1) for both push and pop operations
Space complexity: O(n) where n is the number of elements in the stack
"""
# Stack
letters = []
# Let's push some letters into our stack
letters.append('c')
letters.append('a')
letters.append('t')
letters.append('g')
# Now let's pop letters, we should get 'g'
last_item = letters.pop() # Takes O(1) time because its the last element
print(last_item)
# If we pop again we'll get 't'
last_item = letters.pop() # Takes O(1) time because its the last element
print(last_item)
# 'c' and 'a' remain
print(letters) # ['c', 'a']
def queue_operations():
"""
A function that demonstrates queue operations.
Time complexity: O(1) for enqueue operation, O(n) for dequeue operation as all elements have to be shifted
Space complexity: O(n) where n is the number of elements in the queue
"""
# Queue
fruits = []
# Let's enqueue some fruits into our list
fruits.append('banana')
fruits.append('grapes')
fruits.append('mango')
fruits.append('orange')
# Now let's dequeue our fruits, we should get 'banana'
first_item = fruits.pop(0) # takes O(N) time because all elements have to be shifted
print(first_item)
# If we dequeue again we'll get 'grapes'
first_item = fruits.pop(0) # takes O(N) time because all elements have to be shifted
print(first_item)
# 'mango' and 'orange' remain
print(fruits) # ['mango', 'orange']
# Call the functions
stack_operations()
queue_operations()
Trees and Binary Search Trees
class Tree:
"""
A node for Binary Search Tree(BST) has data, pointer to left child and pointer to right child.
Time complexity of BST operations are:
Search: O(h), where h is height of the tree.
Insert: O(h), where h is height of the tree.
Delete: O(h), where h is height of the tree.
"""
def __init__(self, data):
self.left = None
self.right = None
self.data = data
def insert(self, data):
"""
Inserts a new node with given data in the BST.
"""
if self.data: # check if there is data at current node
if data < self.data: # if data is less than current node's data
if self.left is None: # and left child is empty
self.left = Tree(data) # insert data in left child
else:
self.left.insert(data) # else, recur for left subtree
elif data > self.data: # if data is more than current node's data
if self.right is None: # and right child is empty
self.right = Tree(data) # insert data in right child
else:
self.right.insert(data) # else, recur for right subtree
else: # if tree is empty
self.data = data # position data at root
def getTree(self):
"""
Print nodes at Inorder traversal: left child, root, right child.
"""
if self.left: # traverse left subtree first
self.left.getTree()
print(self.data), # print root data
if self.right: # then traverse right subtree
self.right.getTree()
def printInorder(self):
"""
A function to do inorder tree traversal
"""
if self:
self.left.printInorder() # First recur on left child
print(self.data), # then print the data of node
self.right.printInorder() # now recur on right child
def printPostorder(self):
"""
A function to do postorder tree traversal
"""
if self:
self.left.printPostorder() # First recur on left child
self.right.printPostorder() # then recur on right child
print(self.data), # now print the data of node
def printPreorder(self):
"""
A function to do preorder tree traversal
"""
if self:
print(self.data), # First print the data of node
self.left.printPreorder() # Then recur on left child
self.right.printPreorder() # Finally recur on right child
Graphs and BFS/DFS
def dfs(visited, graph, node):
"""
Depth-First Search(DFS) is an algorithm for traversing or searching tree or graph data structures.
Time Complexity: O(V+E), where V is number of vertices and E is number of edges.
Space Complexity: O(V).
"""
if node not in visited: # if node is not visited
print(node)
visited.append(node) # mark it as visited
for neighbor in graph[node]: # then for each neighbor of current node
dfs(visited, graph, neighbor) # apply dfs
def bfs(visited, graph, node):
"""
Breadth-First Search(BFS) is an algorithm for traversing or searching tree or graph data structures.
Time Complexity: O(V+E), where V is number of vertices and E is number of edges.
Space Complexity: O(V).
"""
visited.append(node) # mark the current node as visited
queue.append(node) # add it to the queue
while queue: # while there are elements in the queue
s = queue.pop(0) # dequeue a vertex/node
for neighbor in graph[s]: # for each neighbor of the current node
if neighbor not in visited: # if it is not visited
visited.append(neighbor) # mark it as visited
queue.append(neighbor) # and add it to the queue
Heaps
import heapq
def create_heap(data):
"""
Function to convert a list into a heap.
The resulting heap has the property that each parent node is smaller than or equal to its child nodes.
Time Complexity: O(n).
Space complexity: O(1)
"""
heapq.heapify(data) # Transform list data into a heap
return data
def add_element(heap, ele):
"""
Function to add an element to the heap.
The heap structure is maintained after addition.
Time Complexity: O(log n).
Space complexity: O(1).
"""
heapq.heappush(heap, ele) # Pushes a value item onto the heap
return heap
def remove_element(heap):
"""
Function to remove and return the smallest element from the heap.
The heap structure is maintained after removal.
Time Complexity: O(log n).
Space complexity: O(1).
"""
smallest = heapq.heappop(heap) # Pops and returns the smallest element from heap
return heap, smallest
def replace_element(heap, ele):
"""
Function to remove the smallest element from the heap and then add a new element.
The heap structure is maintained.
Time Complexity: O(log n).
Space complexity: O(1).
"""
heapq.heapreplace(heap, ele) # Pops and returns the smallest element, and add the new item
return heap
# Testing our functions
H = [21,1,45,78,3,5]
H = create_heap(H)
print(f'Heap: {H}')
H = add_element(H, 8)
print(f'Heap after adding 8: {H}')
H, smallest = remove_element(H)
print(f'Smallest element: {smallest}')
print(f'Heap after removing smallest element: {H}')
H = replace_element(H, 6)
print(f'Heap after replacing smallest element with 6: {H}')