Find Conflicting Events
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
# Find Conflicting Events
You are given a list of `n` access events. Each event records a single user being active from some region at some moment in time and has three fields:
- `user_id` — a non-empty string identifying the user.
- `region` — a non-empty string naming the region the activity came from (e.g. `"us-east"`).
- `timestamp` — an integer time (e.g. epoch seconds).
You are also given an integer threshold `k`.
Two **distinct** events `i` and `j` are **conflicting** when all of the following hold:
1. **Same user:** `user_id[i] == user_id[j]`.
2. **Different region:** `region[i] != region[j]`.
3. **Close in time:** `abs(timestamp[i] - timestamp[j]) < k` (strictly less than `k`).
Intuitively, the same user cannot plausibly be active from two different regions within a window shorter than `k` — an "impossible travel" style signal worth flagging.
Return **all** conflicting pairs as a list of index pairs `[i, j]` with `i < j`, sorted in ascending order: first by `i`, then by `j`. If there are no conflicting pairs, return an empty list.
## Input format
- `k`: a positive integer threshold.
- `events`: a 0-indexed list where `events[t] = [user_id, region, timestamp]`. Output indices refer to positions in this list, in the order given.
## Output format
- A list of `[i, j]` pairs (`i < j`), sorted ascending by `(i, j)`. Empty list if none.
## Example
```
Input:
k = 100
events = [
["u1", "us-east", 10],
["u1", "us-west", 50],
["u1", "us-east", 200],
["u2", "eu-west", 60],
["u1", "us-west", 180]
]
Output:
[[0, 1], [2, 4]]
```
Explanation, considering only the `u1` events (indices `0, 1, 2, 4`):
- `(0, 1)`: regions `us-east` vs `us-west` differ, `|10 - 50| = 40 < 100` → conflict.
- `(0, 2)`: same region `us-east` → not a conflict.
- `(0, 4)`: `|10 - 180| = 170 \ge 100` → not a conflict.
- `(1, 2)`: `|50 - 200| = 150 \ge 100` → not a conflict.
- `(1, 4)`: same region `us-west` → not a conflict.
- `(2, 4)`: regions `us-east` vs `us-west` differ, `|200 - 180| = 20 < 100` → conflict.
Index `3` belongs to user `u2` and has no same-user partner, so it never conflicts.
## Constraints
- $1 \le n \le 10^5$.
- $1 \le k$, and `k` fits in a signed 64-bit integer.
- Timestamps fit in a signed 64-bit integer and may be negative, zero, or duplicated.
- `user_id` and `region` are non-empty strings.
- An efficient solution groups events by `user_id`, sorts each group by `timestamp`, and uses a sliding window over the sorted timestamps so that work is proportional to the number of actual conflicts rather than to all $O(n^2)$ pairs.
Quick Answer: This question evaluates algorithmic problem-solving in coding and algorithms, focusing on grouping, sorting, and sliding-window techniques applied to time-constrained event data. It is commonly asked to test the ability to design an efficient solution over a brute-force pairwise comparison, assessing practical, applied coding skill.
You are given `n` access events supplied as three parallel, index-aligned arrays plus an integer threshold `k`:
- `user_ids[t]` — a non-empty string identifying the user for event `t`.
- `regions[t]` — a non-empty string naming the region event `t` came from (e.g. `"us-east"`).
- `timestamps[t]` — an integer time (e.g. epoch seconds) for event `t`. May be negative, zero, or duplicated.
Two **distinct** events `i` and `j` are **conflicting** when ALL of the following hold:
1. **Same user:** `user_ids[i] == user_ids[j]`.
2. **Different region:** `regions[i] != regions[j]`.
3. **Close in time:** `abs(timestamps[i] - timestamps[j]) < k` (strictly less than `k`).
Intuitively, the same user cannot plausibly be active from two different regions within a window shorter than `k` — an "impossible travel" signal worth flagging.
Return **all** conflicting pairs as a list of index pairs `[i, j]` with `i < j`, sorted ascending first by `i`, then by `j`. Return an empty list if there are no conflicts.
Example: `k = 100`, `user_ids = ["u1","u1","u1","u2","u1"]`, `regions = ["us-east","us-west","us-east","eu-west","us-west"]`, `timestamps = [10,50,200,60,180]` → `[[0, 1], [2, 4]]`. Pair (0,1): different regions, |10-50|=40<100. Pair (2,4): different regions, |200-180|=20<100. Index 3 (user u2) has no same-user partner.
An efficient approach groups events by `user_id`, sorts each group by timestamp, and slides a window so the work is proportional to the actual conflicts rather than to all O(n^2) pairs.
Constraints
- 1 <= n <= 10^5
- 1 <= k, and k fits in a signed 64-bit integer
- Timestamps fit in a signed 64-bit integer and may be negative, zero, or duplicated
- user_id and region are non-empty strings
- The three input arrays user_ids, regions, timestamps are index-aligned and have the same length n
- Output pairs use i < j and are sorted ascending by (i, j)
Examples
Input: (100, ["u1", "u1", "u1", "u2", "u1"], ["us-east", "us-west", "us-east", "eu-west", "us-west"], [10, 50, 200, 60, 180])
Expected Output: [[0, 1], [2, 4]]
Explanation: u1 events are at indices 0,1,2,4. (0,1): us-east vs us-west, |10-50|=40<100 -> conflict. (2,4): us-east vs us-west, |200-180|=20<100 -> conflict. (0,2) same region; (0,4) |170|>=100; (1,4) same region. Index 3 (u2) has no same-user partner.
Input: (100, [], [], [])
Expected Output: []
Explanation: No events, so no pairs.
Input: (5, ["a"], ["r1"], [0])
Expected Output: []
Explanation: A single event cannot form a pair.
Input: (100, ["u1", "u1"], ["r1", "r1"], [10, 20])
Expected Output: []
Explanation: Same user and close in time, but the region is identical, so it is not a conflict.
Input: (10, ["u1", "u1"], ["r1", "r2"], [0, 10])
Expected Output: []
Explanation: Different region but |0-10|=10 is NOT strictly less than k=10, so no conflict (boundary case).
Input: (100, ["u1", "u1"], ["r1", "r2"], [-50, 20])
Expected Output: [[0, 1]]
Explanation: Negative timestamp handled: different region, |-50-20|=70<100 -> conflict.
Input: (1, ["u1", "u1"], ["a", "b"], [5, 5])
Expected Output: [[0, 1]]
Explanation: Duplicate timestamps: |5-5|=0<1 and regions differ -> conflict.
Input: (100, ["u1", "u1", "u1"], ["r2", "r1", "r3"], [100, 50, 60])
Expected Output: [[0, 1], [0, 2], [1, 2]]
Explanation: All three u1 events are mutually within k=100 with pairwise-different regions. Note index 0 has the largest timestamp; the final sort by (i, j) restores index order even though processing was timestamp-ordered.
Input: (100, ["u1", "u2", "u1", "u2"], ["a", "a", "b", "b"], [0, 0, 10, 10])
Expected Output: [[0, 2], [1, 3]]
Explanation: Two users interleaved. u1: indices 0,2 differ in region within window -> (0,2). u2: indices 1,3 -> (1,3). Cross-user pairs are ignored.
Hints
- Events for different users can never conflict, so group indices by user_id first and handle each user independently.
- Within one user's events, sort by timestamp. After sorting, for any right index, the events with abs(ts diff) < k form a contiguous window ending at right — advance a left pointer while timestamps[right] - timestamps[left] >= k.
- Inside the window, only pairs with DIFFERENT regions conflict. Because you sorted by timestamp (not original index), remember to emit each pair as (min(i, j), max(i, j)) using the ORIGINAL indices, then sort all collected pairs by (i, j) at the end.
- Use strict '<' for the time check: a difference exactly equal to k is NOT a conflict.