Find Active Users

Problem

Table: Users

+-------------+----------+
| Column Name | Type     |
+-------------+----------+
| user_id     | int      |
| item        | varchar  |
| created_at  | datetime |
| amount      | int      |
+-------------+----------+
This table may contain duplicate records.
Each row includes the user ID, the purchased item, the date of purchase, and the purchase amount.

Write a solution to identify active users. An active user is a user that has made a second purchase **within 7 days **of any other of their purchases.

For example, if the ending date is May 31, 2023. So any date between May 31, 2023, and June 7, 2023 (inclusive) would be considered “within 7 days” of May 31, 2023.

Return a list of user_id which denotes the list of active users in any order.

The result format is in the following example.

Examples

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


Input: Users table:
+---------+-------------------+------------+--------+ 
| user_id | item              | created_at | amount |  
+---------+-------------------+------------+--------+
| 5       | Smart Crock Pot   | 2021-09-18 | 698882 |
| 6       | Smart Lock        | 2021-09-14 | 11487  |
| 6       | Smart Thermostat  | 2021-09-10 | 674762 |
| 8       | Smart Light Strip | 2021-09-29 | 630773 |
| 4       | Smart Cat Feeder  | 2021-09-02 | 693545 |
| 4       | Smart Bed         | 2021-09-13 | 170249 |
+---------+-------------------+------------+--------+ 
Output:
+---------+
| user_id | 
+---------+
| 6       | 
+---------+
Explanation: 
- User with user_id 5 has only one transaction, so he is not an active user.
- User with user_id 6 has two transaction his first transaction was on 2021-09-10 and second transation was on 2021-09-14. The distance between the first and second transactions date is <= 7 days. So he is an active user. 
- User with user_id 8 has only one transaction, so he is not an active user.  
- User with user_id 4 has two transaction his first transaction was on 2021-09-02 and second transation was on 2021-09-13. The distance between the first and second transactions date is > 7 days. So he is not an active user.

Solution

Method 1 – SQL Self-Join and Date Comparison

Intuition

To find active users, we need to check for each user if there exists at least one pair of purchases where the difference between their dates is at most 7 days (inclusive). We can self-join the table on user_id and compare the created_at dates.

Approach

Self-join the Users table on user_id.
For each pair of purchases (u1, u2), check if the absolute difference between their created_at dates is ≤ 7 days and the purchases are not the same row.
Select distinct user_ids that satisfy this condition.

Code

1
2
3
4
5
6


SELECT DISTINCT u1.user_id
FROM Users u1
JOIN Users u2
  ON u1.user_id = u2.user_id
 AND u1.created_at <> u2.created_at
WHERE ABS(DATEDIFF(u1.created_at, u2.created_at)) <= 7;

1
2
3
4
5
6


SELECT DISTINCT u1.user_id
FROM Users u1
JOIN Users u2
  ON u1.user_id = u2.user_id
 AND u1.created_at <> u2.created_at
WHERE ABS(u1.created_at::date - u2.created_at::date) <= 7;

1
2
3
4
5
6
7


def find_active_users(users: 'pd.DataFrame') -> 'pd.DataFrame':
    users = users.copy()
    users['created_at'] = pd.to_datetime(users['created_at'])
    merged = users.merge(users, on='user_id')
    mask = (merged['created_at_x'] != merged['created_at_y']) & (abs((merged['created_at_x'] - merged['created_at_y']).dt.days) <= 7)
    active = merged.loc[mask, 'user_id'].drop_duplicates().to_frame()
    return active

Complexity

⏰ Time complexity: O(n^2) in the worst case, where n is the number of purchases, due to the self-join.
🧺 Space complexity: O(n), for storing the result set.

Problem#

Examples#

Solution#

Method 1 – SQL Self-Join and Date Comparison#

Intuition#

Approach#

Code#

Complexity#