-
Distributed Systems: Reading
Topology Concurrency Consistency and Availability Scalability Systems Patterns
-
LeetCode 424: Longest Repeating Character Replacement
link We can convert any characters to any other character. Say in a substring of s, the char has the most frequency. We should try matching other characters in the window to using replacements. In other words, as long as window_length – count_of[c] , the window is good. Longer windows can be good only if…
-
LeetCode 727: Minimum Window Subsequence
link Starting at each index of s1 we can try matching s2. Say len(s1) = and len(s2) = . Time: , space: . The window in s1 that contains s2 as a subsequence must have all characters of s2. So, to decrease the number of match_window() calls, we may first try finding the minimum window…
-
LeetCode 239: Sliding Window Maximum
link If we find that is bigger than all numbers in the current (sliding) window, we need to keep track of just from then on. With the above observation, we can maintain a queue of possible maxes for the current and future windows. The head of the queue will be the current max. Each number…
-
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 287: Find the Duplicate Number
link Here values in nums is a permutation of the indices. If we consider i and nums[i] as consecutive nodes of a linked list, we have a permutation of the indices in the linked list. Say nums[i] = 2 and nums[j] = 2. This creates a cycle. With fast and slow pointers we can find…
-
LeetCode 457: Circular Array Loop
link Since the array is circular, there is always a cycle. A loop is: For example, below, if we start from index 0, the direction changes at the hop . But within the cycle: , the direction does not change. So, we declare it has a loop. Starting from each index we can check the…
-
LeetCode 202: Happy Number
link We run until we see a repeated number and check if that is 1. Say is an digit number. So, . Let . The maximum value of is when digits are all ‘s. In other words, the maximum value of . Since , . So, one step of sum of digit squared reduces to…
-
LeetCode 1650: Lowest Common Ancestor of a Binary Tree III
link Since we have parent pointer, we can find the path from p -> root and q -> root and then traverse the two paths in sync to find the LCA. Time: , space: . We do not need to precompute the paths. Say p and q are traversing towards the root. Below, by the…
-
LeetCode 1442: Count Triplets That Can Form Two Arrays of Equal XOR
link All triplets For all (i, j, k), we check if xor(i, j) = xor(j, k+1). Time: , space: . Prefix XOR Say XOR(i, j) represents the xor of the numbers in the sublist nums[i : j+1], then XOR(i, j) = XOR(0, j) XOR(0, i-1). So, we could precompute xor’s of prefixes and avoid computing…
-
Subscribe
Subscribed
Already have a WordPress.com account? Log in now.
unreasonably effective 