Count users over n connections

Given a stream of relationship events in the form [[user_a, user_b, op], ...], where op ∈ {"connect", "disconnect"}, treat connections as undirected edges. Process events in order, updating the current graph. After all events, return the count of users whose number of current connections is strictly greater than a given integer n. Specify and implement an efficient approach that handles up to 100,000 events and users appearing lazily.

What a Strong Answer Covers

• A clear algorithm with the right data structures and enough pseudocode or code-level detail to implement it.
• A correctness argument that explains why the algorithm covers all required cases.
• Time and space complexity, plus at least one alternative approach when relevant.
• Focused tests for normal cases, edge cases, and failure modes.

Follow-up Questions

• How would the approach change if the input were streaming or too large for memory?
• What invariants would you assert in production code?
• Which tests would catch off-by-one, duplicate, or tie-breaking bugs?

Count Users Over n Connections

You are given a stream of relationship events in the form events = [[user_a, user_b, op], ...], where op is either "connect" or "disconnect". Treat each connection as an undirected edge between two users.

Process the events in order, updating the current graph:

• "connect" adds an undirected edge between user_a and user_b. If the edge already exists, it has no additional effect (no double counting).
• "disconnect" removes the undirected edge between user_a and user_b if it exists; otherwise it has no effect.

Users appear lazily — a user exists once they show up in any event. After processing all events, return the count of users whose current number of connections (degree) is strictly greater than the given integer n.

Design an efficient approach that scales to up to 100,000 events and users.

Example

events = [["a","b","connect"], ["a","c","connect"], ["a","d","connect"]], n = 2

User a ends with degree 3 (connected to b, c, d); b, c, d each have degree 1. Only a has degree > 2, so the answer is 1.

Constraints

• 1 <= number of events <= 100000 (the stream may also be empty)
• Each event is [user_a, user_b, op] with op in {"connect", "disconnect"}
• 0 <= n
• Users appear lazily — a user exists once referenced in any event
• Connections are undirected; connect/disconnect on an already-present/absent edge is idempotent (no double counting)

Hints

1. Maintain an adjacency set per user so that a repeated "connect" on the same pair does not increase the degree twice, and a "disconnect" on a non-existent edge is a no-op.
2. A user's degree is simply the size of their adjacency set. After processing all events, count how many users have a set size strictly greater than n.
3. Using sets keeps each connect/disconnect O(1) on average, so the whole stream is processed in linear time — important for up to 100,000 events.

Solution

Solution Alignment

The prompt asks for an implementation-level answer. The safest way to present it is to define the state, maintain clear invariants, then walk through complexity and tests.

Problem Restatement

Given a stream of relationship events in the form [[user_a, user_b, op], ...], where op ∈ {"connect", "disconnect"}, treat connections as undirected edges. Process events in order, updating the current graph. After all events, return the count of users whose number of current connections is strictly greater than a given integer n. Specify and implement an efficient approach that handles up to 100,000 events and users appearing lazily.

Recommended Approach

Model each reachable configuration as a graph state and choose the traversal by edge cost: BFS for unweighted shortest paths, Dijkstra for non-negative weighted paths, or topological DP for DAGs. Track visited states at the correct granularity so cycles do not cause repeated work.

Correctness

The implementation should maintain an invariant after each loop or operation that directly matches the problem statement. At termination, that invariant implies the returned value has considered every valid candidate exactly once, or has preserved the required data-structure state after every API call.

Complexity

BFS is O(V + E) time and O(V) space for a standard graph. Expanded-state problems multiply those bounds by the number of state dimensions.

Edge Cases and Tests

Disconnected graph, source equals target, cycles, duplicate edges, unreachable target, and whether the answer counts nodes, edges, moves, or transfers.