Stage II: Hard Questions

7. Linked List Cycle

Problem: Given the head of a linked list, determine if the linked list has a cycle in it.

Concept Tested: The "fast and slow pointer" (Floyd's Tortoise and Hare) algorithm.

Companies: Amazon, Microsoft, Apple, Bloomberg

8. Linked List Cycle II

Problem: Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return null.

Concept Tested: An advanced application of the fast/slow pointer technique.

Companies: Microsoft, Amazon, Apple, Oracle

9. Copy List with Random Pointer

Problem: Construct a deep copy of a linked list where each node contains an additional random pointer, which could point to any node in the list or null.

Concept Tested: Using a hash map to associate original nodes with their copies to resolve the random pointers correctly.

Companies: Amazon, Microsoft, Bloomberg, Facebook (Meta)

10. Reverse Nodes in k-Group

Problem: Given the head of a linked list, reverse the nodes of the list k at a time, and return the modified list.

Concept Tested: Advanced pointer manipulation, recursion, and breaking the problem into sub-problems.

Companies: Microsoft, Amazon, Google, Facebook (Meta)

11. LRU Cache

Problem: Design a data structure that follows the constraints of a Least Recently Used (LRU) Cache. It must support get(key) and put(key, value) operations in O(1) time.

Concept Tested: Combining a Hash Map (for O(1) access) and a Doubly Linked List (for O(1) eviction/ordering).

Companies: Amazon, Google, Facebook (Meta), Microsoft, Apple, Dropbox

6. Largest Rectangle in Histogram

Problem: Given bar heights, find the area of the largest rectangle that can be formed.

Concept Tested: The canonical monotonic stack problem for finding previous/next smaller elements.

Companies: Amazon, Google, Microsoft, Facebook (Meta)

7. Trapping Rain Water

Problem: Given an elevation map, compute how much water it can trap.

Concept Tested: Using a stack to keep track of the boundaries of a potential water trap.

Companies: Amazon, Google, Microsoft, Apple, Bloomberg

8. Basic Calculator

Problem: Implement a basic calculator to evaluate a string expression with +, -, (, and ).

Concept Tested: Using a stack to handle nested parentheses and signs.

Companies: Google, Microsoft, Facebook (Meta), Amazon

5. Sliding Window Maximum

Problem: Find the maximum value in each sliding window of size k.

Concept Tested: Using a Deque to maintain a monotonically decreasing window of indices.

Companies: Amazon, Google, Facebook (Meta), Microsoft

6. Shortest Path in a Binary Matrix

Problem: Find the shortest path from top-left to bottom-right in a grid of 0s and 1s.

Concept Tested: A complex BFS on a 2D grid where the queue stores the path length.

Companies: Amazon, Facebook (Meta), Google

7. Design Circular Queue

Problem: Design your implementation of the circular queue data structure.

Concept Tested: Implementing Circular Queue logic with an array and pointers.

Companies: Amazon, Microsoft, Apple

6. Subarray Sum Equals K

Problem: Return the total number of subarrays whose sum equals k.

Concept Tested: Using a hash map to store prefix sums and their frequencies.

Companies: Amazon, Facebook (Meta), Google, Microsoft

7. Longest Substring Without Repeating Characters

Problem: Find the length of the longest substring without repeating characters.

Concept Tested: Combining a hash map with the sliding window technique.

Companies: Amazon, Microsoft, Apple, Google, Facebook (Meta)

8. Insert Delete GetRandom O(1)

Problem: Implement a data structure that supports insert, remove, and getRandom all in average O(1) time.

Concept Tested: A brilliant synthesis of a hash map and a dynamic array.

Companies: Amazon, Facebook (Meta), Google, Microsoft, Twitter

7. Binary Tree Maximum Path Sum

Concept Tested: An advanced DFS where the recursive helper function must do two things: return the maximum path sum that can extend upwards to its parent, and update a global maximum for paths that are contained entirely within the current subtree (i.e., paths that "turn" at the current node).

Companies: Google, Amazon, Facebook (Meta), Microsoft

class Solution:
    def maxPathSum(self, root: TreeNode) -> int:
        self.max_sum = float('-inf')
    def dfs(node):
        if not node:
            return 0

        left_max = max(0, dfs(node.left))
        right_max = max(0, dfs(node.right))

        self.max_sum = max(self.max_sum, node.val + left_max + right_max)

        return node.val + max(left_max, right_max)

    dfs(root)
    return self.max_sum

8. Construct Binary Tree from Preorder and Inorder Traversal

Concept Tested: A classic problem demonstrating the unique properties of traversals. The preorder traversal always gives you the root of any subtree, while the inorder traversal tells you which nodes are in the left subtree and which are in the right subtree relative to that root.

Companies: Amazon, Microsoft, Bloomberg, Apple

def buildTree(preorder: list[int], inorder: list[int]) -> TreeNode:
    if not preorder or not inorder:
        return None
root_val = preorder[0]
root = TreeNode(root_val)

mid_idx = inorder.index(root_val)

root.left = buildTree(preorder[1 : mid_idx + 1], inorder[:mid_idx])
root.right = buildTree(preorder[mid_idx + 1 :], inorder[mid_idx + 1:])

return root

9. Serialize and Deserialize Binary Tree

Concept Tested: A practical problem that requires converting a tree into a string format and vice-versa. A common approach is to use a preorder DFS for serialization (to capture the structure including null nodes) and a queue or an iterator for deserialization.

Companies: Amazon, Google, Facebook (Meta), Microsoft

class Codec:
    def serialize(self, root):
        res = []
        def dfs(node):
            if not node:
                res.append("N")
                return
            res.append(str(node.val))
            dfs(node.left)
            dfs(node.right)
        dfs(root)
        return ",".join(res)
def deserialize(self, data):
    vals = data.split(',')
    self.i = 0
    def dfs():
        if vals[self.i] == "N":
            self.i += 1
            return None
        node = TreeNode(int(vals[self.i]))
        self.i += 1
        node.left = dfs()
        node.right = dfs()
        return node
    return dfs()

10. Lowest Common Ancestor of a Binary Tree

Concept Tested: A clever recursive solution. The recursive function returns the LCA if found in its subtree, or p or q if one of them is found, or null. If a node receives non-null values from both its left and right recursive calls, it must be the LCA.

Companies: Amazon, Facebook (Meta), Microsoft, Apple, LinkedIn

def lowestCommonAncestor(root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
    if not root or root == p or root == q:
        return root
left = lowestCommonAncestor(root.left, p, q)
right = lowestCommonAncestor(root.right, p, q)

if left and right:
    return root

return left or right

7. Convert Sorted Array to Binary Search Tree

Concept Tested: Building a height-balanced BST to avoid the O(n) worst-case scenario. This is achieved by recursively choosing the middle element of the current array segment as the root, and using the left and right halves to build the subtrees.

Companies: Amazon, Microsoft, Apple

def sortedArrayToBST(nums: list[int]) -> TreeNode:
    def helper(l, r):
        if l > r:
            return None
    mid = (l + r) // 2
    root = TreeNode(nums[mid])
    root.left = helper(l, mid - 1)
    root.right = helper(mid + 1, r)
    return root

return helper(0, len(nums) - 1)

8. Delete Node in a BST

Concept Tested: Direct implementation of the complex three-case deletion algorithm, with a focus on correctly handling the two-child case by finding and replacing with the in-order successor.

Companies: Amazon, Microsoft, Facebook (Meta)

def deleteNode(root: TreeNode, key: int) -> TreeNode:
    if not root:
        return None
if key > root.val:
    root.right = deleteNode(root.right, key)
elif key < root.val:
    root.left = deleteNode(root.left, key)
else: # Node to delete found
    if not root.left:
        return root.right
    elif not root.right:
        return root.left
    else:
        # Node has two children: find in-order successor (min in right subtree)
        curr = root.right
        while curr.left:
            curr = curr.left
        root.val = curr.val # Copy successor's value
        root.right = deleteNode(root.right, root.val) # Delete the successor
return root

9. Unique Binary Search Trees

Concept Tested: A Dynamic Programming problem related to BSTs, specifically Catalan numbers. The number of unique BSTs with n nodes, G(n), is the sum of possibilities where each number i from 1 to n is the root. G(n) = Σ (G(i-1) * G(n-i)) for i in 1...n.

Companies: Amazon, Google, Microsoft

def numTrees(n: int) -> int:
    dp = [0] * (n + 1)
    dp[0] = 1 # Base case: one way to form an empty tree
    dp[1] = 1 # Base case: one way to form a tree with one node
# Calculate for nodes 2 through n
for i in range(2, n + 1):
    # For a tree with i nodes, iterate through all possible roots (1 to i)
    for j in range(1, i + 1):
        # j-1 nodes in the left subtree, i-j nodes in the right
        dp[i] += dp[j - 1] * dp[i - j]

return dp[n]

10. Recover Binary Search Tree

Concept Tested: A problem where two nodes in a BST have been swapped, violating the property. The solution requires finding these two nodes and swapping them back. This can be done by performing an in-order traversal and finding the one or two "dips" in the otherwise sorted sequence.

Companies: Amazon, Google, Microsoft

def recoverTree(root: TreeNode) -> None:
    first, second, prev = None, None, TreeNode(float('-inf'))
def inorder(node):
    nonlocal first, second, prev
    if not node:
        return

    inorder(node.left)

    # Find the first misplaced node
    if not first and prev.val >= node.val:
        first = prev

    # Find the second misplaced node
    if first and prev.val >= node.val:
        second = node

    prev = node
    inorder(node.right)

inorder(root)
# Swap the values of the two misplaced nodes
first.val, second.val = second.val, first.val

6. Find Median from Data Stream

Concept Tested: The canonical "two heaps" problem. You maintain two heaps: a max-heap to store the smaller half of the numbers and a min-heap for the larger half. By keeping the heaps balanced (or differing by at most one element), the median can be calculated in O(1) time from the roots of the heaps.

Companies: Amazon, Google, Facebook (Meta), Microsoft, Apple

import heapq
class MedianFinder:
    def __init__(self):
        self.small_half = []  # max-heap (using negative numbers)
        self.large_half = []  # min-heap
def addNum(self, num: int) -> None:
    heapq.heappush(self.small_half, -1 * num)
    if (self.small_half and self.large_half and
            (-1 * self.small_half[0]) > self.large_half[0]):
        val = -1 * heapq.heappop(self.small_half)
        heapq.heappush(self.large_half, val)
    if len(self.small_half) > len(self.large_half) + 1:
        val = -1 * heapq.heappop(self.small_half)
        heapq.heappush(self.large_half, val)
    if len(self.large_half) > len(self.small_half) + 1:
        val = heapq.heappop(self.large_half)
        heapq.heappush(self.small_half, -1 * val)

def findMedian(self) -> float:
    if len(self.small_half) > len(self.large_half):
        return -1 * self.small_half[0]
    if len(self.large_half) > len(self.small_half):
        return self.large_half[0]
    return (-1 * self.small_half[0] + self.large_half[0]) / 2.0

7. Merge k Sorted Lists

Concept Tested: A classic problem perfectly solved with a min-heap. The heap stores the head node from each of the k lists. You repeatedly extract the overall minimum node from the heap, add it to your result, and then insert the next node from its original list back into the heap.

Companies: Amazon, Google, Microsoft, Facebook (Meta)

import heapq
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
def mergeKLists(lists: list[ListNode]) -> ListNode:
min_heap = []
for i, l in enumerate(lists):
if l:
heapq.heappush(min_heap, (l.val, i, l))
dummy = ListNode()
tail = dummy

while min_heap:
    val, i, node = heapq.heappop(min_heap)
    tail.next = node
    tail = tail.next
    if node.next:
        heapq.heappush(min_heap, (node.next.val, i, node.next))

return dummy.next

8. IPO (Find Maximized Capital)

Concept Tested: A challenging problem combining a greedy approach with a heap. First, sort all projects by their required capital. Then, iterate through the sorted projects. For each project you can currently afford, push its profit onto a max-heap. After adding all affordable projects, greedily pick the one with the highest profit from the heap, update your capital, and repeat.

Companies: Google, Amazon

import heapq
def findMaximizedCapital(k: int, w: int, profits: list[int], capital: list[int]) -> int:
    projects = sorted(zip(capital, profits))
    max_heap = [] # Stores profits of affordable projects
    i = 0
for _ in range(k):
    while i < len(projects) and projects[i][0] <= w:
        heapq.heappush(max_heap, -projects[i][1]) # Use negative for max-heap
        i += 1

    if not max_heap:
        break

    w += -heapq.heappop(max_heap)

return w