Aug 5, 2024 | monday 8:00 pm
This series will be mainly focused for my own accountability and reference, as well as anyone who wants to follow my journey to becoming a better problem solver. Each week, I will highlight problems that I thought was interesting or difficult. Additionally, other problems that I solved and their solutions are listed below.
MediumHeap
Try it yourself here!
This problem is particularly interesting due to its real-world applicability. It provides insight into how complex systems operate in the real world and inspires me to create a social media SaaS (Software as a Service) application.
Problem Statement: Build a simple twitter, where users can follow other users, tweet, and see the ten most recent tweets on their feed.
Example:
Input:
[“Twitter”, “postTweet”, “getNewsFeed”, “follow”, “postTweet”, “getNewsFeed”, “unfollow”, “getNewsFeed”]
[[], [1, 5], [1], [1, 2], [2, 6], [1], [1, 2], [1]]
Output: [null, null, [5], null, null, [6, 5], null, [5]]
Edge Cases:
Complexity:
class Twitter:
def __init__(self):
self.followMap = defaultdict(set)
self.tweetMap = defaultdict(list)
self.count = 0
self.k = 10
def postTweet(self, userId: int, tweetId: int) -> None:
self.tweetMap[userId].append([tweetId, self.count])
self.count += 1
def getNewsFeed(self, userId: int) -> List[int]:
res = []
heap = []
self.followMap[userId].add(userId)
for f in self.followMap[userId]:
if f in self.tweetMap:
index = len(self.tweetMap[f]) - 1
tweet, count = self.tweetMap[f][index]
heappush(heap, (-count, tweet, index - 1, f))
while heap and len(res) < 10:
cnt, twt, idx, f = heappop(heap)
res.append(twt)
if idx >= 0:
twt, count = self.tweetMap[f][idx]
heappush(heap, (-count, twt, idx - 1, f))
return res
def follow(self, followerId: int, followeeId: int) -> None:
self.followMap[followerId].add(followeeId)
def unfollow(self, followerId: int, followeeId: int) -> None:
if followeeId in self.followMap[followerId]:
self.followMap[followerId].remove(followeeId)
EasyHeap
Try it yourself here!
class KthLargest:
def __init__(self, k: int, nums: List[int]):
self.k = k
self.heap = nums
heapify(self.heap)
while len(self.heap) > k:
heappop(self.heap)
def add(self, val: int) -> int:
heappush(self.heap, val)
while len(self.heap) > self.k:
heappop(self.heap)
return self.heap[0]
Complexity:
EasyHeap
Try it yourself here!
def lastStoneWeight(self, stones: List[int]) -> int:
heap = []
for s in stones:
heappush(heap, -s)
while len(heap) > 1:
y, x = heappop(heap), heappop(heap)
if x != y:
heappush(heap, y - x)
return -heap[0] if heap else 0
Complexity:
MediumTrie
Try it yourself here!
class Trie:
def __init__(self):
self.trie = {}
def insert(self, word: str) -> None:
trie = self.trie
for s in word:
if s not in trie:
trie[s] = {}
trie = trie[s]
trie["*"] = True
def search(self, word: str) -> bool:
trie = self.trie
for s in word:
if s not in trie:
return False
trie = trie[s]
return "*" in trie
def startsWith(self, prefix: str) -> bool:
trie = self.trie
for s in prefix:
if s not in trie:
return False
trie = trie[s]
return True
Complexity:
MediumTrie
Try it yourself here!
class WordDictionary:
def __init__(self):
self.root = {}
def addWord(self, word: str) -> None:
root = self.root
for s in word:
if s not in root:
root[s] = {}
root = root[s]
root["*"] = "!"
def search(self, word: str) -> bool:
def searchWord(word, trie):
for i, ch in enumerate(word):
if not ch in trie:
if ch == ".":
for l in trie:
if l != "*" and searchWord(word[i + 1:], trie[l]):
return True
return False
else:
trie = trie[ch]
return "*" in trie
return searchWord(word, self.root)
Complexity:
MediumHeap
Try it yourself here!
def leastInterval(self, tasks: List[str], n: int) -> int:
time = 0
idle_queue = deque()
task_heap = [-v for v in Counter(tasks).values()]
heapify(task_heap)
while task_heap or idle_queue:
time += 1
if task_heap:
cnt = heappop(task_heap) + 1
if cnt:
idle_queue.append([cnt, time + n])
if idle_queue and idle_queue[0][1] == time:
cnt = idle_queue.popleft()[0]
heappush(task_heap, cnt)
return time
Complexity:
HardHeap
Try it yourself here!
class MedianFinder:
def __init__(self):
self.small, self.large = [], []
def addNum(self, num: int) -> None:
heappush(self.large, num)
# move if its smaller than the largest in self.small
if self.small and -self.small[0] >= self.large[0]:
heappush(self.small, -heappop(self.large))
if len(self.small) > len(self.large) + 1:
heappush(self.large, -heappop(self.small))
if len(self.large) > len(self.small) + 1:
heappush(self.small, -heappop(self.large))
def findMedian(self) -> float:
if len(self.small) > len(self.large):
return -self.small[0]
elif len(self.large) > len(self.small):
return self.large[0]
else:
return (self.large[0] + -self.small[0]) / 2
Complexity: