Category: foundational_interview
-
LeetCode 299: Bulls and Cows
link If secret[i] = guess[i] that is a bull. So, we can process and exclude bull positions. In the remaining positions if guess[i] could be matched with a secret[j], that is a cow. So, we use two passes: (1) Bull pass (2) Cow pass. Time , space: . Note, len(secret) = len(guess). Say for a…
-
LeetCode 1086: High Five
link We create a map: {id -> minq(score)} and we cap the length of the minq at 5. In that way, in the end, we have the top five scores per id. Say len(items) = . There are two extreme cases: Time: , space: . Note, the heap plays a role only if there are…
-
LeetCode 1570: Dot Product of Two Sparse Vectors
link For two vectors and , the dot product . So, we represent a sparse vector as a map of nonzero values: {index -> value}. While computing dot product, we iterate over the vector that has a shorter sparse representation. Say len(nums) = and only values are nonzero. Operation Time Space __init__ dotProduct Follow up: What…
-
LeetCode 609: Find Duplicate File in System
link We build a map: content -> [file_path]. If there are more than one files against a content, they are duplicates. Say there are files and the longest file path has length , then time: , space is proportional to the total number of characters including contents. Follow-up Imagine you are given a real file…
-
LeetCode 205: Isomorphic Strings
link Two strings are isomorphic if we can find a two-way mapping between their characters that makes the two strings identical. We keep two maps to validate the two-way mapping. Two maps we maintain are: s -> t and t -> s. For s[i] and t[i], either they have not been mapped yet or s[i]…
-
LeetCode 496: Next Greater Element I
link It’s a mapping problem: nums1 -> nums2 -> next_greater_element. To build the mapping nums2 -> next_greater_element, we take the approach in the next warmer day problem. Time: , space: .
-
LeetCode 359: Logger Rate Limiter
link For each unique message we keep the next valid timestamp. If a message is early, we simply discard it returning False. Otherwise, we update the next valid timestamp and return True. Time: , space: . We can also do the filtering based on elapsed time. Time: , space: . To optimize for space, we…
-
LeetCode 166: Fraction to Recurring Decimal
link The answer may look like: . For example: . Details For q, r = divmod(numerator, denominator), . Consequently, the longest length before a fractional digit repeats is . The get_repeated_decimal()‘s outer loop can have these many iterations. On each of these iterations, the inner while loop can run for iterations. So, time: , space:…
-
LeetCode 706: Design HashMap
link Indexed sequence Since , we can use a list of length to implement the API. Total space is . Operation Time Space put get remove Linked list We can use a doubly linked list where an item is . Total space is . Operation Time Space put get remove Indexed sequence of linked lists…
-
LeetCode 386: Lexicographical Numbers
link String sort Since there are digits in a number, time: , space: . DFS in a Trie There are digits in a number. So, building the trie and a DFS of the trie, both take time . Time: , space: . DFS in implicit Trie We could traverse the trie without explicitly building it.…
unreasonably effective 