6. OOD / LLD / DS-design

Live Code method: compile the invariant first

1. Ask who calls it and what success returns.
2. Ask in-memory versus persistent and single host versus multiple hosts.
3. Ask the invalid transitions: double checkout, unknown id, no capacity, bad code, duplicate key.
4. Draw four to six types, not a product org chart.
5. Put mutable state behind one owner class.
6. Use composition for policies, sinks, parsers, validators, and capabilities.
7. Use inheritance only for a real is-a relation that remains substitutable.
8. State time and space complexity for HashMap, Trie, heap, deque, and window-backed designs.

Short Java / OOP opener

• Encapsulation: a locker exposes occupy/release; callers cannot mutate its occupant directly.
• Abstraction: a site exposes dropOff/pickUp without exposing free-list bookkeeping.
• Polymorphism: the site calls an assignment strategy; the logger calls a sink.
• Inheritance: use only for a genuine is-a. None of these cards needs a deep subclass tree.
• Composition: a tablet has a display and a speaker; a logger has sinks; a calculator expression has an operator.
• Interface: a narrow can-do contract. Java permits many interfaces and one class parent.
• Default method: useful for a tiny stateless convenience, but shared mutable state belongs in a composed object.
• Immutability: final identity/value fields, defensive copies, and no setters for records placed in queues or maps.
• Equality: map keys use stable identity fields; equal objects must have equal hash codes; do not mutate key fields.

import java.util.*;
interface Named {
    String id();
    default boolean sameId(Named other) {
        return other != null && id().equals(other.id());
    }
}
final class StableId implements Named {
    private final String value;
    StableId(String value) {
        if (value == null || value.isBlank()) {
            throw new IllegalArgumentException("blank id");
        }
        this.value = value;
    }
    public String id() {
        return value;
    }
    @Override
    public boolean equals(Object other) {
        return other instanceof StableId
                && value.equals(((StableId) other).value);
    }
    @Override
    public int hashCode() {
        return value.hashCode();
    }
}

Concrete example. A StableId("L-12") can safely be a HashMap key because its value never changes. A mutable locker status is not part of equality.

Answered opener probes. Interface versus abstract class? Use an interface for a capability or policy; add an abstract class only when subclasses truly share state and a template. Why composition? It avoids a subclass for every combination and lets behavior change independently. Why final? Identity and queued records cannot change underneath indexes or worker threads. What next? Write the owner method that enforces the invariant.

1. Amazon Locker / warehouse packages IE-asked

Question stem. Design locker management for warehouse or customer packages: assign a cubby, generate an access code, and release the package on valid pickup.

Evidence and remap. Prince reported the family in R1 for Job 3057703. Uday Singh reported Amazon Locker in a second live in an OA+3 loop, with UX and scale follow-ups. These are two reports of one family, not Job 10454435 evidence and not a UTA/AUTA default.

Clarify before classes

• Actors: courier, customer, and site operator.
• Operations: add locker, drop off package, pick up package, expire package.
• Scale: one site in memory first; site sharding only after the core works.
• Fit: SMALL, MEDIUM, LARGE and smallest adequate free locker.
• Invalid states: duplicate package, occupied locker, undersized locker, wrong/expired code, double pickup.
• Ask whether customer chooses or assignment is automatic.

Entities, relationships, pattern

LockerSite owns lockers and free lists. A Locker may hold zero or one package. LockerAssignmentStrategy is Strategy because closest entrance versus smallest fit can vary. The package and assignment result are immutable values; occupancy is encapsulated.

import java.util.*;
enum LockerSize { SMALL, MEDIUM, LARGE }
final class LockerPackage {
    final String id;
    final LockerSize minimum;
    LockerPackage(String id, LockerSize minimum) {
        this.id = Objects.requireNonNull(id);
        this.minimum = Objects.requireNonNull(minimum);
    }
}
final class Locker {
    final String id;
    final LockerSize size;
    private String packageId;
    private String code;
    Locker(String id, LockerSize size) {
        this.id = id;
        this.size = size;
    }
    boolean isFree() {
        return packageId == null;
    }
    void occupy(String nextPackageId, String nextCode) {
        if (!isFree()) throw new IllegalStateException("occupied");
        packageId = nextPackageId;
        code = nextCode;
    }
    String release(String suppliedCode) {
        if (code == null || !code.equals(suppliedCode)) {
            throw new IllegalArgumentException("invalid code");
        }
        String released = packageId;
        packageId = null;
        code = null;
        return released;
    }
}
interface LockerAssignmentStrategy {
    LockerSize choose(Map<LockerSize, Deque<Locker>> free,
                      LockerSize minimum);
}
final class SmallestFit implements LockerAssignmentStrategy {
    public LockerSize choose(Map<LockerSize, Deque<Locker>> free,
                             LockerSize minimum) {
        for (LockerSize size : LockerSize.values()) {
            if (size.ordinal() >= minimum.ordinal()
                    && !free.get(size).isEmpty()) {
                return size;
            }
        }
        return null;
    }
}
final class LockerSite {
    private final Map<String, Locker> lockers = new HashMap<>();
    private final Map<String, String> packageToLocker = new HashMap<>();
    private final Map<LockerSize, Deque<Locker>> free =
            new EnumMap<>(LockerSize.class);
    private final LockerAssignmentStrategy assignment;
    LockerSite(LockerAssignmentStrategy assignment) {
        this.assignment = assignment;
        for (LockerSize size : LockerSize.values()) {
            free.put(size, new ArrayDeque<>());
        }
    }
    synchronized void addLocker(Locker locker) {
        if (lockers.putIfAbsent(locker.id, locker) != null) {
            throw new IllegalArgumentException("duplicate locker");
        }
        free.get(locker.size).addLast(locker);
    }
    synchronized String dropOff(LockerPackage item) {
        if (packageToLocker.containsKey(item.id)) {
            throw new IllegalStateException("package already assigned");
        }
        LockerSize size = assignment.choose(free, item.minimum);
        if (size == null) throw new IllegalStateException("no fit");
        Locker locker = free.get(size).removeFirst();
        String code = UUID.randomUUID().toString().substring(0, 6);
        locker.occupy(item.id, code);
        packageToLocker.put(item.id, locker.id);
        return locker.id + ":" + code;
    }
    synchronized String pickUp(String lockerId, String code) {
        Locker locker = lockers.get(lockerId);
        if (locker == null) throw new IllegalArgumentException("unknown locker");
        String packageId = locker.release(code);
        packageToLocker.remove(packageId);
        free.get(locker.size).addLast(locker);
        return packageId;
    }
}

Walk, failure, alternatives, complexity

Happy path: a MEDIUM package asks the strategy; SMALL is skipped; the first free MEDIUM is removed; the locker owns the package and code; pickup validates and returns the locker to the MEDIUM deque.

Failure/concurrency: two couriers competing for the last MEDIUM cannot both remove it because the in-memory owner is synchronized. Across hosts, synchronized is insufficient; use a conditional database transition from FREE to OCCUPIED.

Why not one list scan? It is acceptable for ten lockers, but per-size deques make smallest-fit selection O(number of sizes), effectively O(1). Why not subclass SmallLocker/MediumLocker? Size is data; behavior is identical.

Concrete example. Free counts S=2, M=1, L=1; package minimum M. Assignment chooses M, returns M-07:a1b2c3. A wrong code leaves M-07 occupied.

Complexity: add, lookup, and pickup are O(1) average. Assignment is O(3) with three size classes. Space is O(lockers + assigned packages).

Answered extensions. Expiry? Store expiresAt, sweep, then release to return-to-facility flow. Notifications? Emit an event after commit; do not put SMS inside Locker. Closest locker? Add a strategy using distance metadata. Multi-site? Route by site id and keep each site’s occupancy authoritative. Crash after occupy? Make assignment transactional/idempotent using package id. Oversized? Return no fit and route to an associate. What next? Add expiry without weakening the one-package invariant.

Stuck path. Write Map<size, Deque<locker>>, dropOff, and pickUp. Then extract only the locker-selection line into LockerAssignmentStrategy.

2. Parking Lot IE-asked

Question stem. Design an in-memory parking lot that assigns a compatible spot, issues a ticket, releases the spot, and computes a fee.

Evidence and remap. A GFG fresher report placed Parking Lot OOD in R2 after Burning Tree and Merge Intervals. Taanya reported “similar to parking lot” with intervals/stream; similar-to is not a second independent Parking Lot. DevBrainiac’s experienced four-round “R3” is not this UTA/AUTA format.

Clarify before classes

• Actors: driver, entry gate, exit gate, operator.
• Vehicle types: motorcycle, car, bus.
• Spot types and compatibility: confirm whether smaller vehicles can use larger spots.
• Operations: enter, exit, fee; reserve/EV only if requested.
• Scale: one lot first; floor and gate concurrency as follow-up.
• Invalid states: full lot, duplicate active plate, unknown/double-used ticket, occupied spot.

Entities, relationships, pattern

ParkingLot owns spots, free queues, and open tickets. PricingPolicy is Strategy. Ticket is immutable. Vehicle compatibility belongs on the spot, not in gate if-else ladders.

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 vehicle) {
        if (occupant != null) return false;
        if (vehicle.type == VehicleType.MOTORCYCLE) return true;
        if (vehicle.type == VehicleType.CAR) return type != SpotType.MOTORCYCLE;
        return type == SpotType.LARGE;
    }
    void occupy(Vehicle vehicle) {
        if (!canFit(vehicle)) throw new IllegalStateException("cannot fit");
        occupant = vehicle;
    }
    void release() {
        if (occupant == null) throw new IllegalStateException("already free");
        occupant = null;
    }
}
final class ParkingTicket {
    final String id;
    final String spotId;
    final String plate;
    final long enteredAtMs;
    ParkingTicket(String id, String spotId, String plate, long enteredAtMs) {
        this.id = id;
        this.spotId = spotId;
        this.plate = plate;
        this.enteredAtMs = enteredAtMs;
    }
}
interface PricingPolicy {
    int cents(ParkingTicket ticket, long exitAtMs);
}
final class HourlyPricing implements PricingPolicy {
    private final int centsPerHour;
    HourlyPricing(int centsPerHour) {
        this.centsPerHour = centsPerHour;
    }
    public int cents(ParkingTicket ticket, long exitAtMs) {
        long elapsed = Math.max(0, exitAtMs - ticket.enteredAtMs);
        long hours = Math.max(1, (elapsed + 3_599_999L) / 3_600_000L);
        return Math.toIntExact(hours * 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> activePlates = new HashSet<>();
    private final PricingPolicy pricing;
    ParkingLot(PricingPolicy pricing) {
        this.pricing = pricing;
        for (SpotType type : SpotType.values()) {
            free.put(type, new ArrayDeque<>());
        }
    }
    void addSpot(ParkingSpot spot) {
        spots.put(spot.id, spot);
        free.get(spot.type).addLast(spot);
    }
    synchronized ParkingTicket enter(Vehicle vehicle) {
        if (!activePlates.add(vehicle.plate)) {
            throw new IllegalStateException("plate already inside");
        }
        ParkingSpot spot = firstFit(vehicle);
        if (spot == null) {
            activePlates.remove(vehicle.plate);
            return null;
        }
        free.get(spot.type).remove(spot);
        spot.occupy(vehicle);
        ParkingTicket ticket = new ParkingTicket(
                UUID.randomUUID().toString(),
                spot.id,
                vehicle.plate,
                System.currentTimeMillis());
        open.put(ticket.id, ticket);
        return ticket;
    }
    synchronized int exit(String ticketId, long exitAtMs) {
        ParkingTicket ticket = open.remove(ticketId);
        if (ticket == null) throw new IllegalArgumentException("unknown ticket");
        ParkingSpot spot = spots.get(ticket.spotId);
        spot.release();
        free.get(spot.type).addLast(spot);
        activePlates.remove(ticket.plate);
        return pricing.cents(ticket, exitAtMs);
    }
    private ParkingSpot firstFit(Vehicle vehicle) {
        for (SpotType type : SpotType.values()) {
            for (ParkingSpot spot : free.get(type)) {
                if (spot.canFit(vehicle)) return spot;
            }
        }
        return null;
    }
}

Happy path: a car takes the first compatible COMPACT spot, receives an immutable ticket, and returns that spot to the same free queue at exit.

Failure/concurrency: an unknown or reused ticket throws before any spot changes. One monitor makes ticket removal and spot release atomic in memory. Multi-gate production uses a conditional state transition, not independent gate maps.

Alternative: scan all spots in O(n) for the smallest implementation. Free queues improve availability lookup. Do not introduce EV chargers, reservations, payments, or a display board until requested.

Concrete example. Car C-1 enters at 10:10, gets compact C17. Exit at 11:05 under ₹100/hour bills two started hours only if the confirmed policy rounds up; the code above does.

Complexity: ticket lookup and exit O(1) average. The shown first-fit may scan O(number of free spots); a compatibility-aware deque head makes it O(number of spot types). Space O(spots + open tickets).

Answered extensions. Multi-floor? Each Floor owns its free maps; lot chooses nearest floor with a fit. Weekend price? New PricingPolicy. Reserved/EV? Add explicit spot attributes only after rules are confirmed. Full lot? Return null or enqueue a wait request. Lost ticket? Operator lookup by plate plus a penalty policy. Stream of in/out intervals? Sort events on half-open [in,out) and maintain running occupancy. What next? Replace the scan with compatible free queues.

Stuck path. Write Spot, Ticket, Map<ticketId, Ticket>, enter, and exit. Then extract fee math into PricingPolicy.

3. Searchable Collection add/search IE-asked

Question stem. Design a typed collection with add(key, value) and search(query). The interviewer decides whether search is exact, prefix, contains, or top-K.

Evidence and remap. Aditya reported Searchable Collection LLD add/search in a non-UTA/AUTA onsite loop. Prefix top-K is a separate LC 6282609 SERP-only row whose body was unavailable in the research pass. Do not merge top-K into Aditya’s exact wording unless the interviewer asks.

Clarify before classes

• Actors: writer and search client.
• Exact versus prefix versus substring.
• Duplicate key: reject, overwrite, or retain a list.
• Return one, all, or top-K; define ordering.
• Normalization: case, punctuation, Unicode.
• Scale/concurrency: in-memory, then one lock for Trie writes.
• Invalid states: blank key, null value, duplicate id under a unique policy.

Entities, relationships, pattern

SearchableCollection<T> is the contract. Exact HashMap and prefix Trie are substitutable implementations. That is Strategy at the composition point and Open/Closed for a future inverted index.

import java.util.*;
interface SearchableCollection<T> {
    void add(String key, T value);
    List<T> search(String query);
}
final class ExactCollection<T> implements SearchableCollection<T> {
    private final Map<String, List<T>> values = new HashMap<>();
    public void add(String key, T value) {
        String normalized = normalize(key);
        values.computeIfAbsent(normalized, ignored -> new ArrayList<>())
                .add(Objects.requireNonNull(value));
    }
    public List<T> search(String query) {
        return List.copyOf(values.getOrDefault(normalize(query), List.of()));
    }
    private String normalize(String text) {
        if (text == null || text.isBlank()) {
            throw new IllegalArgumentException("blank key");
        }
        return text.toLowerCase(Locale.ROOT);
    }
}
final class PrefixNode<T> {
    final Map<Character, PrefixNode<T>> children = new HashMap<>();
    final List<T> terminalValues = new ArrayList<>();
}
final class PrefixCollection<T> implements SearchableCollection<T> {
    private final PrefixNode<T> root = new PrefixNode<>();
    public synchronized void add(String key, T value) {
        String normalized = normalize(key);
        PrefixNode<T> node = root;
        for (char ch : normalized.toCharArray()) {
            node = node.children.computeIfAbsent(ch, ignored -> new PrefixNode<>());
        }
        node.terminalValues.add(Objects.requireNonNull(value));
    }
    public synchronized List<T> search(String query) {
        PrefixNode<T> node = root;
        for (char ch : normalize(query).toCharArray()) {
            node = node.children.get(ch);
            if (node == null) return List.of();
        }
        List<T> result = new ArrayList<>();
        collect(node, result);
        return List.copyOf(result);
    }
    private void collect(PrefixNode<T> node, List<T> result) {
        result.addAll(node.terminalValues);
        for (PrefixNode<T> child : node.children.values()) {
            collect(child, result);
        }
    }
    private String normalize(String text) {
        if (text == null || text.isBlank()) {
            throw new IllegalArgumentException("blank query");
        }
        return text.toLowerCase(Locale.ROOT);
    }
}

Happy path: add yolov9 and yolov8; prefix search yolo walks four edges and collects both terminal payloads.

Failure/concurrency: define empty query before coding. Returning the entire Trie accidentally may be expensive. The shown lock keeps a write from changing child maps during DFS.

Why not one god class with a mode switch? Separate implementations make the semantics explicit. Why not Trie for exact only? HashMap is simpler and O(1) average. Contains search needs a scan or different index; a prefix Trie does not solve arbitrary substring search.

Concrete example. add("YOLOv9", modelCard) normalizes to yolov9. Exact search("yolo") misses; prefix search returns the card.

Complexity: exact add/search O(1) average plus key length. Trie add O(L); prefix search O(P + nodes visited + output). Space O(total indexed characters + values).

Answered extensions. Unique keys? Store one value and reject duplicate. Top-K? Add frequency and a size-K heap, as in card 8. Contains? Start with O(n) scan; propose an inverted/suffix index only at scale. Delete? Remove terminal value and prune empty nodes. Unicode? Normalize code points rather than indexing a-z. Concurrent reads? Read/write lock or immutable snapshots. What next? Confirm ordering before adding ranking.

Stuck path. Implement exact HashMap first. Say “prefix changes the implementation, not the interface,” then add a Trie walk and DFS.

4. Bookstore word-count OOD IE-asked

Question stem. Given a bookstore and books, return the count of a particular word in a specific book.

Evidence and remap. Shiwangi reported this in a named UTA later live labeled R3. OA was separate in that loop. It is later-slot evidence, not the UTA two-DSA default and not Job 10454435 evidence.

Clarify before classes

• Actors: catalog loader and reader query.
• Specific book by ISBN; title is not necessarily unique.
• Case-folding and punctuation rules.
• Build once/query many versus scanning on each query.
• Whole words versus phrases.
• Invalid states: duplicate ISBN, unknown book, blank word, concurrent edition replacement.

Entities, relationships, pattern

Book owns an immutable frequency map built from text. Bookstore indexes books by ISBN. Tokenizer is Strategy only if tokenization varies; do not start with a framework.

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 IndexedBook {
    final String isbn;
    final String title;
    private final Map<String, Integer> frequency;
    IndexedBook(String isbn, String title, String text, Tokenizer tokenizer) {
        this.isbn = Objects.requireNonNull(isbn);
        this.title = Objects.requireNonNull(title);
        Map<String, Integer> counts = new HashMap<>();
        for (String word : tokenizer.words(text)) {
            counts.merge(word, 1, Integer::sum);
        }
        frequency = Map.copyOf(counts);
    }
    int count(String word) {
        if (word == null || word.isBlank()) {
            throw new IllegalArgumentException("blank word");
        }
        return frequency.getOrDefault(word.toLowerCase(Locale.ROOT), 0);
    }
}
final class Bookstore {
    private final Map<String, IndexedBook> byIsbn = new HashMap<>();
    void add(IndexedBook book) {
        if (byIsbn.putIfAbsent(book.isbn, book) != null) {
            throw new IllegalArgumentException("duplicate isbn");
        }
    }
    int countInBook(String isbn, String word) {
        IndexedBook book = byIsbn.get(isbn);
        if (book == null) throw new IllegalArgumentException("unknown isbn");
        return book.count(word);
    }
}

Happy path: tokenize once in the constructor; query by ISBN; normalize the requested word; return the precomputed count.

Failure/concurrency: duplicate ISBN must not silently replace an edition. Immutable maps make concurrent reads safe after publication.

Why not scan the book each time? Fine for one query, O(tokens) each; precomputation gives O(1) average query. Why not inverted word-to-books index? That solves “which books contain X,” not this specific-book operation. GiftedBooks PDF Q&A is RAG, not this frequency map.

Concrete example. “The cat sat on the mat.” After normalization, the → 2. countInBook(isbn, "THE") returns 2.

Complexity: build O(T) expected for T tokens; query O(1) average; space O(unique words).

Answered extensions. Phrase count? Keep token sequence and use sliding match/KMP. Which books contain a word? Build an inverted index. Different languages? Inject a tokenizer with locale-aware segmentation. New edition? Version by ISBN/edition and atomically publish. Memory? Compress counts or build on demand. Stop words? Put policy in tokenizer/indexer, not Bookstore. What next? Add the exact follow-up index, not a microservice.

Stuck path. Write Book { Map<String,Integer> } and Bookstore { Map<isbn,Book> }. Extract Tokenizer only after punctuation/language varies.

5. Sprint / TaskBoard IE-asked

Question stem. Design a small board that creates tasks, assigns them, moves them through TODO/DOING/DONE, and lists a column in stable order.

Evidence and remap. LC 6567842 reported TaskBoard in a Chennai internal FTC loop with 2.8 YOE and four rounds. This is not §5.C UTA/AUTA evidence and is not a Job 10454435 forecast. Keep it DS-design sized.

Clarify before classes

• Actors: board member and assignee.
• Operations: add, assign, move, list by status.
• Unique task id; title may repeat.
• Allowed transitions: any, or TODO→DOING→DONE only?
• Ordering: insertion order within a column.
• Invalid states: duplicate id, unknown task, forbidden transition, null assignee.

Entities, relationships, pattern

TaskBoard owns task and column indexes. Task identity is immutable; status changes only through the board so both indexes remain consistent. LinkedHashSet gives O(1) average move and stable order.

import java.util.*;
enum TaskStatus { TODO, DOING, DONE }
final class BoardTask {
    final String id;
    private String title;
    private String assignee;
    private TaskStatus status = TaskStatus.TODO;
    BoardTask(String id, String title) {
        this.id = id;
        this.title = title;
    }
    TaskStatus status() {
        return status;
    }
    void assignTo(String userId) {
        assignee = Objects.requireNonNull(userId);
    }
    void moveTo(TaskStatus next) {
        status = Objects.requireNonNull(next);
    }
}
final class TaskBoard {
    private final Map<String, BoardTask> byId = new HashMap<>();
    private final Map<TaskStatus, LinkedHashSet<String>> columns =
            new EnumMap<>(TaskStatus.class);
    TaskBoard() {
        for (TaskStatus status : TaskStatus.values()) {
            columns.put(status, new LinkedHashSet<>());
        }
    }
    synchronized void add(BoardTask task) {
        if (byId.putIfAbsent(task.id, task) != null) {
            throw new IllegalArgumentException("duplicate task");
        }
        columns.get(TaskStatus.TODO).add(task.id);
    }
    synchronized void assign(String id, String userId) {
        getRequired(id).assignTo(userId);
    }
    synchronized void move(String id, TaskStatus next) {
        BoardTask task = getRequired(id);
        TaskStatus old = task.status();
        if (old == next) return;
        if (next.ordinal() > old.ordinal() + 1) {
            throw new IllegalStateException("skipped workflow state");
        }
        columns.get(old).remove(id);
        task.moveTo(next);
        columns.get(next).add(id);
    }
    synchronized List<String> idsIn(TaskStatus status) {
        return List.copyOf(columns.get(status));
    }
    private BoardTask getRequired(String id) {
        BoardTask task = byId.get(id);
        if (task == null) throw new IllegalArgumentException("unknown task");
        return task;
    }
}

Happy path: add T1 to TODO, assign Ada, move to DOING; remove from the old set before adding to the new set.

Failure/concurrency: moving TODO directly to DONE is rejected under the chosen rule, so both indexes remain unchanged. One lock covers map plus column sets.

Why not scan all tasks to list a column? That is O(n); the secondary index makes listing O(k). Why not model Jira sprints, events, and Kafka? They are outside this prompt.

Concrete example. TODO [T1,T2]. Move T1 to DOING. Result TODO [T2], DOING [T1], with no duplicate id.

Complexity: add, assign, move O(1) average; list O(k); space O(tasks).

Answered extensions. Backward move? Put transition rules in a policy. Sprint? Add sprint id as data and a secondary index. Priority? Add a comparator/sorted view only if ordered retrieval is needed. Audit? Append immutable transition events. Delete? Remove from byId and current column atomically. Concurrent editors? Version each task and reject stale updates. What next? Extract workflow policy if states become configurable.

Stuck path. Start with Map<id,Task> and status on Task. Then add Map<Status,LinkedHashSet<id>> when list-by-column must be fast.

6. Logger — SOLID applied to code IE-asked

Question stem. Design a logger with levels, filtering, formatting, and one or more outputs. Show SOLID and useful patterns.

Evidence and remap. Reddit 1ueybmg reported this in an AUTA India same-day R2. R1’s greedy/tree/puzzle details remain unnamed. This is named AUTA OOD evidence, not proof of Adarsh’s next format.

Clarify before classes

• Actors: application caller and operations consumer.
• Levels and minimum threshold.
• Sinks: console/file; network only if requested.
• Format: timestamp, level, message.
• Synchronous first; async as extension.
• Invalid states: null message, sink failure, formatter failure, queue full.
• One injected logger versus mutable global Singleton.

Entities, relationships, patterns

Logger is a facade. Formatter and sink are Strategies. A list of sinks is Composite fan-out. Timestamp/JSON/async may be Decorators. Dependency injection is preferred to Logger.getInstance().

import java.util.*;
enum LogLevel { DEBUG, INFO, WARN, ERROR }
final class LogRecord {
    final long timestampMs;
    final LogLevel level;
    final String message;
    LogRecord(long timestampMs, LogLevel level, String message) {
        this.timestampMs = timestampMs;
        this.level = Objects.requireNonNull(level);
        this.message = Objects.requireNonNull(message);
    }
}
interface LogFormatter {
    String format(LogRecord record);
}
interface LogSink {
    void write(String line);
}
final class PlainFormatter implements LogFormatter {
    public String format(LogRecord record) {
        return record.timestampMs + " " + record.level + " " + record.message;
    }
}
final class ConsoleSink implements LogSink {
    public void write(String line) {
        System.out.println(line);
    }
}
final class CompositeSink implements LogSink {
    private final List<LogSink> sinks;
    CompositeSink(List<LogSink> sinks) {
        this.sinks = List.copyOf(sinks);
    }
    public void write(String line) {
        RuntimeException first = null;
        for (LogSink sink : sinks) {
            try {
                sink.write(line);
            } catch (RuntimeException failure) {
                if (first == null) first = failure;
            }
        }
        if (first != null) {
            System.err.println("one or more log sinks failed");
        }
    }
}
final class Logger {
    private final LogLevel minimum;
    private final LogFormatter formatter;
    private final LogSink sink;
    Logger(LogLevel minimum, LogFormatter formatter, LogSink sink) {
        this.minimum = minimum;
        this.formatter = formatter;
        this.sink = sink;
    }
    void log(LogLevel level, String message) {
        if (level.ordinal() < minimum.ordinal()) return;
        LogRecord record = new LogRecord(
                System.currentTimeMillis(),
                level,
                message);
        sink.write(formatter.format(record));
    }
}

SOLID on this board, not as a poster

• S: Logger filters; formatter shapes; sink writes.
• O: add FileSink or JsonFormatter without editing Logger.log.
• L: every LogSink accepts a legal line; a sink that only accepts ERROR violates its contract unless the interface says so.
• I: write is separate from format; console is not forced to implement rotate/close.
• D: Logger depends on LogSink and LogFormatter, not FileWriter.

Happy path: INFO passes an INFO threshold, becomes an immutable record, is formatted once, and fans out to all sinks.

Failure/concurrency: one failed sink should not prevent later sinks or crash the request path. A production design emits an internal metric through a separate emergency path. For thread safety, use thread-safe sinks or serialize writes.

Why not FileLogger extends ConsoleLogger? A file logger is not a console logger; compose sinks. Why not a global Singleton? It hides dependencies and makes tests/order configuration brittle.

Concrete example. Minimum INFO drops DEBUG. ERROR formats once and writes to console plus file. Disk-full is isolated; console still receives the line.

Complexity: O(number of sinks) per accepted record; O(1) without queue; formatter output space O(message length).

Answered extensions. Async? Decorate sink with a bounded BlockingQueue and worker. Rotation? Implement a rotating file sink. JSON? New formatter. Per-package levels? Inject a level policy keyed by logger name. Queue full? Confirm block/drop/sample and expose a dropped counter. Correlation id? Put immutable context on LogRecord. Singleton? Construct once in composition root and inject it. What next? Add bounded async behavior without changing caller API.

Stuck path. Compile log(level,message) with System.out.println. Extract LogSink, then formatter, then a composite only if asked.

7. Dog check-in / check-out IE-asked

Question stem. Track registered dogs entering and leaving a daycare, enforce capacity and one active stay per dog, and retain history.

Evidence and remap. Nisarg reported LP plus this LLD in an AUTA same-day R2. The candidate said tracking, not “Amazon Pets.” Do not invent an Amazon product name or location.

Clarify before classes

• Actors: owner, front desk, operator.
• Operations: register, check in, check out, is boarded, history.
• One facility and integer capacity first.
• Re-entry after checkout is allowed as a new stay.
• Invalid states: unknown dog, duplicate registration, double check-in, checkout when absent, checkout before check-in.
• Ask whether billing/waitlist/owner lookup is required.

Entities, relationships, pattern

Daycare owns registry, active map, and append-only history. Stay is the state-transition record. This is a state machine and HashMap design, not a graph.

import java.time.*;
import java.util.*;
final class Dog {
    final String id;
    final String name;
    final String ownerId;
    Dog(String id, String name, String ownerId) {
        this.id = id;
        this.name = name;
        this.ownerId = ownerId;
    }
}
final class Stay {
    final String dogId;
    final Instant checkedIn;
    private Instant checkedOut;
    Stay(String dogId, Instant checkedIn) {
        this.dogId = dogId;
        this.checkedIn = checkedIn;
    }
    void close(Instant at) {
        if (checkedOut != null) throw new IllegalStateException("already closed");
        if (at.isBefore(checkedIn)) throw new IllegalArgumentException("time reversed");
        checkedOut = at;
    }
}
final class Daycare {
    private final int capacity;
    private final Map<String, Dog> dogs = new HashMap<>();
    private final Map<String, Stay> active = new HashMap<>();
    private final List<Stay> history = new ArrayList<>();
    Daycare(int capacity) {
        if (capacity < 1) throw new IllegalArgumentException("capacity");
        this.capacity = capacity;
    }
    synchronized void register(Dog dog) {
        if (dogs.putIfAbsent(dog.id, dog) != null) {
            throw new IllegalArgumentException("duplicate dog");
        }
    }
    synchronized void checkIn(String dogId, Instant at) {
        if (!dogs.containsKey(dogId)) throw new IllegalArgumentException("unknown dog");
        if (active.containsKey(dogId)) throw new IllegalStateException("already in");
        if (active.size() == capacity) throw new IllegalStateException("full");
        active.put(dogId, new Stay(dogId, at));
    }
    synchronized void checkOut(String dogId, Instant at) {
        Stay stay = active.get(dogId);
        if (stay == null) throw new IllegalStateException("not checked in");
        stay.close(at);
        active.remove(dogId);
        history.add(stay);
    }
    synchronized boolean isBoarded(String dogId) {
        return active.containsKey(dogId);
    }
    synchronized List<Stay> history() {
        return List.copyOf(history);
    }
}

Happy path: registered dog D1 enters, gets one active Stay, leaves, that Stay is closed and appended, and D1 may enter again with a new Stay.

Failure/concurrency: a second check-in sees the active entry and fails. The owner lock makes capacity check plus insert atomic.

Why not one status field on Dog? It loses visit history and couples identity to temporal state. Why not a graph? There is one legal active interval per dog.

Concrete example. Capacity 2; D1 and D2 are active. D3 check-in fails full. D1 checkout opens one place; D3 can then enter.

Complexity: register/check-in/check-out/isBoarded O(1) average; history listing O(h); space O(dogs + stays).

Answered extensions. Waitlist? Queue dog ids and promote after checkout. Billing? Price closed stay duration through a policy. Owner’s dogs? Add ownerId→set of dog ids. Current count? active.size(). Persistence? Transactionally enforce unique active dog id. Multiple facilities? One Daycare aggregate per facility. What next? Add a waitlist while preserving capacity.

Stuck path. Write Map<dogId,Stay> active and two methods. Add history and registration after the one-active-stay rule compiles.

8. Historical search / autocomplete — Trie + heap Standard CS

Question stem. Record historical search terms and return the K most frequent terms matching a prefix.

Evidence and remap. Some later research notes say this DS-design shape may appear more often than a full Parking Lot. The first-hand named AUTA OOD rows are Logger and dog check-in, not this. The nearest named row is LC 6282609 prefix top-K, but only the SERP was visible and the round was unlabeled. Treat this as a Standard CS pattern card; do not stamp an LC id.

Clarify before classes

• Actor: search user; writer records completed terms.
• Rank by total frequency, recency, or weighted score.
• K varies per query or fixed globally.
• Tie-break lexicographically or by recency.
• Case/Unicode normalization.
• Scale: query-time DFS first; precompute node top-K if QPS dominates.
• Invalid states: blank term, negative increment, non-positive K.

Entities, relationships, pattern

Trie nodes own character edges. Terminal nodes own immutable term identity and mutable count. Query walks prefix, DFSes descendants, and keeps a min-heap of size K.

import java.util.*;
final class TermNode {
    final Map<Character, TermNode> children = new HashMap<>();
    String term;
    int count;
}
final class HistoricalSearch {
    private final TermNode root = new TermNode();
    synchronized void record(String rawTerm) {
        String term = normalize(rawTerm);
        TermNode node = root;
        for (char ch : term.toCharArray()) {
            node = node.children.computeIfAbsent(ch, ignored -> new TermNode());
        }
        node.term = term;
        node.count++;
    }
    synchronized List<String> topK(String rawPrefix, int k) {
        if (k <= 0) return List.of();
        String prefix = normalize(rawPrefix);
        TermNode node = root;
        for (char ch : prefix.toCharArray()) {
            node = node.children.get(ch);
            if (node == null) return List.of();
        }
        Comparator<TermNode> worstFirst = (a, b) -> {
            int byCount = Integer.compare(a.count, b.count);
            if (byCount != 0) return byCount;
            return b.term.compareTo(a.term);
        };
        PriorityQueue<TermNode> heap = new PriorityQueue<>(worstFirst);
        collect(node, k, heap);
        List<TermNode> ordered = new ArrayList<>(heap);
        ordered.sort((a, b) -> {
            int byCount = Integer.compare(b.count, a.count);
            return byCount != 0 ? byCount : a.term.compareTo(b.term);
        });
        List<String> result = new ArrayList<>();
        for (TermNode hit : ordered) result.add(hit.term);
        return result;
    }
    private void collect(TermNode node,
                         int k,
                         PriorityQueue<TermNode> heap) {
        if (node.term != null) {
            heap.offer(node);
            if (heap.size() > k) heap.poll();
        }
        for (TermNode child : node.children.values()) {
            collect(child, k, heap);
        }
    }
    private String normalize(String text) {
        if (text == null || text.isBlank()) {
            throw new IllegalArgumentException("blank text");
        }
        return text.toLowerCase(Locale.ROOT);
    }
}

Happy path: record amazon 10 times, amazon locker 4, amass 3; prefix ama, K=2 returns amazon then amazon locker.

Failure/concurrency: tie behavior must be deterministic. The comparator keeps lower frequency or lexicographically larger term at the heap head for eviction. One lock prevents count changes while ranking.

Why not sort every term? Sorting M descendants is O(M log M); heap is O(M log K). Why not precompute immediately? Node-level top-K increases update work and memory; use it only under read-heavy QPS.

Concrete example. Prefix xy has no node, so return an empty immutable list. Equal counts choose lexicographically smaller first.

Complexity: record O(L). Query O(P + M log K + K log K), where M is terminal terms under the prefix. Space O(total characters).

Answered extensions. Fixed K/high QPS? Cache top-K at each node. Recency? Store last-used and define a score/comparator. Delete? Decrement and prune zero-count terminals. Distributed counts? Aggregate sharded counters, then merge K-sized heaps. Typo tolerance? Different problem: edit-distance search/BK-tree. Personalization? Separate global and user scores; do not mutate global truth. What next? Measure read/write ratio before precomputation.

Stuck path. Insert terms into a Trie, walk prefix, DFS all terminals. Add a size-K min-heap after correctness.

9. Spring login layers — not Login Tracker IE-asked

Question stem. Model a login flow through Controller, Facade, Service, and Repository, then eliminate an if-else validation ladder.

Evidence and remap. Bhavya reported this in an HM interview. LRU was Interview 2. This login layering prompt is not the unverified new_login/get_oldest_login tracker.

Clarify before classes

• Actor: user submitting username/password.
• Operations: validate request, authenticate credentials, return HTTP status.
• Authentication only; authorization/RBAC is separate.
• Repository is in-memory for Live Code; password hashing is an injected verifier.
• Invalid states: blank fields, malformed username, unknown user, wrong password, locked user.
• Scale: stateless service first; session/JWT only if asked.

Entities, relationships, pattern

Controller translates HTTP. Facade runs a Chain of Responsibility of validators. Service authenticates. Repository loads users. Dependency inversion lets service depend on repository and password-verifier interfaces.

import java.util.*;
final class LoginRequest {
    final String username;
    final String password;
    LoginRequest(String username, String password) {
        this.username = username;
        this.password = password;
    }
}
interface LoginValidator {
    void validate(LoginRequest request);
}
final class RequiredFieldsValidator implements LoginValidator {
    public void validate(LoginRequest request) {
        if (request == null
                || request.username == null
                || request.username.isBlank()
                || request.password == null
                || request.password.isBlank()) {
            throw new IllegalArgumentException("missing credentials");
        }
    }
}
final class UserAccount {
    final String username;
    final String passwordHash;
    final boolean locked;
    UserAccount(String username, String passwordHash, boolean locked) {
        this.username = username;
        this.passwordHash = passwordHash;
        this.locked = locked;
    }
}
interface UserRepository {
    Optional<UserAccount> find(String username);
}
interface PasswordVerifier {
    boolean matches(String raw, String encoded);
}
final class AuthService {
    private final UserRepository users;
    private final PasswordVerifier passwords;
    AuthService(UserRepository users, PasswordVerifier passwords) {
        this.users = users;
        this.passwords = passwords;
    }
    boolean authenticate(LoginRequest request) {
        UserAccount user = users.find(request.username).orElse(null);
        if (user == null || user.locked) return false;
        return passwords.matches(request.password, user.passwordHash);
    }
}
final class LoginFacade {
    private final List<LoginValidator> validators;
    private final AuthService auth;
    LoginFacade(List<LoginValidator> validators, AuthService auth) {
        this.validators = List.copyOf(validators);
        this.auth = auth;
    }
    boolean login(LoginRequest request) {
        for (LoginValidator validator : validators) {
            validator.validate(request);
        }
        return auth.authenticate(request);
    }
}
final class LoginController {
    private final LoginFacade facade;
    LoginController(LoginFacade facade) {
        this.facade = facade;
    }
    int post(LoginRequest request) {
        try {
            return facade.login(request) ? 200 : 401;
        } catch (IllegalArgumentException invalid) {
            return 400;
        }
    }
}

Happy path: controller receives request, validators accept syntax, service loads account and verifies password, controller maps true to 200.

Failure/concurrency: wrong password is not a validation error; it returns authentication failure/401. Blank username is malformed/400. Repository updates must atomically manage lock state.

Why not put every check in Controller? HTTP, validation, and authentication would change for different reasons. Why not role checks in LoginFacade? Authentication establishes identity; authorization belongs after login.

Concrete example. Blank username stops at RequiredFieldsValidator. Existing user with wrong password reaches AuthService and returns false.

Complexity: validators O(v); repository lookup O(1) average in memory or store-dependent; space O(v + users).

Answered extensions. New password rule? Add a validator without facade if-else. Locked account? Service returns false or a typed result. Sessions? Add a token/session issuer after authentication. Audit? Inject an auth-event sink; never log passwords. Rate-limit attempts? Put a limiter at the controller/filter boundary. Authorization? Separate AuthZ service; do not copy role if-else. What next? Replace boolean with a typed result if callers need locked/not-found distinctions.

Stuck path. Draw Controller→Facade→Service→Repository. Compile one validator list loop, then keep credential verification in Service.

10. Device capability interfaces Standard CS

Question stem. Model monitor, speaker, and tablet capabilities using PowerAware, DisplayCapable, and SpeakerCapable without an inheritance explosion.

Evidence and remap. This came from a user-pasted Round 2 LLD block without an opened source URL in the research bible. It remains Class C / unverified pattern practice, not a Job 10454435 question.

Clarify before classes

• Device families: monitor, speaker box, tablet.
• Capabilities: power, display/brightness, speaker/volume.
• Tablet has all three; monitor has power/display; speaker has power/speaker.
• Operation while powered off is invalid.
• Ranges are 0–100.
• Persistence and cloud control are out of scope.
• Ask whether battery exists only on portable devices.

Entities, relationships, pattern

Narrow capability interfaces apply Interface Segregation. Concrete devices implement only legal capabilities. Shared stateful mechanics are composed as PowerState, DisplayPanel, and SpeakerDriver. Tablet does not extend Monitor.

interface PowerAware {
    void powerOn();
    void powerOff();
    boolean isOn();
}
interface DisplayCapable {
    void show(String content);
    void setBrightness(int percent);
}
interface SpeakerCapable {
    void play(String audio);
    void setVolume(int percent);
}
final class PowerState {
    private boolean on;
    void on() { on = true; }
    void off() { on = false; }
    boolean isOn() { return on; }
}
final class DisplayPanel implements DisplayCapable {
    private int brightness = 50;
    public void show(String content) {
        if (content == null) throw new IllegalArgumentException("content");
    }
    public void setBrightness(int percent) {
        brightness = bounded(percent);
    }
    private int bounded(int value) {
        if (value < 0 || value > 100) {
            throw new IllegalArgumentException("range");
        }
        return value;
    }
}
final class SpeakerDriver implements SpeakerCapable {
    private int volume = 50;
    public void play(String audio) {
        if (audio == null) throw new IllegalArgumentException("audio");
    }
    public void setVolume(int percent) {
        if (percent < 0 || percent > 100) {
            throw new IllegalArgumentException("range");
        }
        volume = percent;
    }
}
final class Monitor implements PowerAware, DisplayCapable {
    private final PowerState power = new PowerState();
    private final DisplayPanel panel = new DisplayPanel();
    public void powerOn() { power.on(); }
    public void powerOff() { power.off(); }
    public boolean isOn() { return power.isOn(); }
    public void show(String content) {
        requireOn();
        panel.show(content);
    }
    public void setBrightness(int percent) {
        panel.setBrightness(percent);
    }
    private void requireOn() {
        if (!isOn()) throw new IllegalStateException("powered off");
    }
}
final class SpeakerBox implements PowerAware, SpeakerCapable {
    private final PowerState power = new PowerState();
    private final SpeakerDriver speaker = new SpeakerDriver();
    public void powerOn() { power.on(); }
    public void powerOff() { power.off(); }
    public boolean isOn() { return power.isOn(); }
    public void play(String audio) {
        if (!isOn()) throw new IllegalStateException("powered off");
        speaker.play(audio);
    }
    public void setVolume(int percent) {
        speaker.setVolume(percent);
    }
}
final class Tablet implements PowerAware, DisplayCapable, SpeakerCapable {
    private final PowerState power = new PowerState();
    private final DisplayPanel panel = new DisplayPanel();
    private final SpeakerDriver speaker = new SpeakerDriver();
    public void powerOn() { power.on(); }
    public void powerOff() { power.off(); }
    public boolean isOn() { return power.isOn(); }
    public void show(String content) {
        requireOn();
        panel.show(content);
    }
    public void setBrightness(int percent) {
        panel.setBrightness(percent);
    }
    public void play(String audio) {
        requireOn();
        speaker.play(audio);
    }
    public void setVolume(int percent) {
        speaker.setVolume(percent);
    }
    private void requireOn() {
        if (!isOn()) throw new IllegalStateException("powered off");
    }
}

Happy path: power on Tablet, display content through its panel, play audio through its speaker. A client that accepts DisplayCapable accepts Monitor and Tablet but rejects SpeakerBox at compile time.

Failure/invariant: powered-off show/play throws. A monitor is never forced to implement a fake speaker method. That is the point of narrow interfaces.

Why not GodDevice? Monitor would stub speaker/camera/GPS methods, violating ISP and usually LSP. Why not Tablet extends Monitor? A tablet is not a monitor; reuse the panel through composition. Why not subclasses for every capability combination? Three binary capabilities already yield eight combinations.

Concrete example. showSplash(DisplayCapable d) compiles for Monitor and Tablet. Passing SpeakerBox does not compile, which prevents a runtime “unsupported” stub.

Complexity: all operations O(1); space O(1) per device.

Answered extensions. Camera? Add CameraCapable; only camera devices implement it. Battery? Compose Battery in portable devices, not PowerAware globally. Mute? Add to SpeakerCapable only if all speakers support it, otherwise a narrower capability. Shared power code? Compose PowerState rather than an abstract mega-device. Defaults? Use only stateless convenience defaults; state remains concrete. Test? Inject fake panel/driver interfaces if behavior needs observation. What next? Add one new capability without editing existing device classes.

Stuck path. Write the three interfaces first. Implement Monitor with two and Tablet with three. Then replace duplicated state with composed helpers.

11. Basic Calculator, then OOD extension Standard CS

Question stem. Evaluate a Basic Calculator II expression with + - * /, spaces, and integer truncation. Then redesign so adding operators does not grow a god switch.

Evidence and remap. DevBrainiac 129 is an intern Basic Calculator II analogue and counts OA as R1. The FTE “calculator then OOD extend” block is paste-only without a verified URL. Do not stamp LC 224/227 as an asked id.

Clarify before classes

• Actor: caller supplying one expression.
• Operators and precedence.
• Parentheses and unary minus are excluded unless requested.
• Integer division truncates toward zero.
• Invalid states: empty input, bad token, divide by zero, overflow.
• OOD extension: new operator, variables, functions, or parentheses?

Algorithm first, then objects

One pass uses a stack of additive terms. Multiplication/division collapse the previous term immediately. For extension, parse to an Expr tree whose BinaryOp is Strategy.

import java.util.*;
final class BasicCalculator {
    int calculate(String text) {
        if (text == null || text.isBlank()) {
            throw new IllegalArgumentException("empty expression");
        }
        Deque<Integer> terms = new ArrayDeque<>();
        int number = 0;
        char pending = '+';
        boolean sawDigit = false;
        for (int i = 0; i <= text.length(); i++) {
            char ch = i == text.length() ? '+' : text.charAt(i);
            if (Character.isDigit(ch)) {
                number = Math.addExact(Math.multiplyExact(number, 10), ch - '0');
                sawDigit = true;
                continue;
            }
            if (ch == ' ') continue;
            if (!sawDigit) throw new IllegalArgumentException("expected number");
            apply(terms, pending, number);
            if (i < text.length() && "+-*/".indexOf(ch) < 0) {
                throw new IllegalArgumentException("bad operator");
            }
            pending = ch;
            number = 0;
            sawDigit = false;
        }
        int result = 0;
        for (int term : terms) result = Math.addExact(result, term);
        return result;
    }
    private void apply(Deque<Integer> terms, char operator, int value) {
        if (operator == '+') terms.push(value);
        else if (operator == '-') terms.push(-value);
        else if (operator == '*') terms.push(Math.multiplyExact(terms.pop(), value));
        else if (operator == '/') {
            if (value == 0) throw new ArithmeticException("divide by zero");
            terms.push(terms.pop() / value);
        }
    }
}
interface Expr {
    int eval();
}
interface BinaryOp {
    int apply(int left, int right);
}
final class NumberExpr implements Expr {
    private final int value;
    NumberExpr(int value) {
        this.value = value;
    }
    public int eval() {
        return value;
    }
}
final class BinaryExpr implements Expr {
    private final Expr left;
    private final Expr right;
    private final BinaryOp operation;
    BinaryExpr(Expr left, BinaryOp operation, Expr right) {
        this.left = left;
        this.operation = operation;
        this.right = right;
    }
    public int eval() {
        return operation.apply(left.eval(), right.eval());
    }
}
final class AddOp implements BinaryOp {
    public int apply(int left, int right) {
        return Math.addExact(left, right);
    }
}
final class MultiplyOp implements BinaryOp {
    public int apply(int left, int right) {
        return Math.multiplyExact(left, right);
    }
}
final class PowerOp implements BinaryOp {
    public int apply(int left, int right) {
        if (right < 0) throw new IllegalArgumentException("negative exponent");
        int result = 1;
        for (int i = 0; i < right; i++) {
            result = Math.multiplyExact(result, left);
        }
        return result;
    }
}

Happy path: 3+2*2 pushes 3, pushes 2, then replaces 2 with 4; summing terms returns 7.

Failure/invariant: division by zero fails at the operator, and malformed consecutive operators fail before stack mutation. Overflow is explicit through Math.*Exact.

Why not ScriptEngine/eval? It hides parsing, has security/runtime concerns, and does not show precedence. Why not a forty-case switch? A parser maps symbols to operators; evaluation stays polymorphic. Why not build the full AST first? The interviewer may only require Calculator II; compile the algorithm before the extension.

Concrete example. Tree BinaryExpr(NumberExpr(3), AddOp, BinaryExpr(2, MultiplyOp, 2)) evaluates to 7. Add power by registering PowerOp; existing expression classes do not change.

Complexity: one-pass calculator O(n) time/O(n) stack. AST evaluation O(nodes) time/O(height) call stack.

Answered extensions. Parentheses? Recursive descent: expression→term→factor returning Expr. Unary minus? Parse it in factor as a unary expression. Variables? VariableExpr reads an injected environment. Power precedence? Add a grammar level, not an if in eval. Division policy? Separate integer and decimal numeric domains. Overflow? Keep exact arithmetic or switch to BigInteger. What next? Implement parser registration for operators.

Stuck path. Write the stack with last operator. Then show Expr, BinaryOp, and one BinaryExpr; say parser construction is next.

12. Per-message + global logger limiter Standard CS

Question stem. Print the same message at most once per T seconds and also allow at most G total printed messages per global window.

Evidence and remap. This was a paste-only new-grad BR-adjacent OOD card. It is not a second independent distributed Rate Limiter report. The independent SDE I Rate Limiter live count remains exactly one.

Clarify before classes

• Actor: logger caller.
• T and global G/window.
• Timestamps monotonic or arbitrary.
• Record last printed time, not last attempted time.
• At a boundary, timestamps exactly window-old expire.
• Invalid states: negative timestamp, blank message, non-positive configuration.
• Single process first; distributed is the separate card.

Entities, relationships, pattern

HashMap stores the last accepted timestamp per message. Deque stores accepted global timestamps inside the current sliding window. Allow only if both policies pass, and mutate both only after acceptance.

import java.util.*;
final class MessageAndGlobalLogger {
    private final int messageGapSeconds;
    private final int globalMaximum;
    private final int globalWindowSeconds;
    private final Map<String, Integer> lastAccepted = new HashMap<>();
    private final Deque<Integer> globalAccepted = new ArrayDeque<>();
    private int lastTimestamp = Integer.MIN_VALUE;
    MessageAndGlobalLogger(int messageGapSeconds,
                           int globalMaximum,
                           int globalWindowSeconds) {
        if (messageGapSeconds < 0
                || globalMaximum <= 0
                || globalWindowSeconds <= 0) {
            throw new IllegalArgumentException("configuration");
        }
        this.messageGapSeconds = messageGapSeconds;
        this.globalMaximum = globalMaximum;
        this.globalWindowSeconds = globalWindowSeconds;
    }
    synchronized boolean shouldPrint(int timestamp, String message) {
        if (timestamp < lastTimestamp) {
            throw new IllegalArgumentException("timestamps must be monotonic");
        }
        if (message == null || message.isBlank()) {
            throw new IllegalArgumentException("blank message");
        }
        lastTimestamp = timestamp;
        while (!globalAccepted.isEmpty()
                && timestamp - globalAccepted.peekFirst() >= globalWindowSeconds) {
            globalAccepted.removeFirst();
        }
        if (globalAccepted.size() >= globalMaximum) return false;
        Integer previous = lastAccepted.get(message);
        if (previous != null && timestamp - previous < messageGapSeconds) {
            return false;
        }
        lastAccepted.put(message, timestamp);
        globalAccepted.addLast(timestamp);
        return true;
    }
}

Happy path: gap 10, global 2 per second; (1,a) and (1,b) pass; after the one-second window expires, another distinct message may pass.

Failure/concurrency: (1,c) fails global and must not update c’s per-message timestamp. Otherwise c could be suppressed later despite never printing. One lock protects both structures.

Why not one map only? It cannot count accepted messages across all keys. Why not call this the full Rate Limiter IE? This is a local logger rule from an unverified paste; the distributed SD report remains one.

Concrete example. Gap=10, globalMax=2, window=1: (1,a) true; (1,b) true; (1,c) false; (2,c) true; (5,a) false; (11,a) true.

Complexity: amortized O(1) each because every accepted timestamp enters/leaves the deque once. Space O(unique messages + globalMaximum).

Answered extensions. Out-of-order timestamps? Use a clock or ordered event buffer; do not use this deque unchanged. Memory leak in message map? Expire old message entries lazily or with a heap. Different gaps? Inject per-category policy. Return reason? Return enum ALLOW/MESSAGE_LIMIT/GLOBAL_LIMIT. Thread safety? One lock; do not split two structures. Distributed? Move atomic decision to Redis/script and open the full limiter card. What next? Add reason plus retry time.

Stuck path. Implement per-message HashMap first, then add a deque of accepted global timestamps. Remember: rejected calls change neither accepted structure.

13. Full Rate Limiter + distributed scale IE-asked

Evidence lock. Independent SDE I live-round count is exactly 1. It was a Second Technical system-design round in an OA+3 loop on 13 Feb 2025: IE.in 2025-grad. The first technical was graph + tree + OS. This is not UTA two-DSA, not a Job 10454435 forecast, and not increased by SDE II posts, videos, mentor prep, elevator DoS, or the local logger limiter above.

Question stem. Design a Rate Limiter and scale it across distributed application servers.

Clarify before classes

• Actor/key: user, IP, API key, tenant, route, or combinations.
• Policy: N requests per W seconds.
• Burst: allowed up to what capacity?
• Action: reject with HTTP 429 and Retry-After, queue, or drop.
• Topology: one JVM or many behind a load balancer.
• Consistency: exact versus approximate.
• Failure: Redis unavailable—fail-open or fail-closed by endpoint risk.
• Invalid states: negative rate/capacity, non-monotonic time, unbounded key retention.

Where it sits

Place the limiter at API gateway, middleware, or sidecar before business logic. Do not copy checks into every use case. Per-user and global policies may be composed with AND.

Five strategies: say all, choose token bucket

• Fixed window: O(1) state per key; simple; up to almost 2× burst across a boundary.
• Sliding log: deque/sorted timestamps; exact; O(requests in window) memory per hot key.
• Sliding counter: current + previous bucket weighted by elapsed fraction; O(1) memory; approximate.
• Token bucket: capacity tokens, continuous refill; O(1) state; allows controlled bursts.
• Leaky bucket: queue/water level drains steadily; smooth output; may queue or discard excess.

Local Java — fixed, sliding log, sliding counter, token, leaky

import java.util.*;
interface RateLimiter {
    Decision allow(String key, long nowNanos);
}
final class Decision {
    final boolean allowed;
    final long retryAfterMillis;
    private Decision(boolean allowed, long retryAfterMillis) {
        this.allowed = allowed;
        this.retryAfterMillis = retryAfterMillis;
    }
    static Decision yes() {
        return new Decision(true, 0);
    }
    static Decision no(long retryAfterMillis) {
        return new Decision(false, Math.max(1, retryAfterMillis));
    }
}
final class FixedWindowLimiter implements RateLimiter {
    private static final class Window {
        long start;
        int count;
        Window(long start) {
            this.start = start;
        }
    }
    private final int maximum;
    private final long windowNanos;
    private final Map<String, Window> states = new HashMap<>();
    FixedWindowLimiter(int maximum, long windowNanos) {
        this.maximum = maximum;
        this.windowNanos = windowNanos;
    }
    public synchronized Decision allow(String key, long now) {
        Window window = states.get(key);
        if (window == null || now - window.start >= windowNanos) {
            window = new Window(now);
            states.put(key, window);
        }
        if (window.count < maximum) {
            window.count++;
            return Decision.yes();
        }
        return Decision.no((windowNanos - (now - window.start)) / 1_000_000L);
    }
}
final class SlidingLogLimiter implements RateLimiter {
    private final int maximum;
    private final long windowNanos;
    private final Map<String, Deque<Long>> logs = new HashMap<>();
    SlidingLogLimiter(int maximum, long windowNanos) {
        this.maximum = maximum;
        this.windowNanos = windowNanos;
    }
    public synchronized Decision allow(String key, long now) {
        Deque<Long> log = logs.computeIfAbsent(key, ignored -> new ArrayDeque<>());
        while (!log.isEmpty() && now - log.peekFirst() >= windowNanos) {
            log.removeFirst();
        }
        if (log.size() < maximum) {
            log.addLast(now);
            return Decision.yes();
        }
        return Decision.no((windowNanos - (now - log.peekFirst())) / 1_000_000L);
    }
}
final class SlidingCounterLimiter implements RateLimiter {
    private static final class Counter {
        long currentStart;
        int current;
        int previous;
        Counter(long currentStart) {
            this.currentStart = currentStart;
        }
    }
    private final int maximum;
    private final long windowNanos;
    private final Map<String, Counter> states = new HashMap<>();
    SlidingCounterLimiter(int maximum, long windowNanos) {
        this.maximum = maximum;
        this.windowNanos = windowNanos;
    }
    public synchronized Decision allow(String key, long now) {
        Counter state = states.computeIfAbsent(key, ignored -> new Counter(now));
        long elapsed = now - state.currentStart;
        if (elapsed >= windowNanos) {
            state.previous = elapsed < 2L * windowNanos ? state.current : 0;
            state.current = 0;
            state.currentStart = now;
            elapsed = 0;
        }
        double previousWeight = (double) (windowNanos - elapsed) / windowNanos;
        double estimate = state.previous * previousWeight + state.current;
        if (estimate >= maximum) {
            return Decision.no(Math.max(1, (windowNanos - elapsed) / 1_000_000L));
        }
        state.current++;
        return Decision.yes();
    }
}
final class TokenBucketLimiter implements RateLimiter {
    private static final class Bucket {
        double tokens;
        long lastRefill;
        Bucket(double tokens, long lastRefill) {
            this.tokens = tokens;
            this.lastRefill = lastRefill;
        }
    }
    private final int capacity;
    private final double refillPerSecond;
    private final Map<String, Bucket> buckets = new HashMap<>();
    TokenBucketLimiter(int capacity, double refillPerSecond) {
        if (capacity <= 0 || refillPerSecond <= 0) {
            throw new IllegalArgumentException("configuration");
        }
        this.capacity = capacity;
        this.refillPerSecond = refillPerSecond;
    }
    public synchronized Decision allow(String key, long now) {
        Bucket bucket = buckets.computeIfAbsent(
                key,
                ignored -> new Bucket(capacity, now));
        if (now < bucket.lastRefill) {
            throw new IllegalArgumentException("clock reversed");
        }
        double elapsedSeconds = (now - bucket.lastRefill) / 1_000_000_000.0;
        bucket.tokens = Math.min(
                capacity,
                bucket.tokens + elapsedSeconds * refillPerSecond);
        bucket.lastRefill = now;
        if (bucket.tokens >= 1.0) {
            bucket.tokens -= 1.0;
            return Decision.yes();
        }
        double seconds = (1.0 - bucket.tokens) / refillPerSecond;
        return Decision.no((long) Math.ceil(seconds * 1000.0));
    }
}
final class LeakyBucketLimiter implements RateLimiter {
    private static final class Water {
        double level;
        long lastLeak;
        Water(long lastLeak) {
            this.lastLeak = lastLeak;
        }
    }
    private final int capacity;
    private final double leakPerSecond;
    private final Map<String, Water> states = new HashMap<>();
    LeakyBucketLimiter(int capacity, double leakPerSecond) {
        this.capacity = capacity;
        this.leakPerSecond = leakPerSecond;
    }
    public synchronized Decision allow(String key, long now) {
        Water water = states.computeIfAbsent(key, ignored -> new Water(now));
        double elapsed = (now - water.lastLeak) / 1_000_000_000.0;
        water.level = Math.max(0.0, water.level - elapsed * leakPerSecond);
        water.lastLeak = now;
        if (water.level + 1.0 > capacity) {
            return Decision.no((long) Math.ceil(1000.0 / leakPerSecond));
        }
        water.level += 1.0;
        return Decision.yes();
    }
}
final class RateLimitFilter {
    private final RateLimiter perUser;
    private final RateLimiter global;
    RateLimitFilter(RateLimiter perUser, RateLimiter global) {
        this.perUser = perUser;
        this.global = global;
    }
    Response preHandle(String userId, long nowNanos) {
        Decision user = perUser.allow(userId, nowNanos);
        if (!user.allowed) return Response.tooMany(user.retryAfterMillis);
        Decision all = global.allow("GLOBAL", nowNanos);
        if (!all.allowed) return Response.tooMany(all.retryAfterMillis);
        return Response.ok();
    }
}
final class Response {
    final int status;
    final long retryAfterMillis;
    private Response(int status, long retryAfterMillis) {
        this.status = status;
        this.retryAfterMillis = retryAfterMillis;
    }
    static Response ok() {
        return new Response(200, 0);
    }
    static Response tooMany(long retryAfterMillis) {
        return new Response(429, retryAfterMillis);
    }
}

Happy path and local race

Choose token bucket for a bursty API. Capacity 10, refill 5/sec. After idle time the bucket fills to at most 10. Each accepted request atomically refills and consumes one token.

Without the lock, two threads may both observe one token and both decrement. ConcurrentHashMap alone does not make read-refill-decrement-write atomic. A per-key atomic compute or striped lock can reduce contention, but one monitor is the Live Code baseline.

Distributed design: Redis + atomic Lua concept

Local JVM state is wrong behind a load balancer because N application tasks each grant their own budget. Store each key’s tokens and last-refill timestamp in shared Redis. Execute fetch, refill, decision, decrement, write, and expiry in one Lua script. Use Redis TIME inside the script so application clocks cannot disagree.

-- Concept only: TOKEN_BUCKET
-- KEYS[1] = route:user key
-- ARGV[1] = capacity
-- ARGV[2] = refill tokens per second
--
-- 1. now = Redis TIME
-- 2. HMGET tokens,last_refill
-- 3. refill = min(capacity, tokens + elapsed * rate)
-- 4. if refill >= 1 then decrement and allowed=1 else allowed=0
-- 5. HMSET tokens,last_refill and EXPIRE after an idle horizon
-- 6. return {allowed,retry_after_ms}
--
-- One script is atomic: two app servers cannot spend the same token.

HTTP behavior and failure policy

Denial returns HTTP 429 Too Many Requests plus Retry-After. Do not return 200 with empty data and do not use 503 unless the service itself is unavailable.

Redis down: fail-closed for checkout/payments or expensive writes to protect origin, accepting false 429s. Fail-open for a cheap marketing pixel when availability is more important, accepting overload risk. Pick based on the endpoint; do not waffle.

Hot keys can be sharded only if semantics permit. A strict global key is inherently centralized/contended. Approximate local quotas with periodic reconciliation trade correctness for availability; say the trade.

Alternatives and complexity

Fixed window is simplest but boundary-bursty. Sliding log is exact but memory-heavy. Sliding counter is approximate and cheap. Token bucket matches bursty APIs. Leaky bucket protects a downstream with smooth output.

Local fixed/counter/token/leaky operations are O(1) average and O(keys) space. Sliding log is amortized O(1) operation and O(requests retained) space. Distributed Redis script is one network round trip and O(1) state per key for token bucket.

Concrete example. Capacity 3, refill 1/sec. Three requests at t=0 pass; the fourth gets 429 with roughly one-second Retry-After. At t=1, one token has refilled and one request passes. Two app servers share the same Redis key, so total is still three, not six.

Answered extensions. Per-route and per-user? Compose keys/policies and require both decisions. Global plus local? Global key protects origin; user key protects fairness; atomic rollback/reservation matters if the second check fails. Memory cleanup? Expire idle Redis keys after enough time to refill fully. Hot tenant? Dedicated quota/shard or hierarchical buckets. Multi-region? Decide strict global correctness versus region quotas; cross-region consensus adds latency. Redis race? Lua keeps refill/decrement atomic. Clock? Redis TIME, monotonic local clock for one JVM. Fail policy? Closed for payments, open for cheap telemetry. What next? Add metrics for allowed/denied/retry and test boundaries.

Stuck path. Compile allow(key) with HashMap token state. Say “many servers move the same math into atomic Redis Lua.” Finish with 429/Retry-After and a concrete fail-open/closed choice.

Resume honesty: do not claim Ylogx shipped this limiter. Ylogx Redis reduced bot database latency by 35% as a cache. ALB is the architectural seat where a gateway limiter could sit, but that is an analogy, not a shipped feature.

14. OPTIONAL MENTOR — Login Tracker Standard CS

Unverified / mentor-only. new_login / get_oldest_login is not first-hand evidence in Question-Research-BIBLE §10. Do not present it as an R2, R3, AUTA, UTA, or Job 10454435 question. Bhavya’s Spring login layers are card 9 and are not this tracker. Bhavya’s LRU is another separate prompt.

Practice stem. Record a user login. A repeat login refreshes that user to newest. Return the oldest current user/timestamp without removing it.

Clarify before classes

• Actor: login event consumer.
• One current timestamp per user.
• Repeat login refreshes recency.
• getOldestLogin peeks, not pops.
• Empty returns Optional.
• Timestamps may be stored but ordering follows accepted event order unless specified otherwise.
• Invalid states: blank id, reversed timestamps if monotonicity is required.

Entities, relationships, pattern

HashMap finds a user node in O(1). Doubly linked list stores oldest-to-newest. This is LRU-shaped without capacity eviction.

import java.util.*;
final class LoginEntry {
    final String userId;
    final long timestamp;
    LoginEntry(String userId, long timestamp) {
        this.userId = userId;
        this.timestamp = timestamp;
    }
}
final class LoginTracker {
    private static final class Node {
        LoginEntry value;
        Node previous;
        Node next;
        Node(LoginEntry value) {
            this.value = value;
        }
    }
    private final Map<String, Node> byUser = new HashMap<>();
    private final Node head = new Node(null);
    private final Node tail = new Node(null);
    LoginTracker() {
        head.next = tail;
        tail.previous = head;
    }
    synchronized void newLogin(String userId, long timestamp) {
        if (userId == null || userId.isBlank()) {
            throw new IllegalArgumentException("blank user");
        }
        Node old = byUser.remove(userId);
        if (old != null) unlink(old);
        Node fresh = new Node(new LoginEntry(userId, timestamp));
        append(fresh);
        byUser.put(userId, fresh);
    }
    synchronized Optional<LoginEntry> getOldestLogin() {
        return head.next == tail
                ? Optional.empty()
                : Optional.of(head.next.value);
    }
    private void unlink(Node node) {
        node.previous.next = node.next;
        node.next.previous = node.previous;
    }
    private void append(Node node) {
        Node last = tail.previous;
        last.next = node;
        node.previous = last;
        node.next = tail;
        tail.previous = node;
    }
}

Happy path: A logs in at 1, B at 2; oldest is A. A logs in at 3; unlink A’s old node and append a fresh node; oldest becomes B.

Failure/concurrency: map update and list splice must be under one lock. ConcurrentHashMap plus an unlocked DLL is a bug.

Why not TreeMap timestamp→user? Duplicate timestamps and repeat-user removal need a second index; operations become O(log n). Why not a queue? Refreshing an arbitrary existing user is O(n) or leaves stale entries. LinkedHashMap with remove+put is the JDK shortcut.

Concrete example. A@1, B@2, A@3 produces list B@2→A@3. getOldestLogin() returns B@2 and does not remove it.

Complexity: newLogin/getOldest O(1) average; space O(active users).

Answered extensions. TTL? Add expiration and lazy cleanup/heap; still unverified practice. Remove user? Map lookup plus unlink. Oldest N? Walk first N nodes, O(N). Distributed? A sorted set can model recency, but consistency and duplicate events must be specified. Idempotency? Include event id/version before refreshing. Thread safety? One lock covers map and list. What next? Stop; do not promote this mentor card into evidence.

Stuck path. Use LinkedHashMap: remove existing user, put user at end, read first iterator entry. If asked to show internals, replace it with HashMap + DLL.

Rapid rehearsal: one minute per design

Locker

1. Say one package per cubby.
2. Use free deques by size.
3. Compile dropOff and pickUp.
4. Fail wrong code without releasing.
5. Extract assignment strategy.

Parking Lot

1. Confirm compatibility and pricing.
2. Use ticket map plus free spot queues.
3. Compile enter and exit.
4. Reject double ticket use.
5. Extract pricing.

Searchable Collection

1. Ask exact/prefix/contains.
2. HashMap exact, Trie prefix.
3. Define duplicate and empty-query behavior.
4. State output-sensitive DFS complexity.
5. Add heap only for top-K.

Bookstore

1. Key by ISBN.
2. Tokenize once.
3. Store per-book frequency map.
4. Reject unknown ISBN.
5. Phrase search needs tokens, not counts.

TaskBoard

1. Map id to Task.
2. Map status to ordered ids.
3. Move updates both under one lock.
4. Enforce transition rule.
5. Do not design Jira.

Logger SOLID

1. Logger facade filters.
2. Formatter formats.
3. Sink writes.
4. Composite fans out.
5. New sink does not edit Logger.

Dog check-in/out

1. Registry, active map, history list.
2. One active stay per dog.
3. Capacity check and insert atomic.
4. Checkout closes then archives.
5. No “Amazon Pets” invention.

Historical autocomplete

1. Trie stores terms/counts.
2. Walk prefix.
3. DFS descendants.
4. Keep size-K min-heap.
5. State tie-break explicitly.

Spring login

1. Controller handles HTTP.
2. Facade chains validators.
3. Service authenticates.
4. Repository loads user.
5. Wrong password is not malformed input.

Device capabilities

1. Write three narrow interfaces.
2. Monitor gets power/display.
3. Speaker gets power/speaker.
4. Tablet gets all three.
5. Compose panel/driver; no Tablet extends Monitor.

Calculator

1. Stack additive terms.
2. Collapse multiply/divide immediately.
3. Dry-run 3+2*2=7.
4. Expr tree for extension.
5. New BinaryOp, not a growing eval switch.

Message + global logger limiter

1. Map message to last accepted time.
2. Deque global accepted times.
3. Expire old global entries.
4. Check both before mutation.
5. Not a second Rate Limiter IE.

Rate Limiter

1. Count exactly one: OA+3 Second Technical SD.
2. Say five strategies.
3. Choose token bucket.
4. Local atomic refill/decrement.
5. Redis + Lua + Redis TIME across hosts.
6. 429 + Retry-After.
7. Pick fail-open or fail-closed by endpoint.
8. Do not claim Ylogx shipped it.

Optional Login Tracker

1. Say unverified mentor-only first.
2. HashMap + DLL.
3. Repeat login moves to tail.
4. Oldest is head.next peek.
5. Do not promote it.

Final evidence and honesty locks

• Adarsh Vishwakarma; SDE I AUTA APJ; Job 10454435; ADCI Karnataka.
• Java Live Code on Zoom.
• R1 and R2 are done; OA is not a round.
• This is for R3 and a possible R4, with no format prediction.
• Job 10454435 still has no public IE naming a live-round question.
• Unnamed and paste-only prompts stay unnamed.
• Logger and dog are named AUTA OOD evidence; full Parking Lot and Trie/heap both remain prep shapes.
• Rate Limiter independent SDE I live count is exactly 1: OA+3 Second Technical SD, not UTA two-DSA.
• Per-message+global logger is not a second distributed Rate Limiter count.
• Login Tracker is unverified mentor-only.
• Spring login layers are verified as a different HM prompt.
• Do not claim Ylogx shipped a limiter; Ylogx Redis was a cache that reduced bot DB latency by 35%.
• Do not overprepare Amazon retail HLD, Kafka, or unrelated microservices for these cards.