mock day · 60-minute graph DSA mock · chat-system review
Tonight's goal: solve two graph problems under interview pressure, then explain the chat-system design aloud using fan-out, WebSockets, and queues.
Tonight's protocol
Use the mock-day protocol: speak first, code second, compare after the timer.
0:00-0:05: answer the warm-up MCQs below. If you miss one, read only its explanation, then start the mock.
0:05-0:35: solve Problem 1. Before typing, say the pattern, brute force, better approach, and time/space complexity aloud.
0:35-1:05: solve Problem 2 with the same rule. If stuck at minute 25 of either problem, read only the pattern name in the menu and use the last 5 minutes.
1:05-1:15: compare both attempts. Write one note per miss: invariant, bug, or edge case.
Source invariant: "DFS floods everything reachable in one component; count how many times you must start a new flood. The grid itself is the adjacency list — mark visited in place."
2. A clone routine recurses before recording the clone. What breaks?
Source invariant: "A hashmap from original node to its clone doubles as the visited set — create the clone on first visit, reuse it ever after."
3. A prerequisite graph cannot peel every course. What does that mean?
Source invariant: "A dependency order exists iff the directed graph has no cycle — detect it with three-color DFS or Kahn's in-degree peeling."
4. Which move makes Pacific Atlantic efficient?
Source invariant: "Instead of asking where each cell drains, flood inward from each ocean and intersect the two reachable sets."
5. Which statement chooses the right shortest-path tool?
Source invariants: "First decide what a node and an edge are — here words, one letter apart — then BFS finds the shortest unweighted path." Also: "Dijkstra is BFS with a priority queue: always settle the closest unsettled node, because no cheaper path to it can appear later."
6. Which line belongs in the chat-system review?
Source invariant: "Chat is fan-out over persistent connections: WebSockets hold the pipe open, queues absorb bursts, and presence and receipts live as separate small services."
Self-check gate
Pass tonight only if all three are true
You stated node, edge, traversal choice, and complexity before coding both DSA problems.
You completed the timed attempts without solution text during the 60-minute mock.
You explained the chat design aloud with fan-out, WebSocket gateways, delivery queues, presence, receipts, and at least two failure modes.
If a DSA item fails, add that exact problem to the next graph revision list and tag the miss as pattern choice, complexity, implementation, or edge case. If the chat review fails, add "chat fan-out/WebSocket/queues redraw" to the next system-design revision.