Category: foundational_interview
-
LeetCode 346: Moving Average from Data Stream
link We keep track of the window sum. If window has too many numbers we pop the oldest, updating sum. Operation Time Space __init__ next
-
LeetCode 716: Max Stack
link Stack of (num, curr_max) We can keep current max with the element. Say len(stack) = . Operation Time Space __init__ push pop top peekMax popMax Above, in the worst-case, popMax() needs to sift through the entire stack. To make finding max faster, we can use max heap. LinkedList and Max-Heap We keep two stacks:…
-
LeetCode 705: Design HashSet
link List of LinkedLists We can use a fixed length list of LinkedList‘s. A key is put into the LinkedList or bucket at index hash(key). Say len(buckets) = and there are keys. The cost of operations depend on the load-factor, . And the load-factor depends on how evenly the hash distributes the keys across different…
-
LeetCode 244: Shortest Word Distance II
link There can be multiple instances of both word1 and word2. We need to find the shortest distance among the possible pairs. List and sliding window We do not maintain any auxiliary data structure. Using sliding window [begin_word, end_word], where begin_word in {word1, word2} and end_word in {word1, word2} \ {begin_word}, we can find the…
-
LeetCode 715: Range Module
link Set We can keep a set of the actual numbers contained within ranges. Sorted list of ranges We maintain a list of disjoint ranges sorted by left. Say at the time of operations, there are disjoint ranges. Total space is . Operation Time Space __init__ addRange queryRange removeRange Since we have a sorted list…
-
LeetCode 155: Min Stack
link Top of the stack also keeps current minimum. Operation Time Space __init__ push pop top getMin Instead of keeping min per value, we can use a separate stack for mins. This way we need space for unique mins only.
-
LeetCode 380: Insert Delete GetRandom O(1)
If we have a set of values: , in a sequence of getRandom() calls, each of the six permutations of must appear roughly equal number of times. We assume random.randint(lo, hi) takes time. List We can keep a list of values and pick an index at random. Say there are values. Total space is .…
-
LeetCode 146. LRU Cache
link Dict and LinkedList If we did not have to evict keys, we could just keep a {key -> value} map. When there are too many keys, we need to evict the least-recently-used key therefore the key for which a get or put was called furthest into the past. As a result, we need to…
-
LeetCode 981: Time Based Key-Value Store
link Note, if get() is called for a timestamp that was not set, we need to find the latest value until that timestamp. In other words, say for a key, we have (1, val1), (2, val2, 2), (5, val3) where 1, 2, and 5 are timestamps. For that key, if get() is now called with…
-
LeetCode 1146. Snapshot Array
link We keep the below three pieces of information: On get(), we may need to search through earlier snapshots to get the value at an index that has not changed for a while. Say snap‘s have been called. Operation Time Space __init__ set snap get
unreasonably effective 