34 — LLD: Train Platform Management

Understanding the Problem

A train station has a fixed set of platforms. Trains get assigned to a platform for a time interval. The system must reject overlapping assignments on the same platform and answer "where is train T at time t?" in sub-millisecond time. The design hinges on keeping two sorted indexes in lockstep — one per platform, one per train.

What is Train Platform Management?

A per-platform calendar plus a per-train history. Think of it as a bipartite scheduling system: platforms own time slots; trains own their trajectories through the station across the day.

---

Requirements

Clarifying Questions

You: Can a train be on multiple platforms at different times on the same day?

Interviewer: Yes — same train, different platforms, different intervals.

So the per-train index is a sequence of non-overlapping intervals, not a single current-platform field.

You: For query(trainId, t) — exact match at time t, or closest before?

Interviewer: Return the platform where the train actually is at time t. If no assignment covers t, return null.

The predicate is prev.start <= t < prev.end. A floorEntry on the per-train map gets you the candidate.

You: Do we garbage-collect assignments after they end?

Interviewer: Nice-to-have. Let's talk about it as an extension.

Final Requirements

1. assign(trainId, platformId, start, end) — reject if the platform is busy for any part of [start, end).
2. query(trainId, time) — return platform id the train is on at time, or null.
3. listPlatform(platformId) — all current/future assignments sorted by start.
4. Thread-safe under concurrent assignments.

Out of scope: Train entry/exit events, real-time arrival delays, cross-station coordination.

Deferred tradeoff: A small two-step consistency gap between the platform index and the train index is acceptable for a display query; strict consistency would require a two-phase protocol.

---

Core Entities and Relationships

One assignment lives in two indexes simultaneously. Platforms need to enforce no-overlap on their own timeline; trains need a fast lookup by time. A single global index would make one of the queries slow.

Entity	Responsibility
Assignment	Immutable value — trainId, platformId, start, end.
Platform	Sorted interval map of assignments on that platform. Enforces no-overlap. Owns its lock.
TrainIndex	Map<trainId, TreeMap<start, Assignment>> — per-train history.
Station	Holds all platforms and the train index. Orchestrates assignment and query.

Why dual-indexing instead of a single sorted structure? Because the two queries ask about different keys: "what's on platform P at time t" versus "where is train T at time t". Each index is O(log N) for its own question. A single global index would force a linear scan for one side.

Design is iterative. If a third query dimension appears (e.g., "which trains originated in city X"), you add a third index without touching the first two.

---

Class Design

Assignment (value object)

• trainId, platformId, start, end. Immutable.

Platform

State:

• id: int
• byStart: TreeMap<Long, Assignment> — sorted by start time.
• lock: ReentrantLock.

Methods:

• tryAssign(Assignment) -> boolean — overlap check + insert under lock.
• list() -> List<Assignment>.

The overlap check is exactly the same as RoomSchedule in the meeting room problem — floorEntry and ceilingEntry against the new [s, e).

Station

State:

• platforms: ConcurrentHashMap<Integer, Platform>.
• byTrain: ConcurrentHashMap<String, TreeMap<Long, Assignment>>.

Methods:

• assign(trainId, platformId, start, end).
• query(trainId, time) -> Integer (platform id or null).

Java

public record Assignment(String trainId, int platformId, long start, long end) {}

public class Platform {
    final int id;
    final TreeMap<Long, Assignment> byStart = new TreeMap<>();
    final ReentrantLock lock = new ReentrantLock();

    public Platform(int id) { this.id = id; }

    public boolean tryAssign(Assignment a) { /* overlap check, like RoomSchedule */ }
    public List<Assignment> list() { return new ArrayList<>(byStart.values()); }
}

public class Station {
    private final Map<Integer, Platform> platforms = new ConcurrentHashMap<>();
    private final ConcurrentHashMap<String, TreeMap<Long, Assignment>> byTrain = new ConcurrentHashMap<>();

    public boolean assign(String trainId, int platformId, long start, long end) { /* ... */ }
    public Integer query(String trainId, long time) { /* ... */ }
}

C++

struct Assignment { std::string trainId; int platformId; long start, end; };

class Platform {
    int id;
    std::map<long, Assignment> byStart;
    std::mutex mtx;
public:
    explicit Platform(int i) : id(i) {}
    bool tryAssign(const Assignment& a);
};

class Station {
    std::unordered_map<int, std::shared_ptr<Platform>> platforms;
    std::unordered_map<std::string, std::map<long, Assignment>> byTrain;
    std::mutex trainMtx;
public:
    bool assign(const std::string& trainId, int platformId, long s, long e);
    std::optional<int> query(const std::string& trainId, long t);
};

TypeScript

export interface Assignment { trainId: string; platformId: number; start: number; end: number; }

export class Platform {
  private byStart = new Map<number, Assignment>();
  private sortedStarts: number[] = [];
  constructor(public id: number) {}
  tryAssign(a: Assignment): boolean { /* ... */ }
}

export class Station {
  private platforms = new Map<number, Platform>();
  private byTrain = new Map<string, { starts: number[]; map: Map<number, Assignment> }>();
  assign(trainId: string, platformId: number, start: number, end: number): boolean { /* ... */ }
  query(trainId: string, time: number): number | null { /* ... */ }
}

Design principles at play:

• Dual-index: The same record appears in two structures keyed differently, for two kinds of fast queries.
• Single Responsibility: Platform enforces platform-local invariants; Station handles cross-index bookkeeping.
• Lock ordering: Always lock Platform first, then the byTrain map, to avoid deadlock on reassignments.

---

Implementation

Core Logic: assign

1. Reject invalid input (start >= end).
2. Get or create the Platform for platformId.
3. Attempt tryAssign on the platform — this is the authoritative overlap check.
4. If accepted, also insert into byTrain[trainId].

The two-step insertion is where you earn senior points: you must either accept eventual consistency (the platform is authoritative; train index is a cache) or go two-phase. For most systems, option 1 is the right call.

Core Logic: query

1. Look up the train's history map.
2. floorEntry(time) gives the most recent assignment whose start <= time.
3. Check time < assignment.end — otherwise the train already left that platform.

Implementations

Java

public boolean assign(String trainId, int platformId, long start, long end) {
    if (start >= end) return false;
    Platform p = platforms.computeIfAbsent(platformId, Platform::new);
    Assignment a = new Assignment(trainId, platformId, start, end);
    if (!p.tryAssign(a)) return false;
    byTrain.computeIfAbsent(trainId, k -> new TreeMap<>())
           .put(start, a);
    return true;
}

public Integer query(String trainId, long time) {
    TreeMap<Long, Assignment> hist = byTrain.get(trainId);
    if (hist == null) return null;
    Map.Entry<Long, Assignment> prev = hist.floorEntry(time);
    if (prev == null) return null;
    Assignment a = prev.getValue();
    return (time < a.end()) ? a.platformId() : null;
}

// Inside Platform
public boolean tryAssign(Assignment a) {
    lock.lock();
    try {
        Map.Entry<Long, Assignment> prev = byStart.floorEntry(a.start());
        if (prev != null && prev.getValue().end() > a.start()) return false;
        Map.Entry<Long, Assignment> next = byStart.ceilingEntry(a.start());
        if (next != null && next.getKey() < a.end()) return false;
        byStart.put(a.start(), a);
        return true;
    } finally { lock.unlock(); }
}

C++

bool Platform::tryAssign(const Assignment& a) {
    std::lock_guard<std::mutex> lk(mtx);
    auto it = byStart.lower_bound(a.start);
    if (it != byStart.begin()) {
        auto prev = std::prev(it);
        if (prev->second.end > a.start) return false;
    }
    if (it != byStart.end() && it->first < a.end) return false;
    byStart.emplace(a.start, a);
    return true;
}

bool Station::assign(const std::string& trainId, int platformId, long s, long e) {
    if (s >= e) return false;
    std::shared_ptr<Platform> p;
    {
        std::lock_guard<std::mutex> lk(trainMtx);
        auto it = platforms.find(platformId);
        if (it == platforms.end()) {
            p = std::make_shared<Platform>(platformId);
            platforms[platformId] = p;
        } else p = it->second;
    }
    Assignment a{trainId, platformId, s, e};
    if (!p->tryAssign(a)) return false;
    std::lock_guard<std::mutex> lk(trainMtx);
    byTrain[trainId][s] = a;
    return true;
}

std::optional<int> Station::query(const std::string& trainId, long t) {
    std::lock_guard<std::mutex> lk(trainMtx);
    auto it = byTrain.find(trainId);
    if (it == byTrain.end()) return std::nullopt;
    auto& m = it->second;
    auto hit = m.upper_bound(t);
    if (hit == m.begin()) return std::nullopt;
    --hit;
    return t < hit->second.end ? std::optional<int>(hit->second.platformId) : std::nullopt;
}

TypeScript

function lowerBound(arr: number[], t: number): number {
  let lo = 0, hi = arr.length;
  while (lo < hi) { const mid = (lo + hi) >>> 1; if (arr[mid] < t) lo = mid + 1; else hi = mid; }
  return lo;
}

export class Platform {
  private byStart = new Map<number, Assignment>();
  private sorted: number[] = [];
  constructor(public id: number) {}
  tryAssign(a: Assignment): boolean {
    const idx = lowerBound(this.sorted, a.start);
    if (idx > 0) {
      const prev = this.byStart.get(this.sorted[idx - 1])!;
      if (prev.end > a.start) return false;
    }
    if (idx < this.sorted.length && this.sorted[idx] < a.end) return false;
    this.sorted.splice(idx, 0, a.start);
    this.byStart.set(a.start, a);
    return true;
  }
}

assign(trainId: string, platformId: number, start: number, end: number): boolean {
  if (start >= end) return false;
  if (!this.platforms.has(platformId)) this.platforms.set(platformId, new Platform(platformId));
  const a: Assignment = { trainId, platformId, start, end };
  if (!this.platforms.get(platformId)!.tryAssign(a)) return false;
  if (!this.byTrain.has(trainId)) this.byTrain.set(trainId, { starts: [], map: new Map() });
  const h = this.byTrain.get(trainId)!;
  const idx = lowerBound(h.starts, start);
  h.starts.splice(idx, 0, start);
  h.map.set(start, a);
  return true;
}

query(trainId: string, time: number): number | null {
  const h = this.byTrain.get(trainId);
  if (!h) return null;
  const idx = lowerBound(h.starts, time + 1);
  if (idx === 0) return null;
  const a = h.map.get(h.starts[idx - 1])!;
  return time < a.end ? a.platformId : null;
}

Thread Safety

Two-step assignment has a consistency hazard: platform accepts, another concurrent assign for the same train wins the byTrain update before the first one completes. Two options:

1. Accept eventual consistency. Platform is authoritative. The train index converges; queries may be briefly stale. This is almost always fine for a display.
2. Two-phase. Reserve on platform (returns a handle), commit to the train index under a per-train lock, confirm on the platform. Add complexity only if query must be strictly consistent.

Always lock platform first, then the train index, to prevent deadlock during reassignments that touch two platforms.

Verification

Assignments: T1 → P1 [09, 10), T1 → P2 [10, 11), T2 → P1 [11, 12).

Query	Result
query(T1, 09:30)	1
query(T1, 10:00)	2
query(T1, 10:30)	2
query(T1, 11:00)	null (T1's last segment ends at 11:00)
query(T2, 11:30)	1

Trace for query(T1, 10:00):

• byTrain["T1"] → {9 → A1, 10 → A2}.
• floorEntry(10) → (10, A2).
• Predicate 10 < A2.end (11) → true. Return A2.platformId = 2.

---

Complete Code Implementation

Java

import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.locks.ReentrantLock;

public record Assignment(String trainId, int platformId, long start, long end) {}

public class Platform {
    final int id;
    final TreeMap<Long, Assignment> byStart = new TreeMap<>();
    final ReentrantLock lock = new ReentrantLock();

    public Platform(int id) { this.id = id; }

    public boolean tryAssign(Assignment a) {
        lock.lock();
        try {
            Map.Entry<Long, Assignment> prev = byStart.floorEntry(a.start());
            if (prev != null && prev.getValue().end() > a.start()) return false;
            Map.Entry<Long, Assignment> next = byStart.ceilingEntry(a.start());
            if (next != null && next.getKey() < a.end()) return false;
            byStart.put(a.start(), a);
            return true;
        } finally { lock.unlock(); }
    }

    public List<Assignment> list() {
        lock.lock();
        try { return new ArrayList<>(byStart.values()); }
        finally { lock.unlock(); }
    }
}

public class Station {
    private final Map<Integer, Platform> platforms = new ConcurrentHashMap<>();
    private final ConcurrentHashMap<String, TreeMap<Long, Assignment>> byTrain = new ConcurrentHashMap<>();

    public boolean assign(String trainId, int platformId, long start, long end) {
        if (start >= end) return false;
        Platform p = platforms.computeIfAbsent(platformId, Platform::new);
        Assignment a = new Assignment(trainId, platformId, start, end);
        if (!p.tryAssign(a)) return false;
        byTrain.compute(trainId, (k, v) -> {
            TreeMap<Long, Assignment> m = (v == null) ? new TreeMap<>() : v;
            m.put(start, a);
            return m;
        });
        return true;
    }

    public Integer query(String trainId, long time) {
        TreeMap<Long, Assignment> hist = byTrain.get(trainId);
        if (hist == null) return null;
        Map.Entry<Long, Assignment> prev;
        synchronized (hist) { prev = hist.floorEntry(time); }
        if (prev == null) return null;
        Assignment a = prev.getValue();
        return (time < a.end()) ? a.platformId() : null;
    }

    public List<Assignment> listPlatform(int platformId) {
        Platform p = platforms.get(platformId);
        return p == null ? List.of() : p.list();
    }
}

C++

#include <map>
#include <unordered_map>
#include <memory>
#include <mutex>
#include <optional>
#include <string>
#include <vector>

struct Assignment { std::string trainId; int platformId; long start, end; };

class Platform {
    int id_;
    std::map<long, Assignment> byStart;
    std::mutex mtx;
public:
    explicit Platform(int i) : id_(i) {}
    bool tryAssign(const Assignment& a) {
        std::lock_guard<std::mutex> lk(mtx);
        auto it = byStart.lower_bound(a.start);
        if (it != byStart.begin()) {
            auto prev = std::prev(it);
            if (prev->second.end > a.start) return false;
        }
        if (it != byStart.end() && it->first < a.end) return false;
        byStart.emplace(a.start, a);
        return true;
    }
    std::vector<Assignment> list() {
        std::lock_guard<std::mutex> lk(mtx);
        std::vector<Assignment> out;
        for (auto& kv : byStart) out.push_back(kv.second);
        return out;
    }
};

class Station {
    std::unordered_map<int, std::shared_ptr<Platform>> platforms;
    std::unordered_map<std::string, std::map<long, Assignment>> byTrain;
    std::mutex stationMtx;
public:
    bool assign(const std::string& trainId, int platformId, long s, long e) {
        if (s >= e) return false;
        std::shared_ptr<Platform> p;
        {
            std::lock_guard<std::mutex> lk(stationMtx);
            auto it = platforms.find(platformId);
            if (it == platforms.end()) {
                p = std::make_shared<Platform>(platformId);
                platforms[platformId] = p;
            } else p = it->second;
        }
        Assignment a{trainId, platformId, s, e};
        if (!p->tryAssign(a)) return false;
        std::lock_guard<std::mutex> lk(stationMtx);
        byTrain[trainId][s] = a;
        return true;
    }

    std::optional<int> query(const std::string& trainId, long t) {
        std::lock_guard<std::mutex> lk(stationMtx);
        auto it = byTrain.find(trainId);
        if (it == byTrain.end()) return std::nullopt;
        auto& m = it->second;
        auto hit = m.upper_bound(t);
        if (hit == m.begin()) return std::nullopt;
        --hit;
        if (t < hit->second.end) return hit->second.platformId;
        return std::nullopt;
    }
};

TypeScript

export interface Assignment { trainId: string; platformId: number; start: number; end: number; }

function lowerBound(arr: number[], t: number): number {
  let lo = 0, hi = arr.length;
  while (lo < hi) { const mid = (lo + hi) >>> 1; if (arr[mid] < t) lo = mid + 1; else hi = mid; }
  return lo;
}

export class Platform {
  private byStart = new Map<number, Assignment>();
  private sorted: number[] = [];
  constructor(public id: number) {}

  tryAssign(a: Assignment): boolean {
    const idx = lowerBound(this.sorted, a.start);
    if (idx > 0) {
      const prev = this.byStart.get(this.sorted[idx - 1])!;
      if (prev.end > a.start) return false;
    }
    if (idx < this.sorted.length && this.sorted[idx] < a.end) return false;
    this.sorted.splice(idx, 0, a.start);
    this.byStart.set(a.start, a);
    return true;
  }

  list(): Assignment[] { return this.sorted.map(s => this.byStart.get(s)!); }
}

export class Station {
  private platforms = new Map<number, Platform>();
  private byTrain = new Map<string, { starts: number[]; map: Map<number, Assignment> }>();

  assign(trainId: string, platformId: number, start: number, end: number): boolean {
    if (start >= end) return false;
    if (!this.platforms.has(platformId)) this.platforms.set(platformId, new Platform(platformId));
    const a: Assignment = { trainId, platformId, start, end };
    if (!this.platforms.get(platformId)!.tryAssign(a)) return false;
    if (!this.byTrain.has(trainId)) this.byTrain.set(trainId, { starts: [], map: new Map() });
    const h = this.byTrain.get(trainId)!;
    const idx = lowerBound(h.starts, start);
    h.starts.splice(idx, 0, start);
    h.map.set(start, a);
    return true;
  }

  query(trainId: string, time: number): number | null {
    const h = this.byTrain.get(trainId);
    if (!h) return null;
    const idx = lowerBound(h.starts, time + 1);
    if (idx === 0) return null;
    const a = h.map.get(h.starts[idx - 1])!;
    return time < a.end ? a.platformId : null;
  }

  listPlatform(id: number): Assignment[] {
    return this.platforms.get(id)?.list() ?? [];
  }
}

---

Extensibility

1. "Which trains are at the station at time t?"

Iterate platforms; for each, do a floorEntry(t) and check end > t. O(P log N) where P is number of platforms and N is assignments per platform. Cache the result for a short TTL if the display refreshes frequently.

2. "Reassign — move a train to another platform?"

Cancel the old assignment and assign a new one. Must be atomic: lock both platforms (in consistent ID order to avoid deadlock), then update both the platform indexes and byTrain. If the new assignment fails, restore the old one.

public boolean reassign(String trainId, int oldPlatform, long oldStart, int newPlatform) {
    // Acquire locks in id-order: min first, then max
    // Remove from old, try add to new, on failure restore.
}

Tradeoff: Two-platform transactions are more complex than a single assign. Keep them rare — only the reassign path needs this.

3. "GC old assignments?"

A background task that evicts assignments with end < now - TTL from both indexes. Run under the platform lock so nothing is mid-query. If you never evict, memory grows without bound over days of operation.

---

What is Expected at Each Level

Level	Expectations
Junior (L4)	Single index, linear scan for overlap. Misses the "query by train" use case entirely.
Mid (L5)	One index per question, TreeMap/floorEntry usage correct. Mentions locking but may not articulate ordering.
Senior (L5A)	Dual index, per-platform lock, explicit lock ordering discussion. Names the eventual-consistency trade-off between the two indexes. Clean extension plan for GC and reassignment.
Staff (L6)	Event-sourced journal of platform events, multi-station topology, real-time dashboards, SLOs for query, integration with train arrival streams.