Python

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.

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.

The Principle of Built-in Hash Table The key value can be any hashable type. A value that belongs to a hashable type has a hash code, and this code is used to get the bucket index. Each bucket contains an array to store all the values in the same bucket initially If there are too many values in the bucket, these values will be stored in the form of height-balanced BST so that look-up can be more efficient.

Intro Random notes of relating OOP Terminology Parameter A parameter is a named variable passed into a function. Parameter variables are used to import arguments into functions. The difference between parameters and arguments Function parameters are the names listed in the function’s definition. Function arguments are the real values passed to the function. Parameters are initialized to the values of the arguments supplied. MDN Parameter Override Overriding a method means

Overview A tree is a frequently-used data structure to simulate a hierarchical tree structure. Each node of the tree will have a root value and a list of References to other nodes that are called child nodes. From graph view, a tree can also be defined as a directed acyclic graph that has N nodes and N-1 edges. A Binary Tree is one of the most typical tree structures. As the name suggests, a binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child.

Introduction The linked list is a linear data structure. There are two types of linked lists, the singly linked list and the doubly linked list. Singly Linked list The linked list elements are not stored at a contiguous location; the elements are linked using pointers. Advantages over arrays Dynamic size Ease of insertion/deletion (Need to move all elements after targeted element in array) Implementation class Node(object): def __init__(self, val): self.

マルチプロセスについて 複数のプロセスが、ある共有メモリ領域を競合するアクセスをしている時、競合アクセスしているプログラム部分をクリティカルセ