0

Sliding window conversation scores with percentiles

by Frontier Interview· about 4 hours ago· ⑂ 0 remixes

Question: Sliding window conversation scores with percentiles

Companies: Decagon

Difficulty: Medium

Problem statement

Track conversation quality scores in a sliding window and answer percentile queries over the current window. Reported on 1point3acres' Decagon bank; reconstructed in our own words.

Clarify the setup

A support agent platform scores every finished conversation (say 0 to 100 from an automated grader). Operations:

  • record(timestamp, score): timestamps arrive in non-decreasing order.
  • percentile(p, now): the p-th percentile of the scores recorded in the window (now - W, now].

Ask:

  • Which percentile definition? Use nearest rank: sort the n scores and return the one at rank ceil(p / 100 × n) (rank 1 for p = 0). It always returns a real score, which dashboards prefer. Interpolated percentiles are a follow-up.
  • What range do scores have? Integers 0 to 100 here. That matters a lot: a bounded integer range allows a counting structure.
  • Query rate versus record rate. Dashboards query often (p50, p90, p99 every few seconds); records arrive at conversation rate.

Approach

Brute force: keep the window in a deque, and on each query copy it, sort it, pick the rank. O(n log n) per query.

Bounded integer scores: counts plus a Fenwick tree.

  • A deque of (timestamp, score) holds the window in arrival order. Evicting expired entries from the left is O(1) each, and every entry is evicted at most once.
  • A Fenwick tree over the 101 possible scores holds how many window entries have each score. record adds 1 at score; eviction adds −1.
  • A percentile query is "find the smallest score s whose count of entries <= s reaches the rank". A Fenwick tree answers that with a binary descent in O(log R), where R = 101.

With R this small, a plain count array and a linear scan (101 steps) is also fine and simpler. Say that, then show the Fenwick version as the answer that still works for R = 10,000 (scores with two decimals).

Arbitrary real scores need an order-statistic structure: a sorted list with binary search (Python's bisect.insort is O(n) per insert but a fast memmove; fine to about 10^5 entries), or a balanced tree or skip list with subtree sizes for O(log n). For millions of entries per window, approximate with a t-digest or a histogram sketch and say what error you accept.

Code

import bisect
import math
from collections import deque
from typing import Deque, List, Optional, Tuple


class ScoreWindow:
    """Percentiles over integer scores in [0, max_score] within a time window."""

    def __init__(self, window: float, max_score: int = 100) -> None:
        self.window = window
        self.size = max_score + 1
        self.tree = [0] * (self.size + 1)     # Fenwick over score values, 1-based
        self.events: Deque[Tuple[float, int]] = deque()
        self.top = 1 << (self.size.bit_length() - 1)

    def record(self, timestamp: float, score: int) -> None:
        if not 0 <= score < self.size:
            raise ValueError("score out of range")
        if self.events and timestamp < self.events[-1][0]:
            raise ValueError("timestamps must not go backwards")
        self.events.append((timestamp, score))
        self._add(score, 1)

    def count(self, now: float) -> int:
        self._expire(now)
        return len(self.events)

    def percentile(self, p: float, now: float) -> Optional[int]:
        self._expire(now)
        n = len(self.events)
        if n == 0:
            return None
        rank = max(1, math.ceil(p / 100 * n))
        return self._kth(rank)

    # ---- internals ----------------------------------------------------------
    def _expire(self, now: float) -> None:
        while self.events and self.events[0][0] <= now - self.window:
            _, score = self.events.popleft()
            self._add(score, -1)

    def _add(self, score: int, delta: int) -> None:
        i = score + 1
        while i <= self.size:
            self.tree[i] += delta
            i += i & -i

    def _kth(self, k: int) -> int:
        """Smallest score whose cumulative count reaches k (binary descent)."""
        pos, step = 0, self.top
        while step:
            nxt = pos + step
            if nxt <= self.size and self.tree[nxt] < k:
                pos = nxt
                k -= self.tree[nxt]
            step >>= 1
        return pos  # 1-based position pos + 1 is score pos


class RealScoreWindow:
    """Any real-valued score: sorted list, O(log n) search, O(n) memmove insert."""

    def __init__(self, window: float) -> None:
        self.window = window
        self.events: Deque[Tuple[float, float]] = deque()
        self.sorted: List[float] = []

    def record(self, timestamp: float, score: float) -> None:
        self.events.append((timestamp, score))
        bisect.insort(self.sorted, score)

    def percentile(self, p: float, now: float) -> Optional[float]:
        while self.events and self.events[0][0] <= now - self.window:
            _, score = self.events.popleft()
            del self.sorted[bisect.bisect_left(self.sorted, score)]
        n = len(self.sorted)
        if n == 0:
            return None
        return self.sorted[max(1, math.ceil(p / 100 * n)) - 1]

Worked numbers

A platform handling 2 million conversations a day sees about 23 a second, so a one-hour window holds about 83,000 scores.

  • Brute force: sorting 83,000 values per query is about 83,000 × 17 ≈ 1.4M comparisons, roughly 15 ms in Python. Three percentiles every 5 seconds is tolerable for one dashboard, not for thousands of tenants.
  • Counts plus Fenwick: each record is 7 tree updates (log2 of 101), each query 7 steps. Memory is the deque (83,000 entries) plus 102 counters.
  • If the per-tenant memory of the deque matters, bucket time instead: keep one count array per minute (60 buckets × 101 counters), and a query sums the live buckets. Exact at minute granularity, constant memory per tenant.

Test cases

import math as _math
import random as _random


def _nearest_rank(values, p):
    s = sorted(values)
    return s[max(1, _math.ceil(p / 100 * len(s))) - 1] if s else None


def test_simple_percentiles():
    w = ScoreWindow(window=60)
    for t, s in enumerate([50, 10, 90, 30, 70]):
        w.record(t, s)
    assert w.percentile(50, now=5) == 50
    assert w.percentile(0, now=5) == 10
    assert w.percentile(100, now=5) == 90
    assert w.percentile(90, now=5) == 90
    assert w.percentile(20, now=5) == 10


def test_expiry():
    w = ScoreWindow(window=10)
    w.record(0, 100)
    w.record(5, 0)
    assert w.percentile(100, now=9) == 100
    assert w.percentile(100, now=10) == 0     # t=0 left the window (now - 10, now]
    assert w.percentile(50, now=100) is None
    assert w.count(now=100) == 0


def test_matches_brute_force():
    rng = _random.Random(11)
    w = ScoreWindow(window=50)
    r = RealScoreWindow(window=50)
    events = []
    t = 0.0
    for _ in range(3000):
        t += rng.random() * 2
        s = rng.randint(0, 100)
        w.record(t, s)
        r.record(t, s)
        events.append((t, s))
        if rng.random() < 0.2:
            live = [x for ts, x in events if ts > t - 50]
            p = rng.choice([0, 10, 50, 90, 99, 100])
            assert w.percentile(p, t) == _nearest_rank(live, p) == r.percentile(p, t)

def test_rejects_bad_input():
    w = ScoreWindow(window=10)
    w.record(5, 1)
    for args in ((4, 1), (6, 101), (6, -1)):
        try:
            w.record(*args)
            assert False
        except ValueError:
            pass


def test_large_score_range():
    w = ScoreWindow(window=1000, max_score=9999)
    for i in range(10000):
        w.record(i * 0.01, i)
    assert w.percentile(50, now=100) == 4999
    assert w.percentile(99, now=100) == 9899

Follow-ups

  1. Out-of-order timestamps. Late events (a conversation scored after a delay) break the deque's order. Use time buckets keyed by minute: a late event goes into its own bucket if that bucket is still in the window, and is dropped otherwise.
  2. Interpolated percentiles. Linear interpolation between ranks floor and ceil of p/100 × (n − 1) needs the two neighboring order statistics: two _kth calls.
  3. Many tenants and segments. Percentiles per customer, per intent and per channel multiply the structures. Time-bucketed histograms merge by adding counts, so store per-segment buckets and merge at query time.
  4. Alerting. "Page someone when p10 drops below 40 for 10 minutes": evaluate on a schedule from the same structure and require the condition to hold across consecutive checks to avoid flapping.
  5. Approximate at scale. For unbounded real scores and huge windows, t-digest or DDSketch give mergeable percentiles with bounded relative error and kilobytes of memory.

Interviewer expectations

Mid-level (L4)

  • Correct windowing with a deque and a correct nearest-rank percentile, even if each query sorts.
  • Handles an empty window, p = 0 and p = 100, and the window boundary.
  • Tests against a brute-force reference.

Senior (L5)

  • Uses the bounded score range: counts plus a Fenwick tree (or a count array), with O(log R) or O(R) queries, and explains when the simpler array is enough.
  • Handles real-valued scores with an order-statistic structure and states its costs.
  • Works through window size and query cost with real numbers.

Staff (L6+)

  • Moves to time-bucketed, mergeable histograms for late events, many segments and constant memory.
  • Knows the approximate options (t-digest, DDSketch) and their error guarantees.
  • Connects it to the product: quality dashboards per customer, alert thresholds without flapping.

Sign in to comment, vote or remix.