Between the Clicks

A medium Python interview practice problem on DataDriven. Write the Python and run it against test cases, with instant feedback.

Domain
Python
Difficulty
medium
Seniority
mid
Asked in
Google

Problem

Our click stream reaches us out of time order, with each event carrying a user and a ts in seconds. Reconstruct every user's sessions, where a session is a run of that user's clicks with no more than gap seconds between one and the next, and report each session's user, first and last timestamp, and click count, listed by user name and then earliest session first.

Clicks arrive scrambled. Find where one visit ends and the next begins.

Example 1

Input:

gap = 1800, events = [{"ts":800,"user":"u2"},{"ts":5000,"user":"u1"},{"ts":1000,"user":"u1"},{"ts":1500,"user":"u1"},{"ts":1500,"user":"u1"}]

Output:

[{"end":1500,"user":"u1","start":1000,"clicks":3},{"end":5000,"user":"u1","start":5000,"clicks":1},{"end":800,"user":"u2","start":800,"clicks":1}]

Example 2

Input:

gap = 1800, events = [{"ts":0,"user":"a"},{"ts":1800,"user":"a"},{"ts":3601,"user":"a"}]

Output:

[{"end":1800,"user":"a","start":0,"clicks":2},{"end":3601,"user":"a","start":3601,"clicks":1}]

Worked solution and explanation

Why this problem exists in real interviews

This is sessionization wearing an ad-tech costume. The skill being probed is whether you can carve one key's time-ordered events into sessions by an inter-event gap. Anyone can bucket the events by user. The thing that separates candidates is noticing the word 'out of order': at-least-once delivery means arrival order is NOT time order, so before you can reason about gaps at all you have to restore each user's timeline. Skip that and a click that showed up late lands next to the wrong neighbor, so it reads as a brand-new session or blows a hole in an existing one. Your session count comes out wrong and so does every boundary.

Break down the requirements

Step 1: Sort once, by user then time

sorted(events, key=lambda e: (e['user'], e['ts'])) does both jobs the problem hinges on in a single step: the user component co-locates each person's clicks, and the ts component restores time order inside each user's run. This is the line a weaker answer skips when it just counts per user, throwing away the ordering the rest of the problem lives on.

Step 2: Walk the ordered stream, extending or splitting

Keep a running list of session records. For each event, look at the last record: if it belongs to the SAME user and this timestamp is within gap of that record's end, fold the click in (push end forward, bump clicks). Otherwise append a fresh session starting here. The boundary is inclusive: a difference exactly equal to gap stays in the same session.

Step 3: Why there is no final flush

Because you mutate the open session in place as each click arrives, the record is already complete the moment its last click is folded in. There is no dangling session to append after the loop, and the user-equality guard in the comparison is what stops one user's trailing click from fusing with the next user's first click when their raw timestamps happen to sit close together.

The solution

One global sort, then a single gap scan
def sessionize(events, gap):
    ordered = sorted(events, key=lambda e: (e["user"], e["ts"]))
    sessions = []
    for e in ordered:
        user, ts = e["user"], e["ts"]
        current = sessions[-1] if sessions else None
        if current and current["user"] == user and ts - current["end"] <= gap:
            current["end"] = ts
            current["clicks"] += 1
        else:
            sessions.append({"user": user, "start": ts, "end": ts, "clicks": 1})
    return sessions
Walk in arrival order (wrong)
Bucket by user and count, or walk events as they were delivered. A late click at ts 5000 that arrives first, before 1000 and 1500, makes the very first comparison a 3500s jump and splits u1's single early visit incorrectly. The time dimension is gone or scrambled.
Sort by (user, ts), then scan (right)
Sorting puts u1 in order 1000, 1500, 5000. Now 1500-1000=500 keeps them together and 5000-1500=3500 opens a new session. Two sessions, correct boundaries, regardless of the order the events were delivered in.

Common follow-up questions