Category: foundational_interview
-
LeetCode 1863: Sum of All Subset XOR Totals
link Subsets of numbers For each subset we can xor the elements. If there are 3 numbers in the array, there are possible subsets. So, we use the bit patterns for the numbers to find elements of the subsets. Time: , space: . Subsets of bit positions Say we have two -bit numbers: and .…
-
LeetCode 271: Encode and Decode Strings
link If we can mark the end of each word, we can decode. To mark the end of a word, we cannot use a character from the alphabet because we would not know if it is a marker or part of a word. Characters as numbers The ord() of a character is a non-negative integer.…
-
LeetCode 137: Single Number II
link We can create a map: {number -> count}. In the map, the number that has count = 1 is the one we want. Assuming numbers are 32-bit integers, there are distinct numbers. Time: , space: . Above, the count of numbers have a pattern: it is either multiple of 3 or 1. We can…
-
LeetCode 136: Single Number
link If we xor all numbers, the number without a double will remain. Time: , space: .
-
LeetCode 832: Flipping an Image
link Horizontal flip of a row is like swapping the values at pairs of indices starting from the two ends going towards the center. So, if values of a pair of such indices are different, a flip followed by an invert behaves like two inverts in sequence — resulting in zero changes. Likewise, same values…
-
LeetCode 1009: Complement of Base 10 Integer
link To find the complement we can xor with all-ones mask. To create the all-ones mask, we first find the leftmost 1-bit in n. Say -th bit is the leftmost 1-bit. Then, will have all bits right of set to 1’s and that is our mask. Time: , space: . We can create the all-ones…
-
LeetCode 389. Find the Difference
link Two passes Lookup t‘s characters in s to find which one is extra. Say len(s) = . Time: , space: . One pass Note, XOR of same numbers is 0. Also, XOR is commutative. So, if we take XOR of all characters (as number) in both strings, we shall be left with the extra…
-
LeetCode 460: LFU Cache
link LRU Cache per frequency If two keys have the same frequency, we need to evict the least-recently-used one. So, for each frequency we keep an LRU cache — a LinkedList. To know the current frequency of a key, we also keep {key -> frequency} map. Note, frequency of a key starts at 1 and…
-
LeetCode 303: Range Sum Query – Immutable
link We can compute prefix sums in the beginning. Operation Time Space __init__ sumRange
-
LeetCode 170: Two Sum III – Data structure design
link We can keep a map: {number -> count}. To find two numbers that sum up to value, we can iterate through the map. For x, (value – x) must be in the map. If x and (value – x) are equal, then the count of x must be at least 2. Say, there are…
unreasonably effective 