User ID Logs: Parse Access Logs to Find Active Users Within a Time Window

Question

## Problem

You are given a list of log entries. Each entry has a `user_id` (str) and a `timestamp` (int, Unix seconds). Given a time window `[start, end]` (inclusive), return a sorted list of user IDs that appear at least `min_events` times in that window.

```python
def active_users(
    logs: list[dict],
    start: int,
    end: int,
    min_events: int
) -> list[str]:
    # logs: [{"user_id": str, "timestamp": int}]
    pass
```

**Example:**
```
logs = [
  {"user_id": "u1", "timestamp": 100},
  {"user_id": "u2", "timestamp": 110},
  {"user_id": "u1", "timestamp": 120},
  {"user_id": "u1", "timestamp": 150},
  {"user_id": "u2", "timestamp": 200}
]
active_users(logs, start=100, end=160, min_events=2)
-> ["u1"]  (u1 appears 3 times in [100,160]; u2 appears once)
```

## Follow-ups

1. If logs are sorted by timestamp, how can you use binary search to speed up window filtering?
2. How would you answer many different `[start, end]` window queries efficiently (offline vs. online)?
3. If user IDs are numeric and dense, is there a more memory-efficient structure than a hash map?
4. How would you scale this to 1 billion log entries that do not fit in memory?

User ID Logs: Parse Access Logs to Find Active Users Within a Time Window

Question Details

Full Details

Topics

More from Roblox