Problems
August 5, 2022
LRU cache
We will use a hashmap to lookup the key in out cache and a link list to keep track of most and least used cache item.
Time Complexity: O(1) for each operation
Space Complexity:...
August 4, 2022
Find the duplicate number
We will use Floyd's cycle detection algorithm for solve the problem. As the input array has elements from [1, n], and there is n+1 numbers, this is nothing but a linked list, where the list starts as...
ReadAugust 4, 2022
Mirror reflection
First, think about the case p = 3 and q = 2. So, this problem can be transformed into finding m * p = n * q, where m = the number of room extension + 1, n = the number of light reflection + 1. If...
ReadAugust 4, 2022
Find minimum in rotated sorted array
We will start by assuming the minimum number is fisrt element of the list. Then we will do a binary search, but before calculating the mid value, we will check, if the value at left pointer is less...
ReadAugust 4, 2022
Median of two sorted arrays
We will first count the number of elements of both array and find the half. We assume the fisrt list is the longest, if not, then we swap them. Then we apply binary search to the longest list. Then...
ReadAugust 4, 2022
Search in rotated sorted array
We will do a binary search, but when we devide each it to the mid pointer, we will check, if the value at left pointer is less that value of right pointer. In that case, this part of the list is...
ReadAugust 3, 2022
Minimum window substring
We will first count the number of characters in the search substring. Then we create a sliding window, and move it along the whole string. If some character is missing in the sliding window, we then...
ReadAugust 3, 2022
My calendar I
We will create a binary search tree with all the events. If start if greater than root's end, we will insert it in right subtree, if end if less than root's start, then insert it in left subtree. If...
ReadAugust 3, 2022
Sliding window maximum
We can solve this problem using monotonic increasing queue. We will add all the items from the input lust in a monotonic q and add the top of the q to our result. Then when the traverse is finished,...
ReadAugust 2, 2022
Find eventual safe states
This is another topological sort problem, we are using graph coloring to solve it. At first we mark(color) everything as new. When we start our traversing with DFS, we first mark it as unsafe, then...
Read