Stripe·Software Engineer·Technical Phone Screen·Senior

SeniorPrefer not to say

May 2026

Summary

Stripe coding interview that extended a previous parsing problem into something with actual teeth. The twist was adding time-windowed queries on top of the key-value log parsing, which pushed it firmly into design territory.

Questions Asked (1)

You're given log lines in the format `<timestamp>|<key1>:<value1>;<key2>:<value2>;...`. Parse these lines and implement a `top_k(key, t_start, t_end, k)` query that returns the top-k most frequent normalized values for a given key within a time window, sorted by count descending then value ascending.

Algorithms & Data StructuresSystem DesignTechnical Trade-offs

Author's notes

The parsing part felt manageable but the windowed query is where things got interesting.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying requirements and constraints, then propose a two-phase solution: an ingestion/parsing phase that normalizes values and builds an index, and a query phase that uses the index to efficiently retrieve top-k results. Discuss trade-offs between pre-aggregation and on-the-fly computation, and outline how to handle large-scale data with appropriate data structures and algorithms.

Pro tip: Demonstrate awareness of real-world constraints by discussing how to handle out-of-order events, late-arriving data, and the need for approximate algorithms (like count-min sketch) when exact counts are infeasible at scale.

1. Clarify requirements and constraints

Ask about data volume, query frequency, latency requirements, and whether normalization rules are fixed or configurable. Confirm the definition of 'normalized values' and how to handle missing keys or malformed lines.

2. Design parsing and normalization

Outline a parser that splits on '|' and ';', extracts key-value pairs, and applies normalization (e.g., lowercasing, trimming, canonicalization). Discuss error handling for malformed lines.

3. Choose indexing and storage strategy

Propose an index structure: for each key, store a time-ordered list of (timestamp, normalized_value) or pre-aggregated counts per time bucket. Discuss trade-offs between memory usage and query speed.

4. Implement top-k query algorithm

For a given key and time window, retrieve relevant entries, aggregate counts per normalized value, then use a min-heap of size k to find top-k efficiently. Sort results by count descending and value ascending.

5. Discuss scalability and optimizations

Address large-scale scenarios: sharding by key, using approximate data structures (e.g., count-min sketch) for high-cardinality keys, caching frequent queries, and handling out-of-order events with watermarks.

Key Points to Mention

Time-window filtering: use binary search on sorted timestamps or time-bucketed indexes for efficient range queries.
Top-k selection: min-heap of size k gives O(n log k) time, better than full sort when k is small.
Normalization: define clear rules (e.g., case-insensitive, trim whitespace) and apply consistently during ingestion.
Trade-offs: pre-aggregation reduces query latency but increases storage and ingestion cost; on-the-fly computation is flexible but slower.
Scalability: shard by key, use approximate counting for high-cardinality keys, and consider stream processing for real-time updates.
Edge cases: empty results, k larger than distinct values, ties in counts (sort by value ascending), and malformed log lines.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.