Katkat
Back

Implement Disease and Friend Snapshot Models

OpenAISoftware Engineer · Onsite
HardSoftware EngineerOnsiteCoding & Algorithms

Last updated

This question evaluates skills in graph-based modeling and temporal state simulation as well as the design and implementation of snapshot-capable directed graph data structures, covering competencies in propagation and state transitions (including immunity, recovery, and death), efficient snapshotting, querying, ranking, and diffing of follow relationships. It is commonly asked to assess algorithmic reasoning, correctness under edge cases, and complexity-aware implementation; the problem belongs to the Coding & Algorithms domain and tests both conceptual understanding of dynamic graph behavior and practical application-level implementation of data structures and immutable snapshots.

You are asked to solve two independent coding problems.

Problem 1: Simulate disease spread on a contact graph

There are n people labeled 0 through n - 1. An undirected edge between two people means the disease can spread between them. Time advances in whole days, and all state transitions for a day are based on the state at the start of that day unless otherwise stated.

Implement the following follow-ups:

  1. daysToInfectAll(n, edges, initiallyInfected): Initially, every person is susceptible except the initially infected people. Each day, every infected person infects all susceptible neighbors. Return the minimum number of days until everyone is infected. Return -1 if some people can never be infected.

  2. daysToFinishWithImmune(n, edges, initiallyInfected, initiallyImmune): Some people are initially immune. Immune people cannot be infected and do not transmit the disease. Return how many days it takes until no new infection can occur. Also be prepared to report which susceptible people remain uninfected.

  3. daysToStableAfterRecovery(n, edges, initiallyInfected, initiallyImmune, recoveryDays): An infected person remains contagious for recoveryDays days after becoming infected, then becomes immune at the end of that day. Return the first day when the system is stable, meaning no infected people remain and no future infections are possible.

  4. Extend the model with a Dead state. The input provides either a per-person terminal outcome or a deterministic predicate such as willDie(person), plus the number of days before the terminal transition. Dead people cannot be infected and cannot transmit. Return the day the system becomes stable and the final count of susceptible, infected, immune, and dead people.

Clarify edge cases such as an empty initial infection set, disconnected components, simultaneous infection and recovery, and whether recovery or death happens before or after that day’s transmission.

Problem 2: Implement a friend-circle snapshot data structure

Implement a class FriendCircle supporting directed follow relationships between users.

Required operations:

  1. follow(userId, targetId): userId follows targetId.
  2. unfollow(userId, targetId): userId stops following targetId if the relationship exists.
  3. snapshot(): Capture an immutable snapshot of the current follow graph and return a snapshot id.
  4. getFriends(snapshotId, userId): Given a snapshot id, return all users followed by userId at that snapshot.
  5. recommendFriends(snapshotId, userId, k): Given a snapshot id, recommend up to k users that userId does not already follow. A reasonable ranking rule is to recommend two-hop candidates: if userId follows a and a follows x, then x is a candidate. Rank candidates by the number of mutual intermediate users, then by user id or another deterministic tie-breaker.
  6. diffFriends(snapshotIdA, snapshotIdB, userId): Compare two snapshots and return the users added to and removed from userId’s follow list.

Be prepared to discuss API design, whether snapshot-specific logic belongs in FriendCircle or a separate Snapshot abstraction, time and space complexity, and how to avoid copying the entire graph on every snapshot.