LeetCode 1811 - Find Interview Candidates

LeetCode Problem 1811

Difficulty: 🟡 Medium
Topics: Database

Solution

Problem Understanding

The problem is asking us to identify users who qualify as interview candidates based on their performance in LeetCode contests. We are provided two tables: Contests and Users. The Contests table lists contest IDs along with the user IDs of the gold, silver, and bronze medalists for each contest. The Users table contains the user information including user_id, name, and mail.

A user qualifies as an interview candidate if either of the following two conditions is true:

1. The user won any medal (gold, silver, or bronze) in three or more consecutive contests.
2. The user won gold medals in three or more different contests (the contests do not have to be consecutive).

The task is to return the name and mail of all such users. The problem guarantees that contest IDs are consecutive integers and no IDs are skipped. This makes it simpler to detect consecutive contests using arithmetic on the IDs. Edge cases include users who win medals in non-consecutive contests or users who win multiple medals across overlapping sets of contests.

The output can be in any order.

Approaches

The brute-force approach would be to iterate over every user and check every possible triplet of contests to see if they satisfy either condition. For consecutive contests, we would need to track medal wins for every contest and check for runs of length three, while for gold medals we would count the total distinct contests won. This approach works logically but is inefficient because it requires iterating through every possible combination of contests for every user, which can be very slow for large datasets.

The optimal approach leverages SQL capabilities to handle these conditions more efficiently:

• To detect gold medals in three or more contests, we can group by user_id and count the number of gold medals.
• To detect any medal in three consecutive contests, we can "unpivot" the Contests table so each medal is represented as a separate row per contest. Then we can assign a row number partitioned by user_id and order by contest_id, and use a window function to check if any three contests form consecutive sequences.

This approach reduces the need for nested loops and takes advantage of SQL’s set-based operations and window functions.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(u * c^3)	O(c)	Iterates all triplets of contests for each user; very slow
Optimal	O(c)	O(u * c)	Uses grouping and window functions to efficiently check conditions

Algorithm Walkthrough

1. Unpivot medals: Transform the Contests table into a normalized form with columns user_id, contest_id, and medal_type, so each medal type for each contest becomes a separate row.
2. Identify consecutive medals: Use a window function to assign row numbers partitioned by user_id and ordered by contest_id. Calculate a difference between contest_id and the row number to detect consecutive sequences. If a user has at least three rows with the same difference, it means they won medals in three consecutive contests.
3. Identify gold medal winners: Group the Contests table by gold_medal and count the distinct contests. If the count is 3 or more, the user qualifies for this condition.
4. Combine results: Take the union of the two sets of users found in steps 2 and 3.
5. Join with Users table: Retrieve the name and mail for all qualifying user_ids.
6. Return results: Output the result table with name and mail columns.

Why it works: The algorithm correctly identifies users who meet either of the conditions by using SQL window functions and aggregation. Consecutive contests are detected using the difference between contest_id and row number, which forms a constant value for consecutive sequences. Gold medal winners are identified using simple aggregation. Union ensures we capture all users who satisfy at least one condition.

Python Solution

import sqlite3

def find_interview_candidates():
    query = """
    WITH Medalists AS (
        SELECT contest_id, gold_medal AS user_id FROM Contests
        UNION ALL
        SELECT contest_id, silver_medal AS user_id FROM Contests
        UNION ALL
        SELECT contest_id, bronze_medal AS user_id FROM Contests
    ),
    Consecutive AS (
        SELECT user_id
        FROM (
            SELECT user_id, contest_id, contest_id - ROW_NUMBER() OVER(PARTITION BY user_id ORDER BY contest_id) AS grp
            FROM Medalists
        ) t
        GROUP BY user_id, grp
        HAVING COUNT(*) >= 3
    ),
    GoldWinners AS (
        SELECT gold_medal AS user_id
        FROM Contests
        GROUP BY gold_medal
        HAVING COUNT(*) >= 3
    ),
    Candidates AS (
        SELECT user_id FROM Consecutive
        UNION
        SELECT user_id FROM GoldWinners
    )
    SELECT u.name, u.mail
    FROM Users u
    JOIN Candidates c ON u.user_id = c.user_id;
    """
    return query

Explanation: First, the Medalists CTE flattens the Contests table so every medal is a separate row. Consecutive detects users with three or more consecutive medals using ROW_NUMBER() and the difference trick. GoldWinners finds users with at least three gold medals. The Candidates CTE combines these users. Finally, we join with Users to fetch the required details.

Go Solution

package main

import "database/sql"

func FindInterviewCandidates(db *sql.DB) (*sql.Rows, error) {
    query := `
    WITH Medalists AS (
        SELECT contest_id, gold_medal AS user_id FROM Contests
        UNION ALL
        SELECT contest_id, silver_medal AS user_id FROM Contests
        UNION ALL
        SELECT contest_id, bronze_medal AS user_id FROM Contests
    ),
    Consecutive AS (
        SELECT user_id
        FROM (
            SELECT user_id, contest_id, contest_id - ROW_NUMBER() OVER(PARTITION BY user_id ORDER BY contest_id) AS grp
            FROM Medalists
        ) t
        GROUP BY user_id, grp
        HAVING COUNT(*) >= 3
    ),
    GoldWinners AS (
        SELECT gold_medal AS user_id
        FROM Contests
        GROUP BY gold_medal
        HAVING COUNT(*) >= 3
    ),
    Candidates AS (
        SELECT user_id FROM Consecutive
        UNION
        SELECT user_id FROM GoldWinners
    )
    SELECT u.name, u.mail
    FROM Users u
    JOIN Candidates c ON u.user_id = c.user_id;
    `
    return db.Query(query)
}

Explanation: The Go solution executes the same SQL logic. Differences are mainly syntactical: Go uses db.Query to run the query, and the result must be processed using Rows methods. SQL logic is identical to Python.

Worked Examples

Using the provided example:

1. Unpivot the medals:

contest_id | user_id
190        | 1
190        | 5
190        | 2
191        | 2
191        | 3
191        | 5
192        | 5
192        | 2
192        | 3
193        | 1
193        | 3
193        | 5
194        | 4
194        | 5
194        | 2
195        | 4
195        | 2
195        | 1
196        | 1
196        | 5
196        | 2

1. Compute consecutive sequences per user:

• User 1: contests 190, 193, 196 → not consecutive for any medals, but gold medals in 190, 193, 196 → qualifies.
• User 2: contests 190, 191, 192 → consecutive medals → qualifies.
• User 3: contests 191, 192, 193 → consecutive medals → qualifies.
• User 4: contests 194, 195 → does not meet either condition.
• User 5: contests 190, 191, 192, 193, 194 → consecutive medals → qualifies.

1. Combine candidates: Users 1, 2, 3, 5 → join Users table → final output.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(c)	Each CTE processes the contests linearly; window function is linearithmic but practically linear
Space	O(u * c)	Medalists CTE stores a row per medal per contest; additional space for temporary tables

The solution is efficient because it leverages SQL operations rather than nested loops. Window functions and grouping operations scale well with moderate contest data.

Test Cases

# provided example
assert find_interview_candidates() == [
    ("Sarah", "[email protected]"),
    ("Bob", "[email protected]"),
    ("Alice", "[email protected]"),
    ("Quarz", "[email protected]")
]

# edge: user with exactly 3 consecutive medals
# edge: user with exactly 3 gold medals non-consecutive
# edge: user with medals but not enough consecutive contests
# edge: no user qualifies

|