cwHsueh

Consistent Hashing

This is a note of this paragraph. Problem Statement Given a set of servers, we need to distribute the load among them. The load can be anything like requests, data, etc. The goal is to minimize the number of reassignments when a server is added or removed. Also notice that the data on each server might not be the same. First intuition One way to distribute the load is to use a hash function to map the load to a server. ...

Introduction to Makefile

Why make? Make is a build automation tool that automatically builds executable programs and libraries from source code by reading files called Makefiles, which specify how to derive the target program. It avoids the need to manually type everything out every time you want to compile your code. Syntax Make has the following syntax: target: dependencies command For example, if you have a file called hello.c and you want to compile it into an executable called hello, you can write a Makefile like this: ...

Why is the heap so slow?

This is a note from WHY IS THE HEAP SO SLOW? System Calls System calls are the apis provided by the operating system and we use them to request some service which only the operating system can do. System calls can be expensive in terms of performance. When a program is executed, it receives a new name, a process. A process has its own state stored in CPU through register. ...

C++ Primer Plus notes

Chapter 4 Union union is a data structure that can store different types of data, but it can only store one type of data at a time. The size of union is the size of its largest data. union one4all { int int_val; long long_val; double double_val; }; one4all pail; pail.int_val = 15; // store an int cout << pail.int_val; pail.double_val = 1.38; // store a double, int value is lost cout << pail.double_val; Enumerations enum spectrum {red, orange, yellow, green, blue, violet, indigo, ultraviolet}; spectrum band; // band a variable of type spectrum band = blue; // valid, blue is an enumerator band = 2000; // invalid, 2000 not an enumerator Enumarators are integer type, and can be converted to int, but not reversely. ...

C++ notes

這篇文章主要是給自己看的，因此寫的方法是以自己看懂為主，一些自己已經會的東西就不會寫得太詳細。 Source Code to Machine Code source code to machine code 分成四個步驟： preprocessing 處理 #，例如 #include 把 header file 複製到當前的檔案裡面 compiling turn code into assembly assembling turn assembly into machine code, 0s and 1s linking 把不同檔案的 machine code 接在一起雖然說有四個步驟，但是其實會把這四個步驟叫做 compiling。 Command Line Arguments int main(int argc, char *argv[]){ } int main(int argc, char **argv){ } 如果有一個 binary file 叫做 greet，並且在 terminal 輸入 ./greet Hello，此時 argc = 2, argv[0] = "./greet", argv[1] = "Hello"。 echo $? 會回傳來自 main funciton 的 int，也就是 error code。 ...

Majority Voting Algorithm 多數投票算法

問題描述給定一個大小為 n 的整數陣列，如何找到出現頻率大於（必須嚴格大於）n/2 的元素？例如：arr = [1, 1, 2]，那麼 1 就是出現頻率大於 n/2 的元素。如果 arr = [1, 1, 3, 4]，那麼不存在這樣的元素。 Boyer–Moore majority vote algorithm 一個很直覺的方法就是用一個 hash map 計算所有數字出現的頻率，然後找出出現最多次的元素。需要 O(n) 的空間複雜度以及 O(n) 的時間複雜度。但是用 Boyer-Moore algorithm，只要 O(1) 的空間複雜度即可。來看看這個演算法是如何辦到的。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 int majorityElement(vector<int>& nums) { int candidate = 0; int freq = 0; for (int i = 0; i < nums.size(); i++){ if (candidate == nums[i]){ freq++; } else if (freq == 0){ candidate = nums[i]; freq = 1; } else { freq--; } } return candidate; } candidate 是答案的候選人，而 freq 則是 candidate 出現的頻率。 ...

Tree traversal

今天來複習一下常見遍歷樹的方式。 Recursive way Inorder traversal 先拜訪 left subtree，再依序拜訪 root node 跟 right subtree。 void Inorder_traversal(TreeNode *node){ if (node == NULL){ return; } Inorder_traversal(node->left); cout << node->val << " "; Inorder_traversal(node->rihgt); return; } Preorder traversal 先拜訪 root node，再依序拜訪 left subtree 跟 right subtree。 void Preorder_traversal(TreeNode *node){ if (node == NULL){ return; } cout << node->val << " "; Preorder_traversal(node->left); Preorder_traversal(node->rihgt); return; } Postorder traversal 先依序拜訪 left subtree 跟 right subtree，再拜訪 root node。 void Postorder_traversal(TreeNode *node){ if (node == NULL){ return; } Postorder_traversal(node->left); Postorder_traversal(node->rihgt); cout << node->val << " "; return; } 可以看到用 recursive 寫的話，三種方式的 code 基本上長一樣，而且複雜度也都一樣，只是差在遍歷 root node 的時間不一樣。 time complexity: $O(n)$ space complextiy: $O(h)$, where $h = $ tree height ...

Gosper's Hack

這是在寫 1799. Maximize Score After N Operations 時遇到的問題。簡單來說，我想要解決的問題是「找到 n 個物品中取 k 個的所有組合」。而 Gosper’s Hack 可以有效率地找到 n 個 bit 中 k 個 bit 爲 1 的所有組合，剛剛好對應了我的問題。 Gosper’s Hack 的原理就是，從滿足條件（n 個 bit 中 k 個 bit 爲 1）的數字中，從最小的數字，一路找到最大的。如果想找「5 個 bit 中 2 個 bit 爲 1」的組合，那麼 Gosper’s Hack 會依序找到 00011 00101 00110 01001 01010 01100 10001 10010 10100 11000 首先，滿足條件的數字中，最小的數字很容易就找到，就是把所有的 1 塞到最右邊去，也就是 int state = (1 << k) - 1; 接下來比較難的問題是，要如何有效率地找到下一個數字。找到下一個數字，分成兩個步驟把最右邊的 $01$ 變成 $10$ 把剛剛 $10$ 右邊的 $1$ 全部推到最右邊去看一個範例：有數字 $10011110_2$，他的下一個數字應該是多少？根據上面的步驟，$10011100_2$ 的下一個數字就是 $10100111_2$ ...

Digital Root / Repeated digital sum

今天寫到 leetcode 258. Add Digits (https://leetcode.com/problems/add-digits/)，發現了這個有趣的題目。題目本身不難，但是 follow up 要求寫出 O(1) 時間複雜度的解法，因此卡了一下。看到 wiki (https://en.wikipedia.org/wiki/Digital_root#Congruence_formula) 才發現這樣的問題被叫做 Digital Root，而且還可以在不同進位下討論，挺有趣的。先看一個簡單的範例：有一個 5 進位的數字 14324 （這是用 5 進位表示），把這個數字的每一位相加然後用 5 進位表示，直到剩下一位，這個數字會是多少？ 1 + 4 + 3 + 2 + 4 = 14（10 進位） = 24（5 進位） 2 + 4 = 6（10 進位） = 11（5 進位） 1 + 1 = 2（5 進位）這個數字會是 2。但是計算很麻煩，因爲要在 5 進位上面做運算，是人類很不收悉的進位。簡單的方法就是把所有的計算都換到 10 進位上面。有小標的 5 就是指這個數字是 5 進位的。 ...

C++ 中遍歷 set 的同時刪除元素

今天在打 code 的時候遇到一個問題：我想要遍歷 set 的同時，把符合條件的元素刪掉。假設我想要刪除 set 中所有小於 10 的元素。一開始我寫出這樣的東西， set<int> new_set = {1, 3, 4, 6, 7, 10, 15}; for (auto it = new_set.begin(); it != new_set.end() && it* < 10; it++){ new_set.erase(it); } 跑了之後發現雖然沒有報錯，但是 set 似乎沒有變成我預想的樣子。簡單來說當 erase(it) 跑完之後， it 就不見了。it++ 的時候會有無法預期的錯誤。上網找了一下1，發現了有人跟我一樣遇到一樣的問題。一開始看到了這個2解決的辦法： set<int> new_set = {1, 3, 4, 6, 7, 10, 15}; // C++03 for (auto it = new_set.begin(); it != new_set.end() && it* < 10;){ new_set.erase(it++); } 我就很納悶，new_set.erase(it++) 跟 new_set.erase(it), it++ 這樣不是一樣的效果嗎？繼續查下去發現 3 這段話， i is incremented before calling erase, and the previous value is passed to the function. A function’s arguments have to be fully evaluated before the function is called. 對於一個 function f(int i)， f(i++) 做的其實是先 i = i + 1，但是進到 f 的時候會傳入原本的 i，也就是 +1 之前的 i。這就是上面 new_set.erase(it++) 會對的原因。 ...