You are asked to solve two independent coding problems in this session, each followed by a short discussion. This mirrors a 60-minute Amazon SDE coding round: implement a correct, efficient solution, then walk through complexity and edge cases. ### Constraints & Assumptions - **Problem 1 (LRU Cache):** `1 <= capacity`. Keys and values are integers. `get` and `put` are each called many times (assume up to ~$10^5$ operations), so both must run in $O(1)$ average time — a per-operation linear scan will not pass. - **Problem 2 (Connected Groups):** `1 <= n`; nodes are labeled `0` to `n - 1`. `edges[i] = [a, b]` is undirected, `0 <= a, b < n`. The graph may contain self-loops, duplicate edges, and isolated nodes. Assume up to ~$10^5$ nodes and edges. - Single-threaded; you do not need to make either structure thread-safe unless the interviewer asks. ### Part 1: Implement an LRU Cache Design a fixed-capacity **least-recently-used** cache supporting these operations, each in $O(1)$ average time: - `LRUCache(int capacity)`: initialize the cache with a positive capacity. - `int get(int key)`: return the value for `key` if present, else `-1`. A successful `get` marks `key` as the **most recently used** item. - `void put(int key, int value)`: insert or update `key`. If inserting a new key would exceed `capacity`, **evict the least recently used** key first. A `put` also marks `key` as most recently used. ```hint Two structures together No single built-in structure gives you both $O(1)$ keyed lookup *and* $O(1)$ recency reordering. Combine one structure for lookup with another for ordering. ``` ```hint Ordering structure For the recency side, you need a structure that lets you detach an arbitrary element and re-insert it at one end in $O(1)$ — *provided* you already hold a reference to it. Think about which linked structure supports $O(1)$ removal from the middle, and how the lookup structure could hand you that reference directly. ``` ```hint Edge cases to handle Updating an existing key (move, don't duplicate); evicting only when a *new* key overflows capacity; using sentinel head/tail dummy nodes to avoid null checks on every splice. ``` ### Part 2: Count Connected Groups in an Undirected Graph Given an integer `n` (nodes labeled `0` to `n - 1`) and a list of undirected `edges`, return the number of connected components. Isolated nodes count as their own group. ```text Input: n = 5, edges = [[0,1], [1,2], [3,4]] Output: 2 Explanation: Nodes {0,1,2} form one group, and nodes {3,4} form another. ``` ```hint How do you count "reachable groups"? There are two classic families here: one explores the graph directly and counts how many separate explorations it takes to cover every node; the other incrementally merges nodes as you process edges and asks how many independent clusters remain. Decide which fits before committing to data structures. ``` ```hint Why isolated nodes matter A node with no edges is still a component. Initialize as if every node is its own group, then merge — don't only iterate over endpoints that appear in `edges`. ``` ### Clarifying Questions to Ask - For the LRU cache, can `capacity` be `0`, or is it guaranteed positive? Are keys/values always non-negative? - On a `put` that updates an existing key, should it count as a "use" that refreshes recency? (Standard LeetCode semantics: yes.) - For the graph, can `edges` contain self-loops (`[a, a]`) or duplicate edges? Should they be tolerated? - Are node labels guaranteed dense (`0..n-1`), or could they be sparse / non-integer? - What are the expected input sizes — does this need to be $O(1)$ / near-linear, or is a simpler approach acceptable? ### What a Strong Answer Covers - **LRU:** correct $O(1)$ design (hash map + doubly linked list, or an ordered-dict equivalent) with the move-to-front, update-in-place, and eviction logic all correct. - Clean handling of the update-existing-key case without leaking a duplicate node, and eviction triggered only on genuine overflow. - **Graph:** a correct linear-time component count (DFS/BFS or Union-Find) that accounts for isolated nodes, self-loops, and duplicate edges. - Accurate time and space complexity for both ($O(1)$ per cache op; $O(n + m)$ for the graph), stated explicitly. - Communication: stating assumptions, dry-running a small example, and naming trade-offs (e.g. DFS recursion depth vs. iterative/Union-Find). ### Follow-up Questions - How would you make the LRU cache thread-safe, and where would lock contention hurt? Could you shard it? - How would you extend the cache to an **LFU** (least-frequently-used) eviction policy while keeping operations $O(1)$? - For the graph, how would you also return the **size of the largest** connected component, or the sizes of all components? - If the graph edges arrive as a stream (online), which approach scales better, and what does Union-Find's near-constant amortized cost depend on?