Katkat
Back

Implement Cache and Count Components

AmazonSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This question evaluates a candidate's ability to design and implement efficient data structures for constant-time operations and to reason about graph connectivity and component counting, falling under the Coding & Algorithms domain and requiring practical implementation with algorithmic complexity reasoning.

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.

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.

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.

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?

Hints

Hint 1

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 2

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 3

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.

Hint 4

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 5

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`.

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?