DSA

Merge Sort In sorting n objects, merge sort has an average and worst-case performance of O(n log n). Merge sort is a stable sort in the most implementations. The most common implementation does not sort in place, meaning it requires extra space. Implementation in Python from typing import List # Python merge sort implementation # Time complexity: O(NlogN), space complexity: O(N) def merge_sort(nums: List[int]): # Base case if len(nums) <= 1: return nums mid = len(nums) // 2 left, right = merge_sort(nums[:mid]), merge_sort(nums[mid:]) return merge(left, right) def merge(left: List[int], right: List[int]): i, j = 0, 0 res = [] # Compare the elements in the left and right list and append the smaller one to the result list while i < len(left) and j < len(right): if left[i] <= right[j]: res.

Quick Sort In sorting n objects, quick sort has an average performance of O(n log n) and a worst performance of O(n^2). Most implementations of quick sort are not stable, but sort in place, meaning it does not require extra space. Implementation in Python # O(NLogN), space complexity O(n) in this case def quick_sort(nums): if len(nums) <= 1: return nums pivot = nums[len(nums) // 2] left = [n for n in nums if n < pivot] mid = [n for n in nums if n == pivot] right = [n for n in nums if n > pivot] return quick_sort(left) + mid + quick_sort(right) # Test cases if __name__ == "__main__": # Test case 1: Sorting an empty list arr1 = [] result1 = quick_sort(arr1) assert result1 == [], "Test case 1 failed" # Test case 2: Sorting a list with one element arr2 = [5] result2 = quick_sort(arr2) assert result2 == [5], "Test case 2 failed" # Test case 3: Sorting a list with multiple elements arr3 = [3, 6, 1, 8, 2, 4, 5, 7] result3 = quick_sort(arr3) assert result3 == [1, 2, 3, 4, 5, 6, 7, 8], "Test case 3 failed" # Test case 4: Sorting a list with duplicate elements arr4 = [3, 6, 1, 8, 2, 4, 5, 7, 1, 2] result4 = quick_sort(arr4) assert result4 == [1, 1, 2, 2, 3, 4, 5, 6, 7, 8], "Test case 4 failed" # Test case 5: Sorting a list with duplicate pivot elements arr5 = [3, 6, 1, 5, 4, 4, 5, 7, 1, 2] result5= quick_sort(arr5) assert result5 == [1, 1, 2, 3, 4, 4, 5, 5, 6, 7], "Test case 5 failed {0}".

Union-Find Union-Find, aka Disjoint Set, is a rooted tree data structure that can efficiently classifies elements into categories. By utilizing this data structure, it becomes possible to rapidly determine whether two elements belong to the same group, as well as to swiftly merge two groups. Implementation in Python class UnionFind: def __init__(self, n): # Initialize all parents as -1, which means all nodes are root nodes self.parent = [-1] * n # Rank holds a weight to determine which tree has more weight # The tree with a smaller rank should be placed under the tree with a greater rank to keep the height of the merged tree smaller self.

What is Dijkstra’s Algorithm Dijkstra’s Algorithm is the algorithm to find the shortest path between any two vertices in a graph. Dijkstra’s Algorithm will find the shortest path from a given starting vertex to every other vertices in a graph. Steps Prepare a table to have the shortest distance from a starting vertex and previous vertex. Initialize two list of visited and unvisited nodes Let the distance of a start vertex from the start vertex 0.

What is a Graph? A graph G is an ordered pair of a set V of vertices and a set of E of edges. G can be defines as follows $$G=\left(V,E\right)$$ ordered pair $$(a, b) \neq \left(b,a\right) \text{where} \ a \neq b$$ Graph terminology There are two type of graph, the one is directed graph and the other is undirected graph. Directed graphs contain ordered pairs of vertices while undirected

BFS Template A template in a python-ish pseudo-code for bfs from collections import deque def bfs(root, target): step = 0 # Enqueue root node in queue q = deque([root]) # Set to store visited nodes visited = set(q) while q: size = len(q) # Iterated the nodes which are already in the queue for _ in range(size): # Pop the first node in the queue curr = q.popleft if curr

Queue FIFO package queue import "sync" type node struct { data interface{} next *node } type Queue struct { head *node tail *node count int lock *sync.Mutex } func NewQueue() *Queue { return &Queue{lock: &sync.Mutex{}} } func (q *Queue) Len() int { q.lock.Lock() defer q.lock.Unlock() return q.count } func (q *Queue) Push(data interface{}) { q.lock.Lock() defer q.lock.Unlock() ele := &node{data: data} if q.head == nil { q.head = ele q.tail = ele } else { q.

Heap Heap is a special Tree-based data structure in which tree is a complete binary tree. Heaps are basically are binary trees with more properties and specifications and there are mainly two types of heaps. Rules A heap must be a complete binary tree. All of the levels of the tree must be completely filled except maybe the last one. The last level has all keys as left as possible Types of heap Min Heap

Tries It is commonly used to represent a dictionary for looking up words in a vocabulary Implementation https://leetcode.com/problems/implement-trie-prefix-tree/ Trie() Initializes the trie object. void insert(String word) Inserts the string word into the trie. boolean search(String word) Returns true if the string word is in the trie (i.e., was inserted before), and false otherwise. boolean startsWith(String prefix) Returns true if there is a previously inserted string word that has the prefix, and false otherwise.

Tree Properties Every tree has a special node called the root node. The root node can be used to traverse every node of the tree. It is called root because the tree originated from root only. If a tree has N nodes(vertices), the number of edges is always one less than the number of nodes (i.e., N-1). If it has more than that, it’s called a graph not a tree.