Algorithm Problem Solutions
Compiled Reference Document
1. Message Delivery Status (Rate Limiting)
Problem Description:
If a message with the same text was already delivered in the past k seconds, the new one is
considered a duplicate and dropped. Given a list of messages with their arrival times, return
whether each message should be delivered ( true ) or marked as a duplicate ( false ).
Example:
timestamps = [1, 1, 1, 11]
messages = ["message-2", "message-2", "message-3", "message-2"]
k = 5
Output: ["true", "false", "true", "true"]
Solution Approach
This is solved using a Hash Map (Dictionary). We keep track of the exact timestamp when each specific
message was last delivered. If a message has never been seen, or the time elapsed since its last
delivery is strictly greater than k, we deliver it and update the map. Otherwise, we drop it.
def getMessageStatus(timestamps, messages, k):
# Dictionary to store the timestamp of the last *delivered* message
last_delivered = {}
result = []
for t, msg in zip(timestamps, messages):
if msg not in last_delivered or t - last_delivered[msg] > k:
[Link]("true")
last_delivered[msg] = t
else:
[Link]("false")
return result
1
Time Complexity: O(N) where N is the number of messages.
Space Complexity: O(M) where M is the number of unique messages.
2. The Missing Prisoner (Optimal Approach)
Problem Description:
You are given a list of unique integer coordinates [x, y] representing prisoners. They were originally
arranged in groups of 4 forming axis-aligned rectangles. One prisoner is missing. Determine the
coordinates of the missing prisoner.
Solution Approach: Bitwise XOR
In a complete set of rectangles, every X coordinate appears an even number of times, and every Y
coordinate appears an even number of times. When one coordinate point goes missing, its X and Y
values will be the only ones appearing an odd number of times. Using the Bitwise XOR operator ( ^ ), all
paired coordinates cancel each other out (evaluating to 0), leaving only the missing X and Y coordinates.
def missingPrisoner(locations):
missing_x = 0
missing_y = 0
# XOR all x and y coordinates respectively
for x, y in locations:
missing_x ^= x
missing_y ^= y
return [missing_x, missing_y]
Time Complexity: O(N). Single iteration through the list.
Space Complexity: O(1). Only two variables required regardless of input size.
2
3. The Missing Prisoner (Set-Based Approach)
Problem Description:
Solve the "Missing Prisoner" problem without using the Bitwise XOR operation.
Solution Approach: Toggling Sets
We can mimic the canceling-out behavior of XOR by using Sets. For each coordinate, if it is not in the
set, we add it. If it is already in the set, we remove it. By the end, all paired coordinates will have been
removed, leaving only the missing X and Y in their respective sets.
def missingPrisoner_Set(locations):
x_set = set()
y_set = set()
for x, y in locations:
if x in x_set:
x_set.remove(x)
else:
x_set.add(x)
if y in y_set:
y_set.remove(y)
else:
y_set.add(y)
return [x_set.pop(), y_set.pop()]
Time Complexity: O(N). Hash set lookups and insertions are O(1) on average.
Space Complexity: O(N) to store the sets of unique coordinates.
4. Unreachable Warehouses
Problem Description:
A network of bidirectional roads connects warehouses. To avoid traffic, these roads must be made
directional. A warehouse is unreachable if it has no incoming edges. Find the minimum number of
unreachable warehouses after optimal transformation.
3
Solution Approach: Disjoint Set Union (DSU)
We analyze the connected components of the graph. If a component has a cycle (Edges ≥ Vertices), we
can direct edges around the cycle so every node gets an incoming edge (0 unreachable nodes). If a
component is a tree (Edges = Vertices - 1), exactly one node will be left without an incoming edge, no
matter how we direct the roads (1 unreachable node per tree). Isolated nodes also count as trees and
contribute 1.
def countMinimumUnreachableWarehouses(warehouse_nodes, warehouse_from, warehouse_to):
parent = list(range(warehouse_nodes + 1))
nodes_count = [1] * (warehouse_nodes + 1)
edges_count = [0] * (warehouse_nodes + 1)
def find(i):
root = i
while parent[root] != root:
root = parent[root]
curr = i
while curr != root:
nxt = parent[curr]
parent[curr] = root
curr = nxt
return root
for u, v in zip(warehouse_from, warehouse_to):
root_u = find(u)
root_v = find(v)
if root_u != root_v:
parent[root_u] = root_v
nodes_count[root_v] += nodes_count[root_u]
edges_count[root_v] += edges_count[root_u] + 1
else:
edges_count[root_v] += 1
unreachable_count = 0
for i in range(1, warehouse_nodes + 1):
if parent[i] == i:
if edges_count[i] == nodes_count[i] - 1:
unreachable_count += 1
return unreachable_count
4
Time Complexity: O(V + E · α(V)). V is vertices, E is edges, and α is the Inverse Ackermann function
(nearly constant time).
Space Complexity: O(V) to maintain the DSU structures.