tags: GnuPG,GnuPG Agent

tags: Data Structures,Algorithm

tags: Algorithm,Tree,Graph source: https://en.wikipedia.org/wiki/Minimum%5Fspanning%5Ftree

tags: High Performance source: https://en.wikipedia.org/wiki/Non-uniform_memory_access

tags: Linux,Network,Tools netstat -s: show network status(errors) # show udp status $ netstat -s --udp Udp: 437.0k/s packets received 0.0/s packets to unknown port received. 386.9k/s packet receive errors 0.0/s packets sent RcvbufErrors: 123.8k/s SndbufErrors: 0 InCsumErrors: 0

tags: Linux,Network,TCP,UDP,Tools ethtool -S: Reveal where the packets actuaaly went receiver$ watch 'sudo ethtool -S eth2 |grep rx' rx_nodesc_drop_cnt: 451.3k/s rx-0.rx_packets: 8.0/s rx-1.rx_packets: 0.0/s rx-2.rx_packets: 0.0/s rx-3.rx_packets: 0.5/s rx-4.rx_packets: 355.2k/s rx-5.rx_packets: 0.0/s rx-6.rx_packets: 0.0/s rx-7.rx_packets: 0.5/s rx-8.rx_packets: 0.0/s rx-9.rx_packets: 0.0/s rx-10.rx_packets: 0.0/s

tags: Linux,High Performance,Network,ethtool source: The Cloudflare Blog. “How to Receive a Million Packets per Second,” June 16, 2015. http://blog.cloudflare.com/how-to-receive-a-million-packets/. What are Multi-queue NICs RX queue was used to pass packets between hardware and kernel. Now days NICs support multiple RX queues: Each RX queue is pinned to a separate CPU. Multi-queue hashing algorithms Use a hash from packet to decide the RX queue number. The hash is usually counted from a tuple (src IP, dst IP, src port, dst port). This guarantees that packets for a single flow will always end up on exactly the same RX queue, and reordering of packets within a single flow can’t happen. ...

tags: Network,Linux,Tools

tags: Network,UDP,High Performance,iptables,ethtool,netstat,NUMA source: The Cloudflare Blog. “How to Receive a Million Packets per Second,” June 16, 2015. http://blog.cloudflare.com/how-to-receive-a-million-packets/. Keys: Make sure traffic won’t be interfered with by the iptables iptables -I INPUT 1 -p udp --dport 4321 -j ACCEPT iptables -t raw -I PREROUTING 1 -p udp --dport 4321 -j NOTRACK #+end_src[[id:C471A6FF-7F4E-4E23-B070-14CE146BFA14][Multi-queue NICs]] 2. The first bottleneck ​ + All packets are received by a signal RX queue, checked out with =ethtool -S=. ​ + How to solve: according to [[id:C471A6FF-7F4E-4E23-B070-14CE146BFA14][Multi-queue NICs]], change the hash algorithm with =ethtool=: #+begin_src bash ethtool -N eth2 rx-flow-hash udp4 sdfn Multiple threads with NUMA, and with multiple receiver ips to fit in multi-queue hash algorithm. Also note that there is a lock contention on the UDP receive buffer side, see Rivera, Diego, Eduardo Acha, Jose Piquer, and Javier Bustos-Jimenez. “Analysis of Linux UDP Sockets Concurrent Performance.” In 2014 33rd International Conference of the Chilean Computer Science Society (SCCC), 65–69. Talca: IEEE, 2014. https://doi.org/10.1109/SCCC.2014.8. ...

tags: Network

tags: Network

tags: Distributed Systems

tags: C/C++ Capture a map with reference If we capture a map by value, then we can’t use the operator []: unordered_map<int, int> freq; // Won't compile // auto comp_by_map = [freq](const int& a, const int& b) { return freq[a] < freq[b];}; auto comp_by_map = [&freq](const int& a, const int& b) { return freq[a] < freq[b];};

tags: Hash Table,Heap (data structure),LeetCode101,Priority Queue,C++ Lambda class Solution { public: vector<int> topKFrequent(vector<int>& nums, int k) { vector<int> res; unordered_map<int, int> freq; // Note that: we need caputre a map by reference, // otherwise we can't use the operator[]. // See also: https://stackoverflow.com/a/6281071 auto comp_by_map = [&freq](const int& a, const int& b) { return freq[a] < freq[b]; }; // Note that: here we need pass our lambda /comp_by_map/ to the // constructor of std::priority_queue. priority_queue<int, vector<int>, decltype(comp_by_map)> pq(comp_by_map); for (auto n: nums) { freq[n] = freq.find(n) == freq.end() ? 1 : freq[n] + 1; } for (auto iter: freq) { pq.push(iter.first); } while (k > 0) { res.push_back(pq.top()); pq.pop(); k--; } return res; } };

tags: LeetCode101,In-place Travel array in reverse order, and record how many times need to swap, which is how many elements not equal val. class Solution { public: int removeElement(vector<int>& nums, int val) { int k = 0; for (int j = nums.size() - 1; j >= 0; --j) { if (nums[j] == val) { for (int i = 0; i < k; ++i) { swap(nums[i + j], nums[j + i + 1]); } } else { k++; } } return k; } };

tags: Two Pointers,Three Pointers,LeetCode101,Sorting Based on: LeetCode101: 167. Two Sum II - Input Array Is Sorted LeetCode101: 15. 3Sum We create a new loop: class Solution { public: vector<vector<int>> fourSum(vector<int>& nums, int target) { sort(nums.begin(), nums.end()); vector<vector<int>> res; int T, S, r, l; for (int i = 0; i < nums.size(); ++i) { if (i > 0 && nums[i] == nums[i - 1]) { continue; } for (int j = i + 1; j < nums.size(); ++j) { if (j > i + 1 && nums[j] == nums[j - 1]) { continue; } l = j + 1; r = nums.size() - 1; T = target - nums[i] - nums[j]; while (l < r) { S = nums[l] + nums[r]; if (S == T) { res.push_back({nums[i], nums[j], nums[l], nums[r]}); while (l < r && nums[l] == nums[l + 1]) { l++; } while (l < r && nums[r] == nums[r - 1]) { r--; } l++; r--; } else if (S < T) { l++; } else { r--; } } } } return res; } };

tags: Priority Queue,LeetCode101 Using a min heap to keep k elements, top is the Kth largest element. class KthLargest { private: // min heap priority_queue<int, vector<int>, std::greater<int>> pq; int K; public: KthLargest(int k, vector<int>& nums) { K = k; for (auto n: nums) { add(n); } } int add(int val) { pq.push(val); while (pq.size() > K) { pq.pop(); } return pq.top(); } }; /** * Your KthLargest object will be instantiated and called as such: * KthLargest* obj = new KthLargest(k, nums); * int param_1 = obj->add(val); */

tags: Heap (data structure),LeetCode101 Find top k values, classical heap problems. Here we need find top 2 values, and pop them from heap, then we will meet two cases: If they are not same, put back the differ between them, continue. Otherwise, continue directly.

tags: LeetCode101,Sorting,Two Pointers Key ideas: Move both sides to inwards. If the sum value less than target, move left pointer. Otherwise move right poinger. class Solution { public: vector<int> twoSum(vector<int>& numbers, int target) { int S, l = 0, r = numbers.size() - 1; vector<int> res(2, 0); while (l < r) { S = numbers[l] + numbers[r]; if (S == target) { break; } if (S < target) { l++; } else { r--; } } res[0] = l + 1; res[1] = r + 1; return res; } };

tags: LeetCode101,Sorting,Two Pointers,Three Pointers Key ideas see LeetCode101: 15. 3Sum class Solution { public: int threeSumClosest(vector<int>& nums, int target) { sort(nums.begin(), nums.end()); int closest = INT_MAX, l, r, sum, T, res; for (int i = 0; i < nums.size(); i++) { l = i + 1; r = nums.size() - 1; T = target - nums[i]; while (l < r) { sum = nums[l] + nums[r]; if (abs(sum - T) < closest) { res = sum + nums[i]; closest = abs(sum - T); } if (sum == T) { return target; } if (sum < T) { l++; } else { r--; } } } return res; } };

tags: LeetCode101,Sorting,Two Pointers,Three Pointers Key ideas: Sort the nums first. Then, we travel the nums, pick current element as nums[i], and apply LeetCode101: 167. Two Sum II - Input Array Is Sorted to the remains. We skip the same numbers to avoid duplicate. class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { sort(nums.begin(), nums.end()); int l, r, sum, T; vector<vector<int>> res; for (int i = 0; i < nums.size(); i++) { // Skip same numbers to avoid duplicate if(i > 0 && nums[i] == nums[i-1]) { continue; } l = i + 1; r = nums.size() - 1; T = 0 - nums[i]; while (l < r) { sum = nums[l] + nums[r]; if (sum == T) { res.push_back({nums[i], nums[l], nums[r]}); // Skip same numbers in each side to avoid duplicate while (l < r && nums[l] == nums[l + 1]) l++; while (l < r && nums[r] == nums[r - 1]) r--; l++; r--; } else if (sum < T) { l++; } else { r--; } } } return res; } };

tags: Two Pointers

tags: String,Two Pointers,LeetCode101 Two pointers move inwards, when we meet two different characters: Remove left character to see if the remains string still satisfied a valid palindrome. Remove right character to see if the remains string still satisfied a valid palindrome. Returns true if either one above two is true. class Solution { public: bool validPalindrome(string s) { for (int i = 0, j = s.size() -1; i < j; i++,j--) { if (s[i] != s[j]) { // remove left auto left = isPalindrome(s, i + 1, j); // remove right auto right = isPalindrome(s, i, j - 1); // return at here as we have traveled the string in the // invocation of isPalindrome. return right || left; } } return true; } private: bool isPalindrome(string & s, int i, int j) { for (; i < j; i++,j--) { if (s[i] != s[j]) { return false; } } return true; } };

tags: In-place WikiPedia: https://en.wikipedia.org/wiki/In-place%5Falgorithm Let see two examples before we go further: As above we can see, to reverse a array in-place, we just need swap each two elements in the array from both side to middle. The pseudo code from WikiPedia: function reverse_in_place(a[0..n-1]) for i from 0 to floor((n-2)/2) tmp := a[i] a[i] := a[n − 1 − i] a[n − 1 − i] := tmp The loop travels the array to the middle and swap each other in the list, two points we must be noticed: We stop the element at(not before): floor((n - 2) / 2), It’s both 1 of the two above figures. We swap current element with n - 1 - i.

tags: Algorithm

tags: In-place,LeetCode101,In-place Reverse class Solution { public: void reverseString(vector<char>& s) { if (s.size() == 1) { return; } for (int i = 0; i <= (s.size() - 2) / 2; ++i) { swap(s[s.size() - 1 - i], s[i]); } } };

tags: Binary Search,LeetCode101 There is three corner cases must be handled if we don’t find target in nums: Return r + 1 if target is greater than right. Or return mid + 1 if target is greater than mid. Otherwise return mid. class Solution { public: int searchInsert(vector<int>& nums, int target) { int l = 0, r = nums.size() - 1; int mid = r / 2; while (l != r) { mid = l + (r - l) / 2; if (target == nums[mid]) { return mid; } if (target < nums[mid]) { r = mid; } else { l = mid + 1; } } if (target > nums[r]) { return r + 1; } if (target > nums[mid]) { return mid + 1; } return mid; } };

tags: Divide-and-Conquer,LeetCode101,Binary Search class Solution { public: bool searchMatrix(vector<vector<int> > &matrix, int target) { int n = matrix.size(); int m = matrix[0].size(); int l = 0, r = m * n - 1; while (l != r){ int mid = l + (r - l) / 2; if (matrix[mid / m][mid % m] < target) l = mid + 1; else r = mid; } return matrix[r / m][r % m] == target; } };

tags: Algorithm WIKIEPEDIA: https://en.wikipedia.org/wiki/Divide-and-conquer%5Falgorithm The points should been noted: The middle position is not (right - left) / 2, it must be left + ((right - left) / 2).

tags: Bit Manipulation,Bitwise Operator: XOR According to bitwise operator XOR: x ^ x = 0 y ^ 0 = y We apply the XOR operator to all the nums, all the same numbers will apply x ^ x = 0, and then y ^ 0 = y will result the single number. class Solution { public: int singleNumber(vector<int>& nums) { int xorN = 0; for (auto iter = nums.begin(); iter != nums.end(); ++iter) { xorN ^= *iter; } return xorN; } };

tags: Algorithm

tags: Bitwise Operators 0101 (decimal 5) XOR 0011 (decimal 3) = 0110 (decimal 6) 0010 (decimal 2) XOR 1010 (decimal 10) = 1000 (decimal 8) Useful features: 1 ^ 1 = 0 2 ^ 0 = 2

tags: Cycle detection,Fast & Slow Pointers,LeetCode101 Treat as A Linked List with circle According to the length of nums is n + 1, and integer range is [1, n], so we can treat each element as a index that point to some next value. For example: [1,3,4,2,2] It can be treated as(format is element(index)): 1(0) -> 3(1) -> 2(3) -> 4(3) -> 2(4) -> 4(3) We can see there is a circle in it, so: ...

tags: Cycle detection,Fast & Slow Pointers,LeetCode101 /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode *detectCycle(ListNode *head) { if (head == nullptr || head->next == nullptr) { return nullptr; } // tortoise move 1 step auto slow = head->next; // hare move 2 steps auto fast = head->next->next; while (slow != fast) { if (slow == nullptr || fast == nullptr || fast->next == nullptr) { return nullptr; } slow = slow->next; fast = fast->next->next; } slow = head; while (slow != fast) { slow = slow->next; fast = fast->next; } return slow; } };

tags: Algorithm,Two Pointers

tags: Algorithm,Linked List,Fast & Slow Pointers source: https://en.wikipedia.org/wiki/Cycle%5Fdetection Floyd’s tortoise and hare With two pointers: tortoise move slow: move 1 step in each loop. hare move fast: move 2 steps in each loop. If there is a circle existed, tortoise and hare will meet eventually in the circle. Now both tortoise and hare are in the circle, how to figure out the beginning of the circle? We put tortoise back to the beginning they both started. Such as, the first element of the linked list. Then we move both tortoise and hare step by step, they will meet in the beginning of the circle.

tags: Data Structures

tags: Tree

tags: Binary Tree,Tree A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible.

tags: Heap (data structure),Data Structures,Complete Binary Tree,Tree source: https://en.wikipedia.org/wiki/Binary%5Fheap Binary tree with two additional constraints: Shape property: complete binary tree. Heap property: the key stored in each node is greater or equal(max-heaps) to or less than or equal to(min-heaps) the keys in the node’s children, according to some total order. Heap operations Insert Steps to add an element to a heap: Add element to the bottom level of the heap at the leftmost open space. Compare to its parent, if they are in the correct the order, stop. If not, swap element with its parent and return to the previous step. Extract: Delete the root from heap Replace the root of heap with the last element on the bottom level. Compare the new root with its children; if they are in the correct order, stop. If not, swap the element with one of its children and return to the previous step. Search Delete Decrease or increase key Heap implementation with array each element a at index i has ...

tags: Priority Queue,LeetCode101 Max heap priority queue class Solution { public: int findKthLargest(vector<int>& nums, int k) { // max heap priority_queue<int> pq; for (auto iter = nums.begin(); iter != nums.end(); ++iter) { pq.push(*iter); } // The Kth largest element should let k > 1 not k > 0 for (; k > 1; --k) { pq.pop(); } return pq.top(); } };

tags: Priority Queue,LeetCode101 The key ideas: Use a std::pair to hold {count, index}, so it can compare count first then the index. Use a min heap priority queue to get the K weakest rows. class Solution { public: vector<int> kWeakestRows(vector<vector<int>>& mat, int k) { // min heap priority_queue< std::pair<int, int>, vector<std::pair<int, int> >, std::greater<std::pair<int, int> > > pq; for (auto iter = mat.begin(); iter != mat.end(); ++iter) { int c = count((*iter).begin(), (*iter).end(), 1); pq.push({c, iter - mat.begin()}); } vector<int> ret; for (; k > 0; --k) { ret.push_back(pq.top().second); pq.pop(); } return ret; } };

tags: Data Structures,Heap (data structure) The priority queue is solved: The K smallest/largest/weakest X.

tags: Learning English,读书笔记 source: Joseph Devlin. How to Speak and Write Correctly, 2007. http://archive.org/details/how_to_speak_and_write_correctly_librivox. I found this book in my Kindle on the subway to work this morning. And remembered that I downloaded it free from the Kindle store years ago. For some reasons, maybe my English was not good enough to read it, I haven’t read it yet. After read a little, I think it’s prefect for me for now. The reasons is: ...

tags: Data Structures,Tree WHAT is a heap? Tree-based data structure which is essentially an almost complete tree that statifies the heap property. Max heap For any given node C, if P is a parent node of C, then the key(the value) of P is greater than or equal to the key of C. Min heap The P is less than or equal to the key C. When to use a heap? Priority queue. Heapsort.

tags: Algorithm

tags: Hash Table,LeetCode101,Sorting,Two Pointers Intuition with HashMap class Solution { public: int numRescueBoats(vector<int>& people, int limit) { unordered_map<int, int> cntOfWeights; for (auto iter = people.begin(); iter != people.end(); ++iter) { cntOfWeights[*iter]++; } int r = 0; for (int i = 0; i < people.size(); i++) { if (cntOfWeights[people[i]] == 0) { continue; } cntOfWeights[people[i]]--; for (int j = (limit - people[i]); j > 0; --j) { if (cntOfWeights.find(j) != cntOfWeights.end() && cntOfWeights[j] > 0) { cntOfWeights[j]--; break; } } r++; } return r; } }; Sorting and Two Pointers class Solution { public: int numRescueBoats(vector<int>& people, int limit) { int i = 0; int j = people.size() - 1; // heaviest go first sort(people.rbegin(), people.rend()); for (; i <= j; i++) { if (people[i] + people[j] <= limit) j--; } return i; } };

tags: Math,backtracking,LeetCode101 Backtracking and stack overflow Intuition: We can abstract all the operations to a Tree, then apply DFS on it. For example: startValue=2, target=3, the tree looks like: /* 2 /\ / \ / \ 1(-1) 4(x2) /\ /\--+ / \ / \ 0(-1) 2(x2) 3(-1) 8(x2) */ class Solution { public: int brokenCalc(int startValue, int target) { unordered_set<int> visited; return backtracking(0, startValue, target, visited); } int backtracking(int count, int val, int target, unordered_set<int> & visited) { if (val == target) { return count; } if (visited.find(val) != visited.end()) { return -1; } int left = -1, right = -1; count++; visited.insert(val); if (val > 0) { left = backtracking(count, val - 1, target, visited); } if (val <= target * 2) { right = backtracking(count, val * 2, target, visited); } visited.erase(val); if (left != -1 && right != -1) { return min(left, right); } else if (left != -1) { return left; } return right; } }; Change target to startValue class Solution { public: int brokenCalc(int startValue, int target) { int r = 0; while (target > startValue) { target = target % 2 > 0 ? target + 1 : target / 2; r++; } return r + startValue - target; } };