Quick Overview

This interview question evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer for Count users over n connections states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Count users over n connections

Company: Coinbase

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

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.

Quick Answer: This interview question evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer for Count users over n connections states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

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)

Examples

Input: ([['u1', 'u2', 'connect'], ['u2', 'u3', 'disconnect']], 0)

Expected Output: 2

Explanation: u1-u2 are connected (each degree 1). The u2-u3 disconnect targets an edge that was never created, so it is a no-op (u3 has degree 0). With n=0, u1 and u2 (degree 1 > 0) qualify, u3 does not. Answer: 2.

Input: ([['a', 'b', 'connect'], ['a', 'c', 'connect'], ['a', 'd', 'connect']], 2)

Expected Output: 1

Explanation: a connects to b, c, d (degree 3); b, c, d each have degree 1. Only a has degree > 2. Answer: 1.

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.

Loading coding console...