Are you looking for a set of DS&A problems that would be a proxy for all the possible problems you might be asked at a Big Tech Interview?
Is there such a list of Problems? If so, then how do we use these problems?
…
What if I told you there is such a list of problems? A list that will train your brain to process DS&A problems fast and will prepare it to absorb any other problem and its solutions like a sponge. Not only that, but it will also train your brain to come up with solutions to most problems.
Also, if you practice these problems every day till your interview, you will feel invisible.
…
I present to my readers,
The Super Problems.
…
Here is how to use these:
- Start with each problem; of course, you will not be able to solve it initially. But learn the topics I have mentioned and do a few easy then mediums. After that, come back to the problem.
- Then, once you can understand the solution to these problems, try to memorize them.
- You might be thinking, “Memorize, that isn’t the right way to learn DS&A.” To that, I would say, stop wasting your time on such BS notions and put your time into Memorizing these.
- After a few weeks of constantly doing these problems, you should feel the power of DS&A running through your veins.
- Good luck!
84. Largest Rectangle in Histogram
This is a strictly increasing max stack problem. As you iterate over the heights, you keep track of the heights in a strictly increasing stack. If the current height goes down compared to the last height seen, calculate the largest possible rectangle from the current index to the index stored with the height in the last element of the stack. Keep doing this till no element in the stack has a height bigger than the current height element. Then, update the index with the last greater height element found in the stack and add the current height with the index in the stack. At the end, till there are elements in the stack, calculate the possible area of the rectangles with the index and the total length of the heights array for each element in the stack.
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
stk = []
res = 0
for idx, height in enumerate(heights):
x = idx
while stk and stk[-1][0] > height:
res = max(
res,
stk[-1][0] * (idx - stk[-1][1])
)
x = stk[-1][1]
stk.pop()
stk.append((height, x))
while stk:
res = max(
res,
stk[-1][0] * (len(heights) - stk[-1][1])
)
stk.pop()
return res42. Trapping Rain Water
This is a prefix sum problem. Calculate two prefix sum arrays where you store the maximum elements to the left and in the other, and you store the maximum elements to the right. Then, you take the minimum of the two maximums on the left and right and subtract the current height. If you get a positive value, that is, the amount of water that particular block will store above it. Keep adding them up.
class Solution:
def trap(self, height: List[int]) -> int:
max_left = [0 for _ in range(len(height))]
max_right = [0 for _ in range(len(height))]
for i in range(1, len(height)):
max_left[i] = max(
max_left[i - 1],
height[i - 1]
)
for i in reversed(range(0, len(height) - 1)):
max_right[i] = max(
max_right[i + 1],
height[i + 1]
)
res = 0
for i in range(1, len(height)):
val = min(max_left[i], max_right[i]) - height[i]
if val > 0:
res += val
return res332. Reconstruct Itinerary
This is a backtracking while DFS problem. We start first by sorting the tickets. Then, we build an adjacent graph. We then start with “JFK,” and as we do a DFS, we keep removing the edges that we have already looked at; then, if we can get to a state where we have used up all the tickets, we can stop. Otherwise, we backtrack, put the edge back, move to the next edge, and keep traversing with DFS.
class Solution:
def findItinerary(self, tickets: List[List[str]]) -> List[str]:
graph = defaultdict(lambda: [])
tickets.sort()
for ticket in tickets:
frm, to = ticket
graph[frm].append(to)
def dfs(node, res):
if len(res) == len(tickets) + 1:
return True
temp = graph[node]
for idx, neighbor in enumerate(temp):
graph[node].pop(idx)
res.append(neighbor)
if dfs(neighbor, res):
return True
res.pop()
graph[node].insert(idx, neighbor)
return False
res = ["JFK"]
dfs("JFK", res)
return res218. The Skyline Problem
This is a priority queue problem. We first create an array with the tuples (start/end, +/-height) where if we see a rising edge of a building, we put (-) height, and for a falling edge, we put (+) height. Then, we sort this array. After this we iterate through the array, and everytime we see a rising edge of a building (-height) we add the height in the priority queue, and when we run into a falling edge, we remove the height from the priority queue and heapify the priority queue. As we are doing this, we also check if the top height has changed in the priority queue; if it has, then we record the height and the start/end point in the result.
class Solution:
def getSkyline(self, buildings: List[List[int]]) -> List[List[int]]:
heights = []
for building in buildings:
start, end, height = building
heights.append((start, -height))
heights.append((end, height))
heights.sort()
pq, cur_height = [0], 0
res = []
for height in heights:
x, y = height
if y < 0:
heapq.heappush(pq, y)
else:
for idx, val in enumerate(pq):
if val == -y:
pq.pop(idx)
break
heapq.heapify(pq)
if cur_height != pq[0]:
cur_height = pq[0]
res.append((x, -cur_height))
return res778. Swim in Rising Water
This is a BFS with a priority queue problem. We first start at (0, 0), and we will end the BFS traversal when we reach the bottom right cell. We will first calculate the maximum height of the current cell and the neighboring cells and add that with the neighboring cell into the priority queue as (max(current height, neighbor height), neighbor). Instead of a queue, we will use this priority queue to run our BFS, and the final height that we see in the top element of the priority queue when we have reached the bottom right cell is the answer.
class Solution:
def swimInWater(self, grid: List[List[int]]) -> int:
pq = [(grid[0][0], 0,0)]
visited = set()
res = 0
while pq:
height, x, y = heapq.heappop(pq)
if x == len(grid) - 1 and y == len(grid[0]) - 1:
return height
if (x, y) in visited:
continue
visited.add((x, y))
for x_d, y_d in [(0, -1), (0, 1), (-1, 0), (1, 0)]:
n_x, n_y = x + x_d, y + y_d
if n_x >= 0 and n_x < len(grid) and n_y >= 0 and n_y < len(grid[0]) and (n_x, n_y) not in visited:
heapq.heappush(pq,
(max(grid[n_x][n_y], height), n_x, n_y)
)
return -11851. Minimum Interval to Include Each Query
Another priority queue problem, but also requires some greedy way of thinking like any other Interval problem.
class Solution:
def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:
intervals.sort()
queries = sorted([(val, idx) for idx, val in enumerate(queries)])
pq = []
i = 0
res = [-1 for _ in range(len(queries))]
for query in queries:
val, idx = query
while i < len(intervals) and intervals[i][0] <= val:
heapq.heappush(pq, (intervals[i][1] - intervals[i][0] + 1, intervals[i][1]))
i += 1
while pq and pq[0][-1] < val:
heapq.heappop(pq)
if pq:
res[idx] = pq[0][0]
return res
146. LRU Cache
For this, you can use a hashtag and a doubly linked list. To simplify your life, you should use two dummy nodes to denote the beginning and end of the Doubly Linked List, which will help with all the edge cases.
class Node:
def __init__(self, key, value, next=None, prev=None):
self.key = key
self.value = value
self.next = next
self.prev = prev
class LRUCache:
def __init__(self, capacity: int):
self.cap = capacity
self.start, self.end = Node(-1, -1), Node(-1, -1)
self.start.next = self.end
self.end.prev = self.start
self.hashmap = {}
def remove(self, node):
prev = node.prev
nxt = node.next
prev.next = nxt
nxt.prev = prev
def insert(self, node):
prev = self.end.prev
nxt = self.end
prev.next = node
node.prev = prev
nxt.prev = node
node.next = nxt
def get(self, key: int) -> int:
if key not in self.hashmap:
return -1
node = self.hashmap[key]
self.remove(node)
self.insert(node)
return node.value
def put(self, key: int, value: int) -> None:
if key in self.hashmap:
node = self.hashmap[key]
self.remove(node)
node = Node(key, value)
self.hashmap[key] = node
self.insert(node)
return
if len(self.hashmap) == self.cap:
node = self.start.next
self.remove(node)
del self.hashmap[node.key]
node = Node(key, value)
self.hashmap[key] = node
self.insert(node)
# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)493. Reverse Pairs
This requires a strong knowledge of merge sort. After each array breakup, you count the number of pairs just before merging.
class Solution:
def merge(self, arr, low, mid, high):
temp = [] # temporary array
left = low # starting index of left half of arr
right = mid + 1 # starting index of right half of arr
# storing elements in the temporary array in a sorted manner
while left <= mid and right <= high:
if arr[left] <= arr[right]:
temp.append(arr[left])
left += 1
else:
temp.append(arr[right])
right += 1
# if elements on the left half are still left
while left <= mid:
temp.append(arr[left])
left += 1
# if elements on the right half are still left
while right <= high:
temp.append(arr[right])
right += 1
# transferring all elements from temporary to arr
for i in range(low, high + 1):
arr[i] = temp[i - low]
def countPairs(self, arr, low, mid, high):
right = mid + 1
cnt = 0
for left in range(low, mid + 1):
while right <= high and arr[left] > 2 * arr[right]:
right += 1
cnt += (right - (mid + 1))
return cnt
def mergeSort(self, arr, low, high):
if low >= high:
return 0
cnt = 0
mid = (low + high) // 2
cnt += self.mergeSort(arr, low, mid)
cnt += self.mergeSort(arr, mid + 1, high)
cnt += self.countPairs(arr, low, mid, high)
self.merge(arr, low, mid, high)
return cnt
def reversePairs(self, nums: List[int]) -> int:
return self.mergeSort(nums, 0, len(nums) - 1)10. Regular Expression Matching
This is a dynamic programming problem that requires a good understanding of how to break it into smaller recursive steps.
class Solution:
def isMatch(self, s: str, p: str) -> bool:
def dfs(i, j, cache):
if (i, j) in cache:
return cache[(i, j)]
if i >= len(s) and j >= len(p):
return True
if j >= len(p):
return False
match = i < len(s) and (s[i] == p[j] or p[j] == ".")
if j + 1 < len(p) and p[j + 1] == "*":
cache[(i, j)] = dfs(i, j + 2, cache) or (match and dfs(i + 1, j, cache))
return cache[(i, j)]
if match:
cache[(i, j)] = dfs(i + 1, j + 1, cache)
return cache[(i, j)]
cache[(i, j)] = False
return cache[(i, j)]
return dfs(0, 0, {})Few Bonus Problems
18. 4Sum
This can be solved by sorting the array. Then, there are 2 for loops, with a two-pointer at the next element of the 2nd for loop to the end of the array.
class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
nums.sort()
res = []
for i in range(len(nums)):
if i > 0 and nums[i] == nums[i - 1]:
continue
for j in range(i+1, len(nums)):
if j != (i + 1) and nums[j] == nums[j - 1]:
continue
k, l = j + 1, len(nums) - 1
while k < l:
val = nums[i] + nums[j] + nums[k] + nums[l]
if val == target:
res.append([nums[i], nums[j], nums[k], nums[l]])
k += 1
l -= 1
while k < l and nums[k] == nums[k - 1]:
k += 1
while k < l and nums[l] == nums[l + 1]:
l -= 1
elif val > target:
l -= 1
else:
k += 1
return res121. Best Time to Buy and Sell Stock
This is a two-pointer/sliding window problem. Take the two pointers as the first and second element of the prices array, and till the second pointer hits the end of the array, keep iterating. As you iterate, see if the price at the second pointer is below the element at the first pointer. In that case, you have found a lower value to buy the stock, so update the first pointer to be the second. For each first and second pointer pair, calculate the profit. Take the maximum of these profits.
class Solution:
def maxProfit(self, prices: List[int]) -> int:
i, j = 0, 1
res = 0
while j < len(prices):
while prices[j] < prices[i]:
i += 1
res = max(
res,
prices[j] - prices[i]
)
j += 1
return res
