Space
Open
Interview
From Fieldwork
Scales
Archive
It's about satisfying uniqueness constraints, aka there is only one choice at every given node's prerequisite satisfaction.
We can think about this in terms of determinism and degrees of freedom. Locks and queues.
The reward for thinking through these topics isn't in the salary. You are seeking the removal of cognitive load.
This is what it means to be able and willing to sit with a problem for a long time and think through its implications. No, the solving part isn't important. Understanding is the important part. Making connections is the important part.
class Solution:
from collections import deque, defaultdict
def sequenceReconstruction(self, nums, sequences):
# 1. Build the graph and calculate in-degrees
adj = defaultdict(list)
in_degree = {num: 0 for num in nums}
nodes = set()
for seq in sequences:
for i in range(len(seq) - 1):
u, v = seq[i], seq[i+1]
adj[u].append(v)
in_degree[v] += 1
nodes.add(u)
nodes.add(v)
# 2. Initialize the queue with nodes having 0 in-degree
queue = deque([node for node in nums if in_degree[node] == 0])
reconstructed_seq = []
# 3. Process the graph
while queue:
# CRITICAL STEP: If there's more than one choice, the sequence isn't unique
if len(queue) > 1:
return False
curr = queue.popleft()
reconstructed_seq.append(curr)
for neighbor in adj[curr]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
queue.append(neighbor)
# 4. Check if the reconstructed sequence matches the target nums
return reconstructed_seq == numsPractice bench
Drafts stay on this device.
What is still unclear, or what would change the explanation?
Saved on this device · one draft per mode