22. LLD / DS-design answerbook

1. Meeting Room Scheduler Standard CS

Question stem. Design a product that has rooms, books a room for [start, end), rejects conflicts, cancels a booking, and finds a free room that fits capacity. This is not LeetCode Meeting Rooms II. That DSA (min-heap of end times) is a sibling you can drop into findRoom; it is not the whole product.

Evidence / remap. Class C / user-pasted list — no first-hand Job-loop URL in Question-Research-BIBLE.md §5.C for a booking product. TUF 06 named Meeting Rooms II as live DSA after OA-as-R1 (their R2 ≈ Adarsh’s already-done first live analogue). Other candidates reported interval DSA; your loop may differ. Interval tree is Standard CS follow-up, not the opening structure.

Clarify before classes

• Half-open [start, end) so back-to-back 10:00–11:00 and 11:00–12:00 are legal.
• Timezone: store UTC epoch ms; display is not the invariant.
• Same organizer two rooms: allowed unless they forbid it.
• Recurring series: not in v1; one interval per booking id.
• Find-free: first-fit by room id, or earliest-free, or min leftover capacity — pick one.
• In-memory one process; persistence is a follow-up.
• Invalid: unknown room, end ≤ start, double-cancel, overlap, capacity underflow if they add attendee count.

Data structures

Entities and pattern

Room is identity. Booking is an immutable interval. MeetingScheduler owns both maps and the overlap test. No Strategy unless they add pricing or a pluggable find-free policy. No Observer.

import java.util.*;

final class Room {
    final String id;
    final String name;
    final int capacity;
    Room(String id, String name, int capacity) {
        if (capacity <= 0) throw new IllegalArgumentException("capacity");
        this.id = id;
        this.name = name;
        this.capacity = capacity;
    }
}

final class Booking {
    final String id;
    final String roomId;
    final String organizer;
    final long startMs;
    final long endMs;
    Booking(String id, String roomId, String organizer, long startMs, long endMs) {
        if (endMs <= startMs) throw new IllegalArgumentException("empty interval");
        this.id = id;
        this.roomId = roomId;
        this.organizer = organizer;
        this.startMs = startMs;
        this.endMs = endMs;
    }
    boolean overlaps(long start, long end) {
        return startMs < end && start < endMs;
    }
}

final class MeetingScheduler {
    private final Map<String, Room> rooms = new HashMap<>();
    private final Map<String, TreeMap<Long, Booking>> calendar = new HashMap<>();
    private final Map<String, Booking> byId = new HashMap<>();

    synchronized void addRoom(Room room) {
        if (rooms.putIfAbsent(room.id, room) != null) {
            throw new IllegalArgumentException("duplicate room");
        }
        calendar.put(room.id, new TreeMap<>());
    }

    synchronized Booking book(String roomId, String organizer, long startMs, long endMs) {
        if (!rooms.containsKey(roomId)) throw new IllegalArgumentException("unknown room");
        if (conflicts(roomId, startMs, endMs)) throw new IllegalStateException("conflict");
        Booking booking = new Booking(UUID.randomUUID().toString(), roomId, organizer, startMs, endMs);
        calendar.get(roomId).put(startMs, booking);
        byId.put(booking.id, booking);
        return booking;
    }

    synchronized void cancel(String bookingId) {
        Booking booking = byId.remove(bookingId);
        if (booking == null) throw new IllegalArgumentException("unknown booking");
        calendar.get(booking.roomId).remove(booking.startMs);
    }

    synchronized String findFree(int minCapacity, long startMs, long endMs) {
        List<String> ids = new ArrayList<>(rooms.keySet());
        Collections.sort(ids);
        for (String roomId : ids) {
            if (rooms.get(roomId).capacity < minCapacity) continue;
            if (!conflicts(roomId, startMs, endMs)) return roomId;
        }
        return null;
    }

    private boolean conflicts(String roomId, long startMs, long endMs) {
        TreeMap<Long, Booking> tree = calendar.get(roomId);
        Map.Entry<Long, Booking> floor = tree.floorEntry(startMs);
        if (floor != null && floor.getValue().overlaps(startMs, endMs)) return true;
        Map.Entry<Long, Booking> ceil = tree.ceilingEntry(startMs);
        if (ceil != null && ceil.getValue().overlaps(startMs, endMs)) return true;
        return false;
    }
}

/** Sibling DSA — drop into findRoom as "how many concurrent meetings," not the product. */
final class MeetingRoomsII {
    static int minRooms(long[][] intervals) {
        Arrays.sort(intervals, Comparator.comparingLong(a -> a[0]));
        PriorityQueue<Long> ends = new PriorityQueue<>();
        for (long[] iv : intervals) {
            if (!ends.isEmpty() && ends.peek() <= iv[0]) ends.poll();
            ends.offer(iv[1]);
        }
        return ends.size();
    }
}

End-to-end flows

1. Book. Resolve room → conflict check on TreeMap floor/ceiling → put startMs → put bookingId.
2. Conflict. Existing 10:00–11:00, new 10:30–11:30: floor is 10:00, end > 10:30 → throw; no put.
3. Back-to-back. 10:00–11:00 then 11:00–12:00: floor end == new start, half-open, no overlap → put.
4. Cancel. byId get → TreeMap remove(startMs) → byId remove. Second cancel throws.
5. Find-free. Scan rooms by sorted id; first with capacity and !conflicts. Does not book until the caller calls book.

Dry-run. Rooms A(4) and B(12). Book A [10,11). findFree(6, 10, 11) skips A (capacity), B is free → "B". Book B [10,11). findFree(4, 10, 11) → null. Cancel B’s id. findFree(4, 10, 11) → "A" (sorted id). MeetingRoomsII on {[10,11),[10,12),[11,12)} : heap grows to 2 then reuses → 2 rooms.

Ten honest follow-ups

1. Same start twice on one room: TreeMap key clash — reject or key by (start, id).
2. Recurring: store a series id + expand instances into the same TreeMap; cancel-one vs cancel-series.
3. Time zones: store Instant; never compare wall-clock strings.
4. Interval tree if they ask “all rooms busy at T” across a campus.
5. Concurrency: one monitor on the scheduler; production = DB exclusion on (room_id, tstzrange).
6. Persistence: Postgres tstzrange + GiST, not this HashMap.
7. findRoom heuristic: min-heap of “last end” per room — that is Meeting Rooms II thinking inside the product.
8. I did not ship a calendar product. Ylogx 30 KPI dashboards are reads, not this booking map.
9. No Kafka “booking events” unless they promote this to HLD — then chapter 23.
10. Attendee overflow: check capacity at book time if they add a headcount field.

Why TreeMap not a list? Conflict must be logarithmic as a room fills a day. Why not only Meeting Rooms II? That cannot cancel or find a named room. What if they paste the DSA? Sort by start, heap of ends, return heap size — then stop unless they still want classes.

Do not say Job 10454435 asks this. Do not call TUF Meeting Rooms II the product. Do not invent Outlook/Google Calendar. Do not start with microservices.

1b. Meeting Rooms II — DSA sibling IE-asked

TUF 06 listed Meeting Rooms II as live DSA (OA numbered Round 1; remap: their R2 is often a first-live analogue, already done for Adarsh). Speak the heap, then if they still want a scheduler, jump back to the product card.

2. Device backup scheduler and restore Standard CS

Question stem. Many devices must be backed up on a cadence. Schedule the next run, record last success, store file chunks, and restore a device to a point in time by replaying chunks.

Evidence / remap. Class C / user-pasted list — no first-hand §5.C URL. Not Ylogx CI/CD. Not Horizon “backup” of a costmap. Other loops may never ask this.

Clarify before classes

• Full vs incremental: v1 = chunked files; restore concatenates chunks in order.
• Cadence: period ms per device; missed window = run immediately when due.
• Clock: scheduler tick with nowMs injected (testable).
• Retention: keep last N snapshots or all chunks until they add GC.
• Restore as-of: latest snapshot ≤ t, then chunks.
• Invalid: unknown device, restore with no snapshot, duplicate chunk index, empty file list.

Data structures

Entities and pattern

BackupJob is a heap value (equals/hash on deviceId if they re-schedule). Chunk is immutable payload metadata (checksum + index), not bytes. No Strategy unless they add “full vs incremental” policies. Tick is a single-threaded event loop, not Observer.

import java.util.*;

final class Chunk {
    final String fileId;
    final int index;
    final String checksum;
    final int bytes;
    Chunk(String fileId, int index, String checksum, int bytes) {
        this.fileId = fileId;
        this.index = index;
        this.checksum = checksum;
        this.bytes = bytes;
    }
}

final class BackupJob implements Comparable<BackupJob> {
    final String deviceId;
    final long dueMs;
    BackupJob(String deviceId, long dueMs) {
        this.deviceId = deviceId;
        this.dueMs = dueMs;
    }
    public int compareTo(BackupJob other) {
        int byDue = Long.compare(dueMs, other.dueMs);
        return byDue != 0 ? byDue : deviceId.compareTo(other.deviceId);
    }
}

final class BackupScheduler {
    private final long periodMs;
    private final PriorityQueue<BackupJob> due = new PriorityQueue<>();
    private final Map<String, Long> lastBackup = new HashMap<>();
    private final Map<String, List<String>> filesByDevice = new HashMap<>();
    private final Map<String, List<Chunk>> chunks = new HashMap<>();
    private final Set<String> known = new HashSet<>();

    BackupScheduler(long periodMs) {
        if (periodMs <= 0) throw new IllegalArgumentException("period");
        this.periodMs = periodMs;
    }

    synchronized void register(String deviceId, long nowMs) {
        if (!known.add(deviceId)) throw new IllegalArgumentException("duplicate device");
        due.offer(new BackupJob(deviceId, nowMs));
        filesByDevice.put(deviceId, new ArrayList<>());
    }

    synchronized BackupJob pollDue(long nowMs) {
        BackupJob job = due.peek();
        if (job == null || job.dueMs > nowMs) return null;
        return due.poll();
    }

    synchronized void recordSuccess(String deviceId, long nowMs,
            List<String> fileIds, Map<String, List<Chunk>> newChunks) {
        if (!known.contains(deviceId)) throw new IllegalArgumentException("unknown device");
        lastBackup.put(deviceId, nowMs);
        filesByDevice.put(deviceId, List.copyOf(fileIds));
        for (String fileId : fileIds) {
            List<Chunk> list = new ArrayList<>(newChunks.getOrDefault(fileId, List.of()));
            list.sort(Comparator.comparingInt(c -> c.index));
            chunks.put(fileId, List.copyOf(list));
        }
        due.offer(new BackupJob(deviceId, nowMs + periodMs));
    }

    synchronized ArrayDeque<Chunk> restorePlan(String deviceId) {
        Long last = lastBackup.get(deviceId);
        if (last == null) throw new IllegalStateException("never backed up");
        ArrayDeque<Chunk> plan = new ArrayDeque<>();
        for (String fileId : filesByDevice.get(deviceId)) {
            List<Chunk> list = chunks.getOrDefault(fileId, List.of());
            for (int i = 0; i < list.size(); i++) {
                Chunk c = list.get(i);
                if (c.index != i) throw new IllegalStateException("gap in " + fileId);
                plan.addLast(c);
            }
        }
        return plan;
    }

    synchronized Long lastBackupMs(String deviceId) {
        return lastBackup.get(deviceId);
    }
}

End-to-end flows

1. Register. known add → offer due=now (immediate first backup).
2. Tick. peek dueMs ≤ now → poll → worker copies files into chunks (outside this class) → recordSuccess → offer due=now+period.
3. Missed window. If tick is late, dueMs is in the past; pollDue still returns it; next due is now+period, not stacked jobs.
4. Restore. lastBackup must exist → walk fileIds → walk chunks in index order into a deque → worker pollFirst until empty.
5. Gap fail. Missing index 1 in a 3-chunk file → throw before returning a half plan.

Dry-run. Register cam-1 at t=0. pollDue(0) → cam-1. recordSuccess with file f1 chunks [0,1]. lastBackup=0, next due=period. pollDue(period-1) → null. pollDue(period) → cam-1. restorePlan: deque [chunk0, chunk1]. pollFirst twice reconstructs f1.

Ten honest follow-ups

1. Re-register: reject; or update period without duplicating heap entries (tombstone generation id).
2. Failed backup: do not advance lastBackup; re-offer due=now+retryBackoff.
3. Incremental: chunk checksum vs last snapshot; only put changed chunks.
4. Retention: drop fileIds older than last N; do not invent S3 lifecycle unless they go HLD (ch. 23).
5. Many devices: heap is O(D); shard by deviceId if they insist on scale.
6. Concurrency: one lock on maps+heap; workers copy bytes off-lock.
7. Argus 20+ cameras: adjacent “many devices,” not this scheduler I shipped. Postgres there stores violations, not backup chunks.
8. Ylogx ECS rolling deploy is not device backup.
9. Clock skew: inject nowMs; do not trust device wall clocks for due.
10. Encryption at rest: metadata flag, not a crypto design in 60 min.

Why a heap not a wheel timer? D is interview-small; heap is enough and obvious. Why a restore queue? So the caller can backpressure per chunk instead of loading the device into RAM. What if no successful backup? Throw; do not return an empty plan that looks like success.

Do not claim Ylogx 99.9% is this product. Do not jump to S3 multipart HLD. Do not invent a missed backup incident.

3. Secure file/media upload + granular ACL + private links Standard CS Resume-derived

Question stem. Upload an object, grant per-principal permissions, mint a time-limited private link, and deny reads that fail ACL or expiry.

Evidence / remap. Class C / user-pasted list — no §5.C URL. Resume adjacent only: Ylogx CloudFront / ECS is CDN + compute, not this ACL product. Ylogx RLS + RBAC 3 tiers is database tenancy (which rows Postgres returns), not object-store ACL. Say the difference out loud if they analogize.

Clarify before classes

• Principals: user ids; groups only if they add them.
• Perms: READ, WRITE, SHARE, OWNER. OWNER implies the rest.
• Links: opaque token → objectId + principal + expiry. Not a guessable path.
• Prefix listing: optional index prefix → object ids.
• Upload: metadata first; bytes are a store interface, not Live Code I/O.
• Invalid: expired token, missing ACL, WRITE without WRITE, mint without SHARE.

Data structures

Entities and pattern

BlobStore is a narrow put/get of bytes (can be a HashMap in Live Code). AccessService owns ACL + tokens. Composition, not inheritance. No Observer. Strategy only if they add “public vs private bucket policy.”

import java.util.*;

enum Perm { READ, WRITE, SHARE, OWNER }

final class ObjectMeta {
    final String id;
    final String owner;
    final String prefix;
    final String contentType;
    final int size;
    ObjectMeta(String id, String owner, String prefix, String contentType, int size) {
        this.id = id;
        this.owner = owner;
        this.prefix = prefix;
        this.contentType = contentType;
        this.size = size;
    }
}

final class SignedLink {
    final String token;
    final String objectId;
    final String principal;
    final long expiryMs;
    SignedLink(String token, String objectId, String principal, long expiryMs) {
        this.token = token;
        this.objectId = objectId;
        this.principal = principal;
        this.expiryMs = expiryMs;
    }
}

final class AccessStore {
    private final Map<String, ObjectMeta> objects = new HashMap<>();
    private final Map<String, Map<String, EnumSet<Perm>>> acl = new HashMap<>();
    private final Map<String, SignedLink> tokens = new HashMap<>();
    private final Map<String, LinkedHashSet<String>> byPrefix = new HashMap<>();
    private final Map<String, byte[]> blobs = new HashMap<>();

    synchronized ObjectMeta upload(String owner, String prefix, String contentType, byte[] data) {
        String id = UUID.randomUUID().toString();
        ObjectMeta meta = new ObjectMeta(id, owner, prefix, contentType, data.length);
        objects.put(id, meta);
        blobs.put(id, data);
        acl.computeIfAbsent(id, ignored -> new HashMap<>())
                .put(owner, EnumSet.allOf(Perm.class));
        byPrefix.computeIfAbsent(prefix, ignored -> new LinkedHashSet<>()).add(id);
        return meta;
    }

    synchronized boolean can(String principal, String objectId, Perm perm) {
        Map<String, EnumSet<Perm>> row = acl.get(objectId);
        if (row == null) return false;
        EnumSet<Perm> set = row.get(principal);
        if (set == null) return false;
        return set.contains(Perm.OWNER) || set.contains(perm);
    }

    synchronized void grant(String actor, String objectId, String principal, Perm perm) {
        if (!can(actor, objectId, Perm.SHARE) && !can(actor, objectId, Perm.OWNER)) {
            throw new SecurityException("acl deny grant");
        }
        acl.computeIfAbsent(objectId, ignored -> new HashMap<>())
                .computeIfAbsent(principal, ignored -> EnumSet.noneOf(Perm.class))
                .add(perm);
    }

    synchronized String mintLink(String actor, String objectId, long nowMs, long ttlMs) {
        if (!can(actor, objectId, Perm.SHARE) && !can(actor, objectId, Perm.READ)) {
            throw new SecurityException("acl deny mint");
        }
        String token = UUID.randomUUID().toString();
        tokens.put(token, new SignedLink(token, objectId, actor, nowMs + ttlMs));
        return token;
    }

    synchronized byte[] openLink(String token, long nowMs) {
        SignedLink link = tokens.get(token);
        if (link == null) throw new SecurityException("unknown token");
        if (nowMs >= link.expiryMs) {
            tokens.remove(token);
            throw new SecurityException("expired");
        }
        if (!can(link.principal, link.objectId, Perm.READ)) {
            throw new SecurityException("acl deny read");
        }
        return blobs.get(link.objectId);
    }

    synchronized byte[] read(String principal, String objectId) {
        if (!can(principal, objectId, Perm.READ)) throw new SecurityException("acl deny read");
        return blobs.get(objectId);
    }
}

End-to-end flows

1. Upload. New id → metadata put → blob put → owner gets all perms → prefix index add.
2. Grant. Actor must SHARE/OWNER → add perm to principal set.
3. Mint. Actor SHARE or READ → token HashMap put with expiry.
4. Open OK. Token get → now < expiry → ACL READ → return bytes.
5. ACL deny / expiry. Missing perm or now ≥ expiry → SecurityException; expired token is removed. Bytes never returned.

Dry-run. Owner o uploads. User u has no row → read throws. o grants u READ. u.read succeeds. o mints token ttl=60s at t=0. open at t=30 succeeds. open at t=60 throws expired; map no longer has the token.

Ten honest follow-ups

1. Revoke token: tokens.remove; ACL revoke is a different map.
2. Group principals: extra map group → members; can() unions member ACLs — only if they ask.
3. Prefix list must still filter by READ per object; listing is not a bypass.
4. CloudFront: edge cache for public assets. Tenant JSON / private media: no. Ylogx named CloudFront → ALB → ECS.
5. RLS 3 tiers: NestJS maps caller → DB role; Postgres hides rows. Not S3 canned ACL.
6. RBAC: who may call the API. ACL: who may read this object. Both can exist; do not merge names.
7. Signed cookies vs query token: same HashMap idea; I did not ship this service.
8. ECS task role is AWS API auth, not end-user ACL.
9. GiftedBooks per-user PDFs: product isolation on the resume; GitHub currently mismatches AegisAI — speak resume only.
10. HLD multipart / S3 consistency → chapter 23.

Why token HashMap not a JWT-only design? Revoke is then a denylist anyway; interview wants an explicit map. Why OWNER implies all? So you cannot orphan an object with no reader. Difference vs RLS? RLS filters rows in SQL; this filters object keys in an app map.

Do not say “I built S3 ACL at Ylogx.” Do not cache private objects at CloudFront. Do not give phishing or token-theft recipes. InstaRecon: consent demo only, then redirect.

4. Log parser (many files) Standard CS Resume-derived

Question stem. Parse many log files, extract fields, aggregate (count / sum), optionally top-K keys, without loading every file into RAM.

Evidence / remap. Class C / user-pasted list. A US four-round paste mentioned “log parser SD” as NMF / paste-only — not a UTA URL. Argus: Postgres logs of violations — adjacent store, not this streaming parser I shipped.

Clarify before classes

• Format: combined Apache, JSON lines, or custom regex — lock one.
• Bad lines: skip + counter, or fail-fast — pick skip+count for ops logs.
• Aggregation key: status, ip, errorCode.
• Top-K vs full dump.
• Files: iterator of paths; one line at a time.
• Invalid: unreadable file, empty directory, regex mismatch.

Data structures

Entities and pattern

LineParser Strategy (regex vs JSON). LogAggregator owns the map. Composite if they add multiple sinks — only then.

import java.util.*;
import java.util.regex.*;

final class LogRecord {
    final String key;
    final long value;
    LogRecord(String key, long value) {
        this.key = key;
        this.value = value;
    }
}

interface LineParser {
    LogRecord parse(String line);
}

final class RegexLineParser implements LineParser {
    private final Pattern pattern;
    private final int keyGroup;
    private final int valueGroup;
    RegexLineParser(String regex, int keyGroup, int valueGroup) {
        this.pattern = Pattern.compile(regex);
        this.keyGroup = keyGroup;
        this.valueGroup = valueGroup;
    }
    public LogRecord parse(String line) {
        Matcher m = pattern.matcher(line);
        if (!m.matches()) return null;
        String key = m.group(keyGroup);
        long value = valueGroup < 0 ? 1L : Long.parseLong(m.group(valueGroup));
        return new LogRecord(key, value);
    }
}

final class LogAggregator {
    private final LineParser parser;
    private final Map<String, long[]> agg = new HashMap<>();
    private int skipped;

    LogAggregator(LineParser parser) {
        this.parser = parser;
    }

    void consume(Iterator<String> lines) {
        while (lines.hasNext()) {
            LogRecord rec = parser.parse(lines.next());
            if (rec == null) {
                skipped++;
                continue;
            }
            long[] slot = agg.computeIfAbsent(rec.key, ignored -> new long[2]);
            slot[0]++;          // count
            slot[1] += rec.value; // sum
        }
    }

    List<Map.Entry<String, Long>> topK(int k) {
        PriorityQueue<Map.Entry<String, Long>> heap =
                new PriorityQueue<>(Comparator.comparingLong(Map.Entry::getValue));
        for (Map.Entry<String, long[]> e : agg.entrySet()) {
            heap.offer(Map.entry(e.getKey(), e.getValue()[0]));
            if (heap.size() > k) heap.poll();
        }
        List<Map.Entry<String, Long>> out = new ArrayList<>(heap);
        out.sort((a, b) -> Long.compare(b.getValue(), a.getValue()));
        return out;
    }

    int skipped() {
        return skipped;
    }
}

End-to-end flows

1. Open files. For each path, BufferedReader lines iterator — not Files.readAllLines.
2. Parse OK. Regex matches → merge count/sum.
3. Parse fail. null record → skipped++; continue. Do not abort the folder unless they asked fail-fast.
4. Report. topK heap poll remnants, sort descending.
5. Empty. topK empty list; skipped may still be > 0.

Dry-run. Lines: ERROR auth, ERROR auth, WARN disk, not a log. Regex (ERROR|WARN) (\\w+) key=group2. agg: auth→2, disk→1, skipped=1. topK(1) → auth=2.

Ten honest follow-ups

1. Multiline stack traces: state machine “in exception” until a timestamp line.
2. JSON: parse one object per line; same aggregator.
3. Parallel files: one map per file, then merge; watch heap memory of unique keys.
4. Argus: 20+ cameras, 24 FPS detector, violations in Postgres — query SQL, do not grep video.
5. Ylogx: CloudWatch-style thinking is HLD; I will not invent a log pipeline I did not run.
6. Time window: filter by parsed timestamp before merge (see next card for MA).
7. Cardinality explosion: cap unique keys; overflow bucket.
8. Charset / UTF-8: decode errors count as skip.
9. Gzip: wrap InputStream; still line-iterate.
10. No Kafka log bus on this resume.

Why not load all lines? Interview files can be large; RAM is the point. Why heap not sort? K ≪ unique keys. Argus relation? Same idea of structured events; different store.

Do not say you wrote this parser at Argus. Do not dump full confidential logs. Do not invent ELK as internship ownership.

5. Streaming error-log counting + moving average Standard CS

Question stem. Events arrive over time (error code + latency or count). Maintain per-code counts and a moving average over the last W milliseconds (or last N samples) in O(1) per event.

Evidence / remap. Class C / user-pasted list — no §5.C URL. Related DSA: sliding window; not a named UTA LLD.

Clarify before classes

• Window: last N samples vs last W ms — implement W ms with a deque of timestamps.
• Metric: latency MA, or error-rate MA — same deque+sum.
• Per-code counts: lifetime vs in-window — ask; code both lifetime map + window deque.
• Out-of-order events: v1 reject ts < lastTs.
• Invalid: negative latency, blank code, W ≤ 0.

Data structures

Entities and pattern

One ErrorWindow owner. No Strategy unless they plug EMA vs SMA. Not Observer — the caller pushes events.

import java.util.*;

final class Sample {
    final long tsMs;
    final String code;
    final long value;
    Sample(long tsMs, String code, long value) {
        this.tsMs = tsMs;
        this.code = code;
        this.value = value;
    }
}

final class ErrorWindow {
    private final long windowMs;
    private final ArrayDeque<Sample> window = new ArrayDeque<>();
    private final Map<String, Integer> inWindowCounts = new HashMap<>();
    private final Map<String, Integer> lifetimeCounts = new HashMap<>();
    private long sum;
    private long lastTs = Long.MIN_VALUE;

    ErrorWindow(long windowMs) {
        if (windowMs <= 0) throw new IllegalArgumentException("window");
        this.windowMs = windowMs;
    }

    synchronized void add(long tsMs, String code, long value) {
        if (code == null || code.isBlank()) throw new IllegalArgumentException("code");
        if (value < 0) throw new IllegalArgumentException("value");
        if (tsMs < lastTs) throw new IllegalArgumentException("out of order");
        lastTs = tsMs;
        evict(tsMs);
        window.addLast(new Sample(tsMs, code, value));
        sum += value;
        inWindowCounts.merge(code, 1, Integer::sum);
        lifetimeCounts.merge(code, 1, Integer::sum);
    }

    synchronized double movingAverage(long nowMs) {
        evict(nowMs);
        if (window.isEmpty()) return 0.0;
        return (double) sum / window.size();
    }

    synchronized int countInWindow(String code, long nowMs) {
        evict(nowMs);
        return inWindowCounts.getOrDefault(code, 0);
    }

    synchronized int lifetime(String code) {
        return lifetimeCounts.getOrDefault(code, 0);
    }

    private void evict(long nowMs) {
        long cutoff = nowMs - windowMs;
        while (!window.isEmpty() && window.peekFirst().tsMs <= cutoff) {
            Sample old = window.pollFirst();
            sum -= old.value;
            int left = inWindowCounts.merge(old.code, -1, Integer::sum);
            if (left == 0) inWindowCounts.remove(old.code);
        }
    }
}

End-to-end flows

1. Add inside window. addLast, sum += v, counts ++.
2. Window update. New event or movingAverage(now) calls evict: pollFirst while ts ≤ now−W, sum −=, window count −−.
3. Empty window. MA returns 0; do not divide by zero.
4. Out of order. throw; alternative follow-up is a TreeMap by ts (log n).
5. Count vs MA. lifetime map never decrements; in-window map does.

Dry-run. W=1000. Add (0, E500, 10), (400, E500, 30), then (1500, E404, 20). The third add evicts ts≤500 first (drops t=0; sum 40→30; E500=1) then appends 20 → sum=50, size 2, MA=25. inWindow E500=1, E404=1. lifetime E500=2.

Ten honest follow-ups

1. EMA: ema = alpha * x + (1-alpha) * ema — O(1) memory, not exact window.
2. Ring of N: overwrite buf[i%N], adjust sum by the evicted slot.
3. Thread: one lock, or single writer thread (Horizon-style camera loop — adjacent, not this class).
4. Horizon GStreamer 60 FPS: why you bound queues on the rover; not this error MA product.
5. Argus 24 FPS: drop stale frames rather than grow a deque without evict — same backpressure idea.
6. Percentile: deque of values is not enough; need a histogram (follow-up, heavier).
7. Distributed MA: not this card; ch. 23 if they insist.
8. Clock jump: inject now; do not mix wall clock and nanoTime.
9. Zero events: MA 0 is defined; say it.
10. I did not ship a metrics pipeline; Ylogx sub-210 ms is cache+edge, not this deque.

Why deque+sum not scan? Each event would be O(n) if you recompute. Why two count maps? Lifetime vs window answer different probes. Out-of-order? Reject in v1; TreeMap if they require it.

Do not invent p95 or a Grafana board. Do not put Kafka in the moving average. Do not claim Argus mAP is this MA.

6. Parking Lot IE-asked

Question stem. Assign a compatible spot, issue a ticket, release the spot, compute a fee. In-memory. Compact card — full walk-through lives in chapter 06 § parking lot.

Evidence / remap. GFG fresher: Parking Lot OOD as R2 after Burning Tree + Merge Intervals (GFG fresher). Not UTA/AUTA Rank A two-DSA. DevBrainiac labeled Parking Lot as their R3 in an experienced four-round loop — NMF, not Adarsh’s third live. Taanya “similar to parking lot” + intervals is similar-to, not a second independent Parking Lot. Job 10454435 still none. Your loop may differ.

Clarify before classes

• Vehicle: motorcycle / car / bus. Spots: motorcycle / compact / large. Can smaller vehicles use larger spots? Default yes.
• One active plate. Ticket in, pay out.
• EV / reserved only if they add it. One lot first; floors as follow-up.
• Invalid: full lot, duplicate plate, unknown or double-exit ticket.

Data structures

Entities and pattern

ParkingLot owner. PricingPolicy Strategy. Ticket immutable. Compatibility on ParkingSpot.canFit.

import java.util.*;

enum SpotType { MOTORCYCLE, COMPACT, LARGE }
enum VehicleType { MOTORCYCLE, CAR, BUS }

final class Vehicle {
    final String plate;
    final VehicleType type;
    Vehicle(String plate, VehicleType type) {
        this.plate = plate;
        this.type = type;
    }
}

final class ParkingSpot {
    final String id;
    final SpotType type;
    private Vehicle occupant;
    ParkingSpot(String id, SpotType type) {
        this.id = id;
        this.type = type;
    }
    boolean canFit(Vehicle v) {
        if (occupant != null) return false;
        if (v.type == VehicleType.MOTORCYCLE) return true;
        if (v.type == VehicleType.CAR) return type != SpotType.MOTORCYCLE;
        return type == SpotType.LARGE;
    }
    void occupy(Vehicle v) { occupant = v; }
    void release() { occupant = null; }
}

final class ParkingTicket {
    final String id;
    final String spotId;
    final String plate;
    final long inMs;
    ParkingTicket(String id, String spotId, String plate, long inMs) {
        this.id = id;
        this.spotId = spotId;
        this.plate = plate;
        this.inMs = inMs;
    }
}

interface PricingPolicy {
    int cents(ParkingTicket t, long outMs);
}

final class HourlyPricing implements PricingPolicy {
    private final int centsPerHour;
    HourlyPricing(int centsPerHour) { this.centsPerHour = centsPerHour; }
    public int cents(ParkingTicket t, long outMs) {
        long hours = Math.max(1L, (outMs - t.inMs + 3_599_999L) / 3_600_000L);
        return Math.toIntExact(hours * (long) centsPerHour);
    }
}

final class ParkingLot {
    private final Map<String, ParkingSpot> spots = new HashMap<>();
    private final Map<SpotType, Deque<ParkingSpot>> free = new EnumMap<>(SpotType.class);
    private final Map<String, ParkingTicket> open = new HashMap<>();
    private final Set<String> plates = new HashSet<>();
    private final PricingPolicy pricing;

    ParkingLot(PricingPolicy pricing) {
        this.pricing = pricing;
        for (SpotType t : SpotType.values()) free.put(t, new ArrayDeque<>());
    }

    void addSpot(ParkingSpot s) {
        spots.put(s.id, s);
        free.get(s.type).addLast(s);
    }

    synchronized ParkingTicket enter(Vehicle v) {
        if (!plates.add(v.plate)) throw new IllegalStateException("already inside");
        ParkingSpot spot = firstFit(v);
        if (spot == null) {
            plates.remove(v.plate);
            return null;
        }
        free.get(spot.type).remove(spot);
        spot.occupy(v);
        ParkingTicket t = new ParkingTicket(UUID.randomUUID().toString(), spot.id, v.plate,
                System.currentTimeMillis());
        open.put(t.id, t);
        return t;
    }

    synchronized int exit(String ticketId, long outMs) {
        ParkingTicket t = open.remove(ticketId);
        if (t == null) throw new IllegalArgumentException("unknown ticket");
        ParkingSpot s = spots.get(t.spotId);
        s.release();
        free.get(s.type).addLast(s);
        plates.remove(t.plate);
        return pricing.cents(t, outMs);
    }

    private ParkingSpot firstFit(Vehicle v) {
        for (SpotType type : SpotType.values()) {
            for (ParkingSpot s : free.get(type)) {
                if (s.canFit(v)) return s;
            }
        }
        return null;
    }
}

End-to-end flows

1. Enter. plate add → firstFit → remove from free deque → occupy → ticket put.
2. Full. firstFit null → plate rollback → return null. No overwrite.
3. Exit. ticket remove → release → free addLast → fee.
4. Unknown ticket. throw before touching spots.
5. Interval follow-up (Taanya). Sweep [in,out) events for occupancy vs capacity — DSA, not a second lot class.

Dry-run. Compact C1, large L1. Car enters → C1, ticket T. Bus enter → L1. Second car → null if no compact/large left. Exit T at +70 min, ₹100/h → 2 hours (ceil).

Ten honest follow-ups

1. Multi-floor: Floor owns free maps; lot picks nearest floor with fit.
2. EV/reserved: new SpotType + pricing strategy (OCP), do not rewrite enter.
3. Wait queue: Deque of vehicles when full.
4. Lost ticket: lookup by plate + penalty policy.
5. One lock per floor if they add gates.
6. Do not call this “the AUTA R3.”
7. I did not ship a parking product.
8. Stream occupancy: sort events, running count — same as Meeting Rooms II heap family.
9. No Kafka gate events.
10. DevBrainiac R3 parking is experienced 4-round NMF.

Why free deques? Availability without scanning occupied spots. Why Strategy for price? New rates without editing enter/exit. Full lot? Return null or enqueue — say which.

Do not invent Amazon Go. Do not say Job 10454435 asks parking. Do not start with microservices per floor.

7. Vending machine Standard CS

Question stem. Idle → select item → accept payment → dispense → idle. Inventory per SKU. Reject sold-out and insufficient funds. Refund on cancel.

Evidence / remap. Not an IE. getpersonalisedcv 2026 guide invented a “vending machine R3” — Class C coaching, not a first-hand loop. Treat as Standard CS State + Strategy. Your loop may never ask this.

Clarify before classes

• One item per transaction vs cart — v1 one SKU.
• Exact change vs make change from a coin box.
• Payment: cash and card as Strategy.
• Invalid: unknown SKU, qty 0, pay in Idle, dispense twice.

Data structures

Entities and pattern

State: Idle, HasSelection, HasTender. Strategy: PaymentMethod. Machine owns inventory + catalog + state.

import java.util.*;

interface PaymentMethod {
    int capture(int dueCents, int tenderedCents);
}

final class CashPayment implements PaymentMethod {
    public int capture(int dueCents, int tenderedCents) {
        if (tenderedCents < dueCents) throw new IllegalStateException("insufficient");
        return tenderedCents - dueCents;
    }
}

interface VendingState {
    void select(VendingMachine m, String sku);
    void insert(VendingMachine m, int cents);
    int cancel(VendingMachine m);
    int dispense(VendingMachine m);
}

final class IdleState implements VendingState {
    public void select(VendingMachine m, String sku) {
        m.choose(sku);
        m.setState(m.hasSelection);
    }
    public void insert(VendingMachine m, int cents) {
        throw new IllegalStateException("select first");
    }
    public int cancel(VendingMachine m) { return 0; }
    public int dispense(VendingMachine m) {
        throw new IllegalStateException("nothing selected");
    }
}

final class HasSelectionState implements VendingState {
    public void select(VendingMachine m, String sku) { m.choose(sku); }
    public void insert(VendingMachine m, int cents) {
        m.addTender(cents);
        m.setState(m.hasTender);
    }
    public int cancel(VendingMachine m) {
        m.clearSelection();
        m.setState(m.idle);
        return 0;
    }
    public int dispense(VendingMachine m) {
        throw new IllegalStateException("pay first");
    }
}

final class HasTenderState implements VendingState {
    public void select(VendingMachine m, String sku) {
        throw new IllegalStateException("cancel or dispense");
    }
    public void insert(VendingMachine m, int cents) { m.addTender(cents); }
    public int cancel(VendingMachine m) {
        int back = m.clearTender();
        m.clearSelection();
        m.setState(m.idle);
        return back;
    }
    public int dispense(VendingMachine m) {
        int change = m.commitDispense();
        m.setState(m.idle);
        return change;
    }
}

final class VendingMachine {
    final VendingState idle = new IdleState();
    final VendingState hasSelection = new HasSelectionState();
    final VendingState hasTender = new HasTenderState();
    private VendingState state = idle;
    private final Map<String, Integer> inventory = new HashMap<>();
    private final Map<String, Integer> price = new HashMap<>();
    private final PaymentMethod payment;
    private String selected;
    private int tender;

    VendingMachine(PaymentMethod payment) { this.payment = payment; }

    void stock(String sku, int qty, int cents) {
        inventory.put(sku, qty);
        price.put(sku, cents);
    }

    void setState(VendingState s) { state = s; }
    void choose(String sku) {
        if (inventory.getOrDefault(sku, 0) <= 0) throw new IllegalStateException("sold out");
        selected = sku;
    }
    void addTender(int cents) { tender += cents; }
    int clearTender() { int t = tender; tender = 0; return t; }
    void clearSelection() { selected = null; }

    int commitDispense() {
        int due = price.get(selected);
        int change = payment.capture(due, tender);
        inventory.merge(selected, -1, Integer::sum);
        tender = 0;
        selected = null;
        return change;
    }

    public void select(String sku) { state.select(this, sku); }
    public void insert(int cents) { state.insert(this, cents); }
    public int cancel() { return state.cancel(this); }
    public int dispense() { return state.dispense(this); }
}

End-to-end flows

1. Happy. select A1 (qty 2) → insert 100 → insert 50 (due 120) → dispense → change 30, qty 1, Idle.
2. Sold out. qty 0 → choose throws; state stays Idle.
3. Insufficient. capture throws; inventory unchanged; they may insert more in HasTender.
4. Cancel. return tender; no decrement.
5. Dispense in Idle. throw.

Dry-run. stock A1 qty=1 price=100. select A1, insert 100, dispense → change 0, qty 0. select A1 → sold out. insert 50 in Idle → throw.

Ten honest follow-ups

1. Make change: coin box map denomination → count; greedy then fail if cannot.
2. Card payment: capture(due, due) always; no tender field — new Strategy.
3. Multi-item cart: extra state; keep inventory decrement atomic at dispense.
4. Restock: admin method, not customer state.
5. getpersonalisedcv is not evidence — do not cite it in the room.
6. I never shipped a vending machine.
7. Concurrency: one lock; two customers need two machines or a queue.
8. Do not add Kafka “dispense events.”
9. Hardware jam: state Jammed, refund tender, do not decrement if motor failed.
10. Not Job 10454435.

Why State not booleans? Illegal calls are obvious in the wrong class. Why Strategy for pay? Card vs cash without duplicating dispense. Sold out when? At select, not after payment if we check inventory again at commit.

Do not treat getpersonalisedcv as an interview experience. Do not claim an AUTA vending round.

8. Library management Standard CS

Question stem. Catalog of books (ISBN), physical copies, members, checkout, due dates, reservations when a title is exhausted.

Evidence / remap. Class C / user-pasted LMS-style list — no §5.C first-hand URL for this product. Pratyush “file library” is recursive files + inheritance, a different prompt. Do not merge.

Clarify before classes

• Book (ISBN, metadata) vs Copy (copyId, status).
• One active loan per copy. Member loan cap optional.
• Reservation FIFO when all copies are borrowed.
• Due: overdue query needs copies by due time.
• Invalid: checkout missing copy, return wrong member, reserve when a copy is on shelf.

Data structures

Entities and pattern

Library owner. No inheritance Book vs Copy — composition. Queue is the reservation pattern, not Observer.

import java.util.*;

enum CopyStatus { ON_SHELF, LOANED, HOLD }

final class Book {
    final String isbn;
    final String title;
    Book(String isbn, String title) {
        this.isbn = isbn;
        this.title = title;
    }
}

final class Copy {
    final String copyId;
    final String isbn;
    CopyStatus status = CopyStatus.ON_SHELF;
    String borrowerId;
    long dueMs;
    Copy(String copyId, String isbn) {
        this.copyId = copyId;
        this.isbn = isbn;
    }
}

final class Library {
    private final Map<String, Book> books = new HashMap<>();
    private final Map<String, Copy> copies = new HashMap<>();
    private final Map<String, List<String>> copiesByIsbn = new HashMap<>();
    private final Map<String, LinkedHashSet<String>> loans = new HashMap<>();
    private final TreeMap<Long, LinkedHashSet<String>> due = new TreeMap<>();
    private final Map<String, ArrayDeque<String>> holds = new HashMap<>();
    private final int loanDaysMs;

    Library(int loanDaysMs) { this.loanDaysMs = loanDaysMs; }

    void addBook(Book b) { books.put(b.isbn, b); }

    void addCopy(Copy c) {
        if (!books.containsKey(c.isbn)) throw new IllegalArgumentException("unknown isbn");
        copies.put(c.copyId, c);
        copiesByIsbn.computeIfAbsent(c.isbn, ignored -> new ArrayList<>()).add(c.copyId);
    }

    synchronized String checkout(String memberId, String isbn, long nowMs) {
        Copy copy = findOnShelf(isbn);
        if (copy == null) throw new IllegalStateException("none on shelf");
        copy.status = CopyStatus.LOANED;
        copy.borrowerId = memberId;
        copy.dueMs = nowMs + loanDaysMs;
        loans.computeIfAbsent(memberId, ignored -> new LinkedHashSet<>()).add(copy.copyId);
        due.computeIfAbsent(copy.dueMs, ignored -> new LinkedHashSet<>()).add(copy.copyId);
        return copy.copyId;
    }

    synchronized void reserve(String memberId, String isbn) {
        if (findOnShelf(isbn) != null) throw new IllegalStateException("copy available");
        holds.computeIfAbsent(isbn, ignored -> new ArrayDeque<>()).addLast(memberId);
    }

    synchronized void returnCopy(String copyId, long nowMs) {
        Copy copy = copies.get(copyId);
        if (copy == null || copy.status != CopyStatus.LOANED) {
            throw new IllegalStateException("not on loan");
        }
        loans.get(copy.borrowerId).remove(copyId);
        LinkedHashSet<String> bucket = due.get(copy.dueMs);
        if (bucket != null) {
            bucket.remove(copyId);
            if (bucket.isEmpty()) due.remove(copy.dueMs);
        }
        copy.borrowerId = null;
        copy.dueMs = 0;
        ArrayDeque<String> q = holds.get(copy.isbn);
        if (q != null && !q.isEmpty()) {
            copy.status = CopyStatus.HOLD;
            copy.borrowerId = q.pollFirst();
        } else {
            copy.status = CopyStatus.ON_SHELF;
        }
    }

    synchronized List<String> overdue(long nowMs) {
        List<String> out = new ArrayList<>();
        for (LinkedHashSet<String> set : due.headMap(nowMs, false).values()) {
            out.addAll(set);
        }
        return out;
    }

    private Copy findOnShelf(String isbn) {
        for (String id : copiesByIsbn.getOrDefault(isbn, List.of())) {
            Copy c = copies.get(id);
            if (c.status == CopyStatus.ON_SHELF) return c;
        }
        return null;
    }
}

End-to-end flows

1. Checkout. find ON_SHELF → LOANED → loans add → due TreeMap put.
2. None free. throw; caller may reserve → queue addLast.
3. Return with hold. due remove → poll reservation → HOLD for that member (not ON_SHELF).
4. Return no hold. ON_SHELF.
5. Overdue. due.headMap(now) collect copy ids.

Dry-run. ISBN 111, copies c1 c2. checkout m1 → c1. checkout m2 → c2. checkout m3 throws. reserve m3. return c1 → c1 HOLD for m3, not available to m4. overdue just after dueMs: [c2] if m2 still holds it.

Ten honest follow-ups

1. Loan cap: loans.get(member).size() ≥ N → reject.
2. Renew: move due key; reject if another member is queued.
3. HOLD pickup timeout: tick moves HOLD back to queue or shelf.
4. Search by title: secondary map / inverted words — not ISBN HashMap.
5. GiftedBooks is PDF RAG, not this LMS. Resume wins vs GitHub AegisAI mismatch.
6. Fine calculation: (now-due) * rate; not a new map.
7. Concurrency: one lock; production = row lock on copyId.
8. Do not merge with Pratyush file-library Composite.
9. No Kafka “book returned” bus.
10. Not Job 10454435.

Why Copy ≠ Book? Two copies of the same ISBN can be in different states. Why TreeMap for due? Overdue is a prefix of time, not a scan. Why queue? Fairness; a set would starve no one randomly but not FIFO.

Do not invent student headcount. Do not speak GiftedBooks as a library ILS.

9. Elevator controller IE-asked

Question stem. Hall calls (up/down) and cabin buttons. Schedule cars. Step the simulation. DoS / flood of hall-call API as a cyber follow-up.

Evidence / remap. GFG 2025: Elevator Controller LLD + DoS as Tech 2, OA+2 (GFG 2025). Mapped as R2 analogue — already-done shape for Adarsh’s second live, still fair if a later live repeats OOD. DoS rate-cap is not the Rate Limiter SD card (independent SDE I count stays 1 → chapter 23).

Clarify before classes

• One shaft vs N cars. Floors 0..F.
• SCAN / LOOK vs nearest-idle car.
• Capacity/weight only if they add it.
• Single-threaded tick vs thread per car.
• DoS = unauthenticated hallCall flood.

Data structures

Entities and pattern

DispatchPolicy Strategy (NearestCar). Car owns TreeSets. Controller owns cars + hail cap.

import java.util.*;
import java.util.concurrent.atomic.AtomicInteger;

enum Direction { UP, DOWN, IDLE }

final class HallRequest {
    final int floor;
    final Direction dir;
    HallRequest(int floor, Direction dir) {
        this.floor = floor;
        this.dir = dir;
    }
}

interface DispatchPolicy {
    int pickCar(List<ElevatorCar> cars, HallRequest r);
}

final class NearestCarPolicy implements DispatchPolicy {
    public int pickCar(List<ElevatorCar> cars, HallRequest r) {
        int best = 0;
        int bestDist = Integer.MAX_VALUE;
        for (int i = 0; i < cars.size(); i++) {
            int d = Math.abs(cars.get(i).floor - r.floor);
            if (d < bestDist) {
                bestDist = d;
                best = i;
            }
        }
        return best;
    }
}

final class ElevatorCar {
    final int id;
    int floor = 0;
    Direction dir = Direction.IDLE;
    final TreeSet<Integer> ups = new TreeSet<>();
    final TreeSet<Integer> downs = new TreeSet<>(Comparator.reverseOrder());

    ElevatorCar(int id) { this.id = id; }

    void addStop(int dest) {
        if (dest >= floor) ups.add(dest);
        else downs.add(dest);
        if (dir == Direction.IDLE) {
            dir = dest >= floor ? Direction.UP : Direction.DOWN;
        }
    }

    void step() {
        if (dir == Direction.UP && !ups.isEmpty()) {
            floor = ups.pollFirst();
            if (ups.isEmpty()) dir = downs.isEmpty() ? Direction.IDLE : Direction.DOWN;
        } else if (dir == Direction.DOWN && !downs.isEmpty()) {
            floor = downs.pollFirst();
            if (downs.isEmpty()) dir = ups.isEmpty() ? Direction.IDLE : Direction.UP;
        }
    }
}

final class ElevatorController {
    private final List<ElevatorCar> cars = new ArrayList<>();
    private final DispatchPolicy policy;
    private long windowStartMs = 0;
    private int windowCount = 0;
    private static final int HAIL_CAP = 50;
    private final AtomicInteger hails = new AtomicInteger();

    ElevatorController(int n, DispatchPolicy policy) {
        this.policy = policy;
        for (int i = 0; i < n; i++) cars.add(new ElevatorCar(i));
    }

    public synchronized boolean hallCall(int floor, Direction dir, long nowMs) {
        if (flooded(nowMs)) return false;
        int idx = policy.pickCar(cars, new HallRequest(floor, dir));
        cars.get(idx).addStop(floor);
        return true;
    }

    public synchronized void cabinSelect(int carId, int floor) {
        cars.get(carId).addStop(floor);
    }

    public synchronized void tick() {
        for (ElevatorCar c : cars) c.step();
    }

    private boolean flooded(long nowMs) {
        if (nowMs - windowStartMs >= 1000) {
            windowStartMs = nowMs;
            windowCount = 0;
        }
        windowCount++;
        hails.incrementAndGet();
        return windowCount > HAIL_CAP;
    }
}

End-to-end flows

1. Hall request. DoS check → pick car → addStop into ups or downs → set dir if IDLE.
2. Tick. pollFirst next floor in current direction; flip when that set empties.
3. Cabin select. Same addStop; no hail cap (authenticated panel).
4. DoS. 51st hail in 1s → false; cars do not enqueue.
5. Idle. both sets empty → Direction.IDLE.

Dry-run. Car at 0 IDLE. hallCall(5, UP) → ups={5}, dir=UP. tick → floor=5, ups empty, IDLE. hallCall(2, DOWN) while at 5 → downs={2}. tick → floor=2.

Ten honest follow-ups

1. Stuck car: remove from dispatch; dump stops onto others.
2. Capacity: reject addStop if weight exceeded — only if they ask.
3. LOOK vs SCAN: SCAN continues to the end of the set; LOOK turns at the last request.
4. One controller per building, not a Kafka cluster.
5. DoS ≠ Rate Limiter IE (count stays 1, ch. 23).
6. Argus 20+ cameras: flood-of-events talk, not an elevator I shipped.
7. Duplicate hall to same floor: TreeSet add is idempotent — good.
8. Nearest policy can send a busy car; follow-up: idle-first then nearest.
9. OA+2 GFG is not UTA two-DSA default.
10. Not Job 10454435.

Why two TreeSets? Directional SCAN without scanning all floors. Why fail closed on flood? Cars thrash and strand people — availability of the shaft, not a pixel. One car stuck path? TreeSet + hallCall + tick, then N cars.

Do not merge this with the distributed rate limiter card. Do not invent a building you operated.

10. LRU Cache IE-asked

Question stem. Capacity-K cache: get and put in O(1). Evict the least recently used key on overflow.

Evidence / remap. Bhavya Interview 2, Hyderabad onsite (Bhavya). Not Login Tracker (new_login / get_oldest_login is unverified mentor-only, bible §10). Not Ylogx Redis maxmemory — Redis −35% was a bot DB cache, different layer. Spring login layers were Bhavya HM, not this cache. Roundz LRU in R4/BR is a different loop (NMF placement).

Clarify before classes

• get miss: -1 or Optional.empty.
• put existing: update value and mark most recent.
• Thread safety only if they ask.
• TTL: not LRU; say so if they mix.

Data structures

Entities and pattern

One class. Extensible eviction is the LFU IE (Reddit 1idtlan) — Strategy only if they ask to swap LRU/LFU. Not Observer.

import java.util.*;

final class LruCache {
    private static final class Node {
        int key;
        int val;
        Node prev, next;
        Node(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }

    private final int cap;
    private final Map<Integer, Node> map = new HashMap<>();
    private final Node head = new Node(-1, -1);
    private final Node tail = new Node(-1, -1);

    LruCache(int cap) {
        if (cap <= 0) throw new IllegalArgumentException("cap");
        this.cap = cap;
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        Node n = map.get(key);
        if (n == null) return -1;
        unlink(n);
        addToTail(n);
        return n.val;
    }

    public void put(int key, int val) {
        Node n = map.get(key);
        if (n != null) {
            n.val = val;
            unlink(n);
            addToTail(n);
            return;
        }
        if (map.size() == cap) {
            Node lru = head.next;
            unlink(lru);
            map.remove(lru.key);
        }
        Node fresh = new Node(key, val);
        map.put(key, fresh);
        addToTail(fresh);
    }

    private void unlink(Node n) {
        n.prev.next = n.next;
        n.next.prev = n.prev;
    }

    private void addToTail(Node n) {
        Node last = tail.prev;
        last.next = n;
        n.prev = last;
        n.next = tail;
        tail.prev = n;
    }
}

End-to-end flows

1. Put new under cap. map put + addToTail.
2. Get hit. unlink + addToTail; return val.
3. Put existing. update val; move to tail (does not grow size).
4. Put at cap. unlink head.next, map remove, then insert new at tail.
5. Get miss. -1; list unchanged.

Dry-run. cap=2. put(1,1) put(2,2) get(1) put(3,3). After get(1), recency is 2 then 1. put 3 evicts 2. get(2)=-1, get(1)=1, get(3)=3.

Ten honest follow-ups

1. Generic K,V: same nodes.
2. Thread-safe: synchronize the cache; ConcurrentHashMap alone cannot move a DLL safely.
3. TTL: extra expiry heap — different problem.
4. LFU: freq buckets; different IE.
5. LinkedHashMap accessOrder=true is the JDK sidecar — they often want the DLL.
6. Login Tracker: HashMap+DLL oldest-at-head, but unverified — do not volunteer.
7. Ylogx Redis −35%: application cache keyed by tier, not this Java LRU I wrote in prod.
8. Redis maxmemory allkeys-lru is the server; I did not configure it as the intern story.
9. Bhavya HM was Spring layers, not this.
10. Not Job 10454435.

Why dummy nodes? Unlink without null checks. Why not a timestamp sort? That is O(n) or O(log n), not O(1). Miss? Return -1, do not fabricate.

Do not call this Login Tracker. Do not say you implemented Redis LRU at Ylogx.

11. Playlist-Mixing (DJ + recs) Standard CS

Question stem. Mix a DJ playlist and a recommendation stream at equal or custom ratio, apply filters (already played, genre, dislike), never repeat a track in the session.

Evidence / remap. NMF — FTC / mid-level LLD, not UTA two-DSA. Seed LC 6629134 (body not opened as a full requirement list this fleet; bible already NMF). Related but different: Prince Spotify insert/delete/search O(1); Jyoti Music Playlist (SERP/404); LC 6570344 Song/Artist/Album. Do not merge those into this mixer. Your loop may differ.

Clarify before classes

• Ratio DJ:rec = 1:1 or custom weights (e.g. 2:1).
• Filters: skip seen, skip explicit, genre allow-list — pipeline.
• Exhaustion: if DJ runs out, drain recs or stop — ask.
• Session vs persistent playlist.

Data structures

Entities and pattern

Strategy: MixPolicy (equal vs weighted). Filters: composition of predicates (specification). Not Observer.

import java.util.*;
import java.util.function.Predicate;

final class Track {
    final String id;
    final String genre;
    final boolean explicit;
    Track(String id, String genre, boolean explicit) {
        this.id = id;
        this.genre = genre;
        this.explicit = explicit;
    }
}

final class PlaylistMixer {
    private final List<Track> dj;
    private final Iterator<Track> recs;
    private final int djWeight;
    private final int recWeight;
    private final List<Predicate<Track>> filters;
    private final Set<String> seen = new HashSet<>();
    private int djIssued;
    private int recIssued;
    private int djIndex;

    PlaylistMixer(List<Track> dj, Iterator<Track> recs, int djWeight, int recWeight,
            List<Predicate<Track>> filters) {
        if (djWeight < 0 || recWeight < 0 || djWeight + recWeight == 0) {
            throw new IllegalArgumentException("weights");
        }
        this.dj = dj;
        this.recs = recs;
        this.djWeight = djWeight;
        this.recWeight = recWeight;
        this.filters = List.copyOf(filters);
    }

    boolean preferDj() {
        return djIssued * recWeight <= recIssued * djWeight;
    }

    Track next() {
        for (int guard = 0; guard < 10_000; guard++) {
            boolean tryDj = preferDj();
            boolean usedDj = tryDj;
            Track t = tryDj ? takeDj() : takeRec();
            if (t == null) {
                usedDj = !tryDj;
                t = tryDj ? takeRec() : takeDj();
            }
            if (t == null) return null;
            if (!seen.contains(t.id) && filters.stream().allMatch(f -> f.test(t))) {
                seen.add(t.id);
                if (usedDj) djIssued++; else recIssued++;
                return t;
            }
        }
        throw new IllegalStateException("no mixable track");
    }

    private Track takeDj() {
        while (djIndex < dj.size()) {
            Track t = dj.get(djIndex++);
            if (!seen.contains(t.id)) return t;
        }
        return null;
    }

    private Track takeRec() {
        while (recs.hasNext()) {
            Track t = recs.next();
            if (!seen.contains(t.id)) return t;
        }
        return null;
    }
}

End-to-end flows

1. Equal 1:1. preferDj when djIssued ≤ recIssued → DJ, rec, DJ, rec…
2. Custom 2:1. djIssued * 1 ≤ recIssued * 2 keeps DJ ahead until ratio holds.
3. Filter skip. explicit track fails predicate; loop takes next from same or other iterator; seen not marked until emit.
4. Seen. same id in recs after DJ played it → skip.
5. Exhaust. both iterators empty → null (end of mix).

Dry-run. DJ [A,B,C], recs [A,D,E], weights 1:1, filter !explicit. next → A (DJ), D (rec; A seen skipped), B, E, C. Ratio 3:2 at end because DJ had one extra unique.

Ten honest follow-ups

1. Prince O(1) playlist is HashMap+DLL insert/delete — different card; do not mix.
2. Crossfade / audio buffers: next card, not this mixer.
3. Personalized recs: iterator is a black box; I do not invent a two-tower model.
4. Thread: one mixer per session.
5. FTC 5-round is not AUTA two-tech.
6. No Kafka “now playing.”
7. I have no music internship.
8. Tie-break when both sources fail filters: return null or relax filter — ask.
9. Shuffle DJ: shuffle a copy once, then same cursor.
10. Not Job 10454435.

Why counters not Math.random? Interviews want a deterministic ratio. Why HashSet? Repeat skip is the product rule. Why NMF? Say it if they ask “did AUTA ask this?”

Do not claim LC 6629134 is UTA. Do not merge Spotify O(1) with this mixer. Do not speak a DJ story as Adarsh.

12. Audio buffers at X FPS Standard CS Resume-derived

Question stem. A pipeline produces frames at X FPS (audio samples or video frames). Bound memory per stage. Choose backpressure (block the producer) versus drop-oldest when the consumer is slow.

Evidence / remap. Class C / user-pasted list — no §5.C URL for an “audio buffer LLD.” Resume adjacent: Horizon GStreamer 60 FPS and ZED 2 2M+ pts/s explain why bounded queues exist on the rover. That is not “I designed this audio product.” Argus 24 FPS is a detector budget, not GStreamer.

Clarify before classes

• X FPS → period = 1000/X ms; buffer of N frames = N/X seconds of lag.
• Drop-oldest (live) vs block (must not lose) vs drop-newest.
• Single consumer vs fan-out — v1 one consumer.
• Audio vs video: same bounded deque; packet size differs.

Data structures

Entities and pattern

Strategy: overflow policy. Pipeline is a list of Stage. Not Observer unless they add multiple listeners (then a list of consumers — still not a GUI observer zoo).

import java.util.*;

enum Overflow { DROP_OLDEST, BLOCK }

final class Frame {
    final long tsMs;
    final byte[] pcm;
    Frame(long tsMs, byte[] pcm) {
        this.tsMs = tsMs;
        this.pcm = pcm;
    }
}

final class BoundedStage {
    private final int cap;
    private final Overflow overflow;
    private final ArrayDeque<Frame> q = new ArrayDeque<>();

    BoundedStage(int cap, Overflow overflow) {
        if (cap <= 0) throw new IllegalArgumentException("cap");
        this.cap = cap;
        this.overflow = overflow;
    }

    synchronized boolean push(Frame frame) {
        if (q.size() == cap) {
            if (overflow == Overflow.DROP_OLDEST) {
                q.pollFirst();
            } else {
                return false; // caller blocks / retries / drops at source
            }
        }
        q.addLast(frame);
        return true;
    }

    synchronized Frame poll() {
        return q.pollFirst();
    }

    synchronized int size() {
        return q.size();
    }
}

final class FramePipeline {
    private final List<BoundedStage> stages;
    FramePipeline(List<BoundedStage> stages) {
        this.stages = List.copyOf(stages);
    }

    boolean ingest(Frame frame) {
        Frame cur = frame;
        for (BoundedStage stage : stages) {
            if (!stage.push(cur)) return false;
            cur = stage.poll();
            if (cur == null) return true;
        }
        return true;
    }
}

The ingest sketch above is a teaching simplification (push then immediate poll). In a real clocked pipeline, a producer thread only pushes; a consumer thread polls at X FPS. Speak that. Live Code: show push/poll on one stage first.

End-to-end flows

1. Keep up. size < cap → addLast; consumer pollFirst at X Hz.
2. Drop-oldest. size==cap → pollFirst (drop) → addLast (latest). Latency stays ≤ N/X seconds.
3. Backpressure. push returns false; producer sleeps or drops at camera — queue unchanged.
4. Consumer stall. With DROP_OLDEST, the deque holds the newest N; old audio/video is gone on purpose.
5. Empty poll. null → consumer waits; do not invent a frame.

Dry-run. cap=2, DROP_OLDEST, FPS=60 → max lag ≈ 33 ms. Push f1,f2,f3: after f3 the deque is [f2,f3]; f1 dropped. BLOCK would reject f3 until a poll. Horizon line: 60 FPS GStreamer and 2M+ pts/s ZED cannot sit on an unbounded Java heap on the rover.

Ten honest follow-ups

1. Jitter buffer: hold until timestamp + offset — different from drop-oldest live view.
2. Argus 24 FPS: drop stale PPE frame rather than delay the alert; Postgres stores events, not video blobs.
3. UDP vs TCP: Horizon webcam analogue is GStreamer-UDP; drop-over-stall. Standard CS, not this class’s import.
4. Thread: one lock per stage; do not share an unsynchronized deque.
5. Fan-out: each consumer has its own bounded deque so a slow UI does not stall perception.
6. I did not design a DAW or Amazon audio service.
7. No Kafka “frame topic.”
8. Pool byte[] to avoid GC at 60 FPS — mention, do not write an allocator.
9. Clock: producer tsMs; consumer may skip if now-ts > budget.
10. Not Job 10454435.

Why bound? Unbounded queue is a memory leak under a stalled consumer. Drop vs block? Live vs lossless — pick from the use case. Horizon? Why the rover used bounded queues — not a claim I shipped this API.

Do not say “I designed Amazon audio.” Do not mix Argus 24 FPS with Horizon 60 FPS as one number. Do not invent a rover debug clock.

13. Bookstore word-count IE-asked

Question stem. Multiple books. Return the count of a particular word (for example a character name) in a specific book. Classes, objects, methods.

Evidence / remap. Shiwangi UTA later live labeled R3 (Shiwangi) — OA was a separate step, OA-as-R1 = N; this is a true later slot, not Rank A two-DSA. TUF 01 (opened body): same bookstore prompt as their Round 4 after OA numbered Round 1 — OA-as-R1 trap: their R4 is a later live, not Adarsh’s already-done R1. Job 10454435 still none. GiftedBooks PDF Q&A is RAG, not this frequency map.

Clarify before classes

• Lookup by ISBN (unique), not title.
• Case-fold and punctuation: The and the, count as the.
• Precompute map vs scan per query.
• Phrase vs whole word — v1 whole word.
• Invalid: unknown ISBN, blank word, duplicate ISBN on add.

Data structures

Entities and pattern

Tokenizer Strategy only if language varies. Book owns freq. Bookstore owns catalog + optional inverted index.

import java.util.*;

interface Tokenizer {
    List<String> words(String text);
}

final class SimpleTokenizer implements Tokenizer {
    public List<String> words(String text) {
        List<String> out = new ArrayList<>();
        for (String raw : text.split("\\W+")) {
            if (!raw.isEmpty()) out.add(raw.toLowerCase(Locale.ROOT));
        }
        return out;
    }
}

final class Book {
    final String id;
    final String title;
    private final Map<String, Integer> freq;

    Book(String id, String title, String text, Tokenizer tokenizer) {
        this.id = id;
        this.title = title;
        Map<String, Integer> counts = new HashMap<>();
        for (String w : tokenizer.words(text)) {
            counts.merge(w, 1, Integer::sum);
        }
        this.freq = Map.copyOf(counts);
    }

    int count(String word) {
        if (word == null || word.isBlank()) throw new IllegalArgumentException("blank");
        return freq.getOrDefault(word.toLowerCase(Locale.ROOT), 0);
    }
}

final class Bookstore {
    private final Map<String, Book> byId = new HashMap<>();
    private final Map<String, Map<String, Integer>> inverted = new HashMap<>();

    void add(Book book) {
        if (byId.putIfAbsent(book.id, book) != null) {
            throw new IllegalArgumentException("duplicate book");
        }
        // inverted filled from a recount only if they asked corpus search;
        // v1 query does not need it — keep add cheap unless they ask.
    }

    int countInBook(String bookId, String word) {
        Book book = byId.get(bookId);
        if (book == null) throw new IllegalArgumentException("unknown book");
        return book.count(word);
    }

    void indexInverted(Book book, Tokenizer tokenizer, String text) {
        for (String w : tokenizer.words(text)) {
            inverted.computeIfAbsent(w, ignored -> new HashMap<>())
                    .merge(book.id, 1, Integer::sum);
        }
    }

    int countInCorpus(String word) {
        Map<String, Integer> row = inverted.getOrDefault(word.toLowerCase(Locale.ROOT), Map.of());
        int sum = 0;
        for (int n : row.values()) sum += n;
        return sum;
    }
}

End-to-end flows

1. Add. Tokenize once → immutable freq → catalog putIfAbsent.
2. Count in book. get book → normalize word → map getOrDefault 0.
3. Unknown ISBN. throw; do not scan.
4. Punctuation. split on \\W+ so “the,” and “The” both hit the.
5. Inverted follow-up. indexInverted while adding; countInCorpus sums posting values.

Dry-run. Text “The cat sat on the mat.” → the=2, cat=1. countInBook(isbn, "THE") = 2. countInBook(isbn, "hat") = 0.

Ten honest follow-ups

1. Phrases: keep token list + KMP/sliding, not this map.
2. New edition: new ISBN/edition key; do not mutate a published Book.
3. Concurrent read: immutable freq is enough after publish.
4. GiftedBooks sub-300 ms RAG is citations, not word count. GitHub AegisAI mismatch — resume wins.
5. Stop words: tokenizer policy.
6. Unicode: Normalizer + locale; do not index char blindly.
7. Shiwangi was happy with classes/methods — write them, do not skip to HLD.
8. TUF 01 OA-as-R1: do not treat their R4 as “my R1.”
9. No Elasticsearch unless they ask scale in one sentence.
10. Not Job 10454435.

Why precompute? Many queries, one ingest. Why not inverted first? The asked API is specific-book. Unknown book? Throw.

Do not scan every book for one ISBN. Do not call GiftedBooks this design. Do not invent student headcount.

14. Email search IE-asked

Question stem. Store emails. APIs: how many times a keyword appears in a specific email, and across a user’s inbox.

Evidence / remap. TUF 10 opened body, their Round 4 after OA as Round 1 — OA-as-R1: their R4 is a later live analogue (Adarsh’s R3-shaped slot in a long loop, not a 10454435 hit). Selected loop. Your loop may differ.

Clarify before classes

• Keyword = token after same normalize as bookstore, or substring? Lock tokens.
• Inbox = all emails with that userId as owner (not CC) unless they add folders.
• Delete/update: maintain inverted index or rebuild per email.
• Invalid: unknown emailId, unknown user, blank keyword.

Data structures

Entities and pattern

Same tokenizer Strategy as bookstore. No Observer. Email is not a subclass of Book — shared tokenizer by composition.

import java.util.*;

final class Posting {
    final String emailId;
    final int count;
    Posting(String emailId, int count) {
        this.emailId = emailId;
        this.count = count;
    }
}

final class Email {
    final String id;
    final String ownerId;
    final String body;
    final Map<String, Integer> freq;
    Email(String id, String ownerId, String body, Map<String, Integer> freq) {
        this.id = id;
        this.ownerId = ownerId;
        this.body = body;
        this.freq = freq;
    }
}

final class EmailSearch {
    private final Tokenizer tokenizer;
    private final Map<String, Email> emails = new HashMap<>();
    private final Map<String, List<String>> inbox = new HashMap<>();
    private final Map<String, List<Posting>> inverted = new HashMap<>();

    EmailSearch(Tokenizer tokenizer) { this.tokenizer = tokenizer; }

    synchronized String store(String ownerId, String body) {
        Map<String, Integer> freq = new HashMap<>();
        for (String w : tokenizer.words(body)) freq.merge(w, 1, Integer::sum);
        String id = UUID.randomUUID().toString();
        Email email = new Email(id, ownerId, body, Map.copyOf(freq));
        emails.put(id, email);
        inbox.computeIfAbsent(ownerId, ignored -> new ArrayList<>()).add(id);
        for (Map.Entry<String, Integer> e : freq.entrySet()) {
            inverted.computeIfAbsent(e.getKey(), ignored -> new ArrayList<>())
                    .add(new Posting(id, e.getValue()));
        }
        return id;
    }

    synchronized int countInEmail(String emailId, String keyword) {
        Email email = emails.get(emailId);
        if (email == null) throw new IllegalArgumentException("unknown email");
        String w = keyword.toLowerCase(Locale.ROOT);
        return email.freq.getOrDefault(w, 0);
    }

    synchronized int countInInbox(String userId, String keyword) {
        String w = keyword.toLowerCase(Locale.ROOT);
        Set<String> mine = new HashSet<>(inbox.getOrDefault(userId, List.of()));
        int sum = 0;
        for (Posting p : inverted.getOrDefault(w, List.of())) {
            if (mine.contains(p.emailId)) sum += p.count;
        }
        return sum;
    }
}

End-to-end flows

1. Store. tokenize → freq → emails put → inbox add → inverted postings add.
2. Count one email. get Email → freq get. O(1). Does not walk inverted.
3. Count inbox. postings for word, keep those whose emailId is in the user’s set, sum counts.
4. Empty inbox. 0, not throw (unknown user vs empty — ask; here empty list).
5. Unknown email. throw on countInEmail.

Dry-run. User u1 stores “meet meet now”; u2 stores “meet later”. countInEmail(id1, "meet")=2. countInInbox(u1,"meet")=2. countInInbox(u2,"meet")=1. u1 does not see u2’s mail.

Ten honest follow-ups

1. Phrase search: store token arrays per email; inverted becomes positions list.
2. Delete: remove postings (or tombstone generation) — mention, skip coding if time.
3. Folder/label: extra inverted label → ids.
4. Scale: inverted on disk / Lucene — one sentence, not a cluster.
5. Privacy: never return another user’s postings; the mine HashSet is the ACL.
6. Ylogx SQL RAG is not email search. RLS is row tenancy, similar isolation idea only.
7. TUF 10 OA-as-R1 remap: later live, not a 10454435 list.
8. No Kafka mail bus.
9. Substring vs token: lock it; regex scan is O(body) per mail if they insist contains.
10. Not Job 10454435.

Why inverted plus per-email map? One-email query should not scan postings of a hot word. Why filter by owner? Inverted is global; inbox is tenancy. Unknown email vs zero count? Different errors.

Do not dump other users’ mail. Do not invent Gmail. Do not skip the inbox API they named.

15. Type-ahead autocomplete IE-asked

Question stem. E-commerce type-ahead: prefix → top-K suggestions; real-time updates when products are added; high query load. Trie or hash prefix lookup; class/API; extensibility for languages / regional catalogs.

Evidence / remap. TUF 19 opened body: LLD round after OA numbered Round 1 — OA-as-R1: their R2 is often Adarsh’s already-done first live analogue. Still a valid later-slot DS-design if they ask it again. Closest bible row: LC 6282609 searchable-prefix top-K — SERP only this pass; body Cloudflare; round unlabeled. Do not stamp CS II 210 from that post onto other IEs. Conflict: some notes say Trie+heap is more common than Parking Lot OOD for AUTA; first-hand AUTA named OOD is Logger + Dog, not this. Prep both. Your loop may differ.

Clarify before classes

• Rank by frequency, recency, or sales — v1 frequency.
• K per query. Tie-break lexicographic.
• Realtime: increment counts on add/search-complete.
• Regional catalogs: root per locale or a locale field on the term.
• Empty prefix: ask — usually empty list, not the whole Trie.

Data structures

Entities and pattern

TypeaheadService owns the Trie. Optional Strategy for ranker (freq vs recency). Catalog locale = another root map, not inheritance.

import java.util.*;

final class AutoNode {
    final Map<Character, AutoNode> kids = new HashMap<>();
    String term;
    int count;
}

final class Typeahead {
    private final AutoNode root = new AutoNode();

    synchronized void add(String raw, int inc) {
        String term = raw.toLowerCase(Locale.ROOT);
        AutoNode n = root;
        for (int i = 0; i < term.length(); i++) {
            n = n.kids.computeIfAbsent(term.charAt(i), c -> new AutoNode());
        }
        n.term = term;
        n.count += inc;
    }

    synchronized List<String> suggest(String rawPrefix, int k) {
        if (k <= 0 || rawPrefix == null || rawPrefix.isBlank()) return List.of();
        String prefix = rawPrefix.toLowerCase(Locale.ROOT);
        AutoNode n = root;
        for (int i = 0; i < prefix.length(); i++) {
            n = n.kids.get(prefix.charAt(i));
            if (n == null) return List.of();
        }
        PriorityQueue<AutoNode> heap = new PriorityQueue<>((a, b) -> {
            int c = Integer.compare(a.count, b.count);
            if (c != 0) return c;
            return b.term.compareTo(a.term);
        });
        dfs(n, k, heap);
        List<AutoNode> nodes = new ArrayList<>(heap);
        nodes.sort((a, b) -> {
            int c = Integer.compare(b.count, a.count);
            return c != 0 ? c : a.term.compareTo(b.term);
        });
        List<String> out = new ArrayList<>();
        for (AutoNode x : nodes) out.add(x.term);
        return out;
    }

    private void dfs(AutoNode n, int k, PriorityQueue<AutoNode> heap) {
        if (n.term != null) {
            heap.offer(n);
            if (heap.size() > k) heap.poll();
        }
        for (AutoNode c : n.kids.values()) dfs(c, k, heap);
    }
}

End-to-end flows

1. Add product. Walk/create edges; increment terminal count (realtime).
2. Suggest. Walk prefix; if missing → []. Else DFS heap of size K; sort desc.
3. Update existing. Same path; count++. Next suggest sees new rank.
4. Hot prefix. Follow-up: store top-K on the prefix node; on increment, recompute that node (and ancestors if they cache).
5. Empty prefix. return [] in this code (locked).

Dry-run. add("yolov9", 5), add("yolov8", 3), add("yarn", 9). suggest("yo", 2) → yolov9, yolov8. add("yolov8", 4) → yolov8 count 7. suggest("yo", 2) → yolov8, yolov9.

Ten honest follow-ups

1. Cache popular queries in a HashMap prefix→list with TTL — say it; Ylogx Redis is not this cache.
2. Unicode / Indic: normalize; don’t assume a-z.
3. Regional catalog: Map<locale, Typeahead>.
4. Delete product: decrement; prune empty nodes.
5. QPS: cached top-K per node; query O(P).
6. TUF 19 OA-as-R1: already-done analogue possible; still rehearse.
7. LC 6282609 body was Cloudflare — do not invent that post’s extras.
8. Stratify 50+ models / GiftedBooks topics = “add then search” analogy only.
9. No Elasticsearch cluster in 60 min.
10. Not Job 10454435.

Why heap size K? You only need K, not a full sort. Why not HashMap of all prefixes? Memory; Trie shares prefixes. Empty prefix? Ask; default empty.

Do not claim this is the AUTA third live. Do not copy LC 210 onto this card. Do not skip realtime increment.

16. Notification request system IE-asked

Question stem. Write complete code including main for a notification request system.

Evidence / remap. TUF 203 opened body (SDE unspecified, not SDE II): their Round 3 after OA as Round 1 — OA-as-R1: their R3 is often Adarsh’s already-done second-live analogue, not a guaranteed third live. Ghosted loop. Nitesh “notification system–like” is a different R2 row in §5.C — same family, do not invent extra requirements. Rudraksh “practice notification” is prep, not asked. Your loop may differ. This is coded LLD, not notification HLD (fan-out, ch. 23).

Clarify before classes

• Channels: EMAIL, SMS, PUSH as Strategy.
• Sync dispatch in main vs queue — they asked complete code; queue + drain in main is enough.
• Failure: retry once then FAILED; do not silent-drop a payment SMS if they name that follow-up.
• Invalid: unknown channel, blank user, empty payload.

Data structures

Entities and pattern

Strategy: ChannelSender. Optional retry loop in dispatcher. Not Observer unless they add webhooks — then a list of listeners.

import java.util.*;

enum Channel { EMAIL, SMS, PUSH }
enum NStatus { PENDING, SENT, FAILED }

final class NotificationRequest {
    final String id;
    final String userId;
    final Channel channel;
    final String payload;
    NStatus status;
    String lastError;
    NotificationRequest(String id, String userId, Channel channel, String payload) {
        this.id = id;
        this.userId = userId;
        this.channel = channel;
        this.payload = payload;
        this.status = NStatus.PENDING;
    }
}

interface ChannelSender {
    void send(NotificationRequest req) throws Exception;
}

final class ConsoleSender implements ChannelSender {
    private final String name;
    ConsoleSender(String name) { this.name = name; }
    public void send(NotificationRequest req) {
        System.out.println(name + " -> " + req.userId + ": " + req.payload);
    }
}

final class NotificationService {
    private final Map<String, NotificationRequest> byId = new HashMap<>();
    private final ArrayDeque<String> pending = new ArrayDeque<>();
    private final Map<Channel, ChannelSender> senders = new EnumMap<>(Channel.class);

    void register(Channel ch, ChannelSender sender) {
        senders.put(ch, sender);
    }

    synchronized String submit(String userId, Channel channel, String payload) {
        if (userId == null || userId.isBlank()) throw new IllegalArgumentException("user");
        if (payload == null || payload.isBlank()) throw new IllegalArgumentException("payload");
        if (!senders.containsKey(channel)) throw new IllegalArgumentException("no sender");
        String id = UUID.randomUUID().toString();
        NotificationRequest req = new NotificationRequest(id, userId, channel, payload);
        byId.put(id, req);
        pending.addLast(id);
        return id;
    }

    synchronized void dispatchAll() {
        while (!pending.isEmpty()) {
            String id = pending.pollFirst();
            NotificationRequest req = byId.get(id);
            ChannelSender sender = senders.get(req.channel);
            try {
                sender.send(req);
                req.status = NStatus.SENT;
            } catch (Exception e) {
                try {
                    sender.send(req);
                    req.status = NStatus.SENT;
                } catch (Exception e2) {
                    req.status = NStatus.FAILED;
                    req.lastError = e2.getMessage();
                }
            }
        }
    }

    synchronized NStatus status(String id) {
        NotificationRequest req = byId.get(id);
        if (req == null) throw new IllegalArgumentException("unknown");
        return req.status;
    }

    public static void main(String[] args) {
        NotificationService svc = new NotificationService();
        svc.register(Channel.EMAIL, new ConsoleSender("email"));
        svc.register(Channel.SMS, new ConsoleSender("sms"));
        svc.register(Channel.PUSH, new ConsoleSender("push"));
        String a = svc.submit("u1", Channel.EMAIL, "order shipped");
        String b = svc.submit("u1", Channel.SMS, "OTP 123456");
        svc.dispatchAll();
        System.out.println(a + " " + svc.status(a));
        System.out.println(b + " " + svc.status(b));
    }
}

End-to-end flows

1. Register. EnumMap put sender.
2. Submit. validate → HashMap put PENDING → deque addLast → return id.
3. Dispatch. pollFirst → send → SENT. On throw, retry once → FAILED + lastError.
4. Unknown channel at submit. throw before enqueue.
5. main. wires senders, two submits, drain, prints statuses so the interviewer sees a runnable program.

Dry-run. main registers three console senders. submit email + sms. dispatchAll prints two lines, both SENT. If SMS sender threw twice, b is FAILED and lastError is set; email still SENT.

Ten honest follow-ups

1. Priority: PriorityQueue by rank instead of ArrayDeque.
2. Quiet hours: filter in submit or sender.
3. Idempotency key: HashMap clientKey → id so retries do not double-SMS.
4. HLD fan-out / SNS: chapter 23. Do not start there; they asked for main().
5. Ylogx: I did not ship this dispatcher. Alerts on dashboards are REST/poll.
6. Argus: violation rows in Postgres are not this queue.
7. TUF 203 OA-as-R1: second-live analogue possible.
8. Do not silent-drop. FAILED is visible.
9. Thread pool: follow-up; v1 single-thread drain.
10. Not Job 10454435.

Why main()? They asked for complete code; wire a demo. Why Strategy? New WhatsApp sender without editing dispatchAll. Failure? Retry once then FAILED — say the policy.

Do not jump to Kafka. Do not skip main(). Do not claim a notification internship.

17. Org-chart LCA in O(log n) IE-asked

Question stem. Design a data structure to find the lowest common ancestor of two nodes in a hierarchy (company org chart). Class + method. Aim O(log n).

Evidence / remap. TUF 14 opened body, their Round 2 after OA as Round 1 — OA-as-R1: their R2 ≈ Adarsh’s already-done first live analogue. Page linked “Lowest Common Ancestor of a Binary Tree II” — the org-chart DS with O(log n) is what they wrote; do not assume a binary tree (org charts are n-ary). Rejected loop. Your loop may differ.

Clarify before classes

• Forest or one CEO? v1 one root.
• n-ary, not binary. Parent pointers exist after ingest.
• Ids unique. Re-org: rebuild jump table if they allow mutations.
• O(log n) after preprocess — binary lifting is the honest structure. TreeMap of path is O(H) unless balanced.
• Invalid: unknown id, disconnected node.

Data structures

Entities and pattern

OrgChart is the DS. Node is id + manager. No Strategy. Not a binary-tree LeetCode subclass.

import java.util.*;

final class OrgChart {
    private final Map<String, Integer> idx = new HashMap<>();
    private final List<String> ids = new ArrayList<>();
    private final List<List<Integer>> kids = new ArrayList<>();
    private int[][] up;
    private int[] depth;
    private int log;
    private boolean built;
    private int root = -1;

    int addEmployee(String id) {
        if (idx.containsKey(id)) return idx.get(id);
        int i = ids.size();
        idx.put(id, i);
        ids.add(id);
        kids.add(new ArrayList<>());
        built = false;
        return i;
    }

    void setRoot(String id) {
        root = addEmployee(id);
        built = false;
    }

    void addReport(String managerId, String reportId) {
        int m = addEmployee(managerId);
        int r = addEmployee(reportId);
        kids.get(m).add(r);
        built = false;
    }

    String lca(String aId, String bId) {
        if (!built) preprocess();
        Integer a = idx.get(aId);
        Integer b = idx.get(bId);
        if (a == null || b == null) throw new IllegalArgumentException("unknown");
        int u = a, v = b;
        if (depth[u] < depth[v]) {
            int t = u; u = v; v = t;
        }
        int diff = depth[u] - depth[v];
        for (int k = 0; k < log; k++) {
            if (((diff >> k) & 1) == 1) u = up[k][u];
        }
        if (u == v) return ids.get(u);
        for (int k = log - 1; k >= 0; k--) {
            if (up[k][u] != up[k][v]) {
                u = up[k][u];
                v = up[k][v];
            }
        }
        int p = up[0][u];
        if (p < 0) throw new IllegalStateException("no lca");
        return ids.get(p);
    }

    private void preprocess() {
        if (root < 0) throw new IllegalStateException("no root");
        int n = ids.size();
        log = 1;
        while ((1 << log) <= n) log++;
        up = new int[log][n];
        for (int k = 0; k < log; k++) Arrays.fill(up[k], -1);
        depth = new int[n];
        dfs(root, -1);
        for (int k = 1; k < log; k++) {
            for (int v = 0; v < n; v++) {
                int mid = up[k - 1][v];
                up[k][v] = mid < 0 ? -1 : up[k - 1][mid];
            }
        }
        built = true;
    }

    private void dfs(int v, int p) {
        up[0][v] = p;
        for (int c : kids.get(v)) {
            depth[c] = depth[v] + 1;
            dfs(c, v);
        }
    }
}

End-to-end flows

1. Build. setRoot CEO; addReport down the tree; lazy preprocess on first lca.
2. Same node. After leveling, u==v → that id.
3. Ancestor. A is above B: leveling lands on A → A.
4. Cousins. Lift until parents differ; parent[0] is LCA.
5. Unknown id. throw before lifting.

Dry-run. CEO → A, B. A → C, D. lca(C,D)=A. lca(C,B)=CEO. lca(C,A)=A. Chain of 8: parent[3][leaf] jumps 8; query still O(log n).

Ten honest follow-ups

1. Mutation: set built=false; rebuild. Or Euler tour + RMQ if they want static only.
2. Forest: LCA only in same tree; compare roots.
3. O(H) parent walk is the stuck path if they accept it — they asked O(log n).
4. Not LC binary-tree LCA unless the org is binary — TUF linked a binary slug; speak n-ary.
5. Ylogx 3 tiers is RLS roles, not this tree — do not claim I stored org jumps in Postgres.
6. TUF 14 OA-as-R1: first-live analogue.
7. Cycle: DFS visiting set; reject addReport that cycles.
8. No Kafka org events.
9. String ids vs int: HashMap then arrays — I wrote that.
10. Not Job 10454435.

Why binary lifting not TreeMap of paths? Paths are O(H) memory per node and O(H) compare. Why preprocess? O(log n) is for queries after O(n log n). Binary tree slug? Org chart is n-ary unless they draw two children.

Do not only return size or depth. Do not invent an Amazon org you know. Do not skip the O(log n) ask.

18. Min Stack variation returning {size, id} IE-asked

Question stem. A more complex variation of Min Stack: return the full object with size and id, not only the numeric size. Candidate first tried stack + map + priority queue (flagged too complex), then simplified and missed the object — ran out of time.

Evidence / remap. TUF 07 and duplicate 09 (same write-up posted twice — count once). Their Round 2, no OA in this write-up — analogue of a second live (Adarsh’s R2 already done). Still rehearse if a later live is DS-design. Linked “Implement Min Stack.” They wanted {size, id} not getMin(): int. Rejected. Your loop may differ.

Clarify before classes

• Item = id + size (or value). getMin returns the Item, not an int.
• Ties: latest min vs stable id — ask; v1 the most recently pushed among equal mins (second stack of objects).
• pop of non-min must not disturb min object identity.
• Invalid: pop/getMin on empty.

Data structures

Alternative: one stack of nodes each holding value + min-so-far Item. Same O(1). Still an object, not a bare int.

Entities and pattern

Item immutable. MinItemStack owner. No Strategy. Not LRU. Not Login Tracker.

import java.util.*;

final class Item {
    final String id;
    final int size;
    Item(String id, int size) {
        this.id = id;
        this.size = size;
    }
    public String toString() {
        return "{" + id + "," + size + "}";
    }
}

final class MinItemStack {
    private final ArrayDeque<Item> data = new ArrayDeque<>();
    private final ArrayDeque<Item> mins = new ArrayDeque<>();

    void push(Item item) {
        if (item == null) throw new IllegalArgumentException("null");
        data.push(item);
        if (mins.isEmpty() || item.size <= mins.peek().size) {
            mins.push(item);
        }
    }

    Item pop() {
        if (data.isEmpty()) throw new IllegalStateException("empty");
        Item gone = data.pop();
        if (gone.id.equals(mins.peek().id)) mins.pop();
        return gone;
    }

    Item top() {
        if (data.isEmpty()) throw new IllegalStateException("empty");
        return data.peek();
    }

    Item getMin() {
        if (mins.isEmpty()) throw new IllegalStateException("empty");
        return mins.peek();
    }

    int size() {
        return data.size();
    }
}

End-to-end flows

1. Push smaller. data push; mins push (new min object).
2. Push larger. data push; mins unchanged. getMin still previous object (id intact).
3. Pop non-min. data pop; mins id ≠ gone.id → mins stays. getMin unchanged.
4. Pop min. ids equal → mins pop. getMin is the previous min object.
5. Empty getMin. throw — do not return a size-only 0.

Dry-run. push(a,5), push(b,3), push(c,4), push(d,3). getMin → {b,3} after second push; after d (≤) getMin → {d,3}. pop d → getMin {b,3} (id b, not a bare 3). pop c → still {b,3}. pop b → {a,5}. If they only printed size, they fail the IE that wanted the object.

Ten honest follow-ups

1. Equal mins: ≤ vs < changes whether getMin is newest or oldest equal. Lock it.
2. Same id pushed twice: compare references or (id, generation). Prefer new Item each push.
3. Do not add a heap — O(log n) and was flagged too complex.
4. Thread: one lock if they ask.
5. Generic value: Item stays the return type.
6. TUF 07/09 duplicate: one IE, two files.
7. Not Login Tracker, not LRU.
8. I did not ship this structure at Ylogx.
9. getMin must not be int. Speak the object.
10. Not Job 10454435.

Why two stacks? O(1) min without scan; object identity rides on the min stack. Why not map+PQ? Extra complexity; they rejected that path. Empty? Throw, do not return size 0 without id.

Do not return only size after simplifying. Do not start with three structures. Do not mix this with LRU.

Evidence locks for this chapter

• Job 10454435: still none. Unnamed stays unnamed. Other candidates reported these; your loop may differ.
• R1 13 Aug 2026 and R2 18 Aug 2026 are done. OA is not a round. This book is R3 / possible R4.
• OA-as-R1 flagged on TUF 01 (bookstore their R4), 10 (email their R4), 19 (type-ahead their R2), 203 (notification their R3), 14 (org LCA their R2).
• Parking Lot = GFG fresher R2. Elevator = GFG 2025. LRU = Bhavya. Playlist mix = NMF FTC LC 6629134. Vending ≠ getpersonalisedcv IE.
• Class C without a bible URL: meeting-room product, device backup, secure ACL, log parser, streaming MA, library LMS, audio buffers.
• Rate limiter, URL shortener, S3-like HLD → chapter 23. Independent Rate Limiter SDE I live count stays 1, not UTA.
• Login Tracker unverified. Java Live Code. Production was Python / TypeScript / ROS2.