Counter with Time Expiration

Based on my comprehensive research, I found that "Counter with Time Expiration" is indeed listed as an Apple phone screen interview question on HackTheRounds, but the exact public problem statement is not available. However, based on similar Apple interview problems, industry patterns for time-based counter design, and the problem's categorization tags (Design, Queue, Time-based), I can provide a well-reasoned reconstruction:

---

Counter with Time Expiration

Problem Description

Design a counter system where each increment operation automatically expires after a specified duration. You need to implement a class that maintains a count of active (non-expired) increments and automatically decrements the counter as increments reach their expiration time.

The system should track increments individually, allowing each to have its own expiration window. When an increment expires, it no longer contributes to the current count. The counter should efficiently handle repeated operations over long periods without storing unnecessary historical data for expired increments.

This is commonly used in rate limiting, credit tracking, and throttling mechanisms where you want to count actions within a rolling time window (e.g., "5 requests in the last 60 seconds").

Input/Output Format

Constructor: TimedCounter()

• Initializes an empty counter

Methods:

• increment(): Records a new increment operation at the current time with an automatic expiration
• getCount(): int: Returns the current count of non-expired increments
• getExpiredCount(): int (optional): Returns the count of expired increments
• reset(): Clears all increments

The counter should handle the following timing:

• When increment() is called at timestamp t with duration d, that increment expires at timestamp t + d
• When getCount() is called at timestamp t, only increments where expiration_time > t are counted

Examples

Example 1: Basic Expiration

` TimedCounter counter = new TimedCounter();

// At t=0ms counter.increment(); // duration=100ms, expires at t=100ms counter.getCount(); // Returns 1

// At t=50ms counter.getCount(); // Returns 1 (increment still valid)

// At t=100ms counter.getCount(); // Returns 0 (increment expired) `

Example 2: Multiple Increments with Different Expirations

` TimedCounter counter = new TimedCounter();

// At t=0ms counter.increment(); // duration=50ms, expires at t=50ms counter.increment(); // duration=100ms, expires at t=100ms counter.getCount(); // Returns 2

// At t=60ms counter.getCount(); // Returns 1 (only the second increment valid)

// At t=110ms counter.getCount(); // Returns 0 (both expired) `

Example 3: Rolling Window Pattern

` TimedCounter counter = new TimedCounter(1000); // 1000ms window by default

// At t=0ms: Make 3 increments counter.increment(); counter.increment(); counter.increment(); counter.getCount(); // Returns 3

// At t=500ms: Make 2 more increments counter.increment(); counter.increment(); counter.getCount(); // Returns 5

// At t=1050ms: First 3 increments expired counter.getCount(); // Returns 2 (only the 2 made at t=500ms still valid if window is 1000ms) `

Constraints

• 1 <= duration <= 10^6 milliseconds
• 1 <= number of operations <= 10^5
• Timestamps are always non-decreasing (monotonically increasing)
• System time progresses linearly (no time travel backwards)
• O(1) amortized time complexity for increment() and getCount() operations
• O(n) space complexity where n is the number of non-expired increments

Solution Hint

Use a queue (or deque) to maintain increments in chronological order of their expiration times. On each getCount() call, remove all expired entries from the front of the queue by comparing against the current timestamp, then return the queue size. This leverages the fact that timestamps are monotonically increasing—once an entry expires, it will never become valid again.