Amazon

Take a thread dump with jstack <pid> (or jcmd <pid> Thread.print, or kill -3). The dump ends with Found one Java-level deadlock: and lists the cycle. Programmatically use ThreadMXBean.findDeadlockedThreads().

A mutex guards a critical section for one owner at a time and must be released by the thread that acquired it. A semaphore holds a count of permits, lets up to N threads in, and has no owner, so any thread may release it. A race condition is a bug where the outcome depends on the timing of unsynchronised access to shared state.

• Java mutex equivalents: synchronized or ReentrantLock. Semaphore: java.util.concurrent.Semaphore.
• A binary semaphore looks like a mutex but is not reentrant and not owner-checked.
• Typical semaphore use: cap concurrent calls to a downstream or a connection pool.

Semaphore permits = new Semaphore(3);       // at most 3 concurrent callers
void call() throws InterruptedException {
    permits.acquire();
    try { remoteCall(); } finally { permits.release(); }
}

Race example: two threads doing count++ on a shared int can lose updates because the read, add and write are not atomic; fix with AtomicInteger or a lock.

Find the middle with slow and fast pointers, reverse the second half in place, compare it with the first half, then reverse it back to restore the list. Copying into an array is O(n) space; recursion is O(n) stack.

class ListNode { int val; ListNode next; ListNode(int v) { val = v; } }

static boolean isPalindrome(ListNode head) {
    if (head == null || head.next == null) return true;
    ListNode slow = head, fast = head;
    while (fast.next != null && fast.next.next != null) { slow = slow.next; fast = fast.next.next; }
    ListNode second = reverse(slow.next);
    boolean ok = true;
    for (ListNode a = head, b = second; b != null; a = a.next, b = b.next)
        if (a.val != b.val) { ok = false; break; }
    slow.next = reverse(second); // restore
    return ok;
}
static ListNode reverse(ListNode h) {
    ListNode prev = null;
    while (h != null) { ListNode n = h.next; h.next = prev; prev = h; h = n; }
    return prev;
}

Pass an allowed (low, high) range down the recursion; every node must lie strictly inside the range inherited from all its ancestors. Checking only left.val < node.val < right.val is wrong because a deep node can violate an ancestor.

class TreeNode { int val; TreeNode left, right; TreeNode(int v) { val = v; } }

static boolean isBst(TreeNode n, long low, long high) {
    if (n == null) return true;
    if (n.val <= low || n.val >= high) return false;
    return isBst(n.left, low, n.val) && isBst(n.right, n.val, high);
}
// isBst(root, Long.MIN_VALUE, Long.MAX_VALUE)

Time O(n), space O(h). An in-order traversal being strictly increasing is an equivalent test.

Use two pointers with backtracking to the last *: on a mismatch, retry from just after the star and let the star consume one more character. This is O(nm) worst case with O(1) space; the DP table version is O(nm) space.

static boolean match(String s, String p) {
    int i = 0, j = 0, star = -1, mark = 0;
    while (i < s.length()) {
        if (j < p.length() && (p.charAt(j) == '?' || p.charAt(j) == s.charAt(i))) { i++; j++; }
        else if (j < p.length() && p.charAt(j) == '*') { star = j++; mark = i; }
        else if (star != -1) { j = star + 1; i = ++mark; }
        else return false;
    }
    while (j < p.length() && p.charAt(j) == '*') j++;
    return j == p.length();
}

match("AMBAZOKN", "AM*AZO?N*") is true; match("AMAZON", "AM*AZO?N*") is false because nothing remains for ? plus N.

Scan once while tracking the lowest price seen so far and the best profit if you sold today. O(n) time, O(1) space.

static int[] bestTrade(int[] p) {          // returns {buyDay, sellDay, profit}
    int minDay = 0, buy = 0, sell = 0, best = 0;
    for (int i = 1; i < p.length; i++) {
        if (p[i] < p[minDay]) minDay = i;
        if (p[i] - p[minDay] > best) { best = p[i] - p[minDay]; buy = minDay; sell = i; }
    }
    return new int[] { buy, sell, best };
}

For [7, 1, 5, 3, 6, 4] the result is buy day 1, sell day 4, profit 5. If prices only fall, profit is 0 and no trade is made.

Keep the current head of each list in a min-heap, repeatedly pop the smallest, append it and push its successor. Time O(N log k) for N total nodes, extra space O(k), and nodes are relinked in place.

static ListNode mergeK(List<ListNode> lists) {
    PriorityQueue<ListNode> pq = new PriorityQueue<ListNode>(Comparator.comparingInt(n -> n.val));
    for (ListNode h : lists) if (h != null) pq.add(h);
    ListNode dummy = new ListNode(0), tail = dummy;
    while (!pq.isEmpty()) {
        ListNode n = pq.poll();
        tail.next = n; tail = n;
        if (n.next != null) pq.add(n.next);
    }
    return dummy.next;
}

Scan every cell; on an unvisited 1, run a DFS that counts connected cells and marks them visited. Each cell is visited once: O(rows*cols) time.

static int largestIsland(int[][] g) {
    int best = 0;
    for (int r = 0; r < g.length; r++)
        for (int c = 0; c < g[0].length; c++)
            if (g[r][c] == 1) best = Math.max(best, dfs(g, r, c));
    return best;
}
static int dfs(int[][] g, int r, int c) {
    if (r < 0 || c < 0 || r >= g.length || c >= g[0].length || g[r][c] != 1) return 0;
    g[r][c] = 2; // visited
    return 1 + dfs(g, r + 1, c) + dfs(g, r - 1, c) + dfs(g, r, c + 1) + dfs(g, r, c - 1);
}

dp[i] is true if the first i characters can be segmented; it is true when some j < i has dp[j] true and s[j..i) is in the dictionary. A trie on its own does not solve it, because greedy longest-match fails.

static boolean wordBreak(String s, Set<String> dict) {
    boolean[] dp = new boolean[s.length() + 1];
    dp[0] = true;
    for (int i = 1; i <= s.length(); i++)
        for (int j = 0; j < i; j++)
            if (dp[j] && dict.contains(s.substring(j, i))) { dp[i] = true; break; }
    return dp[s.length()];
}

wordBreak("applepenapple", Set.of("apple", "pen")) is true. Cost is O(n^2) substring checks; bound j by the longest dictionary word to cut it down.

Store values in an ArrayList for O(1) random access, and a HashMap from value to index. To delete, swap the target with the last element, update that element's index, then remove the tail.

class RandomizedSet {
    private final List<Integer> vals = new ArrayList<>();
    private final Map<Integer, Integer> pos = new HashMap<>();
    private final Random rnd = new Random();

    boolean insert(int v) {
        if (pos.containsKey(v)) return false;
        pos.put(v, vals.size()); vals.add(v); return true;
    }
    boolean remove(int v) {
        Integer i = pos.remove(v);
        if (i == null) return false;
        int last = vals.remove(vals.size() - 1);
        if (i < vals.size()) { vals.set(i, last); pos.put(last, i); }
        return true;
    }
    int getRandom() { return vals.get(rnd.nextInt(vals.size())); }
}

Composite indexes are sorted by a, then b within a, then c. The leftmost-prefix rule says the index is usable efficiently only for a prefix of the columns.

• a=1: yes, full use.
• b=2: not as an efficient seek (MySQL cannot; PostgreSQL may do a full index scan, MySQL 8.0 has skip scan in limited cases).
• a=1 AND c=3: seeks on a, then c is only filtered inside the range of a (an index condition, not a seek).
• a=1 AND b>5 AND c=3: seeks on a and range on b; c cannot narrow the range because after a range predicate the following columns are not sorted contiguously.

Rule of thumb: equality columns first, then the range or sort column, in order of selectivity and query frequency.

CREATE INDEX idx_orders_cust_status_created ON orders (customer_id, status, created_at);

Combine a hash map for lookup with a doubly linked list for recency order; both get and put are O(1). In Java, LinkedHashMap with access order does this in a few lines.

class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;
    LRUCache(int capacity) { super(16, 0.75f, true); this.capacity = capacity; }
    @Override protected boolean removeEldestEntry(Map.Entry<K, V> e) { return size() > capacity; }
}

• Interviewers often want the manual version: Map<K, Node> plus head/tail sentinels; get moves the node to head, put evicts tail when full.
• Not thread-safe; wrap with Collections.synchronizedMap or a lock (even get mutates order).

Model City -> Theatre -> Screen -> Show -> ShowSeat, with seat status AVAILABLE/LOCKED/BOOKED; locking a seat with a TTL during payment prevents double booking.

• Entities: Movie, Theatre, Screen, Show, Seat, ShowSeat (per show state), Booking, Payment.
• Flow: search shows, pick seats, lockSeats (all or nothing), pay, confirm; unpaid locks expire.
• Lock acquisition must be atomic across multiple seats; sort seat ids and lock in order to avoid deadlock.

class ShowSeat {
    enum S { AVAILABLE, LOCKED, BOOKED }
    S status = S.AVAILABLE; Instant lockedUntil;
    synchronized boolean tryLock(Instant now, Duration ttl) {
        if (status == S.LOCKED && now.isAfter(lockedUntil)) status = S.AVAILABLE;
        if (status != S.AVAILABLE) return false;
        status = S.LOCKED; lockedUntil = now.plus(ttl); return true;
    }
}

• If locking seat 3 of 4 fails, release 1-2 (rollback). In the distributed version this is a DB row update with WHERE status='AVAILABLE' or a Redis lock with TTL.

Model Board with a jump map (snake heads and ladder bottoms to destinations), Dice, Player and a Game loop with turn queue.

• Setup: 100 cells; validate no cell is both a snake head and ladder start and that no snake ends beyond start loops.
• Turn: roll dice, if pos + roll > 100 stay; else move, apply jump once (and follow chains if rules say so); win when exactly 100.
• Extensibility: Dice interface (one/two dice, loaded dice for tests), configurable board size and win rules.

class Board {
    private final int size; private final Map<Integer, Integer> jumps;
    Board(int size, Map<Integer, Integer> jumps){ this.size = size; this.jumps = jumps; }
    int next(int pos, int roll) {
        int p = pos + roll;
        if (p > size) return pos;
        return jumps.getOrDefault(p, p);
    }
}

• Use ArrayDeque<Player>: poll, play, offer back unless won.

RideService finds nearby available drivers via a MatchingStrategy, offers the trip, and drives a Trip through states REQUESTED, ACCEPTED, STARTED, COMPLETED/CANCELLED; FareStrategy computes the price.

• Entities: Rider, Driver (location, status), Cab, Trip, Location, Payment.
• Matching: nearest available driver by haversine distance (or a geo-grid index); offer sequentially with a timeout.
• Concurrency: marking a driver unavailable must be atomic so two riders do not claim him (compareAndSet on status).
• Fare: base + per-km + per-minute, times surge multiplier from SurgeStrategy.

class Driver {
    private final AtomicReference<Status> status = new AtomicReference<>(Status.AVAILABLE);
    boolean tryReserve() { return status.compareAndSet(Status.AVAILABLE, Status.RESERVED); }
    void release() { status.set(Status.AVAILABLE); }
}
interface MatchingStrategy { Optional<Driver> match(Location pickup, Collection<Driver> candidates); }

Model Room(id, capacity), Booking(room, start, end, organizer) and a BookingService that picks a free room using a pluggable strategy. The core is a per-room, overlap-free interval set; use half-open intervals [start, end) so back-to-back meetings do not clash.

• A TreeMap<start, end> per room checks overlap in O(log n): look at the booking starting at or before start and the one starting at or after it.
• Room selection is a Strategy (smallest room that fits, first available, closest floor).
• Protect each room with its own lock so bookings in different rooms run in parallel; for multiple instances use a database exclusion constraint or a unique slot row.

class Room {
    final String id; final int capacity;
    private final TreeMap<Instant, Instant> booked = new TreeMap<>(); // start -> end
    Room(String id, int capacity) { this.id = id; this.capacity = capacity; }

    synchronized boolean book(Instant s, Instant e) {
        if (!s.isBefore(e)) throw new IllegalArgumentException("start must be before end");
        var before = booked.floorEntry(s);
        var after = booked.ceilingEntry(s);
        if (before != null && before.getValue().isAfter(s)) return false;
        if (after != null && after.getKey().isBefore(e)) return false;
        booked.put(s, e);
        return true;
    }
}

Use fan-out on write (push) for normal users, precomputing each follower's feed in a cache, and fan-out on read (pull) for celebrities; merge at read time.

• Requirements: post, follow, home timeline (reverse chronological or ranked), low-latency reads (<200 ms), eventual consistency acceptable.
• Estimates: 300M DAU, 5 reads/day per user-session x 10 = 1.5B timeline reads/day (17K/s avg, 50K peak); 100M posts/day (1.2K/s). Average 200 followers means 240K feed inserts/s.
• API: POST /v1/posts, GET /v1/feed?cursor=; cursor-based pagination.
• Data model: posts(post_id, user_id, text, media_url, ts), follows(follower, followee), feed cache feed:{userId} as a Redis sorted set of post ids (cap 800).

Post API -> Post DB -> Kafka(post-created) -> Fanout Workers -> Redis feed:{follower}
Feed API -> Redis feed (ids) -> Post Cache/DB (hydrate) ; + celebrity posts pulled & merged

• Hybrid: skip fan-out for accounts with >1M followers; at read time merge the cached feed with recent posts of followed celebrities.
• Ranking: candidate generation then ML scoring; keep the pipeline separate from storage.
• Trade-offs: push gives fast reads but heavy writes and wasted work for inactive users (fan-out only to active users); pull is cheap on write but slow on read.
• Failure modes: cache loss rebuilt from follows + posts; fan-out lag means a delayed post appears (acceptable); deleted posts filtered on hydration.