Category: Uncategorized
-
Distributed Cache
Memcache A global, in-memory hash-table distributed across servers. Key and value are strings, item has TTL on top of LRU eviction. Memcache@scale
-
Distributed Systems: Replication
If you are not doing replication, you are not fault-tolerant. The more availability we want from replication, more work is required. The more consistent we want writes and reads to be, the more work is required. Six consistency levels have varying cost in terms of performance and availability. Guarantee Consistency Performance Availability Strong consistency Excellent…
-
LeetCode 187: Repeated DNA Sequences
link Sliding window Each 10-letter sequence is a window. We keep the window counts in a map. Say len(s) = and there are distinct 10-letter repeated sequences. Time: , space: . Since there are four different letters, the window can be considered as a base-4, 10-digit number. Say first window is: . The next window…
-
LeetCode 1207: Unique Number of Occurrences
link We can create a map: {value -> count}. Each value having unique number of occurrences means: in the map, each value has a distinct count. In other words, the number of different counts in the map is same as the map size. Time: , space: .
-
Binary Tree
Special type of directed graph where a node can have at most two outgoing edges and one incoming edge. Unlike graphs, with a binary tree, we differentiate between the two outgoing edges by marking one as left and the other as right. Test helpers Height Height of a node : Height is the count of…
-
LeetCode 114: Flatten Binary Tree to Linked List
link Recursive A flattened list has a head and a tail. We recursively flatten root.left and root.right and then combine the flattened sublists to build a longer list: root -> flattened_left -> flattened_right. Time: , space: Root becomes the head of the flattened list, so we do not need to keep track of head of…
-
LeetCode 1099: Two Sum Less Than K
link Sorting and two pointers Time: that of sorting, . Space: that of sorting. Counting sort and two pointers Time: , space: . Use dict to store count. We need to sort the keys only. If range of values in nums is . Time: , space: .
-
LeetCode 354: Russian Doll Envelopes
link Longest Increasing Subsequence: Dynamic Programming We need to find the largest subset of envelopes which can be ordered as an increasing sequence. Sorting by width, makes it the problem of finding the length of longest increasing subsequence. Time: , space: . Longest Increasing Subsequence: Binary Search Once we sort the envelopes by width, the…
unreasonably effective 