1268. Logger Rate Limiter

easyAsked at Shopify

Shopify's lightest rate-limiting design. Real motivation: throttle warning logs from a misbehaving merchant integration so the log pipeline doesn't get DOSed. The interviewer wants to see a hash-map design and a clear answer on memory growth.

By Sam K., Founder, InterviewChamp.AI · Last verified 2026-05-19

Source citations

Public interview reports confirming this problem appears in Shopify loops.

Glassdoor (2026-Q1)— Shopify Production Engineer + Backend Developer onsites cite the Logger Rate Limiter / token-bucket pattern as a system-design-lite warm-up.
Reddit r/cscareerquestions (2025-12)— Shopify SRE-track interview reports include this with the distributed rate-limiter follow-up.

Problem

Design a logger system that receives a stream of messages along with their timestamps. Each unique message should only be printed at most every 10 seconds. Given a message and a timestamp (in seconds granularity), return true if the message should be printed in the given timestamp, otherwise returns false.

Constraints

0 <= timestamp <= 10^9
Every timestamp will be passed in non-decreasing order (chronological order).
1 <= message.length <= 30
At most 10^4 calls will be made to shouldPrintMessage.

Examples

Example 1

Input

shouldPrintMessage(1, "foo"); shouldPrintMessage(2, "bar"); shouldPrintMessage(3, "foo"); shouldPrintMessage(8, "bar"); shouldPrintMessage(10, "foo"); shouldPrintMessage(11, "foo")

Output

[true,true,false,false,false,true]

Approaches

1. Hash map with unbounded growth

Store the last-printed timestamp per message. On call, check if (timestamp - lastSeen) >= 10.

Time: O(1) per call
Space: O(unique messages, unbounded)

class LoggerUnbounded {
  constructor() { this.lastPrinted = new Map(); }
  shouldPrintMessage(timestamp, message) {
    if (!this.lastPrinted.has(message) || timestamp - this.lastPrinted.get(message) >= 10) {
      this.lastPrinted.set(message, timestamp);
      return true;
    }
    return false;
  }
}

Tradeoff: Easy and correct. Memory grows linearly with unique messages — at Shopify's scale, that's the smell. Mention it; volunteer the bounded variant unprompted.

2. Hash map + lazy eviction (optimal)

Same logic, but on each call, opportunistically prune entries older than (timestamp - 10). For chronological inputs, this caps memory at the number of distinct messages in any 10-second window.

Time: O(1) amortized per call
Space: O(messages in last 10s)

class Logger {
  constructor() { this.lastPrinted = new Map(); }
  shouldPrintMessage(timestamp, message) {
    // Lazy eviction every call adds O(N); do it periodically instead.
    if (this.lastPrinted.size > 1000) {
      const cutoff = timestamp - 10;
      for (const [msg, t] of this.lastPrinted) {
        if (t < cutoff) this.lastPrinted.delete(msg);
      }
    }
    const last = this.lastPrinted.get(message);
    if (last === undefined || timestamp - last >= 10) {
      this.lastPrinted.set(message, timestamp);
      return true;
    }
    return false;
  }
}

Tradeoff: Bounds memory at the cost of an occasional sweep. The threshold (1000) is tunable; pick something that amortizes the sweep to O(1) per call. Shopify accepts this if you discuss the size/sweep tradeoff.

3. Queue + set (alternative bounded design)

Maintain a queue of (timestamp, message) for the last 10 seconds + a Set of currently throttled messages. On each call, pop expired entries from the queue and remove from the Set.

Time: O(1) amortized per call
Space: O(messages in last 10s)

class LoggerQueue {
  constructor() {
    this.queue = [];
    this.active = new Set();
  }
  shouldPrintMessage(timestamp, message) {
    while (this.queue.length && this.queue[0].t <= timestamp - 10) {
      this.active.delete(this.queue.shift().msg);
    }
    if (this.active.has(message)) return false;
    this.active.add(message);
    this.queue.push({ t: timestamp, msg: message });
    return true;
  }
}

Tradeoff: Memory strictly bounded by the 10-second window. Slightly more code than the hash-map version. Array.shift is O(n); for high QPS, switch to a head-pointer deque.

Shopify-specific tips

Shopify's expected follow-up is 'how do you scale this across multiple servers' — answer: shard by message hash; or accept best-effort throttling (each server enforces locally, accepting some over-print). Senior candidates are also asked to extend to a token bucket: 'now allow K prints per 10 seconds, not just one' — store an array of recent timestamps per message.

Common mistakes

Using > instead of >= when comparing the cooldown — off-by-one on the boundary.
Forgetting to update lastPrinted when returning true (the next call will print again immediately).
Letting the hash map grow without bound — interviewers always probe this.
Assuming the timestamp will not have decimals (LeetCode's signature has integer seconds; real systems use ms or epoch).

Follow-up questions

An interviewer at Shopify may pivot to one of these next:

Distributed rate limiter — shard by message hash.
Token bucket — allow K prints per window.
Sliding window log — more precise than fixed window.
Approximate counts — Count-Min Sketch for very high cardinality.
LeetCode 1268 — search suggestions system (rate-limited results).

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why use a hash map and not a sorted structure?

Because lookups by message string are the hot path, and a hash map gives O(1). Sorted structures give O(log n) lookups and gain nothing. The only sorted-friendly variant is when you need 'oldest entry first' for eviction, which is what the queue-based design uses.

Is unbounded memory actually a problem in practice?

At Shopify scale, yes. Unique log messages across all merchants can reach millions per minute. The lazy-eviction or queue-based design caps memory at the active window, which is the engineering bar interviewers grade against.

Free learning resources

Curated free links for this problem.