Low-level design · Libraries and infrastructure

Logger that reports finished processes in start order in constant time

Reported once
Senior Software Engineer (L63)
Decorator
Observer
Strategy
1 source

One candidate write-up. Treat it as a single data point.

The prompt

Design a logger with start, end and log operations. Processes start and end in any order, and log must report the finished processes that started before every process that is still running, without scanning all processes, so each operation takes constant time. A follow-up asks how new logging behaviour can be added without changing the core code.

Restated in our own words, not a quote from Microsoft or any page. The answer below is written for this site.

Try it first.The answer is covered until you pick. Talk it through against a 60 minute clock, or just read it.

Clarify first

Pin the scope down before you name a single class.

The wording of log is the hard part, so pin it down first.

Does log return every finished process, or only those that started before the oldest still-running one? Assume the second: a finished process waits until everything that started before it has finished.
Is each process reported once, and in what order? Assume once, in start order.
Can an id be reused after it was reported? Assume yes, but a live id cannot be started twice.
What counts as constant time? Assume each process is added once, marked once and released once, so the cost per process is constant and log costs the size of what it returns.
Is time given or read from a clock? Assume an injected clock.

In scope: the three operations, the output destinations, thread-safety notes. Out of scope: durable storage and log rotation.

Entities and relationships

Who owns what, and who talks to whom.

Logger is the facade. It stamps times with the clock, forwards start and end to the tracker, and on log writes each released record to every sink.
ProcessTracker holds a singly linked list in start order (head and tail) and a map from id to node. It owns the ordering rule.
ProcessNode holds the id, start time, end time (empty while running) and the next pointer.
Sink is the output interface with one method, write(record). MemorySink stores records.
FilterSink and FormatSink implement the same interface and wrap another sink, so they can be stacked.
Clock is injected so tests control time.

The logger has one tracker and many sinks. The tracker has many nodes, and each node is also indexed by the map.

The design

The class map, the main flow and the patterns that earn their place.

Logger class mapThe tracker decides what is reported. Sinks decide where it goes and can be wrapped without edits.

The caller starts and ends processes by id and calls log.
The logger forwards each call to the tracker, which uses the tail pointer and the map.
On log, nodes leave the head of the list while they have ended.
Each released node becomes a record that is written to every sink.

Open on the whiteboardAll 3 diagrams on one tidy board, with a step-by-step walkthrough.

The core observation is that the answer to log is always a prefix of the start-ordered list: walk from the head while the node has ended and stop at the first node that is still running. Everything before that point started earlier than every running process. The tracker therefore keeps nodes in start order in a linked list and a map from id to node, so each operation is cheap:

start appends a node at the tail and adds it to the map: O(1).
end finds the node through the map and stamps its end time: O(1). It never touches the list order.
release pops nodes from the head while they have ended, deleting them from the map: each node is released once in its life, so the amortised cost is O(1) per process.

A queue plus a map gives the same costs. The linked list just makes the invariant visible: the head is the oldest process not yet reported, and a finished process behind a running one waits. Say plainly that the returned list is proportional to its own size, so "constant time" means constant per process, not a fixed cost for the call.

Extensibility is the part the round probes. The tracker only decides what to report. Where it goes belongs to sinks. Logger.log builds a record from each released node and calls write on every sink, which is the Observer pattern. Decorator adds behaviour without touching existing classes: FilterSink forwards only matching records and FormatSink turns a record into a line, and each wraps another sink behind the same interface so they stack. A new behaviour such as writing to a file, counting slow processes or batching is a new class passed to the constructor or addSink. The logger and tracker do not change. A sink that throws is recorded in failures and the other sinks and records are still written, because the processes have already been released and a thrown error must not lose them.

Concurrency: start, end and release touch the tail, the map and the head, so guard them with one lock, and call sinks after the lock is released, so a slow sink never blocks start. A lock-free version is possible but rarely worth the risk.

Trade-off: sinks run synchronously inside log, which is simple and ordered. A sink that does I/O should sit behind its own queue and thread, at the price of losing the guarantee that log has finished writing when it returns.

The code

Runnable JavaScript, with the checks it passes.

microsoft-logger-service.js

class FakeClock {
  constructor(start = 0) {
    this.time = start;
  }
  now() {
    return this.time;
  }
  advance(ms) {
    this.time += ms;
  }
}

class ProcessNode {
  constructor(id, startedAt) {
    this.id = id;
    this.startedAt = startedAt;
    this.endedAt = null;
    this.next = null;
  }
}

class ProcessTracker {
  constructor() {
    this.byId = new Map();
    this.head = null;
    this.tail = null;
    this.running = 0;
  }
  start(id, at) {
    if (this.byId.has(id)) throw new Error("process already started: " + id);
    const node = new ProcessNode(id, at);
    this.byId.set(id, node);
    if (this.tail) this.tail.next = node;
    else this.head = node;
    this.tail = node;
    this.running += 1;
  }
  end(id, at) {
    const node = this.byId.get(id);
    if (!node) throw new Error("unknown process: " + id);
    if (node.endedAt !== null) throw new Error("process already ended: " + id);
    node.endedAt = at;
    this.running -= 1;
  }
  release() {
    const released = [];
    while (this.head && this.head.endedAt !== null) {
      released.push(this.head);
      this.byId.delete(this.head.id);
      this.head = this.head.next;
    }
    if (!this.head) this.tail = null;
    return released;
  }
}

class MemorySink {
  constructor() {
    this.records = [];
  }
  write(record) {
    this.records.push(record);
  }
}

class FilterSink {
  constructor(inner, accept) {
    this.inner = inner;
    this.accept = accept;
  }
  write(record) {
    if (this.accept(record)) this.inner.write(record);
  }
}

class FormatSink {
  constructor(inner, format) {
    this.inner = inner;
    this.format = format;
  }
  write(record) {
    this.inner.write(this.format(record));
  }
}

class Logger {
  constructor(clock, sinks = []) {
    this.clock = clock;
    this.sinks = sinks;
    this.failures = [];
    this.tracker = new ProcessTracker();
  }
  addSink(sink) {
    this.sinks.push(sink);
  }
  start(id) {
    this.tracker.start(id, this.clock.now());
  }
  end(id) {
    this.tracker.end(id, this.clock.now());
  }
  log() {
    const released = this.tracker.release();
    for (const node of released) {
      const record = { id: node.id, startedAt: node.startedAt, endedAt: node.endedAt };
      for (const sink of this.sinks) {
        try {
          sink.write(record);
        } catch (error) {
          this.failures.push({ id: node.id, error: error instanceof Error ? error.message : String(error) });
        }
      }
    }
    return released.map((node) => node.id);
  }
}

Runs here in your browser, in a sandboxed worker. Nothing is sent anywhere.

Try your own input

Write JavaScript that calls the code above and prints with console.log. It runs after the solution.

Extend it

The change requests an interviewer throws next.

Several threads call start and end at the same time. Which operations need to be atomic, and can you avoid one global lock?
A sink such as a file or a network call can fail or be slow. How do you stop it from blocking log or losing records?
Add log levels or a per-process tag and let sinks subscribe only to some of them. Where does the filtering live?
Some processes are cancelled and never end. How do you stop one stuck process from holding back every later one forever?
Instead of returning a list, log must hand records to the caller one at a time. What changes in the tracker and the sinks?

Where candidates slip

The mistakes this problem punishes.

Scanning all processes on every log call, or sorting by start time each time. That is the O(n) answer the question rules out.
Releasing every finished process instead of only those before the oldest running one. This is the misreading that gives the wrong output.
Reporting a process twice, or leaving its map entry behind so the id can never be reused.
Putting formatting, filtering and file output as if branches inside log. The follow-up then forces edits to the core class.
Making the logger a singleton with static state, which hurts tests and the injected clock.
Skipping error cases: ending an unknown id, ending twice, or starting a live id twice.

Have a go before you read.

Interviews reward the sketch you make cold. Clarify out loud, draw it, then compare with the answer.

Always show the answer straight away

Now make it stick

Sketch the class map on the whiteboard Run a mock interview

Where this was reported

Public pages only. Companies do not confirm these, and they rotate their questions, so treat each link as one person's account or one list's tag.

Candidate write-up · 2025Interview Experience 157, Microsoft SDE L63 (Roundz)

Read these chapters first

Observability at scale

Now make it stick

Where this was reported

Read these chapters first

More on libraries and infrastructure