Quick Overview

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 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.

Overview: 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

  1. Maintain a time-sorted array of timestamps and binary search the [start,end] window.
  2. Filter severity and/or serviceId while scanning only the time-window slice.
  3. For get with limit/offset, skip then collect to avoid building full intermediate lists.
  4. Stable append order within equal timestamps naturally preserves order in timestamp_asc.

Loading coding console...

Show the approach

Approach

Maintain parallel arrays for timestamps and fields. Because appends are in non-decreasing order, timestamps remain sorted. Use binary search to find the window [l, r) of logs whose timestamp is within [start, end]. For count, scan only this slice and apply optional severity/serviceId filters. For get, iterate the slice in ascending or descending order based on orderBy, skip 'offset' matches, then collect up to 'limit' logs into the result. This avoids building large intermediate lists and only touches the relevant time range. Trade-off: Writes are O(1) and simple (append-only), while queries use O(log n) to locate the time window and O(k) to scan matches within that window; this design favors query latency with minimal write amplification.

Time complexity:
append: O(1); count: O(log n + k); get: O(log n + s) where s is the number scanned to skip offset and collect up to limit within the time window
Space complexity:
O(n)