Time-Weighted Moving Average over Irregular Ticks

Weight each price by how long it prevailed instead of counting ticks. Keep the window's ticks in a queue with a running sum of price times duration between consecutive ticks. On a query, evict ticks that no longer prevail, trim the first interval to the window start and extend the latest price to now. O(1) amortized per tick.

mediumPattern: Sliding window·From Devana's Bloomberg question set

Problem

Ticks for an instrument arrive at irregular times: sometimes thousands a second, sometimes none for a minute. You need the time-weighted average price over the last five minutes, where each price counts for as long as it was the latest price.

A plain average of the last n ticks is wrong: a price that held for four minutes and one that lasted a second would count the same. Write a class with push(ts, price) and value(now), which returns the time-weighted average over [now - window, now].

class TimeWeightedAverage:
    def __init__(self, window: int = 300): ...
    def push(self, ts: int, price: float) -> None: ...
    def value(self, now: int) -> float | None: ...

This is one of Devana's own questions, written in the style of Bloomberg's interviews. It is not a question leaked from Bloomberg, and Devana is not affiliated with Bloomberg.

Constraints

• Each price holds from its tick until the next tick; the latest one holds until now.
• Timestamps passed to push and value never decrease, and now is at least the latest tick.
• If the oldest tick still held is after the window start, average over the time since that tick.
• With no ticks, return None; when the covered time is zero, return the latest price.
• O(1) amortized per tick, with memory bounded by the ticks inside the window.

Examples

Input:  window = 300
        push(0, 100); push(240, 200); value(300)
Output: 120.0

Input:  window = 300
        push(0, 100); push(240, 200); value(600)
Output: 200.0

Hints

Open one at a time, and try the problem again after each.

Approach: from brute force to optimal

How to say it in the interview

Describe the step function, even in words: "price against time; the average is area over width." That framing makes the eviction rule and the two partial ends obvious to the interviewer. Then state O(1) amortized, and raise floating-point drift in the running sum before they do.

Solution

Python

from collections import deque

class TimeWeightedAverage:
    def __init__(self, window=300):
        self.window = window
        self.ticks = deque()   # (ts, price), oldest first
        self.area = 0.0        # sum of price * duration between consecutive ticks

    def push(self, ts, price):
        if self.ticks:
            last_ts, last_price = self.ticks[-1]
            self.area += last_price * (ts - last_ts)
        self.ticks.append((ts, price))
        self._evict(ts - self.window)

    def value(self, now):
        start = now - self.window
        self._evict(start)
        if not self.ticks:
            return None
        first_ts, first_price = self.ticks[0]
        last_ts, last_price = self.ticks[-1]
        begin = max(first_ts, start)
        area = (self.area
                + last_price * (now - last_ts)          # the latest price runs to now
                - first_price * (begin - first_ts))     # cut the first interval at the start
        span = now - begin
        return area / span if span > 0 else last_price

    def _evict(self, start):
        # The front price no longer prevails once the next tick is at or before start.
        while len(self.ticks) >= 2 and self.ticks[1][0] <= start:
            (t0, p0), (t1, _) = self.ticks[0], self.ticks[1]
            self.area -= p0 * (t1 - t0)
            self.ticks.popleft()

JavaScript

class TimeWeightedAverage {
  constructor(window = 300) {
    this.window = window;
    this.ticks = []; // [ts, price], oldest first, from this.head
    this.head = 0;
    this.area = 0;   // sum of price * duration between consecutive ticks
  }

  push(ts, price) {
    if (this.size() > 0) {
      const [lastTs, lastPrice] = this.ticks[this.ticks.length - 1];
      this.area += lastPrice * (ts - lastTs);
    }
    this.ticks.push([ts, price]);
    this.evict(ts - this.window);
  }

  value(now) {
    const start = now - this.window;
    this.evict(start);
    if (this.size() === 0) return null;
    const [firstTs, firstPrice] = this.ticks[this.head];
    const [lastTs, lastPrice] = this.ticks[this.ticks.length - 1];
    const begin = Math.max(firstTs, start);
    const area = this.area
      + lastPrice * (now - lastTs)       // the latest price runs to now
      - firstPrice * (begin - firstTs);  // cut the first interval at the start
    const span = now - begin;
    return span > 0 ? area / span : lastPrice;
  }

  size() {
    return this.ticks.length - this.head;
  }

  evict(start) {
    // The front price no longer prevails once the next tick is at or before start.
    while (this.size() >= 2 && this.ticks[this.head + 1][0] <= start) {
      const [t0, p0] = this.ticks[this.head];
      this.area -= p0 * (this.ticks[this.head + 1][0] - t0);
      this.head++;
    }
    if (this.head > 1024 && this.head * 2 > this.ticks.length) {
      this.ticks = this.ticks.slice(this.head);
      this.head = 0;
    }
  }
}

Both versions are tested against the same cases, including every example on this page.

• value evicts too, because time moves on between pushes: a query long after the last tick must still drop prices that stopped prevailing.
• The latest tick is never evicted. It is the price in force now, however old it is.
• A running sum of floats drifts after millions of additions and subtractions. In production, keep prices in integer units such as cents, or recompute the sum from the queue every so often.

Follow-up questions

Common mistakes

• Averaging the last n ticks, which ignores how long each price held.
• Evicting a tick as soon as its own timestamp leaves the window, when it may still be the price in force at the window start.
• Forgetting the open interval from the latest tick to now.
• Recomputing the whole window on every tick, which is O(k) when thousands arrive a second.

Practice it in a mock interview

Reading a solution and explaining one under questioning are different skills. The button below starts this problem as a voice mock interview with Josh, Devana's AI interviewer, with an editor that runs your code.

Practice this problem in a mock interview

Related problems

• Deduplicate a Stream of Retried Events: A hash set for membership and a queue in arrival order, so expired IDs fall out of the window.
• Realign Drifting Subtitles: Binary search for the anchor segment around each time, then interpolate along it.
• Sliding window: the pattern guide, with more practice questions.