Data Structures and Algorithms Takeaways

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.

Data Structures

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.

Algorithms

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.