Ring Buffer
Medium ● Live C++ Rust Java PythonThe Problem
Implement a high-performance circular buffer (ring buffer) for storing and retrieving market tick data. Support concurrent push/pop operations on a fixed-size buffer without dynamic memory allocation.
Scale: 5,000,000 operations (mixed push/pop). The ring buffer is a fundamental data structure in systems programming and high-frequency trading.
Evaluation Criteria
Correctness (70%)
All push/pop operations must maintain FIFO semantics. No data loss or corruption even at buffer capacity.
Performance (30%)
Wall-clock time on 5M mixed operations. Memory usage must be constant (no dynamic allocation).
Ring Buffer Specification
Data Structure
Fixed-size circular array with head and tail pointers. Buffer capacity: N elements.
Operations
- Push: add element to tail, advance tail pointer (wrap around at buffer end)
- Pop: remove element from head, advance head pointer
- Size: return count of elements in buffer
- Empty: return true if head == tail
- Full: return true if (tail + 1) % N == head
Semantics
FIFO order: elements are popped in the same order they were pushed. Pushing to a full buffer overwrites oldest element.
Input Format
- First line
N Mwhere N = buffer capacity, M = number of operations.- Then M lines
- one operation per line, from this set:
PUSH <ts> <price> <volume>- push a tick record.tsis integer,priceis float,volumeis integer. If the buffer is full, the oldest record is overwritten.POP- pop the oldest tick record. Print<ts> <price> <volume>with price to 6 decimal places. If the buffer is empty, printEMPTY.PEEK- look at the oldest record without removing. Same output format as POP.EMPTYif empty.STATS- print two integers: current size and capacity.
Output Format & Sample
Sample input (first 8 lines, full file linked below):
50 16 POP PUSH 1 99.8 3658 PUSH 2 99.4 8936 PUSH 3 99.3 489 PUSH 4 99.0 9864 PUSH 5 98.7 8929 PUSH 6 98.7 4558 ... (more)
Expected output for that sample (first 8 lines):
EMPTY 6 16 9 16 1 99.800000 3658 8 16 2 99.400000 8936 2 99.400000 8936 7 16 ... (more)
↓ download full sample input | ↓ download expected output
Test your solution locally:
./your_solution < input.txt | diff - output.txt
Common Pitfalls
- PUSH takes three values, not one. The legacy spec said
PUSH value. The real format isPUSH ts price volume. - Operations are PUSH / POP / PEEK / STATS. The legacy spec listed SIZE / EMPTY / FULL. Those don't exist in the test data; using them in your code is harmless but you'll waste time looking for tests that fire them.
- POP output format is the full record, e.g.
1 99.800000 3658, not just the value. Match the price to six decimal places. - Read input as one buffer. 5,000,000 lines is the production size. Line-by-line readline() in Python will not hit the Gold tier. Use
sys.stdin.buffer.read().split(). - Empty-buffer output is the literal string
EMPTY, not -1.
Performance Tier Thresholds (applied by the grader)
| Language | Gold | Silver | Bronze | Tier 4 |
|---|---|---|---|---|
| C++ | <500ms | <2000ms | <8000ms | else PASS |
| Rust | <500ms | <2000ms | <8000ms | else PASS |
| Java | <1000ms | <4000ms | <15000ms | else PASS |
| Python | <4000ms | <12000ms | <50000ms | else PASS |
Implementation Notes
Memory Efficiency
Do NOT use dynamic allocation. Allocate buffer once at startup.
Wraparound
Use modulo arithmetic: next_index = (index + 1) % capacity
Thread Safety (Optional)
If using locks, minimize contention via fine-grained locking.
Submission Rules
- Single-file solutions only. All code must be in one file.
- Your program must read from stdin and write to stdout.
- Java class must be named Solution.
- No network access, no filesystem access beyond stdin/stdout.
- Time limit: 120 seconds. Memory limit: 2 GB.