In 2018, I trained myself on hundreds of algorithmic coding problems. It helped me become a better programmer.
In the following paragraphs, I would like to share how I think in solving coding problems and hope it will help you as well.
To be able to understand this article, it is required to have the basic knowledge of data structures and algorithms. There are many online resources introduction data structures and algorithms and it isn’t the main point of this article.
Arrays, Strings, Hash Table and Hash Map
An array is a sequence of elements, such as characters, strings, integers, floats, etc. A string can be considered as a particular array of characters. Here are some characteristics of an array:
- An element in an array can be accessed by its index.
- Looking for an element in an array requires \( O(n) \) runtime.
A common way of optimizing the searching time complexity is to store elements in a hash set / a hash table instead of an array.
Trees and Graphs
Trees are a subset of graphs, a tree is an acyclic connected graph.
Breadth-First-Search (BFS) is often used for finding shortest paths in a graph, or in the case where it is not necessary to traverse all nodes.
Both BFS and Depth-First-Search (DFS) can be implemented either in an iterative way or in a recursive way.
In a binary tree, it is possible to traverse all nodes with \( O(1) \) memory, which means without using stacks or queues, iterative but not recursive. One of the solutions to this problem is tree threading, presented by J. H. Morris in 1979.
class TreeNode: def __init__(self, val): self.val = val self.left, self.right = None, None class Morris: def morris_inorder(self, root): p = root temp = None while p: if p.left is None: print(p.val) p = p.right else: temp = p.left while temp.right is not None and temp.right != p: temp = temp.right if temp.right is None: temp.right = p p = p.left else: print(p.val) temp.right = None p = p.right return res
Stacks and Queues
Stacks and queues are usually used together with other data structures / algorithms. For example: to find the shortest path in a graph, a solution is to use a queue to store the nodes to be visited level by level, deque a node after having visited and enqueue the adjacent unvisited nodes.
Sorting and Searching
The most commonly used sorting algorithms are:
- Merge Sort, runtime \( O(n log(n)) \) in average and worst case, memory depends.
- Quick Sort, runtime \( O(n log(n)) \) in average and \( O(n^2) \) in worst case, memory \( O(log(n)) \).
class MergeSort: def sortIntegers(self, A): temp = [0 for _ in range(len(A))] self.merge_sort(A, 0, len(A) - 1, temp) def merge_sort(self, A, start, end, temp): if start >= end: return mid = start + (end - start) // 2 self.merge_sort(A, start, mid, temp) self.merge_sort(A, mid + 1, end, temp) self.merge(A, start, mid, end, temp) def merge(self, A, start, mid, end, temp): left, right = start, mid + 1 idx = start while left <= mid and right <= end: if A[right] > A[left]: temp[idx] = A[right] right += 1 else: temp[idx] = A[left] left += 1 idx += 1 while left <= mid: temp[idx] = A[left] idx += 1 left += 1 while right <= end: temp[idx] = A[right] idx += 1 right += 1 for i in range(start, end + 1): A[i] = temp[i]
class QuickSort: def sortIntegers(self, A): self.quick_sort(A, 0, len(A) - 1) def quick_sort(self, A, start, end): left, right = start, end pivot = A[left + (right - left) // 2] while left <= right: while left <= right and A[left] < pivot: left += 1 while left <= right and A[right] > pivot: right -= 1 if left <= right: A[left], A[right] = A[right], A[left] left += 1 right -= 1 self.quick_sort(A, start, right) self.quick_sort(A, left, end)
When we think of searching algorithms, we generally think of binary search. If an array is sorted, then it’s possible to accelerate searching an element from \( O(n) \) to \( O(log n) \) runtime.
Recursion and Dynamic Programming
To find all the solutions, a common way is to use recursive Depth-First-Search (DFS), for example, finding all the permutations/combinations which sum to K from an array of integers.
Recursion is also widely used in tree data structure.
There are two types of dynamic programming, Top-Down Dynamic Programming (or Memoization) and Bottom-Up Dynamic Programming.
DP can solve the following problems:
- Shortest/longest paths
- Total number of possibilities
- The possibility having most/least elements among all possibilities
DP is also a way of reducing repeat computation.