How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Coinbase.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Coinbase during technical interviews.

Count users over n connections | Coinbase Coding Question

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.

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

Expected Output: 0

Explanation: a has degree exactly 3, which is not strictly greater than n=3. No user qualifies. Answer: 0.

Input: ([['a', 'b', 'connect'], ['a', 'b', 'connect'], ['a', 'b', 'disconnect']], 0)

Expected Output: 0

Explanation: The duplicate connect is idempotent (a-b edge added once). The disconnect then removes it, leaving both a and b at degree 0. With n=0, nobody has degree > 0. Answer: 0.

Input: ([], 0)

Expected Output: 0

Explanation: Empty event stream — no users exist, so the count is 0.

Input: ([['x', 'y', 'connect']], 0)

Expected Output: 2

Explanation: x and y are connected, each with degree 1 > 0. Both qualify. Answer: 2.

Input: ([['a', 'b', 'connect'], ['b', 'c', 'connect'], ['c', 'a', 'connect'], ['a', 'b', 'disconnect']], 1)

Expected Output: 1

Explanation: Triangle a-b-c is formed, then a-b is removed. Final degrees: a=1 (to c), b=1 (to c), c=2 (to a and b). With n=1, only c (degree 2) is strictly greater. Answer: 1.

Input: ([['a', 'b', 'disconnect']], 0)

Expected Output: 0

Explanation: Disconnecting an edge that was never connected is a no-op; both a and b end at degree 0. Answer: 0.

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

Expected Output: 1

Explanation: The repeated a-b connect does not add a second edge. Final degrees: a=2 (b and c), b=1, c=1. With n=1, only a (degree 2) qualifies. Answer: 1.

Hints

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.
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.
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.

Quick Overview