Company-02-Amazon

Amazon Interview Prep

Interview Profile

• Format: 5–7 rounds — typically 2–3 coding rounds, 1 system design, 1 bar raiser, 1–2 behavioral/LP rounds
• Leadership Principles weight: At senior level, LPs are evaluated as heavily as code correctness. A perfect solution with no LP story can still fail the bar raiser.
• Coding difficulty: Medium — Amazon rarely asks Hard-level trick problems. The bar is clean decomposition, readable variable names, and walking through edge cases out loud.
• What Amazon cares about: “Customer Obsession” in framing (who is the customer of this API?), scalability of design choices, and the ability to walk through past decisions in large-scale systems with specifics (“we served X QPS, we chose Y because of Z tradeoff”).

---

Pattern Frequency Breakdown

Pattern	Estimated Frequency	Notes
Graphs / Trees	25%	Dependency graphs, catalog trees, org charts
Heap / Priority Queue	20%	Top-K, scheduling, stream processing
Dynamic Programming	20%	Knapsack variants, job scheduling, pricing
Greedy / Intervals	15%	Fulfillment scheduling, resource allocation
Sliding Window / Arrays	10%	Metrics aggregation, fraud detection windows
Backtracking	10%	Cart/combination problems, config generation

---

Problems From This Repo

Problem	Why Amazon Asks It
[[Session-07-Heap|Kth Largest Element (LC 215)]]	Order ranking, top-K products in a catalog; appears in recommendation and search-ranking pipelines
[[Session-07-Heap|Task Scheduler (LC 621)]]	Lambda scheduling, EC2 task management — cooling-period constraint maps to resource cooldown in fleet management
[[Session-07-Heap|Merge K Sorted Lists (LC 23)]]	Merging delivery streams from K fulfillment centers into a single timeline; multi-source log merge
[[Session-12-Greedy|Meeting Rooms II (LC 253)]]	Fulfillment center shift scheduling; minimum number of loading docks (resources) for overlapping delivery windows
[[Session-08-Graphs|Course Schedule (LC 207)]]	Package dependency graph; detecting circular dependencies in a service mesh or build DAG
[[Session-14-AdvancedGraphs|Cheapest Flights Within K Stops (LC 787)]]	Delivery route cost optimization with a hop-count budget; multi-carrier shipping cost minimization
[[Session-09-DP1D|Coin Change (LC 322)]]	Pricing denomination problems; gift card denomination covering, AWS credit rounding
[[Session-11-Backtracking|Combination Sum (LC 39)]]	Cart combination pricing; finding all bundles that hit a target promo price
[[Session-04-HashMap|Top K Frequent Elements (LC 347)]]	Top products by search frequency; search-suggestion ranking in A9/OpenSearch
[[Session-12-Greedy|Jump Game (LC 55)]]	Reachability reasoning; can a delivery reach its destination given fuel constraints per leg

---

New Problems (Amazon-Specific)

1. LC 146 — LRU Cache (Medium)

Link: LeetCode 146

Quick Summary: Design a data structure that supports get(key) and put(key, value) in O(1), evicting the least-recently-used entry when capacity is exceeded.

Industry Context: Amazon ElastiCache (Redis/Memcached) eviction policy; session-data caches behind API Gateway; product-detail page caches in the retail catalog service. Senior candidates are expected to know when LRU fails (sequential scan “cache pollution”) and the existence of LFU and 2Q (two-queue) as alternatives.

Key Insight: Combine a HashMap<key, DLL node> for O(1) lookup with a doubly-linked list for O(1) move-to-front and O(1) tail eviction. The head sentinel and tail sentinel eliminate all null checks.

Approach 1: Brute Force — LinkedHashMap one-liner

// Time: O(1) amortized  Space: O(capacity)
import java.util.LinkedHashMap;
import java.util.Map;
 
class LRUCacheBrute {
    private final int capacity;
    private final LinkedHashMap<Integer, Integer> map;
 
    public LRUCacheBrute(int capacity) {
        this.capacity = capacity;
        // accessOrder=true keeps most-recently-used at tail
        this.map = new LinkedHashMap<>(capacity, 0.75f, true) {
            @Override
            protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
                return size() > capacity;
            }
        };
    }
 
    public int get(int key) {
        return map.getOrDefault(key, -1);   // O(1) — also updates access order
    }
 
    public void put(int key, int value) {
        map.put(key, value);                // O(1) — evicts if over capacity
    }
}

• Time: O(1) amortized for both operations
• Space: O(capacity)
• Tradeoff: Works in production Java, but interviewers expect you to implement the underlying DLL manually. Use this as a “here’s how I’d ship it in 5 minutes” opening, then offer to implement from scratch.

Approach 2: Optimal — HashMap + Doubly-Linked List

// Time: O(1) for get and put  Space: O(capacity)
class LRUCache {
 
    private static class Node {
        int key, val;
        Node prev, next;
        Node(int k, int v) { key = k; val = v; }
    }
 
    private final int capacity;
    private final Map<Integer, Node> cache = new HashMap<>();
    // Sentinels: head = MRU end, tail = LRU end
    private final Node head = new Node(0, 0);  // dummy MRU sentinel
    private final Node tail = new Node(0, 0);  // dummy LRU sentinel
 
    public LRUCache(int capacity) {
        this.capacity = capacity;
        head.next = tail;
        tail.prev = head;
    }
 
    public int get(int key) {                  // O(1)
        if (!cache.containsKey(key)) return -1;
        Node node = cache.get(key);
        moveToFront(node);
        return node.val;
    }
 
    public void put(int key, int value) {      // O(1)
        if (cache.containsKey(key)) {
            Node node = cache.get(key);
            node.val = value;
            moveToFront(node);
        } else {
            if (cache.size() == capacity) {
                Node lru = tail.prev;          // evict LRU node
                remove(lru);
                cache.remove(lru.key);
            }
            Node node = new Node(key, value);
            cache.put(key, node);
            insertAtFront(node);
        }
    }
 
    private void remove(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
 
    private void insertAtFront(Node node) {
        node.next = head.next;
        node.prev = head;
        head.next.prev = node;
        head.next = node;
    }
 
    private void moveToFront(Node node) {
        remove(node);
        insertAtFront(node);
    }
}

• Time: O(1) for both get and put
• Space: O(capacity) — map + DLL each hold at most capacity entries
• Senior talking points:
  • When does LRU fail? Sequential scans (e.g., a full-table scan) poison the cache with single-use pages, evicting frequently-used entries. Redis calls this “LRU approximation” and uses a probabilistic sample-based eviction to avoid exact LRU overhead.
  • LFU alternative: tracks frequency, not recency — better for Zipfian access distributions. More complex: requires a frequency bucket map.
  • 2Q (two-queue): A1 (new entries, FIFO) + Am (promoted entries, LRU). Entries must be accessed twice before promotion — solves scan pollution.

---

2. LC 588 — Design In-Memory File System (Hard)

Link: LeetCode 588

Quick Summary: Implement ls, mkdir, addContentToFile, and readContentFromFile on a tree-structured in-memory filesystem.

Industry Context: Amazon S3 object key namespace (prefix-based “directory” simulation), EFS directory trees, and the AWS Console directory browser. Senior bar: path normalization, concurrent read/write discussion, and how you’d shard a large directory namespace.

Key Insight: A Trie where each node represents a directory — Map<String, TrieNode> children for subdirectories and a String content field for file content. Split the path on /, skip empty tokens, and navigate/create nodes incrementally.

Approach 1: HashMap of full paths (naive)

// Time: O(L) per op where L = path length  Space: O(total content)
class FileSystemNaive {
    private final Map<String, String> files = new HashMap<>();
    private final Set<String> dirs = new TreeSet<>();
 
    public FileSystemNaive() {
        dirs.add("/");
    }
 
    public List<String> ls(String path) {              // O(N) — scans all keys
        List<String> result = new ArrayList<>();
        if (files.containsKey(path)) {
            // It's a file — return just its name
            result.add(path.substring(path.lastIndexOf('/') + 1));
            return result;
        }
        String prefix = path.equals("/") ? "/" : path + "/";
        for (String dir : dirs) {
            if (dir.startsWith(prefix)) {
                String remaining = dir.substring(prefix.length());
                if (!remaining.isEmpty() && !remaining.contains("/"))
                    result.add(remaining);
            }
        }
        for (String file : files.keySet()) {
            if (file.startsWith(prefix)) {
                String remaining = file.substring(prefix.length());
                if (!remaining.isEmpty() && !remaining.contains("/"))
                    result.add(remaining);
            }
        }
        Collections.sort(result);
        return result;
    }
 
    public void mkdir(String path) { dirs.add(path); }
 
    public void addContentToFile(String filePath, String content) {
        files.merge(filePath, content, String::concat);
        // ensure parent dirs exist
        String[] parts = filePath.split("/");
        StringBuilder sb = new StringBuilder();
        for (int i = 1; i < parts.length - 1; i++) {
            sb.append("/").append(parts[i]);
            dirs.add(sb.toString());
        }
    }
 
    public String readContentFromFile(String filePath) {
        return files.getOrDefault(filePath, "");
    }
}

• Time: O(N) for ls — scans all stored paths; O(L) for others
• Space: O(total keys + content)
• Tradeoff: Easy to reason about but ls degrades as the namespace grows.

Approach 2: Optimal — Trie with per-node children map

// Time: O(L + K log K) for ls, O(L) for others  Space: O(total chars)
// L = path length, K = number of children at the listed directory
class FileSystem {
 
    private static class TrieNode {
        Map<String, TrieNode> children = new TreeMap<>();  // TreeMap keeps sorted order
        String fileContent = "";          // non-empty only for files
        boolean isFile = false;
    }
 
    private final TrieNode root = new TrieNode();
 
    private TrieNode navigate(String path) {
        TrieNode cur = root;
        for (String part : path.split("/")) {
            if (part.isEmpty()) continue;                  // skip leading ""
            cur = cur.children.computeIfAbsent(part, k -> new TrieNode());
        }
        return cur;
    }
 
    public List<String> ls(String path) {                  // O(L + K log K)
        TrieNode node = navigate(path);
        if (node.isFile) {
            // path points to a file — return just the filename
            String name = path.substring(path.lastIndexOf('/') + 1);
            return Collections.singletonList(name);
        }
        return new ArrayList<>(node.children.keySet());    // TreeMap already sorted
    }
 
    public void mkdir(String path) {                       // O(L)
        navigate(path);
    }
 
    public void addContentToFile(String filePath, String content) {  // O(L)
        TrieNode node = navigate(filePath);
        node.isFile = true;
        node.fileContent += content;
    }
 
    public String readContentFromFile(String filePath) {   // O(L)
        return navigate(filePath).fileContent;
    }
}

• Time: O(L) for mkdir/read/write; O(L + K log K) for ls where K = children count
• Space: O(total characters across all paths + file content)
• Senior talking points:
  • Path normalization: handle trailing slashes, . and .. segments — in production this is a security boundary (path traversal attacks).
  • Concurrent access: read-write lock on each TrieNode for fine-grained concurrency, or a global ReadWriteLock for simplicity. Inode-level locking is how ext4 and APFS handle this.
  • Sharding: partition the Trie by top-level directory (bucket/prefix) across nodes — this is how S3’s key namespace is internally partitioned.

---

3. LC 332 — Reconstruct Itinerary (Medium/Hard)

Link: LeetCode 332

Quick Summary: Given a list of airline tickets [from, to], reconstruct the itinerary using all tickets starting from “JFK” in lexicographically smallest order.

Industry Context: Amazon supply chain routing — find an Eulerian path through a delivery network that visits every route exactly once. Also: audit log reconstruction (replay all events in order), workflow DAG execution ordering.

Key Insight: Hierholzer’s algorithm for Eulerian path — DFS with post-order appending. Use PriorityQueue (min-heap) for neighbors to get lexicographic order. The post-order trick: a node is added to the result after all its outgoing edges are consumed, then reverse at the end.

Approach 1: Brute Force — backtracking

// Time: O(E! / k) worst case  Space: O(E)
// E = number of tickets; k = branching factor
class ReconstructItineraryBrute {
    private List<String> result;
    private Map<String, List<String>> graph;
 
    public List<String> findItinerary(List<List<String>> tickets) {
        graph = new HashMap<>();
        for (List<String> t : tickets)
            graph.computeIfAbsent(t.get(0), k -> new ArrayList<>()).add(t.get(1));
        for (String key : graph.keySet()) Collections.sort(graph.get(key));
 
        result = new ArrayList<>();
        result.add("JFK");
        backtrack("JFK", tickets.size() + 1);
        return result;
    }
 
    private boolean backtrack(String airport, int totalStops) {
        if (result.size() == totalStops) return true;
        List<String> neighbors = graph.getOrDefault(airport, new ArrayList<>());
        for (int i = 0; i < neighbors.size(); i++) {
            String next = neighbors.remove(i);
            result.add(next);
            if (backtrack(next, totalStops)) return true;
            result.remove(result.size() - 1);
            neighbors.add(i, next);
        }
        return false;
    }
}

• Time: O(E! / k) — exponential backtracking
• Space: O(E) recursion depth
• Tradeoff: Correct but impractical for large inputs. Use this to demonstrate you understand why Hierholzer is needed.

Approach 2: Optimal — Hierholzer’s Eulerian path (DFS post-order)

// Time: O(E log E)  Space: O(E)  — log E per edge from heap operations
import java.util.*;
 
class ReconstructItinerary {
    private final Map<String, PriorityQueue<String>> graph = new HashMap<>();
    private final LinkedList<String> result = new LinkedList<>();
 
    public List<String> findItinerary(List<List<String>> tickets) {
        for (List<String> ticket : tickets)
            graph.computeIfAbsent(ticket.get(0), k -> new PriorityQueue<>())
                 .offer(ticket.get(1));
        dfs("JFK");
        return result;
    }
 
    private void dfs(String airport) {
        PriorityQueue<String> neighbors = graph.get(airport);
        while (neighbors != null && !neighbors.isEmpty()) {
            dfs(neighbors.poll());                // consume edge first
        }
        result.addFirst(airport);                 // post-order: add AFTER all edges used
    }
}

• Time: O(E log E) — each of E edges polled from heap once; heap op is O(log E)
• Space: O(E) — graph storage + recursion stack depth = E in worst case
• Key Insight: Post-order insertion is the entire trick. If you add the airport to result before recursing, you get the wrong order for graphs with dead ends. Post-order means: “I only commit this node to the itinerary after I’ve exhausted all places it can go.” Reversing (or addFirst) restores flight order. This is a classic interview differentiator — most candidates know DFS but few know Hierholzer’s post-order formulation.
• Senior talking point: Eulerian path exists iff at most one node has out - in = 1 (start) and at most one has in - out = 1 (end); all others have equal in/out. Verifying this upfront is good defensive coding in production.

---

4. LC 1235 — Maximum Profit in Job Scheduling (Hard)

Link: LeetCode 1235

Quick Summary: Given jobs with startTime, endTime, and profit, select non-overlapping jobs to maximize total profit.

Industry Context: AWS Spot Instance bid scheduling — maximize revenue from non-overlapping compute reservations. Worker shift optimization in Amazon fulfillment centers — maximize throughput given shift overlap constraints.

Key Insight: Sort jobs by end time. DP where dp[i] = max profit considering first i jobs. For each job i, use binary search to find the latest job j that ends before job i starts — then dp[i] = max(dp[i-1], dp[j] + profit[i]).

Approach 1: Brute Force — recursive with memoization

// Time: O(n²)  Space: O(n)
class JobSchedulingBrute {
    public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
        int n = startTime.length;
        int[][] jobs = new int[n][3];
        for (int i = 0; i < n; i++) jobs[i] = new int[]{startTime[i], endTime[i], profit[i]};
        Arrays.sort(jobs, (a, b) -> a[1] - b[1]);         // sort by end time
 
        int[] memo = new int[n + 1];
        Arrays.fill(memo, -1);
        return solve(jobs, 0, memo);
    }
 
    private int solve(int[][] jobs, int idx, int[] memo) {
        if (idx == jobs.length) return 0;
        if (memo[idx] != -1) return memo[idx];
 
        // Option 1: skip job idx
        int skip = solve(jobs, idx + 1, memo);
 
        // Option 2: take job idx — linear scan for next compatible job
        int nextIdx = idx + 1;
        while (nextIdx < jobs.length && jobs[nextIdx][0] < jobs[idx][1]) nextIdx++;
        int take = jobs[idx][2] + solve(jobs, nextIdx, memo);
 
        return memo[idx] = Math.max(skip, take);
    }
}

• Time: O(n²) — linear scan for next compatible job per state
• Space: O(n) memo array

Approach 2: Optimal — DP + Binary Search

// Time: O(n log n)  Space: O(n)
class JobScheduling {
    public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
        int n = startTime.length;
        int[][] jobs = new int[n][3];
        for (int i = 0; i < n; i++) jobs[i] = new int[]{endTime[i], startTime[i], profit[i]};
        Arrays.sort(jobs, (a, b) -> a[0] - b[0]);         // sort by end time
 
        // dp[i] = max profit using only first i jobs (1-indexed)
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            int end   = jobs[i - 1][0];
            int start = jobs[i - 1][1];
            int p     = jobs[i - 1][2];
 
            // Binary search: largest j where jobs[j-1].endTime <= start
            int lo = 0, hi = i - 1;
            while (lo < hi) {
                int mid = (lo + hi + 1) / 2;
                if (jobs[mid - 1][0] <= start) lo = mid;
                else hi = mid - 1;
            }
            // dp[i] = max(skip job i, take job i + best before it starts)
            dp[i] = Math.max(dp[i - 1], dp[lo] + p);
        }
        return dp[n];
    }
}

• Time: O(n log n) — sort + binary search per job
• Space: O(n) dp array
• Key Insight: The DP transition dp[i] = max(dp[i-1], dp[latestNonOverlap] + profit[i]) is the weighted interval scheduling recurrence. The binary search replaces an O(n) linear scan, giving the log factor. Sort by end time (not start time) so that dp[j] always represents a consistent “best before time T” prefix.
• Senior talking point: This problem class (weighted interval scheduling) is the theoretical basis for all reservation/scheduling systems. The unweighted version (Meeting Rooms II, LC 253) is solvable greedily; the weighted version requires DP+BS. Knowing when greedy suffices vs. when DP is needed is an explicit Amazon senior bar signal.

---

5. LC 480 — Sliding Window Median (Hard)

Link: LeetCode 480

Quick Summary: Given an array and window size k, return the median of each window as it slides one position at a time.

Industry Context: Real-time order value median for fraud detection at Amazon Pay — a sliding window over the last K transactions. Extends Find Median from Data Stream (LC 295) (in repo) by adding the critical complexity of evicting the element leaving the window.

Key Insight: Two heaps (max-heap for lower half, min-heap for upper half) as in LC 295, plus lazy deletion — when the outgoing element is removed, mark it in a HashMap<Integer, Integer> as “pending delete” and decrement effective sizes. Rebalance heaps when the lazy-deleted element surfaces at the top.

Approach 1: Brute Force — re-sort each window

// Time: O(n * k log k)  Space: O(k)
class SlidingWindowMedianBrute {
    public double[] medianSlidingWindow(int[] nums, int k) {
        double[] result = new double[nums.length - k + 1];
        int[] window = new int[k];
        for (int i = 0; i <= nums.length - k; i++) {
            System.arraycopy(nums, i, window, 0, k);
            Arrays.sort(window);
            result[i] = k % 2 == 0
                ? ((double) window[k / 2 - 1] + window[k / 2]) / 2.0
                : window[k / 2];
        }
        return result;
    }
}

• Time: O(n · k log k) — sort per window
• Space: O(k)
• Tradeoff: Acceptable for small k; interviewer will ask you to optimize.

Approach 2: Optimal — Two Heaps with Lazy Deletion

// Time: O(n log k)  Space: O(k)
import java.util.*;
 
class SlidingWindowMedian {
    // maxHeap = lower half (negated for max behavior using PriorityQueue min-heap)
    private final PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
    // minHeap = upper half
    private final PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    // lazy deletion map: element -> count of pending removals
    private final Map<Integer, Integer> lazy = new HashMap<>();
    private int maxSize = 0, minSize = 0;  // effective sizes
 
    public double[] medianSlidingWindow(int[] nums, int k) {
        double[] result = new double[nums.length - k + 1];
 
        // Initialize first window
        for (int i = 0; i < k; i++) addNum(nums[i]);
        result[0] = getMedian(k);
 
        for (int i = k; i < nums.length; i++) {
            int outgoing = nums[i - k];
            int incoming = nums[i];
 
            // Lazy-mark outgoing element
            lazy.merge(outgoing, 1, Integer::sum);
            if (outgoing <= maxHeap.peek()) maxSize--;   // was in lower half
            else minSize--;                               // was in upper half
 
            // Add incoming
            addNum(incoming);
            // Rebalance
            rebalance();
            // Purge lazily deleted tops before reading median
            purgeLazy();
            result[i - k + 1] = getMedian(k);
        }
        return result;
    }
 
    private void addNum(int num) {
        if (maxHeap.isEmpty() || num <= maxHeap.peek()) {
            maxHeap.offer(num);
            maxSize++;
        } else {
            minHeap.offer(num);
            minSize++;
        }
        rebalance();
    }
 
    private void rebalance() {
        // Keep: maxSize == minSize or maxSize == minSize + 1
        while (maxSize > minSize + 1) {
            minHeap.offer(maxHeap.poll());
            maxSize--; minSize++;
            purgeLazy();
        }
        while (minSize > maxSize) {
            maxHeap.offer(minHeap.poll());
            minSize--; maxSize++;
            purgeLazy();
        }
    }
 
    private void purgeLazy() {
        // Remove lazily-deleted elements from heap tops
        while (!maxHeap.isEmpty() && lazy.getOrDefault(maxHeap.peek(), 0) > 0) {
            lazy.merge(maxHeap.poll(), -1, Integer::sum);
        }
        while (!minHeap.isEmpty() && lazy.getOrDefault(minHeap.peek(), 0) > 0) {
            lazy.merge(minHeap.poll(), -1, Integer::sum);
        }
    }
 
    private double getMedian(int k) {
        return k % 2 == 0
            ? ((double) maxHeap.peek() + minHeap.peek()) / 2.0
            : maxHeap.peek();
    }
}

• Time: O(n log k) — each element inserted and removed from heap at most once
• Space: O(k) — heaps + lazy map bounded by window size
• Key Insight: Lazy deletion avoids the O(k) removal cost of searching within a heap. The “pending delete” counter means we defer the actual removal until the element happens to float to the top during a future poll. This is the same trick used in some priority-queue based Dijkstra implementations when you can’t efficiently decrease-key.
• Senior talking point: Overflow risk — computing (a + b) / 2.0 can overflow when a and b are Integer.MAX_VALUE. Cast to long or double before adding.

---

Leadership Principle Connections

Problem	Primary LP	Secondary LP	Senior Framing
LRU Cache (LC 146)	Frugality	Customer Obsession	”We chose LRU over LFU to minimize memory overhead; LFU requires an extra frequency map — complexity we didn’t need at our access pattern distribution”
In-Memory File System (LC 588)	Think Big	Dive Deep	”S3 simulates directories via prefix keys; the Trie structure mirrors how we’d shard namespace prefixes across shards for horizontal scaling”
Reconstruct Itinerary (LC 332)	Are Right, A Lot	Deliver Results	”Post-order DFS was non-obvious; I validated it on a dead-end graph before trusting it — correctness first, then optimize”
Job Scheduling (LC 1235)	Dive Deep	Deliver Results	”Greedy was my first instinct; I recognized the weighted case breaks greedy and shifted to DP+BS — articulating why greedy fails is the bar-raiser moment”
Sliding Window Median (LC 480)	Invent and Simplify	Customer Obsession	”Lazy deletion keeps the fraud-detection pipeline at O(n log k) without a specialized data structure — we could ship this with standard Java PriorityQueue”
Top K Frequent (LC 347)	Customer Obsession	Bias for Action	”A9 search suggestions require top-K by frequency in real time; bucket sort gives O(n) — explain the space vs. heap tradeoff”
Meeting Rooms II (LC 253)	Frugality	Earn Trust	”Minimum resources to handle peak overlap — same math as minimum number of checkout lanes or loading docks”

---

System Design Connections

Pattern	System Design Problem	Amazon Mapping
LRU / LFU Cache	Distributed Cache Design	ElastiCache eviction policies; DAX (DynamoDB Accelerator) cache warming
Trie (File System)	Object Storage Namespace	S3 key prefix partitioning; prefix-based IAM policy matching
Eulerian Path	Supply Chain Route Planning	Last-mile delivery route covering every stop exactly once
Weighted Interval DP	Spot Instance Scheduling	Bid-based reservation maximizing compute revenue
Two Heaps + Sliding Window	Real-Time Metrics Service	CloudWatch percentile metrics (p50, p95, p99) over rolling windows
Graph Topological Sort	Build/Deploy Dependency	CodeBuild pipeline DAG; Lambda layer dependency resolution

---

2-Week Sprint Plan

Day	Focus	Problems
1	Heap warm-up	LC 215, LC 295 (from repo)
2	Heap — scheduling	LC 621, LC 23 (from repo)
3	LRU Cache	LC 146 (this sheet)
4	Graph — dependency	LC 207 (from repo), LC 332 (this sheet)
5	DP 1D	LC 322 (from repo), LC 1235 (this sheet)
6	Sliding Window Hard	LC 480 (this sheet)
7	File System Design	LC 588 (this sheet) + system design sketch
8	Greedy + Intervals	LC 253, LC 55 (from repo)
9	Backtracking	LC 39, LC 347 (from repo)
10	Graphs — routing	LC 787 (from repo)
11	Mock coding round 1	2 medium problems timed (45 min)
12	Leadership Principle stories	Map 3 past projects to LP table above
13	Mock coding round 2	1 medium + 1 hard (60 min)
14	System design mock	Design Amazon order tracking service

---

Senior-Level Talking Points

On Clean Code (what Amazon’s bar raiser listens for)

• Name variables after the domain, not the data structure: deliveryWindows not intervals, productRankHeap not pq.
• State assumptions explicitly before coding: “I’m assuming all ticket endpoints are valid IATA codes and no duplicate tickets” — this signals “Earn Trust” and prevents misaligned solutions.
• Offer complexity before being asked: “This is O(n log k) time and O(k) space — the log factor is from the heap, which is acceptable for our k ≤ 10,000 window size.”

On System Design Integration

• LRU Cache → lead into “how would you make this distributed?” (consistent hashing, node failure eviction consistency)
• Interval Scheduling → “how would you handle priority ties in the fulfillment center?” (secondary sort by profit, then by duration)
• File System → “how would you handle concurrent writes to the same file path?” (optimistic locking with CAS, inode-level version vectors)

On Leadership Principles in Code Reviews

• “Frugality”: justify every data structure as the minimum required — don’t use a TreeMap when a HashMap suffices.
• “Dive Deep”: for any O(n log n) solution, know the O(n) alternative and when it’s applicable (e.g., counting sort vs. comparison sort for bounded values).
• “Bias for Action”: write a working brute-force first, then optimize — shows you can ship incrementally.