Copy<\/button><\/div>\n\ndef coin_change_limited(coins, counts, amount):\n\n # coins[i] can be used at most counts[i] times\n\n dp = [float(\u2018inf\u2019)] * (amount + 1)\n\n dp[0] = 0\n for i, coin in enumerate(coins):\n\n # iterate in reverse to enforce use-at-most-once per pass\n\n for _ in range(counts[i]):\n\n for a in range(amount, coin \u2013 1, -1):\n\n if dp[a \u2013 coin] != float(\u2018inf\u2019):\n\n dp[a] = min(dp[a], dp[a \u2013 coin] + 1)\n return dp[amount] if dp[amount] != float(\u2018inf\u2019) else -1\n<\/code><\/pre><\/div>Longest consecutive sequence in an unsorted array<\/span>HashSet<\/span>Medium<\/span><\/span><\/span><\/button><\/p>\n
Load all elements into a hash set. Iterate through the array and for each element, check if it is the start of a sequence (i.e., element – 1 is not in the set). If it is the start, count the sequence length by repeatedly checking element + 1, element + 2, and so on. Track the maximum length seen. O(n) time because each element is visited at most twice.<\/p>\n
Reported from SDE-2 phone screens at Amazon in 2024-2025. The sorting approach is O(n log n) and technically correct but interviewers push for the O(n) set-based solution at mid-level. The follow-up asks what happens if the array contains duplicates: the hash set handles this automatically since set membership is duplicate-agnostic.<\/p>\n
<\/div><\/div><\/div>\n
Serialize and deserialize an N-ary tree<\/span>Tree \/ BFS<\/span>Medium<\/span><\/span><\/span><\/button><\/p>\n
BFS-based serialization. Write each node’s value followed by the count of its children, then its children’s values in the same format. This lets the deserializer know exactly how many children to expect at each node without a delimiter. Alternatively, DFS with an explicit child-count marker works and is slightly simpler to implement recursively.<\/p>\n
Reported from a 2025 SDE-2 onsite, Round 2, with a follow-up asking for O(1) time for dynamic node additions and removals after the serialization is built. The O(1) dynamic update requirement changes the approach: instead of rebuilding the serialized string, maintain a doubly linked list of nodes at each level so insertions and deletions update only the affected position in O(1) time.<\/p>\n
<\/div><\/div><\/div>\n
Implement a rate limiter using the token bucket algorithm<\/span>Concurrency \/ Design<\/span>Medium<\/span><\/span><\/span><\/button><\/p>\n
The token bucket maintains a counter of available tokens, a max capacity, and a refill rate (tokens per second). On each request, check if at least one token is available. If yes, decrement and allow. If no, reject or queue. Refill tokens based on elapsed time since the last refill, capped at capacity. Thread safety requires either a mutex around the token check-and-decrement or an atomic compare-and-swap loop.<\/p>\n
Amazon’s API Gateway uses token bucket rate limiting internally, which makes this question particularly relevant for Amazon infrastructure teams. The interviewer typically asks you to compare token bucket vs. leaky bucket vs. fixed window vs. sliding window rate limiting, each has different burst behavior. Token bucket allows short bursts up to capacity; leaky bucket enforces a smooth outflow rate; fixed window can allow 2x the rate at window boundaries; sliding window is more accurate but computationally heavier.<\/p>\n
java<\/span>Copy<\/button><\/div>\n\nimport java.util.concurrent.atomic.AtomicLong;\npublic class TokenBucketRateLimiter {\n\n private final long capacity;\n\n private final double refillRatePerMs;\n\n private final AtomicLong tokens;\n\n private volatile long lastRefillTime;\n public TokenBucketRateLimiter(long capacity, long refillRatePerSecond) {\n\n this.capacity = capacity;\n\n this.refillRatePerMs = refillRatePerSecond \/ 1000.0;\n\n this.tokens = new AtomicLong(capacity);\n\n this.lastRefillTime = System.currentTimeMillis();\n\n }\n public synchronized boolean tryAcquire() {\n\n refill();\n\n if (tokens.get() > 0) {\n\n tokens.decrementAndGet();\n\n return true;\n\n }\n\n return false;\n\n }\n private void refill() {\n\n long now = System.currentTimeMillis();\n\n long elapsed = now \u2013 lastRefillTime;\n\n long newTokens = (long) (elapsed * refillRatePerMs);\n\n if (newTokens > 0) {\n\n tokens.set(Math.min(capacity, tokens.get() + newTokens));\n\n lastRefillTime = now;\n\n }\n\n }\n\n}\n<\/code><\/pre><\/div>Count the number of islands in a 2D grid of land and water cells<\/span>Graphs \/ BFS-DFS<\/span>Medium<\/span><\/span><\/span><\/button><\/p>\n
Scan every cell. When you hit an unvisited land cell, run a DFS or BFS that flips every connected land cell to visited and expands in all four directions. Each DFS call accounts for exactly one island, so the island counter only increments at the point a new, unvisited land cell is discovered. Time complexity is O(rows × cols) since every cell is visited once.<\/p>\n
This is one of the most frequently reported Amazon SDE-2 phone screen questions across 2024 and 2025 loop write-ups on Glassdoor and LeetCode Discuss. The follow-up interviewers ask most often: what if the grid isn’t static but a live stream of cell updates? That changes the approach to a Union-Find structure with incremental union operations on each update, rather than a full grid rescan per change.<\/p>\n
python<\/span>Copy<\/button><\/div>\n\ndef num_islands(grid):\n\n if not grid:\n\n return 0\n\n rows, cols = len(grid), len(grid[0])\n\n visited = [[False] * cols for _ in range(rows)]\n def dfs(r, c):\n\n if r < 0 or r >= rows or c < 0 or c >= cols:\n\n return\n\n if visited[r][c] or grid[r][c] == \u201c0\u201d:\n\n return\n\n visited[r][c] = True\n\n dfs(r + 1, c)\n\n dfs(r \u2013 1, c)\n\n dfs(r, c + 1)\n\n dfs(r, c \u2013 1)\n count = 0\n\n for r in range(rows):\n\n for c in range(cols):\n\n if grid[r][c] == \u201c1\u201d and not visited[r][c]:\n\n dfs(r, c)\n\n count += 1\n\n return count\n<\/code><\/pre><\/div>Determine whether all courses can be finished given a list of prerequisite pairs<\/span>Graphs \/ Topological Sort<\/span>Medium<\/span><\/span><\/span><\/button><\/p>\n
Build an adjacency list from the prerequisite pairs and track the in-degree of every course. Run Kahn’s algorithm: push every course with in-degree zero onto a queue, pop a course, decrement the in-degree of its dependents, and push any dependent whose in-degree drops to zero. If every course gets processed, there’s no cycle and the courses can all be finished. If some courses never enter the queue, a cycle exists among them.<\/p>\n
Amazon interviewers frame this as a build-dependency problem more often than the textbook version, something like “package A depends on package B, detect a circular build dependency before it breaks the release pipeline.” That framing matches Amazon’s actual internal build tooling. The standard follow-up asks you to also return a valid build order, not just a true\/false answer, which the same queue naturally produces if you record the pop order.<\/p>\n
python<\/span>Copy<\/button><\/div>\n\nfrom collections import deque\ndef can_finish(num_courses, prerequisites):\n\n graph = [[] for _ in range(num_courses)]\n\n in_degree = [0] * num_courses\n\n for course, prereq in prerequisites:\n\n graph[prereq].append(course)\n\n in_degree[course] += 1\n queue = deque(c for c in range(num_courses) if in_degree[c] == 0)\n\n visited = 0\n while queue:\n\n node = queue.popleft()\n\n visited += 1\n\n for neighbor in graph[node]:\n\n in_degree[neighbor] -= 1\n\n if in_degree[neighbor] == 0:\n\n queue.append(neighbor)\n return visited == num_courses\n<\/code><\/pre><\/div>Find the lowest common ancestor of two nodes in a binary tree<\/span>Tree \/ DFS<\/span>Medium<\/span><\/span><\/span><\/button><\/p>\n
Recursive DFS from the root. If the current node is one of the two targets, return it immediately. Otherwise recurse into the left and right subtrees. If both recursive calls return a non-null node, the current node is the lowest common ancestor, since one target was found on each side. If only one side returns non-null, propagate that result up, since the ancestor must be further up that branch.<\/p>\n
Reported repeatedly in Amazon SDE-2 phone screens, usually as the second, easier problem after a harder opener. The two follow-ups worth preparing: what changes if each node has a parent pointer instead of the tree being passed in (it becomes a linked-list intersection problem, not a tree traversal one), and what happens if one of the two target nodes might not exist in the tree at all (you need a separate existence check before trusting the LCA result).<\/p>\n
<\/div><\/div><\/div>\n
Design and implement a Least Recently Used (LRU) cache with O(1) get and put<\/span>Design \/ HashMap<\/span>Medium<\/span><\/span><\/span><\/button><\/p>\n
Combine a hash map for O(1) lookup with a doubly linked list for O(1) reordering. On every get, move the accessed node to the front of the list, since it’s now the most recently used. On every put, insert a new node at the front; if the cache exceeds capacity, evict the node at the tail, since that’s the least recently used, and remove its key from the hash map.<\/p>\n
This is one of Amazon’s most consistently reported SDE-2 coding questions across multiple years of loop write-ups, more so than at most other Big Tech companies. In 2025 loops it’s shown up both as a standalone coding round and as the opening 15 minutes of a Bar Raiser’s hybrid round before pivoting into Leadership Principles questions. The follow-up almost always asks how you’d make the cache thread-safe under concurrent get and put calls from multiple threads.<\/p>\n
python<\/span>Copy<\/button><\/div>\n\nclass Node:\n\n def __init__(self, key, value):\n\n self.key = key\n\n self.value = value\n\n self.prev = None\n\n self.next = None\nclass LRUCache:\n\n def __init__(self, capacity):\n\n self.capacity = capacity\n\n self.cache = {}\n\n self.head = Node(0, 0)\n\n self.tail = Node(0, 0)\n\n self.head.next = self.tail\n\n self.tail.prev = self.head\n def _remove(self, node):\n\n node.prev.next = node.next\n\n node.next.prev = node.prev\n def _add_to_front(self, node):\n\n node.next = self.head.next\n\n node.prev = self.head\n\n self.head.next.prev = node\n\n self.head.next = node\n def get(self, key):\n\n if key not in self.cache:\n\n return -1\n\n node = self.cache[key]\n\n self._remove(node)\n\n self._add_to_front(node)\n\n return node.value\n def put(self, key, value):\n\n if key in self.cache:\n\n self._remove(self.cache[key])\n\n node = Node(key, value)\n\n self.cache[key] = node\n\n self._add_to_front(node)\n\n if len(self.cache) > self.capacity:\n\n lru = self.tail.prev\n\n self._remove(lru)\n\n del self.cache[lru.key]\n<\/code><\/pre><\/div>Given a list of meeting time intervals, find the minimum number of conference rooms required<\/span>Heap \/ Intervals<\/span>Medium<\/span><\/span><\/span><\/button><\/p>\n
Sort meetings by start time. Keep a min-heap of end times representing rooms currently in use. For each meeting, check the smallest end time on the heap: if it’s less than or equal to the current meeting’s start time, that room has freed up, so pop it and push the new end time in its place. If not, no room is free, so push the new end time without popping, which allocates a new room. The final heap size is the answer.<\/p>\n
Reported from Amazon SDE-2 onsite loops tied to internal scheduling systems, conference-room booking and warehouse shift scheduling are the two framings candidates mention most. The follow-up worth preparing: what if meetings can be canceled after being scheduled? That breaks the simple min-heap approach and pushes toward an interval tree or a heap with lazy deletion instead.<\/p>\n
python<\/span>Copy<\/button><\/div>\n\nimport heapq\ndef min_meeting_rooms(intervals):\n\n if not intervals:\n\n return 0\n\n intervals.sort(key=lambda x: x[0])\n\n end_times = [intervals[0][1]]\n for start, end in intervals[1:]:\n\n if start >= end_times[0]:\n\n heapq.heapreplace(end_times, end)\n\n else:\n\n heapq.heappush(end_times, end)\n return len(end_times)\n<\/code><\/pre><\/div>Find the length of the longest strictly increasing subsequence in an array<\/span>Dynamic Programming<\/span>Medium<\/span><\/span><\/span><\/button><\/p>\n
The O(n^2) version defines dp[i] as the length of the longest increasing subsequence ending at index i, computed as 1 plus the max of dp[j] for every j less than i where nums[j] is less than nums[i]. The O(n log n) version keeps a “tails” array, where tails[k] holds the smallest possible tail value of an increasing subsequence of length k+1, and uses binary search to find where each new number belongs.<\/p>\n
Reported from SDE-2 phone screens where interviewers ask for the O(n^2) DP solution first and then push for the O(n log n) optimization as a mid-interview follow-up, the same escalation pattern seen on the coin-change question earlier on this page. Being able to walk from the straightforward DP to the binary-search optimization without starting over is what separates a pass from a borderline result at this level.<\/p>\n
python<\/span>Copy<\/button><\/div>\n\nimport bisect\ndef length_of_lis(nums):\n\n tails = []\n\n for num in nums:\n\n pos = bisect.bisect_left(tails, num)\n\n if pos == len(tails):\n\n tails.append(num)\n\n else:\n\n tails[pos] = num\n\n return len(tails)\n<\/code><\/pre><\/div>Tell me about a time you made a decision that was unpopular with your team but that you believed was right for the customer.<\/span>Customer Obsession<\/span>Medium<\/span><\/span><\/span><\/button>