Implement log storage and querying
Company: Datadog
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Design a data structure to record log entries and support efficient queries. Each log has a timestamp (milliseconds), severity (INFO/WARN/ERROR), serviceId (string), and message (string). Support:
1) append(log),
2) count(startTime, endTime, filters), and
3) get(startTime, endTime, filters, orderBy, limit, offset). Describe your data layout, indexing strategy, and how you handle time-range scans plus optional filters on severity and serviceId. Provide expected time and space complexity for each operation and discuss trade-offs between write amplification and query latency.
Quick Answer: This question evaluates a candidate's skill in designing and analyzing log storage and query systems, covering data layout, indexing strategies, time-range scans with optional filters, and time/space complexity reasoning.
Implement process_logs(ops) to record logs and answer queries. Each log has fields: timestamp (int, milliseconds), severity (INFO/WARN/ERROR), serviceId (string), and message (string). Process a list of operations in order. Supported operations: 1) {"op":"append","timestamp":t,"severity":s,"serviceId":id,"message":m} appends a log; 2) {"op":"count","start":a,"end":b,"filters":{optional severity, serviceId}} returns the number of logs with a <= timestamp <= b matching all provided filters; 3) {"op":"get","start":a,"end":b,"filters":{optional severity, serviceId},"orderBy":"timestamp_asc"|"timestamp_desc","limit":L,"offset":O} returns up to L matching logs after skipping O matches, ordered by timestamp as specified. Return a list containing outputs only for count and get operations, in their occurrence order. Assume append operations are given in non-decreasing timestamp order.
Constraints
- 1 <= len(ops) <= 50000
- Append operations arrive with non-decreasing timestamp
- 0 <= timestamp <= 10^13
- severity ∈ {"INFO","WARN","ERROR"}
- 0 <= length(serviceId) <= 64
- 0 <= length(message) <= 512
- Queries use inclusive time range: start <= timestamp <= end
- orderBy ∈ {"timestamp_asc","timestamp_desc"}
- 0 <= limit <= 100000, 0 <= offset
- Return outputs only for count/get; append produces no output
Hints
- Maintain a time-sorted array of timestamps and binary search the [start,end] window.
- Filter severity and/or serviceId while scanning only the time-window slice.
- For get with limit/offset, skip then collect to avoid building full intermediate lists.
- Stable append order within equal timestamps naturally preserves order in timestamp_asc.