Find Users with High Token Usage

Difficulty: Easy | Acceptance: 56.80% | Paid: No Topics: N/A

Problem Description

Table: Tokens

There is no primary key for this table. It may contain duplicates.

Write a SQL query to find the user_id of users who have used more than 1000 tokens in total.

Return the result table in any order.

Table of Contents

• Examples
• Constraints
• Group By with Having
• Subquery Approach
• Window Function Approach

Examples

Example 1

Input:

Tokens table:
+---------+------------+
| user_id | tokens_used|
+---------+------------+
| 1       | 500        |
| 1       | 600        |
| 2       | 300        |
| 3       | 1200       |
+---------+------------+

Output:

+---------+
| user_id |
+---------+
| 1       |
| 3       |
+---------+

Explanation:

• User 1 has used 500 + 600 = 1100 tokens, which is more than 1000.
• User 2 has used 300 tokens, which is not more than 1000.
• User 3 has used 1200 tokens, which is more than 1000.

Example 2

Input:

Tokens table:
+---------+------------+
| user_id | tokens_used|
+---------+------------+
| 1       | 1000       |
| 2       | 2000       |
+---------+------------+

Output:

+---------+
| user_id |
+---------+
| 2       |
+---------+

Explanation:

• User 1 has used exactly 1000 tokens, which is not more than 1000.
• User 2 has used 2000 tokens, which is more than 1000.

Constraints

- 1 <= tokens_used <= 10^4
- The number of rows in Tokens is at most 10^4

Group By with Having

Intuition Group the records by user_id, sum the tokens for each user, and filter using the HAVING clause to find users exceeding the threshold.

Steps

• Group the table by user_id
• Calculate the sum of tokens_used for each group
• Filter groups where the sum is greater than 1000
• Select the user_id from the filtered groups

import pandas as pd

def find_users(tokens: pd.DataFrame) -> pd.DataFrame:
    result = tokens.groupby('user_id')['tokens_used'].sum().reset_index()
    result = result[result['tokens_used'] > 1000]
    return result[['user_id']]

Complexity

• Time: O(n) where n is the number of rows in the Tokens table
• Space: O(k) where k is the number of unique users
• Notes: This is the most straightforward and efficient approach for this problem.

Subquery Approach

Intuition First calculate the total tokens for each user in a subquery, then filter the results in the outer query.

Steps

• Create a subquery that groups by user_id and sums tokens_used
• In the outer query, select user_id where the sum is greater than 1000

import pandas as pd

def find_users(tokens: pd.DataFrame) -> pd.DataFrame:
    aggregated = tokens.groupby('user_id', as_index=False)['tokens_used'].sum()
    result = aggregated[aggregated['tokens_used'] > 1000]
    return result[['user_id']]

Complexity

• Time: O(n) where n is the number of rows in the Tokens table
• Space: O(k) where k is the number of unique users
• Notes: Similar to the GROUP BY approach but uses a subquery for filtering.

Window Function Approach

Intuition Use window functions to calculate running totals and then filter for users exceeding the threshold.

Steps

• Use SUM() as a window function partitioned by user_id
• Filter rows where the total sum exceeds 1000
• Select distinct user_ids

import pandas as pd

def find_users(tokens: pd.DataFrame) -> pd.DataFrame:
    tokens['total'] = tokens.groupby('user_id')['tokens_used'].transform('sum')
    result = tokens[tokens['total'] > 1000][['user_id']].drop_duplicates()
    return result

Complexity

• Time: O(n) where n is the number of rows in the Tokens table
• Space: O(n) for the window function results
• Notes: Less efficient than GROUP BY approach but demonstrates window function usage.