Free coding interview prep with runnable Python solutions. Practice two sum, linked lists, binary trees, dynamic programming, graph algorithms, sliding window, and more. Filter by topic, company (Amazon, Google, Meta, Microsoft), and level (SWE1, SWE2, SWE3). Every question includes multiple solutions with time and space complexity analysis and an interactive Python editor powered by Pyodide. Reverse a string in Python using two-pointer O(n) and slice approaches. Common Amazon and Google new grad interview question. Topics: strings Companies: amazon, google Level: new-grad Two Pointers: Convert to a list, swap characters from both ends moving inward until the pointers meet. Slice: Use Python slice notation s[::-1] to create a reversed copy in one expression. Count vowels in a string using Python set lookup and generator expressions. Easy Amazon interview question for new grads. Topics: strings Companies: amazon Level: new-grad Set Lookup: Iterate over each character and check membership in a vowel set for O(1) per lookup. Check if a string is a palindrome in Python using two-pointer and slice approaches. Common Amazon and Microsoft interview question. Topics: strings, two-pointers Companies: amazon, microsoft Level: new-grad Two Pointers: Clean the string to only alphanumeric lowercase chars, then use two pointers from both ends. Slice Compare: Clean the string then compare it against its reverse using slice notation. Solve FizzBuzz in Python with a clean string concatenation approach. Classic interview question at Amazon, Google, and Meta. Topics: strings, lists Companies: amazon, google, meta Level: new-grad String Concatenation: Build the token by concatenating "Fizz" and "Buzz" conditionally, falling back to str(i). Find duplicates in a list using hash map counting and two-set O(n) approaches. Common Amazon and Google interview question. Topics: lists, hash-map Companies: amazon, google Level: new-grad, swe2 Hash Map Count: Count occurrences with a dict, then return keys whose count exceeds 1. Two Sets: Track a "seen" set and a "duplicates" set — add to duplicates when a number is already seen. Flatten an arbitrarily nested list in Python using recursion and iterative stack. Common Google and Meta interview question. Topics: lists, recursion Companies: google, meta Level: swe2 Recursive: Recursively extend result for sub-lists, append directly for integers. Stack depth = nesting depth d. Iterative Stack: Use an explicit stack (reversed items) to process elements without recursion limits. Filter and transform a list using Python list comprehensions. Easy Amazon new grad interview question. Topics: lists, comprehensions Companies: amazon Level: new-grad List Comprehension: A single list comprehension with an if clause selects evens and squares them in one expression. Build a word frequency counter in Python using Counter and dict. Common Amazon, Google, Microsoft interview question. Topics: dicts, strings Companies: amazon, google, microsoft Level: new-grad collections.Counter: Normalize to lowercase, split on whitespace, and count with collections.Counter. Implement a Stack class in Python using a list with O(1) push, pop, and peek. Common Amazon and Bloomberg OOP interview question. Topics: stack, oop Companies: amazon, bloomberg Level: new-grad, swe2 List-Backed Stack: Use a Python list with append() for push and pop() from the end — both O(1) amortized. Implement a Queue in Python using collections.deque for O(1) enqueue and dequeue. Common Amazon and Google interview question. Topics: queue, deque Companies: amazon, google Level: new-grad Deque-Backed Queue: Use collections.deque with append() to enqueue at right and popleft() to dequeue from left. Design a BankAccount class in Python with deposit, withdraw, and balance. Common Amazon and Microsoft OOP interview question. Topics: oop Companies: amazon, microsoft Level: new-grad Basic OOP: Store balance as a private attribute, validate withdrawals, raise ValueError for overdrafts. Implement a @timer decorator in Python using functools.wraps and perf_counter. Common Google and Meta SWE2 interview question. Topics: decorators Companies: google, meta Level: swe2 functools.wraps Decorator: Wrap the call with perf_counter before and after, print the delta, return the original result. functools.wraps preserves __name__ and __doc__. Implement an infinite Fibonacci generator in Python using yield. Common Amazon and Google interview question on generators. Topics: generators Companies: amazon, google Level: new-grad, swe2 Generator Function: Use yield to produce one value at a time while maintaining two running variables. Implement a custom context manager in Python with __enter__ and __exit__ for safe file handling. Common Google SWE2 interview question. Topics: oop, exceptions Companies: google Level: swe2 Context Manager Class: __enter__ opens and returns the file; __exit__ closes it and optionally suppresses FileNotFoundError. Filter even numbers using lambda+filter and list comprehension in Python. Easy Amazon new grad interview question. Topics: comprehensions, lists Companies: amazon Level: new-grad List Comprehension: A list comprehension with modulo filter — readable and Pythonic. Lambda + filter(): Pass a lambda to built-in filter() and convert to list — functional programming style. Validate email addresses in Python using regular expressions and re.fullmatch. Common Amazon and Google SWE2 interview question. Topics: regex, strings Companies: amazon, google Level: swe2 Regex Fullmatch: Use re.fullmatch with a pattern covering local part, @, domain segments, and TLD with minimum 2 chars. Format a receipt with aligned columns using Python f-strings. Easy Amazon new grad interview question on string formatting. Topics: strings Companies: amazon Level: new-grad f-String Formatting: Use f-strings with alignment specifiers to build aligned columns, then append subtotal, tax, and total. Read a file and count lines with exception handling in Python. Common Amazon and Microsoft new grad interview question. Topics: exceptions Companies: amazon, microsoft Level: new-grad try/except File Read: try/except wrapping a with-statement. Generator expression counts lines without loading the whole file. Design custom exception hierarchies in Python for payment processing. Common Google and Meta SWE2 OOP interview question. Topics: exceptions, oop Companies: google, meta Level: swe2 Exception Hierarchy: Subclass PaymentError for each specific error type, storing context as attributes and building descriptive messages in __init__. Implement a generic type-hinted Stack using TypeVar and Generic in Python. Common Google and Microsoft SWE2 interview question. Topics: typing, stack, oop Companies: google, microsoft Level: swe2 Generic Stack: Use TypeVar and Generic to parameterize the Stack class, providing type-safe operations with full annotations. Use zip and enumerate together in Python to iterate multiple lists with index. Common Amazon new grad interview question. Topics: lists Companies: amazon Level: new-grad enumerate + zip: Combine enumerate and zip to iterate with index, name, and score in a single loop. Understand and fix the Python mutable default argument bug. Common Google and Meta SWE2 interview question on Python gotchas. Topics: lists Companies: google, meta Level: swe2 None Default Pattern: Use None as default and assign a new list inside the body — creates a fresh list per call instead of sharing one object. Master *args and **kwargs in Python. Common Amazon and Google new grad interview question on variadic functions. Topics: oop Companies: amazon, google Level: new-grad *args and **kwargs: *args captures positional args as a tuple; **kwargs as a dict. Use functools.reduce for the product. Implement a closure-based counter factory in Python using nonlocal. Common Google and Meta SWE2 interview question on closures. Topics: oop Companies: google, meta Level: swe2 Closure with nonlocal: Use nonlocal to allow the inner function to mutate the enclosing scope count variable. Implement a shape hierarchy with inheritance and method overriding in Python. Common Amazon and Microsoft SWE2 interview question. Topics: oop Companies: amazon, microsoft Level: swe2 Inheritance with Override: Base class raises NotImplementedError; each subclass overrides area() with its own formula. Use Python abc to define abstract classes and enforce interfaces. Common Google SWE2 OOP interview question. Topics: oop Companies: google Level: swe2 ABC with abstractmethod: abc.ABC + @abstractmethod enforces the interface. Python raises TypeError at instantiation if any abstract method is missing. Implement a custom iterator in Python using __iter__ and __next__. Common Google and Meta SWE2 interview question. Topics: oop, generators Companies: google, meta Level: swe2 Iterator Protocol: __iter__ resets and returns self; __next__ yields and decrements, raising StopIteration when done. Use @property and @setter in Python for a Temperature class with validation. Common Amazon and Google SWE2 interview question. Topics: oop, decorators Companies: amazon, google Level: swe2 @property with Validation: Store Celsius internally; expose both as properties converting on the fly. Celsius setter validates against absolute zero. Use collections.namedtuple for a Point and compute Euclidean distance. Easy Amazon new grad Python interview question. Topics: oop, typing Companies: amazon Level: new-grad namedtuple + math.sqrt: Named tuple gives readable .x .y access; standard Euclidean formula computes distance. Use Python dataclasses to build a Student Registry with filtering and sorting. Common Google and Microsoft SWE2 interview question. Topics: oop, typing Companies: google, microsoft Level: swe2 dataclass + Registry: @dataclass generates boilerplate; __post_init__ validates; Registry methods filter and sort. Solve Two Sum in O(n) with a hash map and O(n^2) brute force. Classic Amazon, Google, Meta, Microsoft interview question. Topics: array, hash-map Companies: amazon, google, meta, microsoft Level: new-grad, swe2 Optimal - Hash Map: One pass: for each element x, check if complement (target-x) is in the map. If yes return indices, else store x->index. Brute Force: Check every pair (i,j) where i<j and return the pair that sums to target. Maximize stock profit in O(n) with a greedy scan. Classic Amazon, Google, Meta interview question with full Python solution. Topics: array, greedy Companies: amazon, google, meta Level: new-grad, swe2 Greedy: Track min_price and max_profit in one pass. At each price, update min or compute profit. Detect duplicates in an array in O(n) using a Python set. Easy Amazon and Google interview question. Topics: array, hash-map Companies: amazon, google Level: new-grad Set Length: If len(nums) != len(set(nums)), a duplicate exists. Early-Exit Set: Iterate and return True as soon as a repeated element is found. Compute product except self in O(n) without division using prefix and suffix passes. Top Amazon, Google, Meta interview question. Topics: array, prefix-sum Companies: amazon, google, meta, microsoft Level: swe2 Prefix & Suffix Pass: First pass builds prefix products into result. Second pass multiplies by running suffix product from right. Solve Maximum Subarray in O(n) with Kadane's algorithm. Classic Amazon, Google, Microsoft, Bloomberg interview question. Topics: array, dynamic-programming Companies: amazon, google, microsoft, bloomberg Level: new-grad, swe2 Kadane's Algorithm: Maintain running sum; reset to current element if running sum goes negative. Track global max. Find maximum product subarray tracking both max and min products in O(n). Amazon and Google SWE2/SWE3 interview question. Topics: array, dynamic-programming Companies: amazon, google Level: swe2, swe3 Track Max and Min: Track both max and min products ending at each position because a negative product can become the largest when multiplied by another negative. Find minimum in a rotated sorted array in O(log n) with binary search. Common Amazon, Google, Microsoft interview question. Topics: array, binary-search Companies: amazon, google, microsoft Level: swe2 Binary Search: Compare mid with right: if mid > right, minimum is in the right half; otherwise minimum is in the left half (including mid). Search a rotated sorted array in O(log n) with modified binary search. Common Amazon, Google, Meta SWE2/SWE3 question. Topics: array, binary-search Companies: amazon, google, meta Level: swe2, swe3 Modified Binary Search: At each step, one half is always sorted. Check if target lies in the sorted half; if so search there, otherwise search the other half. Find all unique triplets summing to zero in O(n^2) with sort + two pointers. Classic Amazon, Google, Meta, Bloomberg interview question. Topics: array, two-pointers, sorting Companies: amazon, google, meta, microsoft, bloomberg Level: swe2, swe3 Sort + Two Pointers: Sort the array. Fix element i, then use two pointers l=i+1 and r=n-1 to find pairs that sum to -nums[i]. Skip duplicates. Maximize water container area in O(n) using two pointers. Common Amazon, Google, Meta medium interview question. Topics: array, two-pointers, greedy Companies: amazon, google, meta Level: swe2 Two Pointers: Start with left=0 and right=n-1. Area = min(h[l],h[r]) * (r-l). Move the shorter pointer inward; this is the only way to possibly increase area. Check if two strings are anagrams using Counter or sorting. Easy Amazon, Google, Microsoft interview question. Topics: strings, hash-map, sorting Companies: amazon, google, microsoft Level: new-grad, swe2 Counter Comparison: Count character frequencies with Counter and compare — O(1) space since alphabet is fixed size. Sort: Sort both strings and compare — simple and correct, but slower. Group anagrams using sorted key hash map in O(n*k log k). Common Amazon, Google, Meta, Microsoft interview question. Topics: strings, hash-map, sorting Companies: amazon, google, meta, microsoft Level: swe2 Sorted Key HashMap: Sort each string to get a canonical key; group strings with the same key using defaultdict. Find the longest common prefix in a string array in O(S). Easy Amazon, Google, Microsoft interview question. Topics: strings Companies: amazon, google, microsoft Level: new-grad Horizontal Scan: Take first string as prefix. Shrink it until every other string starts with it. Validate bracket strings with a stack in O(n). Classic Amazon, Google, Meta, Microsoft, Bloomberg interview question. Topics: strings, stack Companies: amazon, google, meta, microsoft, bloomberg Level: new-grad, swe2 Stack: Push opening brackets. For each closing bracket, pop from stack and check if it matches. Return True iff stack is empty at end. Reverse word order in a string using split, reverse, join in O(n). Common Amazon and Microsoft SWE2 interview question. Topics: strings, two-pointers Companies: amazon, microsoft Level: swe2 Split, Reverse, Join: split() tokenizes (handles extra spaces), reversed() reverses, join() reassembles with single space. Run-length encode a string in O(n) with two pointers. Common Amazon, Microsoft, Bloomberg SWE2 interview question. Topics: strings, two-pointers Companies: amazon, microsoft, bloomberg Level: swe2 Two Pointer RLE: Walk the string counting consecutive identical characters; append char and count to result; return shorter of compressed vs original. Rotate an array in-place in O(n) O(1) space using three reverses. Common Amazon, Google, Microsoft interview question. Topics: array, two-pointers Companies: amazon, google, microsoft Level: swe2 Three Reverses: Reverse whole array, reverse first k elements, reverse remaining n-k elements. Find the missing number in O(n) O(1) using Gauss sum or XOR trick. Common Amazon, Google, Microsoft new grad interview question. Topics: array, bit-manipulation Companies: amazon, google, microsoft Level: new-grad Math / Gauss Sum: Expected sum of 0..n is n*(n+1)//2. Missing = expected - actual sum. XOR: XOR every index (0..n) with every value. Paired values cancel; only the missing number remains. Find the single non-duplicate element in O(n) O(1) using the XOR trick. Common Amazon, Google, Meta easy interview question. Topics: array, bit-manipulation Companies: amazon, google, meta Level: new-grad XOR: XOR all elements together. Duplicate pairs cancel (a ^ a = 0). What remains is the single number. Move zeros to the end in-place in O(n) O(1) with two pointers. Easy Amazon and Google interview question. Topics: array, two-pointers Companies: amazon, google Level: new-grad Two Pointers: Use an insert_pos pointer. Copy non-zero elements to insert_pos. Fill the rest with zeros. Merge overlapping intervals in O(n log n) by sorting and scanning. Classic Amazon, Google, Meta, Bloomberg interview question. Topics: array, sorting Companies: amazon, google, meta, microsoft, bloomberg Level: swe2, swe3 Sort + Scan: Sort by start. Extend last merged interval if current overlaps, else append new interval. Insert and merge a new interval in O(n) with three-phase approach. Common Google and LinkedIn SWE2 interview question. Topics: array Companies: google, linkedin Level: swe2 Three-Phase Merge: Collect all intervals ending before new starts, then merge overlapping ones, then append the rest. Traverse a matrix in spiral order using boundary simulation. Common Amazon, Google, Microsoft, Bloomberg interview question. Topics: matrix Companies: amazon, google, microsoft, bloomberg Level: swe2 Boundary Simulation: Maintain top/bottom/left/right boundaries. Traverse right, down, left, up in turn, shrinking bounds each time. Set matrix rows and columns to zero in O(m*n) O(1) space using first row/col as markers. Amazon, Google, Microsoft interview question. Topics: matrix Companies: amazon, google, microsoft Level: swe2 O(1) Space Using First Row/Col: Use the first row and first column as markers for which rows/cols need zeroing. Handle the first row/col separately. Find longest substring without repeating chars in O(n) with sliding window. Top Amazon, Google, Meta, Bloomberg interview question. Topics: strings, sliding-window, hash-map Companies: amazon, google, meta, microsoft, bloomberg Level: swe2 Sliding Window + Set: Expand right pointer. When duplicate found, shrink from left until removed. Track max window size. Optimized Hash Map: Store char->last index. On duplicate, jump left pointer directly to last_index+1 instead of stepping one at a time. Find minimum window substring in O(|s|+|t|) with sliding window and frequency maps. Hard Amazon, Google, Meta SWE3 question. Topics: strings, sliding-window, hash-map Companies: amazon, google, meta Level: swe3, senior Sliding Window with Counts: Use two hash maps: required counts from t and current window counts. Track "have" vs "need" to know when window is valid. Expand right, shrink left when valid. Find all anagram positions in a string using fixed sliding window in O(n). Common Amazon and Google SWE2 interview question. Topics: strings, sliding-window, hash-map Companies: amazon, google Level: swe2 Fixed Sliding Window: Use a fixed-size window of len(p). Maintain frequency counts and a "matches" counter to check validity in O(1). Count subarrays summing to k in O(n) with prefix sum and hash map. Common Amazon, Google, Meta SWE2/SWE3 question. Topics: array, prefix-sum, hash-map Companies: amazon, google, meta Level: swe2, swe3 Prefix Sum + HashMap: At each position, compute prefix sum. If prefix_sum - k exists in the map, those subarrays sum to k. Store prefix sums with their counts. Compute trapped rainwater in O(n) O(1) with two pointers. Hard Amazon, Google, Meta, Bloomberg senior interview question. Topics: array, two-pointers, stack Companies: amazon, google, meta, microsoft, bloomberg Level: swe3, senior Two Pointers: Two pointers from both ends. Water at any position = min(left_max, right_max) - height. Process the side with smaller max; that side determines the water level. Solve Jump Game in O(n) with greedy tracking of farthest reachable index. Common Amazon, Google, Meta, Microsoft interview question. Topics: array, greedy, dynamic-programming Companies: amazon, google, meta, microsoft Level: swe2 Greedy: Track farthest reachable index. If current position exceeds it, we are stuck. Otherwise update farthest. Reverse a singly linked list in O(n) iteratively (O(1) space) and recursively. Classic Amazon, Google, Meta, Microsoft interview question. Topics: linked-list, recursion Companies: amazon, google, meta, microsoft Level: new-grad, swe2 Iterative: Walk with three pointers; redirect each node's next to prev. O(1) extra space. Recursive: Recurse to the tail; on the way back reverse each link. Detect a cycle in a linked list in O(n) O(1) using Floyd's tortoise and hare. Classic Amazon, Google, Meta, Microsoft interview question. Topics: linked-list, two-pointers Companies: amazon, google, meta, microsoft Level: new-grad, swe2 Floyd's Tortoise and Hare: Slow pointer moves 1 step, fast moves 2. If they ever point to the same node, a cycle exists. Find the middle of a linked list in O(n) O(1) with slow/fast pointers. Common Amazon and Microsoft new grad interview question. Topics: linked-list, two-pointers Companies: amazon, microsoft Level: new-grad Slow/Fast Pointers: Move slow by 1 and fast by 2. When fast reaches end, slow is at middle. Merge two sorted linked lists in O(m+n) iteratively and recursively. Classic Amazon, Google, Meta, Microsoft, Bloomberg interview question. Topics: linked-list, recursion Companies: amazon, google, meta, microsoft, bloomberg Level: new-grad, swe2 Iterative with Dummy: Use a dummy head. At each step append the smaller of list1/list2 heads. Append remaining. Remove nth node from end in one pass using two pointers. Common Amazon, Google, Microsoft SWE2 interview question. Topics: linked-list, two-pointers Companies: amazon, google, microsoft Level: swe2 Two Pointers One Pass: Advance fast pointer n+1 steps ahead. Then move both until fast is None. Slow is just before the node to delete. Check if a linked list is palindrome in O(n) O(1) by reversing the second half. Common Amazon, Google, Meta interview question. Topics: linked-list, two-pointers, stack Companies: amazon, google, meta Level: new-grad, swe2 Reverse Half: Find middle with slow/fast, reverse second half, compare both halves, then restore. Find linked list intersection in O(m+n) O(1) with two-pointer switch trick. Common Amazon and Microsoft interview question. Topics: linked-list, two-pointers, hash-map Companies: amazon, microsoft Level: new-grad Two Pointer Switch: Each pointer traverses both lists. After m+n steps they either meet at intersection or both reach None together. Remove duplicates from a sorted linked list in O(n) O(1). Easy Amazon and Google new grad interview question. Topics: linked-list Companies: amazon, google Level: new-grad Single Pass: Walk the list; skip nodes whose value equals the current node's value. Insert a node into a sorted circular linked list handling all edge cases. Common Google and Amazon SWE2 interview question. Topics: linked-list, circular-linked-list Companies: google, amazon Level: swe2 Three-Case Insert: Traverse and handle: (1) insert between curr and curr.next when curr <= val <= next, (2) at boundary when curr is max and val is outside range, (3) full loop means all equal. Delete a node without head reference in O(1) by copying next value. Easy Amazon, Microsoft, Bloomberg interview question. Topics: linked-list Companies: amazon, microsoft, bloomberg Level: new-grad Copy and Skip: Copy next node's value into the current node, then bypass the next node. Add two numbers represented as reversed linked lists in O(max(m,n)). Classic Amazon, Google, Meta, Bloomberg interview question. Topics: linked-list, math Companies: amazon, google, meta, microsoft, bloomberg Level: swe2 Digit-by-Digit Simulation: Walk both lists simultaneously, add digits with carry. Continue while either list or carry is non-zero. Reverse linked list nodes in k-groups recursively. Hard Amazon, Google, Microsoft SWE3/Senior interview question. Topics: linked-list, recursion Companies: amazon, google, microsoft Level: swe3, senior Recursive: Check k nodes exist. If yes, reverse them and recurse on the rest. If not, return as-is. Deep copy a linked list with random pointers using hash map in O(n). Common Amazon, Google, Microsoft SWE2/SWE3 interview question. Topics: linked-list, hash-map Companies: amazon, google, microsoft Level: swe2, swe3 Hash Map Two Pass: First pass: create a copy of each node and store in a map. Second pass: set next and random pointers using the map. Implement LRU Cache in O(1) with doubly linked list and hash map. Classic Amazon, Google, Meta, Bloomberg SWE2/SWE3 interview question. Topics: linked-list, doubly-linked-list, hash-map Companies: amazon, google, meta, microsoft, bloomberg Level: swe2, swe3 Doubly Linked List + Hash Map: Use a doubly linked list (most recent at head, LRU at tail) and a hash map. On access/update, move node to head. On capacity overflow, evict tail. Sort a linked list in O(n log n) using merge sort. Common Amazon and Google SWE2/SWE3 interview question. Topics: linked-list, sorting, divide-and-conquer Companies: amazon, google Level: swe2, swe3 Top-Down Merge Sort: Find middle with slow/fast, split, recursively sort both halves, merge. O(log n) recursion stack. Reorder a linked list in O(n) O(1) by finding middle, reversing, and merging. Common Amazon and Google SWE2 interview question. Topics: linked-list, two-pointers Companies: amazon, google Level: swe2 Find Middle + Reverse + Merge: Find middle with slow/fast, reverse second half, then interleave first and reversed second halves. Swap adjacent linked list nodes in O(n) O(1) iteratively. Common Amazon, Google, Microsoft SWE2 interview question. Topics: linked-list, recursion Companies: amazon, google, microsoft Level: swe2 Iterative: Use a dummy head. At each iteration, swap the two nodes after prev pointer, then advance prev by 2. Partition a linked list around value x in O(n) O(1) using two sub-lists. Common Amazon and Bloomberg SWE2 interview question. Topics: linked-list, two-pointers Companies: amazon, bloomberg Level: swe2 Two-Partition Lists: Build two sub-lists: one for nodes < x, one for nodes >= x. Merge them at the end. Flatten a multilevel doubly linked list in O(n) by splicing child lists. Common Amazon and Google SWE2 interview question. Topics: linked-list, doubly-linked-list, dfs Companies: amazon, google Level: swe2 Iterative DFS: Walk the list. When a node has a child, find the tail of the child list, splice it between current and current.next, then set child to None. Rotate a linked list right by k places in O(n) O(1). Common Amazon, Google, Microsoft SWE2 interview question. Topics: linked-list, two-pointers Companies: amazon, google, microsoft Level: swe2 Find Length + Rotate: Find length and tail, make circular, then find new tail at length-k%length-1 and break the circle. Inorder traversal of a binary tree recursively and iteratively with a stack. Common Amazon, Google, Microsoft interview question. Topics: binary-tree, dfs, stack, recursion Companies: amazon, google, microsoft Level: new-grad, swe2 Recursive: Recursively visit left subtree, then root, then right subtree. Iterative Stack: Use an explicit stack: push left nodes until null, then pop and record, then process right subtree. Level order traversal of a binary tree using BFS in O(n). Classic Amazon, Google, Meta, Bloomberg interview question. Topics: binary-tree, bfs Companies: amazon, google, meta, microsoft, bloomberg Level: swe2 BFS with Queue: Use a deque for BFS. At start of each iteration, snapshot the queue length to process exactly one level. Find the maximum depth of a binary tree with recursive DFS in O(n). Easy Amazon, Google, Meta, Microsoft interview question. Topics: binary-tree, dfs, bfs, recursion Companies: amazon, google, meta, microsoft Level: new-grad Recursive DFS: Depth is 0 for null; 1 + max of left and right depths otherwise. Check if a binary tree is symmetric with recursive mirror comparison. Easy Amazon, Google, Microsoft interview question. Topics: binary-tree, dfs, bfs, recursion Companies: amazon, google, microsoft Level: new-grad, swe2 Recursive Mirror Check: A tree is symmetric if its left and right subtrees are mirrors. Mirror check: left.val == right.val AND mirrors(left.left, right.right) AND mirrors(left.right, right.left). Invert a binary tree recursively in O(n). Easy Amazon, Google, Meta interview question. Topics: binary-tree, dfs, bfs, recursion Companies: amazon, google, meta Level: new-grad Recursive: Swap left and right at current node, then recursively invert each subtree. Find the diameter of a binary tree in O(n) with post-order DFS. Easy Amazon, Google, Meta interview question. Topics: binary-tree, dfs Companies: amazon, google, meta Level: new-grad, swe2 DFS with Global Max: Post-order DFS: at each node, diameter candidate = left_height + right_height. Return height to parent. Track global max. Check if a root-to-leaf path sums to target in O(n) with recursive DFS. Easy Amazon and Microsoft new grad interview question. Topics: binary-tree, dfs, recursion Companies: amazon, microsoft Level: new-grad Recursive DFS: At each node subtract its value from target. At a leaf, return True if remaining == 0. Find LCA in a BST in O(h) using BST ordering property. Classic Amazon, Google, Meta, Bloomberg SWE2 interview question. Topics: binary-tree, bst, dfs Companies: amazon, google, meta, microsoft, bloomberg Level: swe2 BST Property: Use BST ordering: if both p,q < root go left; if both > root go right; else current root is LCA. Validate a BST in O(n) by passing min/max bounds through DFS. Classic Amazon, Google, Meta, Bloomberg interview question. Topics: binary-tree, bst, dfs Companies: amazon, google, meta, microsoft, bloomberg Level: swe2 DFS with Bounds: Pass min and max bounds to each recursive call. A node must satisfy min < node.val < max. Find kth smallest in BST in O(H+k) with iterative inorder traversal. Common Amazon, Google, Bloomberg SWE2 interview question. Topics: binary-tree, bst, dfs Companies: amazon, google, bloomberg Level: swe2 Iterative Inorder: Use iterative inorder traversal. Decrement k each time we process a node; return when k hits 0. Convert sorted array to height-balanced BST in O(n) with divide and conquer. Common Amazon and Google SWE2 interview question. Topics: binary-tree, bst, divide-and-conquer Companies: amazon, google Level: swe2 Divide & Conquer: Always pick the middle element as root. Recursively build left subtree from left half and right from right half. Find maximum path sum in a binary tree in O(n) with post-order DFS. Hard Amazon, Google, Meta, Microsoft SWE3/Senior interview question. Topics: binary-tree, dfs Companies: amazon, google, meta, microsoft Level: swe3, senior Post-Order DFS: At each node compute: local_max = node.val + max(0,left) + max(0,right). Update global max. Return node.val + max(0, best_one_side) to parent. Serialize and deserialize a binary tree with BFS in O(n). Hard Amazon, Google, Meta, LinkedIn SWE3/Senior interview question. Topics: binary-tree, bfs, dfs Companies: amazon, google, meta, microsoft, linkedin Level: swe3, senior BFS Level-Order: Serialize with BFS, storing null for missing children. Deserialize by replaying BFS order from the tokens. Get the right side view of a binary tree using BFS in O(n). Common Amazon, Google, Meta SWE2 interview question. Topics: binary-tree, bfs, dfs Companies: amazon, google, meta Level: swe2 BFS Last Node Per Level: BFS level-order; append the last node's value from each level to the result. Sum all root-to-leaf path numbers in O(n) with DFS. Common Amazon and Google SWE2 interview question. Topics: binary-tree, dfs Companies: amazon, google Level: swe2 DFS with Accumulated Sum: Pass current accumulated number (curr * 10 + node.val) down the DFS. At a leaf, return the accumulated value. Check if a tree is a subtree of another in O(m*n) with DFS and same-tree comparison. Common Amazon and Google SWE2 question. Topics: binary-tree, dfs Companies: amazon, google Level: swe2 DFS with Same-Tree Check: At each node in root, check if it matches subRoot with an is_same helper. Return True if any match found. Check if a binary tree is height-balanced in O(n) with post-order DFS and -1 sentinel. Common Amazon, Google, Microsoft interview question. Topics: binary-tree, dfs Companies: amazon, google, microsoft Level: new-grad, swe2 Post-Order DFS: Compute height in post-order. Return -1 as a sentinel for "unbalanced" so we can short-circuit early. Implement a Trie with insert, search, and startsWith in O(m) per operation. Common Amazon, Google, Meta, Microsoft SWE2/SWE3 question. Topics: trie, oop Companies: amazon, google, meta, microsoft Level: swe2, swe3 Dict-Based Trie: Each node stores a dict of children and a is_end flag. Insert/search/startsWith traverse character by character. Flatten a binary tree to linked list in-place in O(n) O(1). Common Amazon, Google, Microsoft SWE2 interview question. Topics: binary-tree, dfs, linked-list Companies: amazon, google, microsoft Level: swe2 Morris-like In-Place: For each node with a left child, find the rightmost node of the left subtree, connect it to right child, move left subtree to right, set left to null. Construct a binary tree from preorder and inorder traversals in O(n) with hash map. Common Amazon, Google, Bloomberg SWE2/SWE3 question. Topics: binary-tree, dfs, hash-map Companies: amazon, google, microsoft, bloomberg Level: swe2, swe3 Recursive with HashMap: preorder[0] is root. Use a hash map to find its position in inorder in O(1). Left subtree has inorder[:pos] elements, right has inorder[pos+1:]. Count islands in a 2D grid using DFS or BFS in O(m*n). Top Amazon, Google, Microsoft interview question with complete Python solution. Topics: graph, bfs, dfs, matrix Companies: amazon, google, microsoft, bloomberg, meta Level: swe2, swe3 DFS: For each unvisited land cell, run DFS marking the island visited by setting "1" to "0". Count DFS initiations. BFS: For each unvisited land cell, BFS to mark the whole island. Count BFS initiations. Deep copy a graph using DFS or BFS with hash map in O(V+E). Common Amazon, Google, Meta interview question with Python solution. Topics: graph, dfs, bfs, hash-table Companies: amazon, google, meta, microsoft Level: swe2, swe3 DFS with Hash Map: Dictionary maps originals to clones. Recursively clone each neighbor, using the map to avoid duplicates. BFS with Hash Map: BFS from start. Clone each node once into a hash map. Link cloned neighbors during traversal. Detect cycle in directed graph with DFS or Kahn's BFS topological sort in O(V+E). Amazon, Google, Bloomberg interview question. Topics: graph, topological-sort, dfs, bfs Companies: amazon, google, microsoft, bloomberg, uber Level: swe2, swe3 DFS Cycle Detection: 3-state DFS: 0=unvisited, 1=visiting, 2=done. If we re-visit a visiting node, there is a cycle. Kahn's BFS Topological Sort: Count in-degrees. Enqueue zero-in-degree nodes. Process BFS decrementing neighbor in-degrees. If all processed, no cycle. Find cells where water flows to both oceans using multi-source BFS in O(m*n). Google, Amazon interview question with Python solution. Topics: graph, bfs, dfs, matrix Companies: amazon, google, bloomberg Level: swe3, senior Multi-Source BFS: BFS from all Pacific border cells and all Atlantic border cells separately. Result is the intersection of both reachable sets. Solve Word Ladder with BFS or bidirectional BFS. Amazon, Google, Bloomberg hard interview question with Python solution. Topics: graph, bfs, hash-table Companies: amazon, google, microsoft, bloomberg, linkedin Level: swe3, senior BFS: BFS level by level. Replace each character with a-z. If result is in word set and unvisited, enqueue. Bidirectional BFS: BFS from both ends simultaneously. Expand the smaller frontier each step. Stop when frontiers meet. Determine if edges form a valid tree using Union-Find or DFS. Google, LinkedIn interview question with Python solution. Topics: graph, dfs, union-find Companies: google, linkedin, amazon, microsoft Level: swe2, swe3 Union-Find: Check n-1 edges first. Union-Find: adding an edge between nodes in the same component creates a cycle. DFS: DFS from node 0 tracking parent to avoid false cycles. Tree is valid if all n nodes are visited. Count connected components in undirected graph using Union-Find or DFS. Google, LinkedIn interview question with Python solution. Topics: graph, dfs, union-find Companies: google, linkedin, amazon, microsoft Level: swe2, swe3 Union-Find: Initialize n components. For each edge, union two nodes. Each successful union decrements component count. DFS: Build adjacency list. DFS from each unvisited node marking all reachable nodes. Count DFS initiations. Derive alien language order using DFS topological sort with cycle detection. Amazon, Google, Airbnb hard interview question. Topics: graph, topological-sort, dfs Companies: amazon, google, meta, microsoft, airbnb Level: swe3, senior DFS Topological Sort: Build directed graph from adjacent word comparisons. DFS topological sort with 3-state cycle detection. Find shortest 8-directional clear path in binary matrix using BFS in O(n^2). Amazon, Google interview question with Python solution. Topics: graph, bfs, matrix Companies: amazon, google, bloomberg, microsoft Level: swe2, swe3 BFS: BFS from (0,0) in 8 directions. Mark visited by setting cells to 1. First arrival at (n-1,n-1) is shortest path. Capture surrounded regions in a board using DFS from borders in O(m*n). Amazon, Google, Bloomberg interview question. Topics: graph, dfs, bfs, matrix Companies: amazon, google, microsoft, bloomberg Level: swe2, swe3 DFS from Border: Mark all border-connected "O"s as "S" (safe). Flip remaining "O" to "X", then "S" back to "O". Solve Rotting Oranges with multi-source BFS in O(m*n). Amazon, Google, Bloomberg medium interview question with Python solution. Topics: graph, bfs, matrix Companies: amazon, google, microsoft, bloomberg Level: swe2, swe3 Multi-Source BFS: Enqueue all initially rotten oranges with time=0. BFS outward decrementing fresh count. Return max time if fresh==0. Check if path exists between two nodes using BFS or Union-Find. Easy graph question for new grads with Python solution. Topics: graph, dfs, bfs, union-find Companies: amazon, google, microsoft Level: new-grad, swe2 BFS: BFS from source. Return True if destination is reached. Union-Find: Union all edges. Check if source and destination share the same root. Find maximum island area using DFS in O(m*n). Amazon, Google, Bloomberg medium interview question with Python solution. Topics: graph, dfs, bfs, matrix Companies: amazon, google, microsoft, bloomberg Level: swe2, swe3 DFS: For each unvisited 1, DFS counting cells by marking them 0. Return max count seen. Find minimum signal delay using Dijkstra's algorithm. Amazon, Google, Uber interview question with Python solution. Topics: graph, dijkstra, heap Companies: amazon, google, microsoft, uber Level: swe3, senior Dijkstra's Algorithm: Min-heap Dijkstra from k. Relax edges greedily. Answer is max shortest distance; -1 if any node unreachable. Find the town judge using net degree scoring in O(E). Easy graph question for new grads with complete Python solution. Topics: graph, array, hash-table Companies: amazon, google, microsoft Level: new-grad, swe2 Net Score: Net score: +1 for being trusted, -1 for trusting. Judge has score exactly n-1. Check graph bipartiteness using BFS 2-coloring in O(V+E). Amazon, Google, Bloomberg interview question with Python solution. Topics: graph, bfs, dfs Companies: amazon, google, microsoft, bloomberg Level: swe2, swe3 BFS 2-Coloring: Assign colors 0/1 via BFS. If any neighbor shares the same color, not bipartite. Implement Kruskal's MST with Union-Find in O(E log E). Amazon, Google, Microsoft hard interview question with Python solution. Topics: graph, union-find, sorting, greedy Companies: amazon, google, microsoft, bloomberg Level: swe3, senior Kruskal's with Union-Find: Sort edges by weight. Greedily add edges using Union-Find, skipping cycle-creating edges. Sum weights of n-1 chosen edges. Merge accounts with shared emails using Union-Find. Amazon, Google, Meta interview question with Python solution. Topics: graph, union-find, dfs, sorting Companies: amazon, google, meta, bloomberg Level: swe3, senior Union-Find: Map each email to a parent. Union all emails in the same account. Group by root then reconstruct. Find the redundant edge creating a cycle using Union-Find. Amazon, Google interview question with Python solution. Topics: graph, union-find, dfs Companies: amazon, google, microsoft Level: swe2, swe3 Union-Find: Process edges in order. When union fails (both endpoints in same component), that edge is redundant. Fill rooms with distances to nearest gate using multi-source BFS in O(m*n). Meta, Google, Amazon interview question. Topics: graph, bfs, matrix Companies: meta, google, amazon, bloomberg Level: swe2, swe3 Multi-Source BFS: Enqueue all gate positions. BFS outward; update each INF room with current distance. Count distinct ways to climb n stairs using DP (Fibonacci) in O(n) O(1). Classic Amazon, Google, Apple interview question. Topics: dynamic-programming, math Companies: amazon, google, microsoft, bloomberg, apple Level: new-grad, swe2 DP (Bottom-Up): dp[i] = dp[i-1] + dp[i-2]. Use two variables instead of full array. Recursive with Memoization: Top-down recursion with memo cache. Base cases: n=1 -> 1, n=2 -> 2. Maximize robbery without adjacent houses using DP in O(n) O(1). Amazon, Google, Bloomberg medium interview question. Topics: dynamic-programming, array Companies: amazon, google, microsoft, bloomberg Level: swe2, swe3 DP O(1) Space: At each house, max is either skip it (prev1) or rob it (prev2 + current). Track just two variables. DP Array: Build dp array where dp[i] = max money robbing up to house i. Circular house robber using two-pass linear DP in O(n). Amazon, Google medium interview question with Python solution. Topics: dynamic-programming, array Companies: amazon, google, microsoft Level: swe2, swe3 Two-Pass DP: Since first and last are adjacent, solve two linear subproblems: rob houses 0..n-2 and rob houses 1..n-1. Return the max. Find LIS length using DP O(n^2) or binary search O(n log n). Amazon, Google, LinkedIn medium interview question. Topics: dynamic-programming, binary-search, array Companies: amazon, google, microsoft, bloomberg, linkedin Level: swe2, swe3 DP O(n^2): dp[i] = length of LIS ending at index i. For each i, check all j < i where nums[j] < nums[i]. Binary Search (Patience Sorting) O(n log n): Maintain a tails array where tails[i] = smallest tail of increasing subsequence of length i+1. Binary search to place each element. Find minimum coins to make amount using bottom-up DP in O(amount*coins). Amazon, Google, Goldman Sachs interview question. Topics: dynamic-programming, array, breadth-first-search Companies: amazon, google, microsoft, goldman-sachs, bloomberg Level: swe2, swe3 Bottom-Up DP: dp[i] = min coins to make amount i. Initialize to infinity. For each amount, try every coin. BFS: BFS treats amount as a graph. Each node is an amount; edges are coin subtractions. BFS finds shortest path to 0. Check if string can be segmented into dictionary words using DP in O(n^2). Amazon, Google, Meta, Bloomberg interview question. Topics: dynamic-programming, trie, hash-table Companies: amazon, google, meta, microsoft, bloomberg Level: swe2, swe3 Bottom-Up DP: dp[i] = True if s[:i] can be formed. For each i, check all j < i where dp[j] is True and s[j:i] is in the word set. Count unique paths in m x n grid using DP in O(m*n). Amazon, Google, Bloomberg medium interview question with Python solution. Topics: dynamic-programming, math, combinatorics Companies: amazon, google, microsoft, bloomberg Level: swe2, swe3 DP O(m*n): dp[i][j] = paths to reach cell (i,j) = paths from top + paths from left. DP O(n) Space: Use a single row dp. Update in-place: dp[j] += dp[j-1]. Determine if you can reach the last index using greedy O(n) or DP. Amazon, Google, Bloomberg medium interview question. Topics: dynamic-programming, greedy, array Companies: amazon, google, microsoft, bloomberg Level: swe2, swe3 Greedy: Track max reachable index. If current index ever exceeds max_reach, return False. DP: dp[i] = True if index i is reachable. For each reachable i, mark all positions i+1 to i+nums[i] as reachable. Find minimum jumps to reach last index using greedy in O(n). Amazon, Google, Bloomberg medium interview question. Topics: dynamic-programming, greedy, array Companies: amazon, google, microsoft, bloomberg Level: swe2, swe3 Greedy: Track current jump end and farthest reachable. When i reaches current_end, increment jumps and set current_end = farthest. Find LCS length using 2D DP in O(m*n). Amazon, Google, Microsoft, Bloomberg medium interview question with Python solution. Topics: dynamic-programming, string Companies: amazon, google, microsoft, bloomberg, oracle Level: swe2, swe3 Bottom-Up DP: 2D DP table. If text1[i-1] == text2[j-1]: dp[i][j] = dp[i-1][j-1] + 1, else dp[i][j] = max(dp[i-1][j], dp[i][j-1]). Space-Optimized DP: Use two rows instead of the full 2D table. Find minimum edit distance between two strings using 2D DP in O(m*n). Amazon, Google, Bloomberg hard interview question. Topics: dynamic-programming, string Companies: amazon, google, microsoft, bloomberg, linkedin Level: swe3, senior Bottom-Up DP: dp[i][j] = min operations to convert word1[:i] to word2[:j]. If chars match, take diagonal. Else 1 + min of insert/delete/replace. Partition array into equal subsets using 0/1 knapsack DP in O(n*sum). Amazon, Google, Bloomberg medium interview question. Topics: dynamic-programming, array Companies: amazon, google, microsoft, bloomberg Level: swe2, swe3 DP with Bitset: Use a set of reachable sums. For each number, add it to all existing reachable sums. Check if target (sum/2) is reachable. DP Array: Boolean array dp where dp[s] = can reach sum s. Traverse in reverse to avoid reuse. Count ways to assign +/- to reach target sum using DFS memoization or DP. Amazon, Google, Meta interview question. Topics: dynamic-programming, dfs, array Companies: amazon, google, meta, bloomberg Level: swe2, swe3 DFS with Memoization: Recursive DFS: at each index choose + or -. Memoize on (index, current_sum). DP with Hash Map: Use a counter dict mapping sum -> count. For each number update all sums by adding or subtracting the number. Count string decoding ways using DP in O(n). Amazon, Google, Meta, Bloomberg medium interview question with Python solution. Topics: dynamic-programming, string Companies: amazon, google, meta, bloomberg, microsoft Level: swe2, swe3 Bottom-Up DP: dp[i] = ways to decode s[:i]. Add dp[i-1] if s[i-1] is 1-9, add dp[i-2] if s[i-2:i] is 10-26. Space-Optimized DP: Only need prev2 and prev1 instead of full dp array. Maximize profit with at most 2 stock transactions using state machine DP in O(n). Amazon, Google, Goldman Sachs hard interview question. Topics: dynamic-programming, array Companies: amazon, google, goldman-sachs, bloomberg Level: swe3, senior State Machine DP: Track 4 states: cost of first buy, profit after first sell, cost of second buy, profit after second sell. Update greedily. Find minimum palindrome partition cuts using 2D DP in O(n^2). Amazon, Google, Bloomberg hard interview question. Topics: dynamic-programming, string Companies: amazon, google, bloomberg Level: swe3, senior DP with Palindrome Precomputation: Precompute is_pal[i][j]. Then dp[i] = min of (dp[j-1] + 1) for all j <= i where s[j:i+1] is palindrome. Wildcard pattern matching with ? and * using 2D DP in O(m*n). Amazon, Google, Bloomberg hard interview question. Topics: dynamic-programming, string, greedy Companies: amazon, google, microsoft, bloomberg Level: swe3, senior Bottom-Up DP: dp[i][j] = True if s[:i] matches p[:j]. Handle "*" as match-zero (dp[i][j-1]) or match-one-more (dp[i-1][j]). Regex pattern matching with . and * using 2D DP in O(m*n). Amazon, Google, Microsoft hard interview question. Topics: dynamic-programming, string, recursion Companies: amazon, google, microsoft, bloomberg Level: swe3, senior Bottom-Up DP: dp[i][j] = s[:i] matches p[:j]. For "*": zero occurrences (dp[i][j-2]) or match one more (dp[i-1][j] if chars match). Find maximum product subarray by tracking min and max in O(n). Amazon, Google, Bloomberg medium interview question. Topics: dynamic-programming, array Companies: amazon, google, microsoft, bloomberg Level: swe2, swe3 DP Track Min and Max: Track current max and min products. A negative number flips max and min. Update global max. Find minimum path sum in triangle using bottom-up DP in O(n^2). Amazon, Google, Bloomberg medium interview question. Topics: dynamic-programming, array Companies: amazon, google, bloomberg, microsoft Level: swe2, swe3 Bottom-Up DP In-Place: Start from second-to-last row, add minimum of the two children below. Result is triangle[0][0]. Find minimum path sum in m x n grid using DP in O(m*n). Amazon, Google, Bloomberg medium interview question. Topics: dynamic-programming, matrix Companies: amazon, google, microsoft, bloomberg Level: swe2, swe3 DP In-Place: Modify grid in-place. dp[i][j] = grid[i][j] + min of left and top neighbors. Maximize coins by bursting balloons using interval DP in O(n^3). Amazon, Google hard interview question with Python solution. Topics: dynamic-programming, divide-and-conquer Companies: amazon, google, bloomberg Level: senior, staff Interval DP: Add boundary 1s. dp[l][r] = max coins bursting all balloons between l and r exclusive. Try each k as the last balloon burst. Solve 0/1 knapsack problem using 2D DP or space-optimized 1D DP in O(n*W). Amazon, Google, Goldman Sachs interview question. Topics: dynamic-programming, array Companies: amazon, google, microsoft, goldman-sachs Level: swe2, swe3 2D DP: dp[i][w] = max value using first i items with capacity w. Either skip item i or take it. 1D DP (Space-Optimized): Use 1D dp array, traverse weights in reverse to avoid using same item twice. Solve rod cutting problem using bottom-up DP in O(n^2). Amazon, Google, Microsoft interview question with Python solution. Topics: dynamic-programming, array Companies: amazon, google, microsoft Level: swe2, swe3 Bottom-Up DP: dp[i] = max revenue for rod of length i. Try all cuts j from 1 to i. Solve egg drop problem with minimum trials using DP in O(k log n). Amazon, Google, Goldman Sachs hard interview question. Topics: dynamic-programming, binary-search, math Companies: amazon, google, goldman-sachs, bloomberg Level: senior, staff DP on Trials: dp[m][k] = max floors checkable with m moves and k eggs. dp[m][k] = dp[m-1][k-1] + dp[m-1][k] + 1. Find min m where dp[m][k] >= n. Implement merge sort from scratch in O(n log n). Amazon, Google, Microsoft interview question with complete Python solution. Topics: sorting, divide-and-conquer, array Companies: amazon, google, microsoft, bloomberg Level: swe2, swe3 Recursive Merge Sort: Recursively split array in half. Merge two sorted halves by comparing elements and building result. In-Place Merge Sort: Sort in-place using index boundaries instead of slicing, reducing memory allocation. Implement quicksort with Lomuto partition or randomized pivot in O(n log n). Amazon, Google interview question. Topics: sorting, divide-and-conquer, array Companies: amazon, google, microsoft, bloomberg Level: swe2, swe3 Lomuto Partition Scheme: Pick last element as pivot. Partition: elements <= pivot go left. Recursively sort both halves. Randomized Pivot: Randomly swap pivot before partitioning to avoid worst-case O(n^2) on sorted input. Implement heap sort in-place using max-heap in O(n log n) O(1) space. Amazon, Google, Microsoft interview question. Topics: sorting, heap, array Companies: amazon, google, microsoft Level: swe2, swe3 Heap Sort In-Place: Build max-heap in O(n). Then repeatedly swap root with last, reduce heap size, and heapify down. Find k-th largest using min-heap O(n log k) or quickselect O(n). Amazon, Google, Meta, Bloomberg interview question. Topics: sorting, heap, divide-and-conquer, array Companies: amazon, google, meta, microsoft, bloomberg Level: swe2, swe3 Min-Heap of Size k: Maintain a min-heap of size k. For each element, push to heap; if size > k, pop the min. The top of heap is the k-th largest. Quickselect: Use quickselect (partial quicksort). Partition around pivot; recurse only into the partition containing position n-k. Sort 0s, 1s, 2s in-place using Dutch National Flag 3-pointer technique in O(n). Amazon, Google interview question. Topics: sorting, two-pointers, array Companies: amazon, google, microsoft, bloomberg Level: swe2, swe3 Dutch National Flag (3 Pointers): Three pointers: low (next 0 spot), mid (current), high (next 2 spot). Advance mid: swap 0 to low, skip 1, swap 2 to high. Merge overlapping intervals after sorting in O(n log n). Amazon, Google, Meta, Bloomberg medium interview question. Topics: sorting, array, intervals Companies: amazon, google, meta, microsoft, bloomberg Level: swe2, swe3 Sort and Merge: Sort by start. Iterate; if current start <= last end, merge by extending end. Otherwise append new interval. Insert and merge a new interval into sorted non-overlapping intervals in O(n). Amazon, Google, Meta interview question. Topics: sorting, array, intervals Companies: amazon, google, meta, bloomberg Level: swe2, swe3 Three-Phase Linear Scan: Phase 1: add all non-overlapping intervals before new. Phase 2: merge all overlapping. Phase 3: add remaining. Binary search in rotated sorted array in O(log n). Amazon, Google, Meta, Bloomberg medium interview question with Python solution. Topics: binary-search, array Companies: amazon, google, meta, microsoft, bloomberg Level: swe2, swe3 Modified Binary Search: At each step, determine which half is sorted. If target is in sorted half, search there; otherwise search the other half. Find peak element using binary search in O(log n). Amazon, Google, Bloomberg medium interview question with Python solution. Topics: binary-search, array Companies: amazon, google, microsoft, bloomberg Level: swe2, swe3 Binary Search: If nums[mid] < nums[mid+1], the peak is to the right. Otherwise it is to the left (inclusive of mid). Search sorted 2D matrix using binary search in O(log(m*n)). Amazon, Google, Bloomberg medium interview question. Topics: binary-search, matrix, array Companies: amazon, google, microsoft, bloomberg Level: swe2, swe3 Binary Search on Virtual 1D Array: Treat the matrix as a sorted 1D array of length m*n. Binary search using virtual index mapping. Find median of two sorted arrays using binary search in O(log(min(m,n))). Amazon, Google, Goldman Sachs hard interview question. Topics: binary-search, array, divide-and-conquer Companies: amazon, google, microsoft, bloomberg, goldman-sachs Level: swe3, senior Binary Search on Partition: Binary search partition in shorter array. Ensure left partition has (m+n+1)//2 elements total. Check cross-border conditions. Find minimum in rotated sorted array using binary search in O(log n). Amazon, Google, Bloomberg interview question. Topics: binary-search, array Companies: amazon, google, microsoft, bloomberg Level: swe2, swe3 Binary Search: If nums[mid] > nums[hi], the min is in the right half. Otherwise min is in left half including mid. Compute h-index by sorting citations in O(n log n). Google, Amazon, Bloomberg interview question with Python solution. Topics: sorting, array, binary-search Companies: google, amazon, bloomberg Level: swe2, swe3 Sort and Scan: Sort descending. Walk through: if citations[i] >= i+1, h = i+1. Return the last valid h. Find minimum conference rooms using min-heap or two sorted arrays in O(n log n). Amazon, Google, Meta interview question. Topics: sorting, heap, intervals Companies: amazon, google, meta, bloomberg, microsoft Level: swe2, swe3 Min-Heap of End Times: Sort by start. Use min-heap of end times. If next meeting starts after earliest ending, reuse that room. Two Sorted Arrays: Sort start and end times separately. Use two pointers; if next start < current end, need another room. Arrange numbers to form largest value using custom comparator sort in O(n log n). Amazon, Google, Bloomberg interview question. Topics: sorting, string, greedy Companies: amazon, google, microsoft, bloomberg Level: swe2, swe3 Custom Sort: Custom comparator: for two numbers a and b, prefer a first if str(a)+str(b) > str(b)+str(a). Edge case: all zeros. Find all unique triplets summing to zero using sort and two pointers in O(n^2). Amazon, Google, Meta, Bloomberg interview question. Topics: two-pointers, sorting, array Companies: amazon, google, meta, microsoft, bloomberg Level: swe2, swe3 Sort + Two Pointers: Sort array. For each index i, use two pointers lo=i+1 and hi=n-1. Move pointers based on sum. Skip duplicates. Find all unique quadruplets summing to target using sort and two pointers in O(n^3). Amazon, Google interview question. Topics: two-pointers, sorting, array Companies: amazon, google, microsoft Level: swe2, swe3 Sort + Two Nested Loops + Two Pointers: Sort. Two outer loops fix first two elements. Inner two pointers find the remaining pair. Skip duplicates. Find max water container using two pointers in O(n). Amazon, Google, Meta, Bloomberg medium interview question. Topics: two-pointers, array, greedy Companies: amazon, google, meta, bloomberg, microsoft Level: swe2, swe3 Two Pointers: Start pointers at both ends. Area = min(h[lo], h[hi]) * (hi-lo). Move shorter pointer inward. Compute trapped rain water using two pointers O(n) O(1) or DP. Amazon, Google, Meta, Bloomberg hard interview question. Topics: two-pointers, dynamic-programming, stack, array Companies: amazon, google, meta, bloomberg, microsoft Level: swe3, senior Two Pointers: Two pointers lo/hi. Track max_left and max_right. Process side with smaller max; water at that side = max - height. DP Precompute Max: Precompute max_left[i] and max_right[i] arrays. Water at i = min(max_left[i], max_right[i]) - height[i]. Find minimum window substring using sliding window in O(|s|+|t|). Amazon, Google, Meta hard interview question. Topics: sliding-window, hash-table, string, two-pointers Companies: amazon, google, meta, bloomberg, microsoft Level: swe3, senior Sliding Window: Track needed char counts. Expand right pointer adding chars. When window is valid, contract left minimizing window. Find longest substring without repeating characters using sliding window in O(n). Amazon, Google, Meta, Bloomberg interview question. Topics: sliding-window, hash-table, string, two-pointers Companies: amazon, google, meta, bloomberg, microsoft Level: swe2, swe3 Sliding Window with Dict: Track last index of each char. When duplicate found, jump left to max(left, last_index+1). Track max window length. Check if s2 contains permutation of s1 using fixed sliding window in O(n). Amazon, Google, Meta interview question. Topics: sliding-window, hash-table, string, two-pointers Companies: amazon, google, meta, bloomberg Level: swe2, swe3 Fixed Sliding Window: Count chars in s1. Slide window of length len(s1) over s2, updating counts. Match when all counts are 0. Find all anagram start indices using fixed sliding window in O(n). Amazon, Google, Meta, Bloomberg interview question. Topics: sliding-window, hash-table, string Companies: amazon, google, meta, bloomberg Level: swe2, swe3 Fixed Sliding Window: Slide window of size len(p). Use have/need counters to track when window is a valid anagram. Find longest substring with at most k replacements using sliding window in O(n). Amazon, Google, Bloomberg interview question. Topics: sliding-window, hash-table, string Companies: amazon, google, bloomberg, microsoft Level: swe2, swe3 Sliding Window: Expand window right. Track frequency of most common char. If window_size - max_freq > k, slide left by 1. Find max consecutive 1s with k flips using sliding window in O(n). Amazon, Google, Bloomberg interview question. Topics: sliding-window, array, two-pointers Companies: amazon, google, bloomberg Level: swe2, swe3 Sliding Window: Expand window right. When zero count exceeds k, move left. Track max window size. Find max fruits with 2 baskets using sliding window in O(n). Amazon, Google, Bloomberg interview question. Topics: sliding-window, hash-table, array Companies: amazon, google, bloomberg Level: swe2, swe3 Sliding Window with At Most 2 Distinct: Sliding window tracking count of each fruit type. When more than 2 types, shrink window from left. Count subarrays with exactly k distinct integers using at-most-K trick in O(n). Amazon, Google, Bloomberg hard question. Topics: sliding-window, hash-table, array Companies: amazon, google, bloomberg Level: swe3, senior At Most K Trick: exactly(k) = at_most(k) - at_most(k-1). Helper counts subarrays with at most k distinct using sliding window. Find minimum subarray with sum >= target using sliding window in O(n). Amazon, Google, Bloomberg medium interview question. Topics: sliding-window, two-pointers, array, binary-search Companies: amazon, google, bloomberg, microsoft Level: swe2, swe3 Sliding Window: Expand right pointer adding elements. When sum >= target, record length and shrink left pointer. Find longest subarray of 1s after deleting one element using sliding window. Amazon, Google interview question. Topics: sliding-window, array, dynamic-programming Companies: amazon, google, bloomberg Level: swe2, swe3 Sliding Window (at most one zero): Sliding window allowing at most one 0 in window. Answer is max(window_size - 1) since we must delete one element. Count subarrays with exactly k odd numbers using prefix sum in O(n). Amazon, Google, Bloomberg interview question. Topics: sliding-window, hash-table, array, math Companies: amazon, google, bloomberg Level: swe2, swe3 Prefix Sum + Hash Map: Count prefix sums of (num % 2). For each prefix, look up (prefix - k) in map. Validate bracket string using a stack in O(n). Classic Amazon, Google, Meta easy interview question with Python solution. Topics: stack, string Companies: amazon, google, meta, bloomberg, microsoft Level: new-grad, swe2 Stack: Push opening brackets onto stack. For closing brackets, check if stack top is the matching opener. Design a min stack with O(1) getMin using dual stacks. Amazon, Google, Meta, Bloomberg medium interview question. Topics: stack, design Companies: amazon, google, meta, bloomberg, microsoft Level: swe2, swe3 Dual Stack: Maintain main stack and min_stack. Min stack stores the current minimum at each point. Push min to min_stack on each push. Evaluate RPN expression using a stack in O(n). Amazon, Google, Bloomberg, LinkedIn medium interview question. Topics: stack, array, math Companies: amazon, google, bloomberg, linkedin Level: swe2, swe3 Stack: Push numbers. On operator, pop two values, apply operation, push result. Final stack top is the answer. Find days until warmer temperature using monotonic stack in O(n). Amazon, Google, Bloomberg medium interview question. Topics: stack, array, monotonic-stack Companies: amazon, google, bloomberg, microsoft Level: swe2, swe3 Monotonic Stack: Stack of indices in decreasing temperature order. When current temp > stack top, pop and record gap. Find largest rectangle in histogram using monotonic stack in O(n). Amazon, Google, Bloomberg hard interview question. Topics: stack, array, monotonic-stack Companies: amazon, google, bloomberg, microsoft Level: swe3, senior Monotonic Stack: Maintain increasing stack of indices. When current bar is shorter, pop and compute area. Use sentinel 0 at start and end. Implement queue using two stacks with amortized O(1) operations. Amazon, Google easy design interview question. Topics: stack, queue, design Companies: amazon, google, microsoft, bloomberg Level: new-grad, swe2 Two Stacks (Amortized O(1)): Input stack for push. Output stack for pop/peek. Transfer all from input to output when output is empty. Implement stack using queues with O(n) push. Amazon, Google easy design interview question with Python solution. Topics: stack, queue, design Companies: amazon, google, microsoft Level: new-grad, swe2 Single Queue (rotate on push): After pushing new element, rotate queue (n-1 times) so new element is at the front. Find sliding window maximum using monotonic deque in O(n). Amazon, Google, Bloomberg hard interview question. Topics: stack, queue, sliding-window, array, monotonic-stack Companies: amazon, google, bloomberg, microsoft Level: swe3, senior Monotonic Deque: Maintain deque of indices in decreasing value order. Front is always the window max. Remove indices out of window. Find next greater element using monotonic stack in O(m+n). Amazon, Google, Bloomberg easy interview question. Topics: stack, array, hash-table, monotonic-stack Companies: amazon, google, bloomberg Level: new-grad, swe2 Monotonic Stack + Hash Map: Process nums2 with monotonic stack. Build a map from value to its next greater. Look up each nums1 element. Evaluate arithmetic expression with stack in O(n). Amazon, Google, Bloomberg medium interview question with Python solution. Topics: stack, string, math Companies: amazon, google, bloomberg, microsoft Level: swe2, swe3 Stack: Parse left to right. On + push num, on - push -num, on * or / pop stack top and push result. Sum stack at end. Find the single non-duplicate number using XOR in O(n) O(1). Classic Amazon, Google, Meta easy bit manipulation question. Topics: bit-manipulation, array Companies: amazon, google, meta, bloomberg Level: new-grad, swe2 XOR: XOR all elements. a XOR a = 0, a XOR 0 = a. All pairs cancel leaving the single element. Count 1 bits using Brian Kernighan's algorithm in O(k). Amazon, Google easy bit manipulation interview question. Topics: bit-manipulation Companies: amazon, google, bloomberg Level: new-grad, swe2 Brian Kernighan: n & (n-1) clears the lowest set bit. Count iterations until n becomes 0. Built-in / Shift: Count set bits by shifting right and checking LSB, or use bin(n).count("1"). Reverse 32 bits of an integer using bit shifting in O(32). Amazon, Google easy bit manipulation interview question. Topics: bit-manipulation Companies: amazon, google, bloomberg Level: new-grad, swe2 Bit by Bit: For each of 32 bits, shift result left by 1, add LSB of n, then shift n right by 1. Find missing number using math sum or XOR in O(n) O(1). Amazon, Google, Bloomberg easy interview question. Topics: bit-manipulation, math, array Companies: amazon, google, bloomberg, microsoft Level: new-grad, swe2 Math (Sum): Expected sum = n*(n+1)/2. Actual sum = sum(nums). Missing = expected - actual. XOR: XOR all indices 0..n with all values. Pairs cancel, missing index remains. Check if number is power of two using bit trick n & (n-1) in O(1). Amazon, Google easy bit manipulation question. Topics: bit-manipulation, math Companies: amazon, google, bloomberg Level: new-grad, swe2 Bit Trick: n > 0 and (n & (n-1)) == 0. Powers of 2 have exactly one set bit; n-1 has all lower bits set; AND is 0. Count set bits for 0..n using DP bit trick in O(n). Amazon, Google easy bit manipulation and DP question. Topics: bit-manipulation, dynamic-programming Companies: amazon, google, bloomberg Level: new-grad, swe2 DP with Bit Trick: dp[i] = dp[i >> 1] + (i & 1). The count for i equals count for i/2 plus the last bit of i. Add two integers without + using XOR and AND carry in O(1). Amazon, Google, Bloomberg medium bit manipulation question. Topics: bit-manipulation, math Companies: amazon, google, bloomberg Level: swe2, swe3 Bit Manipulation: XOR gives bits where exactly one is set (sum without carry). AND<<1 gives carry. Repeat until carry=0. Reverse integer digits with overflow check in O(log n). Amazon, Google, Bloomberg medium interview question. Topics: math Companies: amazon, google, bloomberg, microsoft Level: swe2, swe3 Math: Extract digits with mod 10. Build reversed number. Check 32-bit bounds before returning. Check if integer is a palindrome without string conversion. Amazon, Google easy math interview question. Topics: math Companies: amazon, google, bloomberg, microsoft Level: new-grad, swe2 Reverse Half: Negative or trailing-zero numbers are not palindromes. Reverse second half of digits and compare with first half. String Conversion: Convert to string and compare with its reverse. Convert integer to Roman numeral using greedy approach in O(1). Amazon, Google, Bloomberg medium interview question. Topics: math, string, hash-table Companies: amazon, google, bloomberg, microsoft Level: swe2, swe3 Greedy with Value Table: Table of values from 1000 to 1 including subtractive cases. Greedily subtract largest value, append symbol. Convert Roman numeral to integer using right-to-left scan in O(n). Amazon, Google easy math interview question. Topics: math, string, hash-table Companies: amazon, google, bloomberg, microsoft Level: new-grad, swe2 Right to Left Scan: Scan right to left. If current value < previous value, subtract; otherwise add. Convert Excel column title to number using base-26 in O(n). Amazon, Google easy math interview question. Topics: math, string Companies: amazon, google, bloomberg, microsoft Level: new-grad, swe2 Base-26 Conversion: Treat each char as a base-26 digit. A=1..Z=26. Accumulate result = result*26 + (ord(c)-64). Determine if a number is happy using hash set or Floyd's cycle detection in O(log n). Amazon, Google easy math question. Topics: math, hash-table, two-pointers Companies: amazon, google, bloomberg Level: new-grad, swe2 Hash Set for Cycle Detection: Compute sum of digit squares. If seen before, not happy. If reaches 1, happy. Floyd's Cycle Detection: Fast pointer moves two steps, slow moves one. If they meet at 1, happy. If they meet elsewhere, unhappy. Compute integer square root using binary search in O(log x). Amazon, Google easy interview question with Python solution. Topics: math, binary-search Companies: amazon, google, bloomberg, microsoft Level: new-grad, swe2 Binary Search: Binary search: find largest k where k*k <= x. Narrow range [0, x]. Find GCD of strings using math GCD of lengths in O(m+n). Amazon, Google easy math and string interview question. Topics: math, string Companies: amazon, google, bloomberg Level: new-grad, swe2 Math GCD: If str1+str2 == str2+str1, a GCD string exists. Its length is gcd(len(str1), len(str2)). Find the element appearing once in O(n) time O(1) space using XOR bit manipulation. Classic Amazon Google interview question. Topics: bit-manipulation, array, math Companies: amazon, google, microsoft, meta, bloomberg Level: new-grad, swe2 XOR Bit Manipulation: XOR all numbers together. Pairs cancel out (a^a=0) and 0^x=x leaves the single number. Math (2*sum(set) - sum): 2 * sum(set(nums)) - sum(nums) equals the single number because each duplicate is counted once in the set. Find the element appearing once when all others appear 3 times. Bit counting and state machine approaches in Python. Topics: bit-manipulation, array, math Companies: google, amazon, microsoft, bloomberg Level: swe2, swe3 Bit Count Modulo 3: For each of the 32 bit positions, count how many numbers have that bit set. If count % 3 != 0, the single number has that bit set. State Machine (ones, twos): Use two bitmasks: ones tracks bits seen once, twos tracks bits seen twice. When a bit is seen 3 times it resets to 0 in both. Find two numbers appearing once using XOR partitioning in O(n) time O(1) space. Google Amazon interview question. Topics: bit-manipulation, array, math Companies: google, amazon, microsoft Level: swe2, swe3 XOR Partitioning: XOR all to get a^b. Find a set bit in a^b and use it to split numbers into two groups, each containing one unique number. XOR each group. HashSet: Use a set: add elements not seen, remove if already present. What remains are the two unique numbers. Count set bits in an integer using Brian Kernighan algorithm and bit shifting. Classic bit manipulation interview question. Topics: bit-manipulation, math Companies: apple, microsoft, amazon, google Level: new-grad, swe2 Brian Kernighan Algorithm: n & (n-1) clears the lowest set bit. Count how many times until n becomes 0. Bit Check Each Position: Check each of the 32 bit positions by ANDing with 1 and right-shifting. Reverse bits of a 32-bit unsigned integer using bit manipulation. Apple Amazon interview question with complete Python solution. Topics: bit-manipulation, math Companies: apple, amazon, microsoft Level: new-grad, swe2 Bit by Bit Reversal: For each of 32 positions, take the LSB of n, add to result, shift n right and result left. Python String Reversal: Format as 32-bit binary string, reverse it, convert back to int. Find the missing number in range [0,n] using Gauss formula or XOR in O(n) time O(1) space. Amazon Microsoft interview question. Topics: bit-manipulation, math, array Companies: amazon, microsoft, google, bloomberg Level: new-grad, swe2 Gauss Sum Formula: Expected sum is n*(n+1)/2. Subtract actual sum to find missing number. XOR Approach: XOR all indices 0..n and all values. Each present number cancels its index; missing index remains. Check if a number is power of two in O(1) using bit trick n&(n-1)==0. Classic bit manipulation interview question. Topics: bit-manipulation, math, recursion Companies: amazon, google, microsoft Level: new-grad, swe2 Bit Trick: A power of two has exactly one bit set. n & (n-1) clears the lowest set bit; if result is 0, n was a power of two. Repeated Division: Repeatedly divide by 2. If we reach 1, it is a power of two. Count 1 bits for every number 0 to n in O(n) using DP relationship dp[i]=dp[i>>1]+(i&1). Topics: bit-manipulation, dynamic-programming, math Companies: amazon, google, microsoft, bloomberg Level: new-grad, swe2 DP with Right Shift: dp[i] = dp[i // 2] + (i % 2). Dividing by 2 right-shifts, LSB contributes 1 if odd. Brian Kernighan per element: For each number, repeatedly clear lowest bit to count set bits. Add two integers without + operator using XOR and carry bit manipulation. Amazon Google interview question. Topics: bit-manipulation, math Companies: amazon, google, microsoft, meta Level: swe2, swe3 Bit Manipulation with Carry: XOR gives bits that differ (sum without carry). AND<<1 gives carry. Repeat until carry is zero. Use mask for Python 32-bit handling. Recursive: Recursively compute sum and carry until no carry remains. Reverse digits of a 32-bit integer with overflow handling. Amazon Bloomberg interview question with two Python solutions. Topics: math Companies: amazon, bloomberg, apple, microsoft Level: new-grad, swe2 Pop and Push Digits: Extract digits from x using modulo, build reversed number, check 32-bit overflow. String Reversal: Convert to string, reverse, handle sign and leading zeros, check overflow. Check if integer is palindrome by reversing half the number. Amazon Microsoft Bloomberg interview question. Topics: math Companies: amazon, microsoft, bloomberg, apple Level: new-grad, swe2 Reverse Half the Number: Reverse the second half of x and compare with first half. Negative numbers and multiples of 10 (except 0) are not palindromes. String Conversion: Convert to string and check if it equals its reverse. Convert integer to Roman numeral using greedy approach. Amazon Bloomberg Microsoft interview question with complete Python solution. Topics: math, string-matching Companies: amazon, bloomberg, microsoft, uber Level: swe2, swe3 Greedy with Value-Symbol Table: Define value-symbol pairs including subtractive forms in descending order. Greedily subtract largest possible value. Digit by Digit Table: Pre-define Roman representations for each digit position (thousands, hundreds, tens, ones). Convert Roman numeral to integer using right-to-left scan. Amazon Google Bloomberg easy interview question. Topics: math, string-matching Companies: amazon, bloomberg, microsoft, apple, google Level: new-grad, swe2 Right to Left Scan: Scan right to left. If current symbol value is less than the maximum seen so far, subtract it; otherwise add it. Left to Right Peek Next: Scan left to right. If current value < next value, subtract current; otherwise add it. Convert Excel column title to number using base-26 arithmetic. Microsoft Amazon interview question. Topics: math Companies: microsoft, amazon, bloomberg Level: new-grad, swe2 Base-26 Conversion: Treat as base-26 number where A=1, B=2, ..., Z=26. Process each character left to right. functools.reduce: Use reduce to fold the base-26 accumulation over the string. Determine happy number using Floyd cycle detection or hashset. Amazon Microsoft Google interview question. Topics: math, fast-slow-pointers, hash-map Companies: amazon, microsoft, google, bloomberg Level: new-grad, swe2 Fast-Slow Pointers (Floyd): Treat the sequence as a linked list. Use slow/fast pointers to detect cycle. If fast reaches 1, happy. HashSet Cycle Detection: Track seen values in a set. If n becomes 1 return True; if n repeats return False. Compute integer square root using binary search or Newton method. Amazon Google Bloomberg interview question. Topics: math, binary-search Companies: amazon, google, bloomberg, microsoft Level: new-grad, swe2 Binary Search: Binary search in [0, x]. Find largest m where m*m <= x. Newton's Method: Newton's iteration: r = (r + x/r) / 2 converges to sqrt(x) quadratically. Implement GCD and LCM using Euclidean algorithm recursively and iteratively. Google Amazon math interview question. Topics: math, number-theory, recursion Companies: google, amazon, microsoft, bloomberg Level: new-grad, swe2 Euclidean Algorithm: gcd: repeatedly replace (a,b) with (b, a%b) until b=0. lcm: a*b//gcd(a,b). Recursive GCD: Recursive Euclidean: gcd(a,b) = a if b==0 else gcd(b, a%b). Count primes less than n using Sieve of Eratosthenes in O(n log log n). Classic math interview question. Topics: math, number-theory Companies: amazon, google, microsoft, bloomberg Level: swe2, swe3 Sieve of Eratosthenes: Create boolean array, mark all multiples of each prime p starting from p^2 as composite. Segmented Sieve (memory efficient): Use a standard sieve for small primes up to sqrt(n), then sieve segments of size sqrt(n). Implement pow(x,n) in O(log n) using recursive halving and iterative bit manipulation. Google Amazon interview question. Topics: math, recursion, divide-and-conquer, bit-manipulation Companies: google, amazon, microsoft, bloomberg, facebook Level: swe2, swe3 Recursive Fast Exponentiation: Halve n each step: if n even x^n=(x^2)^(n/2), if n odd multiply by x. Handle negative n. Iterative Bit Manipulation: Use bits of n to decide which powers of x to multiply. Square x each step, multiply result when bit is set. Multiply two large numbers represented as strings without converting to int. Amazon Google interview question. Topics: math, string-matching, array Companies: amazon, google, microsoft, bloomberg, facebook Level: swe2, swe3 Grade School Multiplication: Each pair of digits (i,j) contributes to positions (i+j, i+j+1) in the result array. Build array, handle carries, convert to string. Built-in Conversion (reference): Convert strings to int using ord arithmetic only, multiply, convert back without int(). Add two binary strings and return the sum as binary string. Amazon Google easy interview question. Topics: math, bit-manipulation, string-matching Companies: amazon, google, microsoft, bloomberg, apple Level: new-grad, swe2 Two Pointer from Right: Use pointers starting from end of each string. Add digits + carry, build result in reverse. Python int Conversion: Convert both binary strings to int using base 2, add, convert result back to binary string. Add two large numbers represented as strings using grade school algorithm. Amazon Google interview question. Topics: math, string-matching Companies: amazon, google, microsoft, bloomberg Level: swe2, swe3 Grade School Addition: Add digit by digit from right with carry, using ord to convert chars to ints. zip_longest approach: Use itertools.zip_longest to pair up reversed strings, add digits + carry. Count occurrences of digit 1 in all numbers from 0 to n using mathematical position analysis. Hard Google Amazon interview. Topics: math, number-theory, dynamic-programming Companies: google, amazon, bloomberg, microsoft Level: swe3, senior Mathematical Position Analysis: For each digit position p (1,10,100...), calculate how many 1s appear in that position across all numbers 0..n. Digit DP: Use digit DP counting 1s digit by digit with tight constraints. Find nth ugly number (factors 2,3,5) using three pointer DP in O(n). Google Amazon interview question. Topics: math, dynamic-programming, heap, two-pointers Companies: google, amazon, bloomberg, microsoft Level: swe2, swe3 Three Pointers DP: Maintain three pointers p2, p3, p5 into the ugly array. Each step take the minimum of dp[p2]*2, dp[p3]*3, dp[p5]*5. Min Heap: Use a min-heap. Pop the minimum, push *2, *3, *5 of popped value. Skip duplicates with a seen set. Find minimum perfect squares summing to n using DP and BFS. Google Amazon interview question with two Python solutions. Topics: dynamic-programming, bfs, math, number-theory Companies: google, amazon, microsoft, bloomberg Level: swe2, swe3 Dynamic Programming: dp[i] = minimum squares summing to i. For each i, try all perfect squares <= i. BFS Level by Level: Treat as shortest path: BFS level = number of squares used. Return level when n is reached. Implement merge sort from scratch in Python. Covers recursive divide-and-conquer approach with O(n log n) time complexity. Topics: sorting, divide-and-conquer, recursion Companies: google, amazon, microsoft, meta, bloomberg Level: new-grad, swe2 Recursive Merge Sort: Divide the array in half, recursively sort each half, then merge the two sorted halves by comparing elements one at a time. In-place Merge Sort: Sort in place by modifying the input array directly during merge, using O(log n) stack space for recursion. Implement quicksort with randomized pivot in Python. Covers Lomuto and three-way partition approaches with complexity analysis. Topics: sorting, divide-and-conquer, recursion Companies: google, amazon, meta, microsoft, apple Level: new-grad, swe2, swe3 Randomized QuickSort (Lomuto partition): Pick a random pivot, swap it to the end, then partition the array so all elements less than pivot are on the left. Recurse on both sides. Three-Way Partition (Dutch Flag): Use Dutch National Flag three-way partition to handle duplicates efficiently. Partition into <pivot, ==pivot, >pivot. Implement heap sort in Python using a max-heap. In-place O(n log n) sorting with detailed heapify explanation. Topics: sorting, heap Companies: microsoft, amazon, google, bloomberg Level: new-grad, swe2 Heap Sort (in-place max-heap): Build a max-heap in-place with O(n) heapify. Then repeatedly swap root (max) with last element, reduce heap size, and sift down. Find the kth largest element using min-heap O(n log k) and quickselect O(n). Top Amazon, Google, Meta interview question. Topics: heap, sorting, divide-and-conquer Companies: amazon, google, meta, microsoft, apple, uber, linkedin Level: swe2, swe3 Min-Heap of size k: Maintain a min-heap of size k. For each element, push it. If heap exceeds k, pop the minimum. The root is always the kth largest. Quickselect: Use quickselect: partition around a random pivot. If the pivot lands at position k-1 from the end, it is the answer. Recurse only on the relevant partition. Sort colors (0,1,2) in one pass using Dutch National Flag algorithm with three pointers. Classic Amazon and Microsoft interview question. Topics: array, sorting, two-pointers, dutch-flag Companies: amazon, microsoft, google, meta, bloomberg, uber Level: new-grad, swe2 Dutch National Flag (one pass): Use three pointers: low (boundary of 0s), mid (current), high (boundary of 2s). Swap 0s left and 2s right while advancing mid. Two-pass count sort: Count occurrences of 0, 1, 2, then overwrite the array. Simple but two passes. Merge overlapping intervals in Python with sort and scan approach. O(n log n) solution for Google, Amazon, Meta interviews. Topics: array, sorting, interval Companies: google, amazon, microsoft, meta, bloomberg, uber, linkedin, apple Level: swe2, swe3 Sort and Merge: Sort intervals by start time. Iterate through and merge the current interval with the last interval in result if they overlap (start <= last end). Insert and merge a new interval into a sorted non-overlapping interval list. O(n) linear scan solution for Google and Amazon interviews. Topics: array, interval, binary-search Companies: google, amazon, microsoft, linkedin, bloomberg Level: swe2, swe3 Linear Scan Three Phases: Add all intervals ending before new interval starts. Merge all overlapping intervals. Add all remaining intervals. Binary search in a rotated sorted array in O(log n). Essential Amazon, Google, Apple interview question with clear Python solution. Topics: binary-search, array Companies: amazon, google, microsoft, meta, apple, bloomberg, uber Level: swe2, swe3 Binary Search on Rotated Array: At each step, determine which half is sorted. If the target lies in the sorted half, search there. Otherwise search the other half. Find a peak element in O(log n) using binary search. Google interview question with detailed explanation. Topics: binary-search, array Companies: google, microsoft, amazon, meta Level: swe2, swe3 Binary Search: If nums[mid] < nums[mid+1], slope is going up so peak is to the right. Otherwise slope is going down (or mid is peak) so peak is to the left or at mid. Search a sorted 2D matrix in O(log(mn)) by treating it as a 1D array. Amazon and Microsoft interview question. Topics: binary-search, matrix, array Companies: amazon, microsoft, google, bloomberg, apple Level: swe2, swe3 Binary Search (treat as 1D): Treat the m*n matrix as a sorted 1D array. Binary search on indices 0 to m*n-1. Convert mid index to row=mid//n, col=mid%n. Find median of two sorted arrays in O(log(min(m,n))) using binary search partition. Hard Google and Amazon interview problem. Topics: binary-search, divide-and-conquer, array Companies: google, amazon, microsoft, meta, apple, uber, bloomberg Level: swe3, senior, staff Binary Search on partition: Binary search on the smaller array to find partition point. Left side of both arrays combined = half of total elements. Median comes from max of left parts and min of right parts. Merge then find median (O(m+n)): Merge both sorted arrays fully, then return the middle element(s). Simpler but does not meet the O(log(m+n)) constraint. Find minimum element in rotated sorted array in O(log n) with binary search. Amazon, Google interview question. Topics: binary-search, array Companies: amazon, microsoft, google, apple, bloomberg Level: swe2, swe3 Binary Search: Binary search: if nums[mid] > nums[right], minimum is in right half. Otherwise minimum is in left half (including mid). Calculate researcher h-index in Python using sort or counting sort. Google and LinkedIn interview question with O(n) solution. Topics: array, sorting, binary-search Companies: google, amazon, bloomberg, linkedin Level: swe2, swe3 Sort descending: Sort descending. h is the largest index+1 where citations[i] >= i+1. After sort, citations[i] >= i+1 means at least i+1 papers with >= i+1 citations. Counting Sort O(n): Use bucket counting: bucket[i] = papers with exactly i citations (cap at n). Scan from right; accumulate count; first position where count >= i is h-index. Find minimum conference rooms needed with min-heap approach. O(n log n) solution for Amazon, Google, Meta interviews. Topics: heap, sorting, interval, greedy Companies: amazon, google, microsoft, meta, bloomberg, uber, linkedin Level: swe2, swe3, senior Min-Heap of end times: Sort by start. Maintain a min-heap of end times (rooms in use). For each meeting, if the earliest-ending room ends before this starts, reuse it. Otherwise allocate a new room. Two sorted arrays (events): Create separate sorted arrays of start times and end times. Use two pointers: when a new meeting starts, if earliest end has passed, decrement rooms needed. Arrange numbers to form largest number using custom comparator sort. Amazon and Google interview question. Topics: sorting, greedy, strings Companies: amazon, microsoft, google, bloomberg, uber Level: swe2, swe3 Custom Comparator Sort: Convert numbers to strings. Custom sort: a comes before b if str(a)+str(b) > str(b)+str(a). Join sorted strings and handle leading zeros. Count smaller elements to the right using merge sort in O(n log n). Hard Google and Amazon interview problem. Topics: sorting, divide-and-conquer, binary-search Companies: google, amazon, meta, microsoft Level: swe3, senior Merge Sort with index tracking: Merge sort on (value, original_index) pairs. During merge, whenever a right-half element is placed before a left-half element, all remaining left-half elements get +1 count. Sort a linked list in O(n log n) using merge sort with slow/fast pointer split. Amazon and Google interview question. Topics: linked-list, sorting, divide-and-conquer, two-pointers Companies: amazon, microsoft, google, meta, bloomberg Level: swe2, swe3 Merge Sort (top-down recursive): Find midpoint with slow/fast pointers, split into two halves, sort each half recursively, then merge the two sorted lists. Find top k frequent elements using heap O(n log k) or bucket sort O(n). Amazon, Google, Meta interview question. Topics: heap, hash-map, sorting, bucket-sort Companies: amazon, google, meta, microsoft, bloomberg, uber, apple Level: swe2, swe3 Min-Heap: Count frequency of each element. Maintain min-heap of size k keyed by frequency. Final heap contains the k most frequent elements. Bucket Sort O(n): Count frequencies. Create frequency buckets where bucket[i] holds all elements with frequency i. Read from highest bucket downward until k elements collected. Find top k frequent words sorted by frequency then lexicographically using a min-heap. Amazon and Google interview question. Topics: heap, hash-map, sorting, strings Companies: amazon, google, microsoft, bloomberg, apple Level: swe2, swe3 Min-Heap with negated frequency: Count frequencies. Use a min-heap of (-frequency, word) tuples. Python heaps are min-heaps; negating frequency makes highest frequency float up. Pop when size > k. Find k closest elements to x in sorted array using binary search on window boundary. Google and Amazon interview question. Topics: binary-search, array, two-pointers, sliding-window Companies: google, amazon, microsoft, linkedin Level: swe2, swe3 Binary Search on window left boundary: Binary search for the left start of the k-element window. At each mid, compare distance of arr[mid] vs arr[mid+k] to x to decide which side the window should be on. Find kth smallest in sorted matrix using binary search or min-heap. Google and Goldman Sachs interview question. Topics: binary-search, heap, matrix Companies: google, amazon, microsoft, goldman-sachs, bloomberg Level: swe3, senior Binary Search on value: Binary search on answer in range [matrix[0][0], matrix[n-1][n-1]]. Count elements <= mid using sorted row property. Find smallest value with count >= k. Min-Heap k-way merge: Push first element of each row into min-heap. Pop k times; each pop, push the next element in same row. Find k pairs with smallest sums from two sorted arrays using min-heap. Google interview question with O(k log k) solution. Topics: heap, array, k-way-merge Companies: google, amazon, microsoft, bloomberg Level: swe3, senior Min-Heap: Initialize heap with (sum, i=0..min(k,len(nums1)), j=0). Pop smallest, record pair, push next j for same i. Sort string characters by frequency using Counter and heap. Amazon and Google interview question with clean O(n log n) solution. Topics: hash-map, heap, sorting, strings Companies: amazon, google, microsoft, bloomberg Level: new-grad, swe2 Counter + Sort: Count character frequencies. Sort unique characters by frequency descending. Build result by repeating each character by its frequency count. Reorder array into wiggle pattern using sort and interleave. Google and Amazon interview question. Topics: array, sorting, dutch-flag Companies: google, amazon, microsoft Level: swe3, senior Sort + interleave: Sort array. Place upper half (larger values) at odd indices and lower half (smaller) at even indices, both from back to front to handle duplicate medians. Assign relative ranks and medals to athletes by score. Easy sorting problem for Amazon and Microsoft interviews. Topics: array, sorting, heap Companies: amazon, microsoft, bloomberg Level: new-grad, swe2 Sort by index: Create list of (score, index) pairs, sort by score descending. Assign medal or rank string to each index in that order. Find all unique triplets summing to zero using sort and two pointers in O(n^2). Amazon, Google, Meta interview question. Topics: array, two-pointers, sorting Companies: amazon, google, meta, microsoft, apple, bloomberg, uber, adobe Level: swe2, swe3 Sort + Two Pointers: Sort the array. For each index i, use two pointers left=i+1 and right=n-1. Move pointers based on sum. Skip duplicates by advancing past equal values. Find all unique quadruplets summing to target using nested loops and two pointers. Amazon and Google interview question. Topics: array, two-pointers, sorting Companies: amazon, google, microsoft, bloomberg Level: swe2, swe3 Sort + Two Nested Loops + Two Pointers: Sort array. Two outer loops fix first two elements, two pointers scan remaining. Skip duplicates at all four positions. Find maximum water container area using two pointers in O(n). Amazon, Google, Meta, Apple interview question. Topics: array, two-pointers, greedy Companies: amazon, google, meta, microsoft, apple, bloomberg, uber, adobe Level: swe2, swe3 Two Pointers: Start with left=0, right=n-1. Area = min(height[left], height[right]) * (right-left). Move the pointer with shorter height inward to potentially find larger area. Compute trapped rain water in O(n) time O(1) space using two pointers. Hard Amazon, Google, Meta interview problem. Topics: array, two-pointers, stack, dynamic-programming Companies: amazon, google, microsoft, meta, apple, bloomberg, uber, goldman-sachs Level: swe3, senior Two Pointers O(1) space: Two pointers from each end. Track max_left and max_right. The side with smaller max determines the water at that position. Move that pointer inward. Precompute left/right max arrays: Precompute max height to the left and right of each position. Water at each position is min(left_max, right_max) - height[i]. Find minimum window substring using sliding window and frequency maps in O(|s|+|t|). Hard Amazon, Google, Meta interview. Topics: sliding-window, hash-map, two-pointers, strings Companies: amazon, google, meta, microsoft, bloomberg, uber, linkedin Level: swe3, senior Sliding Window with Frequency Map: Expand window right pointer. Once all chars of t covered, try shrinking from left. Track "formed" count (chars meeting their required frequency). Update min window whenever formed == required. Find longest substring without repeating characters using sliding window in O(n). Classic Amazon, Google, Meta interview question. Topics: sliding-window, hash-map, strings, two-pointers Companies: amazon, google, meta, microsoft, apple, bloomberg, uber, adobe Level: new-grad, swe2 Sliding Window with Set: Expand right. If character already in window set, shrink left until it is removed. Track max window length. Sliding Window with HashMap (O(n) jumps): Store last seen index of each character. When a repeat is found, jump left pointer directly to last_seen[char]+1 instead of shrinking one step at a time. Check if string contains permutation of s1 using fixed sliding window with frequency arrays. Amazon and Microsoft interview question. Topics: sliding-window, hash-map, strings, two-pointers Companies: amazon, microsoft, google, bloomberg, meta Level: swe2, swe3 Fixed Sliding Window with frequency arrays: Maintain frequency count arrays of size 26 for s1 and current window. Slide window of length len(s1) across s2, updating counts. If arrays match, return True. Find all anagram start indices using sliding window in O(|s|). Amazon, Google, Meta interview question. Topics: sliding-window, hash-map, strings Companies: amazon, google, meta, microsoft, bloomberg Level: swe2, swe3 Sliding Window with "matches" counter: Track count of characters with matching frequencies between window and p. When matches == 26, window is an anagram. Slide and update matches count. Find longest substring after k replacements using sliding window in O(n). Amazon and Google interview question. Topics: sliding-window, hash-map, strings, two-pointers Companies: amazon, google, microsoft, bloomberg, uber Level: swe2, swe3 Sliding Window: Expand window right. Valid if (window_size - max_char_count) <= k. When invalid, slide window right by moving left pointer. Track global max_count (never decrease it since smaller windows cannot give better answer). Maximize consecutive ones with k zero flips using sliding window in O(n). Google and Amazon interview question. Topics: sliding-window, array, two-pointers Companies: google, amazon, microsoft, bloomberg Level: swe2, swe3 Sliding Window: Expand right. Count zeros in window. When zeros > k, shrink left until zeros <= k. Track max window size. Find max fruits with 2 baskets using sliding window with at most 2 distinct types. Amazon and Google interview question. Topics: sliding-window, hash-map, array Companies: amazon, google, microsoft Level: swe2, swe3 Sliding Window - at most 2 distinct: Sliding window maintaining at most 2 distinct fruit types in a frequency map. When map has 3 types, shrink left until one type is removed. Count subarrays with exactly k distinct integers using at-most trick with sliding window. Hard Google interview question. Topics: sliding-window, hash-map, array Companies: google, amazon, meta Level: swe3, senior Sliding Window: exact = atMost(k) - atMost(k-1): Subarrays with exactly k distinct = subarrays with at most k distinct - subarrays with at most k-1 distinct. The atMost function uses a sliding window. Find minimum subarray with sum >= target using sliding window in O(n). Amazon and Google interview question. Topics: sliding-window, array, binary-search, two-pointers Companies: amazon, google, microsoft, bloomberg, linkedin Level: swe2, swe3 Sliding Window: Expand right adding to current sum. Whenever sum >= target, try shrinking from left and update minimum length. Find longest subarray of 1s after deleting one element using sliding window. Amazon and Google interview question. Topics: sliding-window, array, dynamic-programming Companies: amazon, google, microsoft Level: swe2, swe3 Sliding Window with at most 1 zero: Sliding window allowing at most 1 zero. Result is max window length - 1 (one element must be deleted). Count subarrays with exactly k odd numbers using prefix sum in O(n). Amazon and Google interview question. Topics: sliding-window, prefix-sum, array Companies: amazon, google, bloomberg Level: swe2, swe3 Prefix Sum: Track cumulative odd count. For each position, if (odd_count - k) seen before, those starting positions give valid subarrays. Store prefix odd counts in a hash map. Count subarrays with product less than k using sliding window in O(n). Amazon and Google interview question. Topics: sliding-window, array, two-pointers Companies: amazon, google, microsoft, bloomberg Level: swe2, swe3 Sliding Window: Expand right, multiply product. When product >= k, shrink left by dividing. Count of new valid subarrays ending at right = right - left + 1. Minimum edge removals to reduce x to zero using complement sliding window. Google and Amazon interview question. Topics: sliding-window, array, prefix-sum, hash-map Companies: google, amazon, microsoft Level: swe2, swe3 Sliding Window on complement: Instead of removing from edges, find the longest subarray in the middle with sum = total - x. Answer is n minus that length. Find maximum sum subarray with unique elements using sliding window in O(n). Amazon and Google interview question. Topics: sliding-window, hash-map, array Companies: amazon, google, microsoft Level: swe2, swe3 Sliding Window with Set: Maintain a set of current window elements and running sum. When a duplicate is found, remove elements from the left until the duplicate is gone. Count substrings with all three characters a, b, c using last-seen index trick in O(n). Google interview question. Topics: sliding-window, hash-map, strings Companies: google, amazon, bloomberg Level: swe2, swe3 Sliding Window: Track last seen index of each of a, b, c. For each right position, the number of valid subarrays ending at right equals min(last_a, last_b, last_c) + 1. Find minimum replacement window to balance QWER string using sliding window. Google interview question. Topics: sliding-window, strings, two-pointers Companies: google, amazon Level: swe3, senior Sliding Window: Count frequencies. Slide a window: outside window, all character counts must be <= n/4. Shrink left when possible. Track minimum valid window size. Compute sliding window median using two heaps with lazy deletion in O(n log k). Hard Google and Amazon interview problem. Topics: sliding-window, heap, two-heaps Companies: google, amazon, meta, bloomberg Level: senior, staff Two Heaps with Lazy Deletion: Maintain max-heap (lower half) and min-heap (upper half). Use lazy deletion: track counts of elements to remove. Balance heaps after each slide. Median comes from heap tops. Maximize card points from edges using complement sliding window. Amazon and Google interview question. Topics: sliding-window, array, prefix-sum Companies: amazon, google, microsoft Level: swe2, swe3 Sliding Window on middle subarray: Total - minimum window sum of size (n-k). Slide a window of size n-k and find the minimum sum. Answer is total - that minimum. Find longest subarray with max-min <= limit using monotonic deques. Google and Amazon interview question. Topics: sliding-window, deque, monotonic-stack Companies: google, amazon, meta Level: swe3, senior Sliding Window with Two Deques: Maintain two deques: max_deque (decreasing) and min_deque (increasing). Max-min gives range of window. When range > limit, shrink left, removing from deques if they point to left index. Maximize satisfied customers using sliding window on grumpy minutes. Amazon and Google interview question. Topics: sliding-window, array Companies: amazon, google, bloomberg Level: swe2, swe3 Sliding Window: Base satisfied customers when not grumpy. Add sliding window of size minutes to find maximum extra customers gained (grumpy minutes converted). Result = base + max_extra. Find minimum k-bit flips to make all ones using greedy sliding window. Hard Google interview problem. Topics: sliding-window, array, greedy, bit-manipulation Companies: google, amazon, meta Level: senior, staff Sliding Window with flip tracker: Use a deque to track flip endpoints. For each position, current flip state = len(deque) % 2. If flip needed (nums[i] XOR flips == 0), flip and add end position. If window expired, pop from deque. Validate matching parentheses using a stack in O(n). Classic Amazon, Google, Meta interview question. Topics: stack, strings Companies: amazon, google, meta, microsoft, bloomberg, apple, uber Level: new-grad, swe2 Stack: Use a stack. Push open brackets. For each closing bracket, check if the top of the stack is the corresponding open bracket. If stack is empty or mismatch, return False. Design a stack with O(1) push, pop, top, and getMin. Classic Amazon, Google, Apple interview question. Topics: stack, design Companies: amazon, google, microsoft, meta, bloomberg, apple Level: new-grad, swe2 Auxiliary min stack: Maintain two stacks: main stack and min_stack. min_stack[i] = minimum of all elements up to position i. Push to both; pop from both; getMin returns min_stack top. Single stack storing (val, min) pairs: Store tuples (value, current_min) in a single stack. Each push records the running minimum. Evaluate RPN arithmetic expression using a stack in O(n). Amazon, Microsoft, Bloomberg interview question. Topics: stack, array, math Companies: amazon, microsoft, bloomberg, google, linkedin Level: swe2, swe3 Stack: Iterate tokens. Push numbers onto stack. For each operator, pop two operands, compute result, push back. Final stack element is the answer. Find days until warmer temperature using monotonic stack in O(n). Amazon, Google, Microsoft interview question. Topics: stack, array, monotonic-stack Companies: amazon, google, microsoft, bloomberg, uber, meta Level: swe2, swe3 Monotonic Stack: Maintain a monotonic decreasing stack of indices. For each day, pop all indices where current temperature is warmer; record the wait. Push current index. Find largest rectangle in histogram using monotonic stack in O(n). Hard Amazon, Google, Goldman Sachs interview problem. Topics: stack, array, monotonic-stack Companies: amazon, google, microsoft, meta, bloomberg, goldman-sachs Level: swe3, senior, staff Monotonic Stack: Maintain a monotonic increasing stack of (index, height) pairs. When a shorter bar is encountered, pop taller bars and compute their maximum rectangles using the current index as the right boundary. Implement FIFO queue using two stacks with amortized O(1) operations. Amazon and Microsoft interview design question. Topics: stack, queue, design Companies: amazon, microsoft, google, bloomberg Level: new-grad, swe2 Two Stacks with lazy transfer: Push always goes to in_stack. Pop/peek: if out_stack is empty, transfer all from in_stack to out_stack. Then operate on out_stack. Implement LIFO stack using queues with rotation approach. Amazon and Google interview design question. Topics: stack, queue, design Companies: amazon, google, microsoft Level: new-grad, swe2 One Queue with rotation: Push x to queue, then rotate all previous elements to the back (dequeue and enqueue n-1 times). Now x is at the front, simulating LIFO. Find sliding window maximum using monotonic deque in O(n). Hard Amazon, Google, Meta interview problem. Topics: deque, sliding-window, monotonic-stack, array Companies: amazon, google, meta, microsoft, bloomberg, uber Level: swe3, senior Monotonic Deque: Maintain a deque of indices with decreasing values. Front is always the max of current window. Remove front when it falls out of window. Remove from back when adding larger elements. Find next greater element for each number using monotonic stack and hash map in O(n). Amazon interview question. Topics: stack, array, hash-map, monotonic-stack Companies: amazon, microsoft, bloomberg Level: new-grad, swe2 Monotonic Stack + Hash Map: Compute next greater element for each element in nums2 using a monotonic stack. Store results in a hash map. Answer for each element of nums1 is a lookup. Find next greater element in circular array using monotonic stack with double pass. Amazon and Google interview question. Topics: stack, array, monotonic-stack Companies: amazon, google, microsoft, bloomberg Level: swe2, swe3 Monotonic Stack with 2x pass: Iterate 2n indices. Use i % n for circular indexing. Monotonic decreasing stack stores indices. When current > stack top element, pop and record next greater. Evaluate arithmetic expression with parentheses using a stack in O(n). Hard Google, Amazon interview problem. Topics: stack, strings, math Companies: google, amazon, microsoft, bloomberg, meta Level: swe3, senior Stack for parentheses: Track current result and sign. On "(", push current result and sign to stack, reset. On ")", pop saved result and sign and combine. Accumulate number before processing operator. Evaluate expression with +, -, *, / using stack in O(n). Amazon, Google, Meta interview question. Topics: stack, strings, math Companies: amazon, google, microsoft, bloomberg, meta, uber Level: swe2, swe3 Stack with operator handling: Iterate through string building current number. At each operator (or end), apply the previous operator to the current number: push for +/-, compute immediately for */. Sum the stack. Find lexicographically smallest string after removing duplicates using greedy monotonic stack. Google interview question. Topics: stack, greedy, strings, monotonic-stack Companies: google, amazon, meta Level: swe3, senior Greedy Monotonic Stack: Count last occurrences. Maintain stack (result). For each char: if already in stack, skip. Else pop stack top while top > current char AND top appears again later. Push current char. Find smallest number after removing k digits using greedy monotonic stack. Google and Amazon interview question. Topics: stack, greedy, strings, monotonic-stack Companies: google, amazon, microsoft, bloomberg Level: swe2, swe3 Greedy Monotonic Stack: Maintain monotonic increasing stack. For each digit, pop the stack top when it is larger than current digit and k > 0. Append current digit. After all digits, remove remaining k from end. Strip leading zeros. Detect 132 pattern in array using monotonic stack from right in O(n). Google and Amazon interview question. Topics: stack, array, monotonic-stack Companies: google, amazon, microsoft Level: swe3, senior Monotonic Stack from right: Scan right to left. Maintain a decreasing stack. Whenever we pop (current > stack top), that popped value is "k" (the middle). If we ever find a value smaller than k, we found nums[i] < k < nums[j]. Compute score of balanced parentheses string using a stack in O(n). Google and Bloomberg interview question. Topics: stack, strings Companies: google, amazon, bloomberg Level: swe2, swe3 Stack: Push 0 onto stack for each "(". For each ")", if top is 0 it was "()" so replace with 1; else pop, double it, add to new top (cumulative at that level). Simulate asteroid collisions using a stack in O(n). Amazon and Google interview question. Topics: stack, array Companies: amazon, google, microsoft, bloomberg Level: swe2, swe3 Stack: Push each asteroid. If current is negative and top is positive, they collide. Pop the stack if current wins. If equal, both explode. Current is destroyed if stack top wins. Compute stock price span online using monotonic stack with O(1) amortized per call. Amazon and Google interview question. Topics: stack, design, monotonic-stack Companies: amazon, google, microsoft, bloomberg Level: swe2, swe3 Monotonic Stack: Stack of (price, span) pairs, monotonically decreasing by price. When new price >= top price, pop and add span. Push (price, total_span). Return total_span. Compute sum of subarray minimums using contribution technique with monotonic stack in O(n). Amazon and Google interview question. Topics: stack, array, monotonic-stack, dynamic-programming Companies: amazon, google, meta, microsoft Level: swe3, senior Monotonic Stack - contribution technique: For each element arr[i], find the number of subarrays where it is the minimum: left_count = distance to previous smaller, right_count = distance to next smaller or equal. Contribution = arr[i] * left_count * right_count. Find maximal rectangle in binary matrix using histogram and monotonic stack. Hard Amazon, Google interview problem. Topics: stack, matrix, array, dynamic-programming, monotonic-stack Companies: amazon, google, microsoft, meta, bloomberg Level: swe3, senior, staff Histogram + Monotonic Stack: Build cumulative height histogram row by row (height[j] = consecutive 1s above, reset to 0 on "0"). Apply largest rectangle in histogram algorithm on each row. Count car fleets arriving at destination using sort and stack in O(n log n). Amazon and Google interview question. Topics: stack, array, sorting, monotonic-stack Companies: amazon, google, microsoft Level: swe2, swe3 Sort + Stack: Sort cars by position descending. Compute time to target for each. Use a stack: if current car arrives faster than stack top (closer car), they merge (same fleet, current does not add). Else push. Decode encoded string with k[encoded_string] format using two stacks. Amazon, Google, Bloomberg interview question. Topics: stack, strings, recursion Companies: amazon, google, microsoft, bloomberg, meta Level: swe2, swe3 Two-stack approach: Maintain a count_stack and string_stack. On digit, accumulate count. On "[", push current string and count to stacks, reset. On "]", pop count and base, repeat current and concatenate. Find maximum width ramp using prefix minimum stack and right scan in O(n). Google interview question. Topics: stack, array, two-pointers, monotonic-stack Companies: google, amazon Level: swe3, senior Monotonic Stack + Right Scan: Build decreasing stack of indices (prefix minimums, left candidates). Then scan right to left: for each j, pop stack while nums[stack.top] <= nums[j] and record j - stack.top. Count visible people in queue using monotonic stack scan from right. Hard Google and Amazon interview problem. Topics: stack, array, monotonic-stack Companies: google, amazon, meta Level: swe3, senior Monotonic Stack from right: Scan right to left. Maintain a decreasing monotonic stack. For each person i, pop all shorter people from stack (they are visible to i). The first taller person in the stack (if any) is also visible. Count = pops + (1 if stack non-empty). Find minimum insertions to make parentheses string valid using counter in O(n). Amazon and Google interview question. Topics: stack, strings, greedy Companies: amazon, google, bloomberg Level: swe2, swe3 Greedy Counter: Track open (unmatched opens) and close (unmatched closes). For "(" increment open. For ")" if open > 0 decrement open (matched), else increment close. Answer = open + close. Find kth largest element using min-heap of size k. Amazon, Google, Meta interview question with heap focus. Topics: heap, sorting Companies: amazon, google, meta, microsoft, apple, bloomberg Level: swe2, swe3 heapq.nlargest: Use heapq.nlargest which internally maintains a min-heap of size k, returning the kth largest element as heap[0]. Manual min-heap of size k: Build heap manually, pushing each element and popping when size exceeds k. The heap root is the kth largest. Find streaming median using two heaps (max + min) with O(log n) insert, O(1) median. Amazon, Google, Meta hard interview. Topics: heap, two-heaps, design, sorting Companies: amazon, google, microsoft, meta, bloomberg, apple Level: swe3, senior Two Heaps (max-heap + min-heap): lo is a max-heap (negated in Python) for the lower half. hi is a min-heap for the upper half. Always maintain len(lo) >= len(hi). On add: push to lo first, then balance. Merge k sorted linked lists using min-heap O(n log k) or divide and conquer. Amazon, Google, Meta hard interview. Topics: heap, linked-list, k-way-merge, divide-and-conquer Companies: amazon, google, microsoft, meta, bloomberg, apple, uber Level: swe3, senior Min-Heap: Initialize heap with (val, index, node) for each list head. Pop min, attach to result, push next node from same list. Use index as tiebreaker. Divide and Conquer: Recursively merge lists in pairs (like merge sort). Each level merges n total nodes across k/2 pairs, log k levels total. Minimize CPU intervals for task scheduling with cooldown using formula or heap simulation. Amazon, Google, Meta interview. Topics: heap, greedy, hash-map, array Companies: amazon, google, microsoft, meta, bloomberg, uber Level: swe2, swe3 Math formula: Count task frequencies. The minimum time is max(len(tasks), (max_freq-1)*(n+1) + count_of_tasks_with_max_freq). The formula accounts for idles between most frequent tasks. Max-Heap Simulation: Simulate scheduling: use a max-heap (negated freq). Each cycle of n+1, pick the most frequent tasks, reduce counts. Count total time including any idles. Rearrange string so no two adjacent characters are equal using max-heap. Amazon and Google interview question. Topics: heap, greedy, hash-map, strings Companies: amazon, google, microsoft, bloomberg Level: swe2, swe3 Max-Heap: Count frequencies. If max_freq > (n+1)//2, impossible. Else use max-heap: pop two most frequent at a time, append both, push back if remaining count > 0. Find k closest points to origin using max-heap O(n log k) or sort O(n log n). Amazon, Google, Meta interview question. Topics: heap, array, sorting, divide-and-conquer Companies: amazon, google, meta, microsoft, uber, linkedin, bloomberg Level: swe2, swe3 Max-Heap of size k: Use a max-heap of size k (negate distance for Python min-heap). For each point, if heap is smaller than k push it. Otherwise if distance < heap max, replace. Return heap elements. Sort by distance: Sort all points by their squared Euclidean distance (no need for sqrt). Return the first k. Find smallest range covering elements from k sorted lists using min-heap. Hard Google and Amazon interview problem. Topics: heap, array, sorting, k-way-merge, sliding-window Companies: google, amazon, meta, bloomberg Level: senior, staff Min-Heap + global max tracking: Initialize heap with first element of each list. Track current_max. Pop min, update range [min, max] if better, push next from same list. Stop when any list exhausted. Find nth ugly number using three pointers DP in O(n) or min-heap. Google and Amazon interview question. Topics: heap, dynamic-programming, math Companies: google, amazon, microsoft, bloomberg Level: swe2, swe3 Dynamic Programming with three pointers: Maintain dp array and three pointers for factors 2, 3, 5. Each step, next ugly = min of the three candidates. Advance pointer(s) that produced the minimum. Min-Heap: Use a min-heap initialized with 1. Pop the smallest, push its 2x, 3x, 5x multiples if not seen. Return after n pops. Find nth super ugly number with custom primes using k-pointer DP in O(nk). Google interview question. Topics: heap, dynamic-programming, array Companies: google, amazon Level: swe3, senior DP with k pointers: Generalize ugly number II: maintain one pointer per prime. At each step, next = min of dp[pointers[i]] * primes[i]. Advance all pointers that produced the min. Maximize capital for IPO using greedy two-heap approach. Hard Amazon and Google interview problem. Topics: heap, greedy, sorting, two-heaps Companies: amazon, google, microsoft Level: swe3, senior Two Heaps (min by capital + max by profit): Sort projects by capital into a min-heap. Maintain a max-heap of profits for affordable projects. For each of k rounds: push all affordable projects to max-heap, pop highest profit, add to w. Find furthest building using greedy ladder/bricks allocation with min-heap. Amazon and Google interview question. Topics: heap, greedy, array Companies: amazon, google, microsoft, bloomberg Level: swe2, swe3 Min-Heap for ladder climbs: Greedily allocate ladders to the largest climbs. Maintain a min-heap of size ladders tracking climbs assigned to ladders. When heap is full and new climb comes in, reassign the smallest ladder-climb to bricks if possible. Simulate single-threaded CPU task scheduling with min-heap in O(n log n). Amazon and Google interview question. Topics: heap, sorting, array Companies: amazon, google, microsoft, bloomberg Level: swe3, senior Min-Heap Simulation: Sort tasks by enqueue time. Simulate CPU: maintain current time and min-heap of (processing_time, index). At each step, push all tasks with enqueue_time <= current_time. Pop shortest, update current_time. Solve the skyline problem using event-based max-heap in O(n log n). Hard Google and Amazon interview problem. Topics: heap, divide-and-conquer, sorting, binary-search Companies: google, amazon, microsoft, bloomberg, apple Level: senior, staff Event-based Max-Heap: Create events: (x, -h) for start and (x, h) for end. Sort events (end before start at same x). Maintain a max-heap of active heights. When max height changes, add to result. Find employee free time by merging intervals and detecting gaps. Hard Amazon, Google, Airbnb interview problem. Topics: heap, interval, sorting, k-way-merge Companies: amazon, google, bloomberg, airbnb Level: swe3, senior Flatten, Sort, Find Gaps: Collect all intervals from all employees, sort by start time. Merge overlapping intervals, then find gaps between consecutive merged intervals. Find minimum cost to hire k workers using ratio sort and max-heap. Hard Google interview problem. Topics: heap, greedy, sorting, two-heaps Companies: google, amazon, meta Level: senior, staff Sort by ratio + max-heap for quality sum: Sort workers by wage/quality ratio. For each worker as the "captain" (highest ratio), choose the k-1 workers with smallest quality from all those seen. Cost = ratio_captain * sum_of_k_qualities. Use max-heap to maintain k smallest qualities. Design seat reservation system with min-heap for O(log n) reserve and unreserve. Amazon and Google interview design question. Topics: heap, design Companies: amazon, google, microsoft, bloomberg Level: swe2, swe3 Min-Heap: Initialize min-heap with all seat numbers. reserve() pops min. unreserve() pushes seat number back. Heap always gives smallest available seat. Maximize subsequence score (sum * min) using sort and min-heap in O(n log n). Amazon and Google interview question. Topics: heap, greedy, sorting, array Companies: amazon, google, meta Level: swe3, senior Sort by nums2 desc + min-heap: Sort pairs by nums2 descending. Maintain a min-heap of size k for nums1 values and their running sum. For each position (which fixes the min of nums2), compute score = sum * nums2[i]. Find minimum refueling stops using greedy max-heap retroactive approach. Hard Amazon and Google interview problem. Topics: heap, greedy, dynamic-programming, array Companies: amazon, google, meta Level: senior, staff Greedy Max-Heap: Simulate driving. When stuck (fuel < 0 after reaching next position), retroactively refuel at the largest station seen so far (max-heap). Count refuels. If heap empty and still stuck, return -1. Find kth smallest fraction from prime array using min-heap in O(k log n). Google and Amazon interview question. Topics: heap, array, binary-search Companies: google, amazon, meta Level: swe3, senior Min-Heap: Initialize min-heap with fractions arr[0]/arr[j] for each denominator j. Pop k times: each pop, if numerator index i+1 < j, push arr[i+1]/arr[j]. Return arr[i], arr[j] of the kth pop. Minimize array deviation using max-heap with multiply/divide operations. Hard Google interview problem. Topics: heap, greedy, array Companies: google, amazon, meta Level: senior, staff Max-Heap: Convert all odds to even (multiply by 2). Push to max-heap. Track min. Pop max: if even, divide by 2, push back; update min; compute max-min. Stop when max is odd (cannot divide further). Maximize team performance (speed sum * min efficiency) using sort and min-heap. Hard Google interview problem. Topics: heap, greedy, sorting, array Companies: google, amazon, meta, bloomberg Level: senior, staff Sort by efficiency + min-heap: Sort engineers by efficiency descending. For each as the minimum efficiency, pick k highest speeds from seen engineers (min-heap). Performance = speed_sum * efficiency. Find kth largest element in data stream using min-heap of size k with O(log k) per insert. Amazon and Google interview. Topics: heap, design, binary-search Companies: amazon, google, microsoft, bloomberg Level: new-grad, swe2 Min-Heap of size k: Maintain a min-heap of size k. The root is always the kth largest. On add, push val and pop if size > k. Return root. Design streaming top-k frequent elements tracker using frequency map and heap. Amazon and Google interview design question. Topics: heap, hash-map, design Companies: amazon, google, twitter, bloomberg Level: swe3, senior HashMap + heapq.nlargest: Maintain a frequency counter. On each add, increment freq[num] and return heapq.nlargest(k) by frequency. Assign tasks to servers greedily using two heaps (free and busy). Amazon and Google interview question. Topics: heap, array, two-heaps Companies: amazon, google, microsoft Level: swe3, senior Two Heaps (free + busy): Free heap: (weight, idx). Busy heap: (end_time, weight, idx). At time j (0-indexed task), move done servers to free. If no free server, advance time to next completion. Assign lightest free server. Find minimum time to swim across grid using Dijkstra min-heap or binary search BFS. Hard Google interview problem. Topics: heap, graph, bfs, binary-search, union-find Companies: google, amazon, meta, bloomberg Level: senior, staff Dijkstra / Min-Heap: Treat problem as finding path from (0,0) to (n-1,n-1) minimizing the maximum elevation encountered. Use Dijkstra with priority key = max(current_t, grid[r][c]). Binary Search + BFS: Binary search on answer t (0..n^2-1). For each t, BFS/DFS checking if path exists from (0,0) to (n-1,n-1) using only cells with elevation <= t. Implement LRU cache with O(1) ops using OrderedDict and doubly linked list. Topics: lru-cache, design-patterns, hash-map, collections Companies: amazon, google, microsoft, meta, bloomberg Level: swe2, swe3 OrderedDict: OrderedDict maintains order. move_to_end on access marks MRU. popitem(last=False) evicts LRU. Doubly Linked List + HashMap: DLL for order, dict for O(1) access. head=LRU, tail=MRU. Remove and insert before tail on access. Implement Least Frequently Used cache with O(1) ops using two dicts and OrderedDict buckets. Topics: lfu-cache, design-patterns, hash-map, collections Companies: amazon, google, microsoft, meta Level: swe3, senior Two Dicts + Min Freq: key_val, key_freq dicts plus freq_keys (freq->OrderedDict). Track min_freq. On access increment freq, move to next bucket. Thread-safe Singleton using Python metaclass with locking. Advanced OOP interview question. Topics: metaclasses, concurrency, design-patterns, oop Companies: amazon, google, microsoft, meta Level: swe3, senior Metaclass with Lock: Override __call__ in metaclass. Lock prevents race condition. Class-keyed dict stores instances. Implement Observer pattern with abstract observers and stock price notification. Amazon Google OOP interview. Topics: design-patterns, oop, object-design Companies: amazon, google, microsoft, meta, bloomberg Level: swe2, swe3 ABC Observer: Abstract Observer with update(). Subject provides subscribe/unsubscribe/notify. Concrete classes implement update(). Implement Python iterator protocol with custom Range, Flatten, and Chain iterators. Topics: iterators, generators, oop, protocols Companies: google, amazon, microsoft Level: swe2, swe3 Iterator Protocol: __iter__ returns self. __next__ advances and raises StopIteration when done. Stack-based flatten. Implement context managers with class protocol and @contextmanager decorator. Advanced Python interview. Topics: context-managers, oop, exceptions, decorators Companies: google, amazon, microsoft, meta Level: swe2, swe3 Class and Decorator Context Managers: __enter__ sets up, __exit__ tears down. @contextmanager: yield splits setup/teardown. Retry decorator with exponential backoff. Amazon Google Stripe interview question. Topics: decorators, exceptions, closures, functools Companies: amazon, google, microsoft, stripe, netflix Level: swe2, swe3 Retry with Exponential Backoff: Loop up to max_attempts, catch specified exceptions, multiply delay. Re-raise on final failure. Build memoize decorator with LRU eviction and cache statistics. Google Amazon Python interview. Topics: decorators, memoization, closures, functools, dynamic-programming Companies: google, amazon, microsoft, meta Level: swe2, swe3 Memoize with LRU and Stats: OrderedDict cache keyed by (args, kwargs_tuple). move_to_end on hit, popitem on overflow. cache_info() reports stats. Flatten arbitrarily nested iterables with yield from recursive generator. Advanced Python interview. Topics: generators, iterators, recursion, typing Companies: google, amazon, microsoft Level: swe2, swe3 Recursive Generator: yield from for sub-iterables. Exclude str/bytes to yield as atomic items. Iterative Stack: Explicit iterator stack avoids recursion depth limits. Implement lazy_property that caches on first access using non-data descriptor protocol. Topics: descriptors, oop, decorators, caching Companies: google, amazon, microsoft Level: swe3, senior Non-Data Descriptor: No __set__, so Python checks instance.__dict__ first. Store result there to bypass descriptor on next access. Typed dataclasses with runtime validation using __post_init__. Advanced Python interview. Topics: dataclasses, typing, oop, descriptors Companies: google, amazon, microsoft, stripe Level: swe2, swe3 __post_init__ Validation: @dataclass with __post_init__ for validation. ClassVar for constraints. Custom validators per field. Payment processor ABC with CreditCard and PayPal implementations using template method. Topics: abstract-classes, oop, design-patterns Companies: stripe, paypal, amazon, google, visa Level: swe2, swe3 ABC Payment Hierarchy: PaymentProcessor ABC with template method process(). Subclasses implement charge() and refund(). Track attribute changes with __getattr__ and __setattr__. Advanced Python OOP interview. Topics: descriptors, oop, metaclasses Companies: google, amazon, microsoft Level: swe3, senior Attribute History Tracking: __setattr__ logs changes. object.__setattr__ for internal state avoids recursion. __getattr__ for missing attrs. Use typing.Protocol for Comparable interface with structural subtyping. Advanced Python interview. Topics: protocols, typing, oop, abstract-classes Companies: google, amazon, microsoft Level: swe3, senior Protocol with Generic Functions: Protocol defines interface via structural typing. Concrete classes need not inherit. Generic functions accept any Comparable. Async producer-consumer with asyncio.Queue, backpressure, and graceful shutdown. Topics: async-await, generators, concurrency Companies: google, amazon, netflix, microsoft Level: swe3, senior asyncio Queue Pipeline: Producer puts items, sends None sentinel per consumer. Consumers loop until None. asyncio.gather runs all. asyncio.gather with semaphore and timeout. Google Netflix async interview. Topics: async-await, concurrency Companies: google, amazon, netflix, stripe Level: swe2, swe3 gather with Semaphore and Timeout: asyncio.gather runs concurrently. Semaphore limits parallelism. wait_for adds per-task timeout. return_exceptions avoids one failure killing all. Thread-safe token bucket rate limiter with lazy refill. Amazon Google Stripe Cloudflare interview. Topics: rate-limiting, design-patterns, system-design-coding, concurrency Companies: amazon, google, stripe, cloudflare, netflix Level: swe3, senior Lazy Token Bucket: Lazily refill on consume based on elapsed time. Lock for thread safety. Optional blocking mode. Parallel task processing with ThreadPoolExecutor and progress tracking. Amazon Google interview. Topics: concurrency, async-await, functools Companies: amazon, google, microsoft, netflix Level: swe2, swe3 ThreadPoolExecutor with Progress: Submit all tasks, use as_completed for progress, handle per-task exceptions, map for ordered results. Implement defaultdict from scratch with __missing__. Classic Python OOP interview. Topics: collections, oop, hash-map Companies: google, amazon, microsoft Level: new-grad, swe2 __missing__ Implementation: Inherit dict, override __missing__ to call default_factory and store result. Implement Trie with insert, search, autocomplete, delete. Amazon Google interview. Topics: trie, oop, hash-map, string-matching Companies: amazon, google, microsoft, meta, bloomberg Level: swe2, swe3 Trie with Autocomplete: TrieNode with children dict and is_end. DFS for autocomplete. Recursive post-order delete. Implement Graph with BFS, DFS, cycle detection, topological sort. Amazon Google interview. Topics: graph, bfs, dfs, oop, topological-sort Companies: amazon, google, microsoft, meta, bloomberg Level: swe2, swe3 Graph with BFS DFS Topo Sort: BFS with deque. DFS recursive. Cycle detection via coloring. Topo sort via DFS post-order. Build MinHeap with insert, extract, build_heap. Amazon Google interview. Topics: heap, array, oop Companies: amazon, google, microsoft, bloomberg Level: swe2, swe3 Array-Based MinHeap: Append and sift up on insert. Swap root with last, pop, sift down on extract. Build by sifting down from n//2-1. Fixed-size circular buffer with head/tail pointers and overwrite mode. Topics: array, design-patterns, queue, system-design-coding Companies: amazon, google, microsoft, nvidia, bloomberg Level: swe2, swe3 Head/Tail Pointer Buffer: Fixed array with head and tail. count tracks size. Modular arithmetic for wrap-around. Bloom filter with optimal bit array and double hashing. Google Databricks Cloudflare interview. Topics: hash-map, bit-manipulation, system-design-coding Companies: google, amazon, databricks, cloudflare, netflix Level: swe3, senior, staff Double Hashing Bloom Filter: bytearray as bit array. Two base hashes (MD5, SHA1) derive k positions. Optimal m and k from n and p. Implement consistent hashing with virtual nodes. Amazon Google Netflix distributed systems interview. Topics: hash-map, system-design-coding, design-patterns, sorting Companies: amazon, google, databricks, netflix, cloudflare, uber Level: swe3, senior, staff Virtual Node Hash Ring: Hash each node v times onto ring (sorted list). Key lookup: hash key, bisect for successor node. LRU cache design with O(1) get/put using OrderedDict. Classic Amazon Google system design coding. Topics: lru-cache, system-design-coding, hash-map, design-patterns Companies: amazon, google, microsoft, meta, bloomberg Level: swe2, swe3 OrderedDict O(1): OrderedDict preserves insertion order. move_to_end marks MRU. popitem(last=False) evicts LRU. LFU cache with O(1) ops using frequency buckets. Hard Amazon Google interview. Topics: lfu-cache, system-design-coding, hash-map, design-patterns Companies: amazon, google, microsoft, meta Level: swe3, senior Freq Bucket + Min Freq Tracking: Three dicts: key->val, key->freq, freq->OrderedDict(keys). min_freq for O(1) eviction. Hit counter counting requests in last 300 seconds. Deque and circular array approaches. Amazon Google interview. Topics: system-design-coding, queue, design-patterns, sliding-window Companies: amazon, google, microsoft, bloomberg, dropbox Level: swe2, swe3 Deque Sliding Window: Deque stores hit timestamps. getHits pops timestamps older than 5 minutes. Circular Array O(1): Fixed array of 300 (seconds, count) pairs. Index by timestamp%300. Reset stale buckets. Rate limiter with sliding window per user. Amazon Google Stripe Cloudflare interview. Topics: rate-limiting, system-design-coding, sliding-window, design-patterns Companies: amazon, google, stripe, cloudflare, netflix Level: swe3, senior Sliding Window Counter: Per-user deque of timestamps. Pop stale, check count, append if allowed. Fixed Window Counter (simpler): Track (window_start, count) per user. Reset on new window. Twitter design with heap-based k-way merge for news feed. Amazon Meta Google system design coding. Topics: system-design-coding, heap, hash-map, design-patterns Companies: twitter, meta, amazon, google, linkedin Level: swe2, swe3 Heap K-Way Merge: Each user has tweet list. getNewsFeed heap-merges followees tweets, returns top 10. Global timestamp orders tweets. In-memory file system with mkdir, ls, addFile using trie. Amazon Google Dropbox interview. Topics: trie, system-design-coding, hash-map, design-patterns Companies: amazon, google, microsoft, dropbox Level: swe2, swe3 Trie Node File System: Each node is a dir or file with children dict and content. Path segments traverse the trie. In-memory KV store with TTL expiry and lazy deletion. Amazon Redis Google interview. Topics: system-design-coding, hash-map, design-patterns, caching Companies: amazon, google, microsoft, redis, stripe Level: swe2, swe3 Lazy Expiration + Background Cleanup: Store (value, expiry). get checks expiry and deletes if stale. Optional background thread purges periodically. In-memory DB with set/get/scan and transaction support. Amazon Snowflake Databricks interview. Topics: system-design-coding, hash-map, sorting, design-patterns Companies: amazon, google, microsoft, snowflake, databricks Level: swe3, senior In-Memory DB with Transactions: Nested defaultdict for storage. Sorted scan with prefix filter. Transaction stack stores undo log. URL shortener with base62 encoding, custom aliases, expiry, and click tracking. Topics: system-design-coding, hash-map, design-patterns Companies: amazon, google, microsoft, twitter, bitly Level: swe2, swe3 Counter + Base62 Encoding: Increment counter, encode to base62 for short key. Two dicts: short->url and url->short for dedup. Track clicks and expiry. Leaderboard with addScore, top K, reset using heap. Amazon Google interview. Topics: system-design-coding, heap, sorting, hash-map Companies: amazon, google, microsoft, gaming-companies Level: swe2, swe3 HashMap + heapq.nlargest: Store scores in dict. top(K) uses heapq.nlargest O(n log K). Parking lot OOP design with vehicles, spots, tickets and fee calculation. Amazon Google Uber interview. Topics: system-design-coding, object-design, oop, design-patterns Companies: amazon, google, microsoft, uber, bloomberg Level: swe2, swe3 OOP Parking Lot System: Vehicle, Spot, Floor, ParkingLot, Ticket classes. park() finds first compatible spot. leave() calculates fee by time. Vending machine using State design pattern. Amazon Google OOP system design interview. Topics: system-design-coding, object-design, oop, design-patterns Companies: amazon, google, microsoft Level: swe2, swe3 State Pattern Vending Machine: VendingMachine holds state. Each State subclass implements transitions. Invalid ops raise in each state. Multi-elevator system with SCAN scheduling algorithm. Amazon Google senior engineer interview. Topics: system-design-coding, object-design, oop, design-patterns, sorting Companies: amazon, google, microsoft, bloomberg Level: swe3, senior SCAN Algorithm Multi-Elevator: Each Elevator has current floor, direction, and sorted queues for up/down. Assign request to nearest elevator. SCAN sweeps then reverses. Library management with checkout, return, reservations, and fines. Amazon Microsoft OOP interview. Topics: system-design-coding, object-design, oop Companies: amazon, microsoft, google, bloomberg Level: swe2, swe3 Library OOP Design: Book, BookCopy, Member, Library classes. Checkout assigns available copy. Return calculates fine. Reservation queue notifies next member. Restaurant table reservation with interval overlap detection. Amazon Airbnb Uber interview. Topics: system-design-coding, object-design, oop, interval Companies: amazon, google, uber, airbnb Level: swe2, swe3 Interval Overlap Reservation: Per-table reservation list. Check overlap with each existing reservation. Find smallest capacity >= party_size. Thread-safe movie booking with seat locking and confirmation. Amazon Netflix interview. Topics: system-design-coding, object-design, oop, concurrency Companies: amazon, google, netflix, uber Level: swe2, swe3 Thread-Safe Movie Booking: Seat has status, lock, expiry. bookSeat atomically checks and locks. Payment confirms. Cancel releases. Chat system with 1:1 and group messaging OOP design. Meta Discord Amazon interview. Topics: system-design-coding, object-design, oop, design-patterns Companies: meta, amazon, google, discord, slack Level: swe2, swe3 Chat System OOP: Conversation keyed by sorted user pair. Group has member set and message list. Unread counter per user-conversation. Autocomplete with trie and frequency tracking. Top 3 results by frequency. Amazon Google interview. Topics: trie, system-design-coding, heap, string-matching Companies: amazon, google, microsoft, meta, linkedin Level: swe2, swe3 Trie with Frequency Tracking: Trie with freq dict at each end node. On input: walk trie to current node, DFS for all sentences, return top 3 by (-freq, text). Merge K sorted log streams with heap-based k-way merge. Amazon Datadog interview. Topics: system-design-coding, heap, k-way-merge, sorting Companies: amazon, google, datadog, splunk, cloudflare Level: swe3, senior K-Way Merge with Heap: Per-stream sorted list. Merge query: push first log of each stream, pop-min into result, push next from same stream. Task scheduler with priority heap and thread workers. Amazon Google Airflow interview. Topics: system-design-coding, heap, design-patterns, concurrency Companies: amazon, google, microsoft, celery, airflow Level: swe2, swe3 Priority Heap Scheduler: Min-heap with (-priority, ready_time, id, func). Worker thread pops when ready_time <= now. ThreadPoolExecutor for concurrent execution. In-memory pub/sub with async delivery and worker threads. Amazon Kafka Google interview. Topics: system-design-coding, design-patterns, concurrency, object-design Companies: amazon, google, meta, kafka, stripe Level: swe3, senior Async Pub/Sub with Worker Threads: Per-subscriber Queue. Dedicated worker thread per subscriber drains queue. publish enqueues to all subscribers. Implement event sourcing with append-only log, snapshots, and state replay. Amazon Stripe Netflix interview. Topics: system-design-coding, design-patterns, object-design, caching Companies: amazon, google, stripe, netflix, databricks Level: swe3, senior, staff Event Store with Snapshots: Append-only event list. Reducer function applies each event to state. Snapshots checkpoint state. Replay from latest snapshot + subsequent events. Thread-safe circuit breaker with CLOSED/OPEN/HALF_OPEN states. Amazon Netflix Google interview. Topics: system-design-coding, design-patterns, concurrency, rate-limiting Companies: amazon, google, netflix, stripe, uber Level: swe3, senior Thread-Safe Circuit Breaker: State machine with CLOSED/OPEN/HALF_OPEN. Failure threshold opens circuit. Timeout allows HALF_OPEN test. Success closes circuit. API gateway with middleware pipeline: auth, rate limiting, caching, routing. Amazon Netflix senior interview. Topics: system-design-coding, design-patterns, rate-limiting, caching Companies: amazon, google, netflix, cloudflare, stripe Level: senior, staff Middleware Pipeline API Gateway: Chain of middleware: auth -> rate limit -> cache -> route -> backend. Each middleware calls next() or returns early. Route registry maps path to handler. Product search suggestions with sorted list and binary search. Amazon Google LinkedIn interview. Topics: trie, system-design-coding, string-matching, sorting Companies: amazon, google, microsoft, linkedin, meta Level: swe2, swe3 Sorted List + Binary Search: Sort products. For each prefix, bisect to find start, take up to 3 matching products. Implement Knuth-Morris-Pratt string matching. Find all pattern occurrences in O(n+m) time. Google Amazon interview. Topics: string, two-pointers Companies: google, amazon, microsoft Level: senior, staff KMP with Failure Function: Build a partial match table (failure function) for the pattern, then use it to skip unnecessary comparisons during search. Implement Rabin-Karp string search with rolling hash. Polynomial hashing and collision handling. Google interview. Topics: string, hash-table Companies: google, facebook, microsoft Level: senior, staff Rolling Hash: Compute hash of pattern and rolling hash of each text window. On hash match, verify character by character. Implement Z-algorithm for string matching and Z-array construction in O(n). Google Amazon senior interview. Topics: string, two-pointers Companies: google, amazon Level: senior, staff Z-Array Construction: Maintain a Z-box [L, R]. For each position, reuse previous results where possible. Find longest palindromic substring using Manacher's O(n) algorithm and expand-around-center. Amazon Google interview. Topics: string, dynamic-programming Companies: amazon, google, microsoft, apple Level: senior, staff Manacher's Algorithm O(n): Transform string with separators, then use Manacher's to find palindrome radii in linear time. Expand Around Center O(n^2): For each center (including between characters), expand outward while palindrome holds. Partition string into all palindrome substrings using backtracking and DP. Amazon Google interview. Topics: backtracking, dynamic-programming, string Companies: amazon, google, facebook Level: swe2, senior Backtracking with DP Palindrome Check: Use DP to precompute is_palindrome[i][j], then backtrack adding valid palindrome prefixes. Solve Merge Intervals in Python with sorting and greedy merge. O(n log n) time complexity with detailed explanation. Topics: array, sorting, interval Companies: google, amazon, microsoft, facebook, bloomberg Level: new-grad, swe2, swe3 Sort and Merge: Sort intervals by start. Iterate and merge when current start <= last merged end. Insert and merge an interval into a sorted non-overlapping interval list in O(n) time using linear scan. Topics: array, interval Companies: google, amazon, linkedin, microsoft Level: new-grad, swe2, swe3 Linear Scan: Three-phase linear scan: add non-overlapping before, merge overlapping, add remaining. Find minimum intervals to remove to make rest non-overlapping using greedy sort by end time in O(n log n). Topics: array, sorting, interval, greedy Companies: google, amazon, microsoft Level: swe2, swe3 Greedy - Sort by End: Sort by end time. Greedily select intervals with earliest end. Count removed = total - kept. Determine if a person can attend all meetings with no overlaps using sorting in O(n log n) time. Topics: array, sorting, interval Companies: amazon, microsoft, bloomberg, facebook Level: new-grad, swe2 Sort and Check: Sort by start. If any meeting starts before previous ends, return False. Find minimum conference rooms needed using min-heap or two sorted arrays approach in O(n log n) time. Topics: array, sorting, interval, heap, two-pointers Companies: amazon, google, microsoft, bloomberg, uber, facebook Level: swe2, swe3, senior Min-Heap: Sort by start. Min-heap tracks earliest ending room. Reuse room if it ends before new meeting starts. Two Sorted Arrays: Separate start and end times sorted. Use two pointers to track concurrent meetings. Find common free time for all employees by flattening, sorting, merging intervals and finding gaps. Topics: array, sorting, interval, heap Companies: google, amazon, uber, airbnb Level: swe3, senior, staff Flatten Sort and Find Gaps: Flatten all intervals, sort by start, merge overlapping, then collect gaps between merged intervals. Find intersections of two sorted interval lists using two pointers in O(m+n) time. Topics: array, two-pointers, interval Companies: facebook, google, amazon, linkedin Level: swe2, swe3 Two Pointers: Two pointers. Intersection = [max(starts), min(ends)]. Advance pointer with smaller end. Count remaining intervals after removing covered ones using sorting in O(n log n) time. Topics: array, sorting, interval, greedy Companies: amazon, google Level: swe2, swe3 Sort and Track Max End: Sort by start asc, end desc. An interval is not covered if its end exceeds max end seen so far. Find minimum video clips to cover event duration using greedy interval jumping in O(n log n) time. Topics: array, interval, greedy, dynamic-programming Companies: google, amazon Level: swe3, senior Greedy Jump: Greedy: sort clips. At each position extend as far as possible with available clips. Count jumps. Find minimum arrows to burst all balloons using greedy sort by end time in O(n log n) time. Topics: array, sorting, interval, greedy Companies: amazon, google, microsoft Level: swe2, swe3 Greedy Sort by End: Sort by end. Shoot at current balloon end. New arrow only when next start > current arrow pos. Implement a calendar booking system without double bookings using binary search in O(n) per operation. Topics: array, binary-search, interval, design-patterns Companies: google, amazon, microsoft Level: swe2, swe3 Binary Search with SortedList: Maintain sorted list of events. Use bisect to find insertion point and check neighbors for overlap. Implement calendar with at most double bookings using two interval lists to track overlaps. Topics: array, binary-search, interval, design-patterns Companies: google, amazon Level: swe3, senior Two Lists: Singles and Doubles: Maintain two lists: single bookings and double bookings. Reject if triple booking would occur. Track maximum k-booking using difference array with sorted dict in O(n) per booking. Topics: interval, segment-tree, design-patterns, binary-search Companies: google, amazon Level: senior, staff Difference Array with Sorted Dict: Difference array approach: +1 at start, -1 at end. Prefix sum gives concurrent events at any point. Summarize a data stream as disjoint intervals with efficient merge operations. Topics: interval, binary-search, design-patterns, sorted-list Companies: google, amazon, stripe Level: senior, staff Sorted List with Merge: Maintain sorted disjoint intervals. On addNum, find and merge all touching/overlapping intervals. Implement a Range Module tracking number ranges with add, remove, and query operations on intervals. Topics: interval, segment-tree, design-patterns, binary-search Companies: google, amazon, stripe Level: senior, staff Sorted Intervals List: Maintain sorted disjoint intervals. Add merges overlapping, remove splits overlapping intervals. Count range sums within bounds using merge sort on prefix sums in O(n log^2 n) time. Topics: array, prefix-sum, divide-and-conquer, binary-search, sorting Companies: google, amazon, jane-street Level: senior, staff Merge Sort on Prefix Sums: Build prefix sums. Use merge sort to count pairs (i,j) where prefix[j]-prefix[i] in [lower,upper]. Simulate falling squares and compute maximum height after each drop using interval overlap detection. Topics: array, interval, segment-tree, sorting Companies: google, amazon Level: senior, staff Brute Force with Interval Heights: For each square, find max height of overlapping previous squares. New height = base + size. Compute total area covered by overlapping rectangles using sweep line with coordinate compression. Topics: array, interval, segment-tree, sorting, prefix-sum Companies: google, amazon, jane-street Level: senior, staff Coordinate Compression + Sweep Line: Sweep line on x-axis with coordinate-compressed y-axis. Track active y segments to compute covered length. Find smallest interval containing each query using sort and min-heap in O((n+q) log n) time. Topics: array, sorting, interval, heap, binary-search Companies: google, amazon, stripe Level: senior, staff Sort + Min-Heap: Sort intervals by start, queries by value. Sweep with min-heap of active intervals keyed by size. Count flowers blooming at each arrival time using binary search on sorted start and end arrays. Topics: array, sorting, binary-search, interval, prefix-sum Companies: google, amazon, databricks Level: swe3, senior Binary Search on Sorted Start/End: Sort starts and ends separately. For each person: blooming = #started_by_t - #ended_before_t. Find the smallest starting interval >= each interval end using binary search in O(n log n) time. Topics: array, binary-search, interval, sorting Companies: amazon, google Level: swe2, swe3 Binary Search on Sorted Starts: Sort (start, index) pairs. For each interval end, binary search in sorted starts for >= end. Partition string into maximum parts where each letter appears in one part using greedy last-occurrence approach. Topics: string, greedy, interval, two-pointers Companies: amazon, google, facebook, microsoft Level: swe2, swe3 Last Occurrence Greedy: Track last index of each char. Expand current partition until current index equals partition end. Find minimum CPU intervals for task scheduling with cooldown using math formula or max-heap simulation. Topics: array, greedy, heap, interval, sorting Companies: amazon, google, facebook, microsoft, bloomberg Level: swe2, swe3, senior Math Formula: Math: answer = max(total_tasks, (max_freq-1)*(n+1)+count_of_max_freq_tasks) Greedy with Max-Heap: Max-heap simulation: each cycle of n+1 slots, execute most frequent tasks. Count car fleets arriving at destination by sorting by position and using a monotonic stack approach. Topics: array, sorting, monotonic-stack, interval Companies: amazon, google, microsoft Level: swe2, swe3 Sort by Position Descending + Stack: Sort by position desc. A car joins fleet ahead if its arrival time <= fleet in front. Use stack. Determine reachability in Jump Game VII using prefix sum of reachable positions in O(n) time. Topics: string, bfs, prefix-sum, sliding-window, interval Companies: amazon, google Level: swe3, senior Prefix Sum BFS: Prefix sum of reachable positions. Position j reachable if any position in [j-maxJump, j-minJump] is reachable. Find minimum eating speed using binary search on the answer in O(n log m) time. Topics: array, binary-search Companies: amazon, google, facebook, uber Level: swe2, swe3 Binary Search on Speed: Binary search on eating speed. Feasibility check: sum of ceil(pile/k) for all piles <= h. Find minimum ship capacity to deliver all packages within D days using binary search on the answer. Topics: array, binary-search Companies: amazon, google, facebook Level: swe2, swe3 Binary Search on Capacity: Binary search on capacity in range [max(w), sum(w)]. Greedy check if packages can be shipped in D days. Find minimum days to form m bouquets of k adjacent flowers using binary search in O(n log max_day). Topics: array, binary-search Companies: amazon, google, bloomberg Level: swe2, swe3 Binary Search on Days: Binary search on the day. Feasibility: greedily count consecutive bloomed flowers forming bouquets. Minimize the largest subarray sum when splitting into k parts using binary search on the answer. Topics: array, binary-search, dynamic-programming, greedy Companies: google, amazon, facebook, bloomberg Level: swe3, senior Binary Search on Answer: Binary search on the max subarray sum. Greedily count splits needed for a given max sum. Maximize minimum distance between balls using binary search on the answer after sorting positions. Topics: array, binary-search, sorting Companies: amazon, google, airbnb Level: swe3, senior Binary Search on Minimum Distance: Sort positions. Binary search on min distance. Greedy feasibility: place balls maximizing spacing. Find target in mountain array using three binary searches: find peak, search ascending, search descending. Topics: array, binary-search, divide-and-conquer Companies: google, amazon, facebook Level: swe3, senior Three Binary Searches: Three binary searches: find peak, search ascending left half, search descending right half. Search for a target in rotated sorted array with duplicates using modified binary search. Topics: array, binary-search Companies: amazon, google, microsoft, facebook Level: swe2, swe3 Binary Search with Duplicate Handling: Binary search. When lo==mid, advance lo. Otherwise determine sorted half and prune. Find the duplicate number in O(n) time O(1) space using Floyd's cycle detection algorithm. Topics: array, two-pointers, binary-search, bit-manipulation Companies: amazon, google, facebook, microsoft, bloomberg Level: swe2, swe3 Floyd's Cycle Detection: Model array as linked list (index->value). Duplicate creates cycle. Floyd's algorithm finds cycle entry. Find the first bad version using binary search to minimize API calls in O(log n) time. Topics: binary-search Companies: amazon, facebook, microsoft, linkedin Level: new-grad, swe2 Binary Search: Standard binary search. Converge lo and hi to the leftmost bad version. Find next greatest letter in circular sorted array using binary search in O(log n) time. Topics: array, binary-search Companies: amazon, google Level: new-grad, swe2 Binary Search: bisect_right finds first position after target. Modulo handles wraparound. Count negatives in row/column sorted matrix using staircase traversal in O(m+n) time. Topics: array, binary-search, matrix Companies: amazon, google, microsoft Level: new-grad, swe2 Staircase from Top-Right: Start top-right. Negative -> count remaining rows, move left. Non-negative -> move down. Find kth smallest element in sorted matrix using binary search on value with staircase count. Topics: matrix, binary-search, heap, sorting Companies: amazon, google, facebook, microsoft Level: swe2, swe3 Binary Search on Value: Binary search on value range. Count elements <= mid using staircase. Converge to kth smallest. Find kth smallest pairwise distance using binary search on distance with sliding window count. Topics: array, binary-search, sorting, two-pointers Companies: google, amazon, stripe Level: senior, staff Binary Search + Sliding Window: Sort array. Binary search on distance value. Count pairs with distance <= mid using sliding window. Find kth smallest in m x n multiplication table using binary search with O(m log mn) complexity. Topics: binary-search, math Companies: google, amazon, jane-street Level: senior, staff Binary Search on Value: Binary search on value. Count(x) = sum(min(x//i, n) for i in 1..m). Find smallest value with count >= k. Implement weighted random selection using prefix sum and binary search in O(log n) per pick. Topics: array, binary-search, prefix-sum, math Companies: google, amazon, facebook, uber, airbnb Level: swe2, swe3 Prefix Sum + Binary Search: Build prefix sums. Random int in [1, total]. Binary search prefix array to find weighted index. Design a time-based key-value store with O(log n) get using HashMap and binary search. Topics: hash-map, binary-search, design-patterns Companies: google, amazon, facebook, stripe, uber Level: swe2, swe3 HashMap + Binary Search: HashMap of sorted (timestamp, value) lists. Binary search for largest timestamp <= query. Precompute election leaders at each timestamp and answer queries with binary search in O(log n). Topics: array, binary-search, hash-map Companies: google, amazon Level: swe3, senior Precompute + Binary Search: Precompute leader at each timestamp. For query t, binary search for latest vote time <= t. Find peak index in mountain array using binary search on slope direction in O(log n) time. Topics: array, binary-search Companies: amazon, google, microsoft Level: new-grad, swe2 Binary Search: Binary search. If arr[mid] < arr[mid+1], rising slope so peak is right. Else peak is left. Search sorted 2D matrix using staircase approach from top-right corner in O(m+n) time. Topics: array, binary-search, matrix, divide-and-conquer Companies: amazon, google, facebook, microsoft, bloomberg Level: swe2, swe3 Staircase Search from Top-Right: Start top-right. Value > target: move left (eliminate column). Value < target: move down (eliminate row). Compute integer square root using binary search without built-in sqrt in O(log x) time. Topics: math, binary-search Companies: amazon, google, microsoft, bloomberg Level: new-grad, swe2 Binary Search: Binary search in [1, x//2]. When lo > hi, hi is floor(sqrt(x)). Find H-Index from sorted citations array using binary search in O(log n) time. Topics: array, binary-search Companies: facebook, google, amazon Level: swe2, swe3 Binary Search: Binary search on h. Check if citations[n-h] >= h (at least h papers with >= h citations). Find minimum train speed to arrive on time using binary search on speed in O(n log max) time. Topics: array, binary-search Companies: amazon, google, uber Level: swe2, swe3 Binary Search on Speed: Binary search on speed. Sum ceiling times for all but last train plus actual last train time. Find minimum time for buses to complete totalTrips using binary search on time value. Topics: array, binary-search Companies: amazon, google, leetcode Level: swe2, swe3 Binary Search on Time: Binary search on total time. Feasibility: sum of t//time[i] for all buses >= totalTrips. Maximize candies per child by binary searching on candy count with pile splitting feasibility check. Topics: array, binary-search Companies: amazon, google Level: swe2, swe3 Binary Search on Candy Count: Binary search on candy count m. Feasibility: sum(c//m for c in candies) >= k children. Minimize maximum bag size after splitting with limited operations using binary search on the answer. Topics: array, binary-search Companies: amazon, google, facebook Level: swe2, swe3 Binary Search on Max Size: Binary search on max bag size. Operations needed for bag n with limit m: ceil(n/m) - 1. Find maximum path sum in binary tree using DFS with global max tracking in O(n) time. Topics: binary-tree, dfs, dynamic-programming, recursion Companies: amazon, google, facebook, microsoft, bloomberg Level: swe3, senior DFS with Global Max: DFS returns max one-sided path sum. At each node compute full path sum and update global max. Place minimum cameras in binary tree using greedy post-order DFS with three-state node classification. Topics: binary-tree, dfs, greedy, dynamic-programming Companies: google, amazon, facebook Level: senior, staff Greedy DFS: Post-order DFS. Place camera when child is uncovered. Greedy: place cameras as high as possible. Find minimum coin moves in binary tree using DFS excess calculation in O(n) time. Topics: binary-tree, dfs, recursion Companies: amazon, google, facebook Level: swe3, senior DFS Excess Calculation: DFS returns excess coins. Each edge move = |excess|. Total moves = sum of excess over all subtrees. Find maximum width of binary tree using BFS with position indices and normalization in O(n). Topics: binary-tree, bfs, dfs Companies: amazon, google, facebook Level: swe2, swe3 BFS with Index Normalization: BFS with node position indices. Left child = 2*i, right child = 2*i+1. Normalize to prevent overflow. Count nodes in complete binary tree in O(log^2 n) by comparing heights to detect perfect subtrees. Topics: binary-tree, binary-search, dfs Companies: amazon, google, microsoft Level: swe2, swe3 Binary Search on Height: Compare left-spine and right-spine heights. If equal: perfect subtree. Else recurse both sides. Sum all root-to-leaf numbers in binary tree using DFS with running number accumulation. Topics: binary-tree, dfs, recursion Companies: amazon, google, facebook, microsoft Level: swe2, swe3 DFS with Running Number: DFS with running number. At each node: cur = cur*10 + val. Return cur at leaves, sum of children otherwise. Count paths with target sum using DFS with prefix sum hash map in O(n) time. Topics: binary-tree, dfs, prefix-sum, hash-map Companies: amazon, google, facebook, microsoft Level: swe2, swe3 Prefix Sum Hash Map: DFS with prefix sum hash map. At each node, check if (cur_sum - target) exists in map. Backtrack on exit. Flatten binary tree to linked list in-place using Morris traversal approach in O(n) O(1) space. Topics: binary-tree, dfs, recursion, linked-list Companies: amazon, google, microsoft, bloomberg Level: swe2, swe3 Iterative with Stack: Morris-style: for each node with left, find rightmost of left subtree, connect to right, move left to right. Get right side view of binary tree using BFS level order traversal taking last node per level. Topics: binary-tree, bfs, dfs Companies: amazon, facebook, google, microsoft, bloomberg Level: swe2, swe3 BFS Level Order: BFS level by level. Take the last node value at each level as the right-side visible node. Find all duplicate subtrees by serializing each subtree and counting occurrences with a hash map. Topics: binary-tree, dfs, hash-map, serialization Companies: amazon, google, facebook Level: swe2, swe3 Post-order Serialization: Post-order DFS serializes each subtree. Hash map counts occurrences; collect on second occurrence. Implement LRU Cache in Python with O(1) get and put using OrderedDict or a doubly linked list + hash map. Includes full solutions with test cases. Topics: design-patterns, hash-map, linked-list, caching Companies: amazon, google, meta, microsoft, uber, bloomberg Level: swe2, swe3, senior OrderedDict (Pythonic): Use collections.OrderedDict. move_to_end() marks recently used; popitem(last=False) evicts LRU. Doubly Linked List + HashMap: Manual DLL with sentinel head/tail. HashMap stores key -> node. O(1) insert/delete/lookup. Implement an LFU Cache in Python with O(1) get and put. Covers three-dict solution and doubly linked list per frequency bucket approach. Topics: design-patterns, hash-map, linked-list, caching Companies: amazon, google, meta, microsoft, databricks Level: swe3, senior, staff Three-dict O(1) solution: key_val: key->val, key_freq: key->freq, freq_keys: freq->OrderedDict(key). min_freq tracks eviction target. Doubly Linked List per frequency: Each frequency bucket is a DLL of nodes. Moving a node to next bucket is O(1). Maintains true LRU order within each bucket. Design a simplified Twitter with postTweet, follow, unfollow, and getNewsFeed in Python. Uses a max-heap to merge per-user tweet lists efficiently. Topics: design-patterns, heap, hash-map, object-design Companies: twitter, amazon, google, meta, uber Level: swe2, swe3, senior Heap merge of per-user tweet lists: Store tweets per user with timestamp. getNewsFeed uses a max-heap seeded with the latest tweet from each followed user, then pops up to 10. Simple list merge (brute force): Collect all tweets from self + followees, sort by timestamp descending, return top 10. Simpler but slower. Implement the Snake Game in Python using a deque and set for O(1) body collision detection. Full solution with food eating and wall boundary logic. Topics: design-patterns, deque, hash-map, object-design Companies: amazon, google, microsoft, apple, bloomberg Level: swe2, swe3, senior Deque + set for O(1) collision: Deque stores body cells (row, col). Set mirrors deque for O(1) membership. New head computed from direction, tail removed before self-collision check to handle tail-chasing correctly. Deque only (O(n) collision check): Same deque approach but uses 'in' on deque for collision check. Simpler but O(n) per move for large snakes. Implement a Hit Counter in Python that counts hits in the past 5 minutes. Covers O(1) circular buffer and queue-based approaches with full test cases. Topics: design-patterns, queue, array, object-design Companies: amazon, google, microsoft, stripe, bloomberg Level: swe2, swe3, senior Circular buffer (O(1) always): Two arrays of size 300: times[i] stores the timestamp that last wrote slot i, counts[i] stores hits at that timestamp. Slot index = timestamp % 300. Queue-based (intuitive): Store (timestamp, count) pairs in a deque. On getHits, pop entries older than 300 seconds from front. Implement a Phone Directory in Python with O(1) get, check, and release operations using a set of available numbers or queue with boolean array. Topics: design-patterns, sets, object-design, hash-map Companies: google, amazon, microsoft, linkedin, bloomberg Level: swe2, swe3 Set of available numbers: Keep a set of free numbers. get() pops any element O(1). check() is O(1) membership. release() adds back O(1). Queue + boolean array: Queue of free numbers for O(1) get. Boolean array for O(1) check. Release adds back to queue only if not already free. Implement an in-memory file system in Python supporting ls, mkdir, addContentToFile, and readContentFromFile using a trie with dict children. Topics: design-patterns, trie, object-design, dicts Companies: google, amazon, microsoft, meta, airbnb, uber Level: swe3, senior, staff Trie with dict children: Each node stores children dict and file content string. Traversal splits path on '/'. ls checks if terminal node is file or dir. Flat dict paths: Two flat dicts: dirs (set of dir paths) and files (file path -> content). ls iterates flat dict to find direct children. Implement a Trie (Prefix Tree) in Python with insert, search, and startsWith operations. Covers TrieNode dict approach and compact defaultdict solution. Topics: trie, design-patterns, strings, dicts Companies: google, amazon, meta, microsoft, apple, bloomberg, uber Level: swe2, swe3, senior TrieNode with dict children: Each node stores a dict of char->TrieNode and a boolean is_end. Dynamic children dict avoids fixed 26-slot arrays. Nested defaultdict (compact): Use nested defaultdict to avoid explicit TrieNode class. Terminator key signals end of word. Design a WordDictionary in Python with addWord and wildcard search using a Trie and DFS. Full solution with dot wildcard matching and test cases. Topics: trie, dfs, backtracking, strings Companies: google, amazon, meta, microsoft, bloomberg, linkedin Level: swe2, swe3, senior Trie with DFS for wildcard: Standard trie insertion. Search uses recursive DFS; when '.' is encountered, recursively check all children nodes. Dict of word lengths: Group words by length. search checks length match, then each stored word character by character allowing dots as wildcards. Simpler but higher memory overhead per lookup. Solve Word Search II in Python using a Trie combined with DFS backtracking on the board. Includes trie pruning optimization and full test cases. Topics: trie, backtracking, dfs, matrix Companies: amazon, google, meta, microsoft, bloomberg, airbnb Level: swe3, senior, staff Trie + DFS with pruning: Build trie from words. DFS from every cell, following trie branches. Record found words and delete trie nodes to avoid revisiting. Trie + DFS (class-based TrieNode): Same algorithm but with an explicit TrieNode class. Cleaner code, easier to extend. Implement a LIFO stack using only queues in Python. Covers one-queue rotation trick and two-queue swap approach with full test cases. Topics: stack, queue, design-patterns Companies: amazon, google, microsoft, bloomberg, adobe Level: new-grad, swe2 One queue, rotate on push: Use one deque. After appending new element, rotate (n-1) elements to front. Now front is always the top of stack. Two queues: q1 holds stack elements (top at front). On push, enqueue to q2, drain q1 into q2, then swap references. Implement a FIFO queue using two stacks in Python with amortized O(1) pop. Covers two-stack inbox/outbox approach and recursive one-stack solution. Topics: queue, stack, design-patterns Companies: amazon, google, meta, microsoft, bloomberg Level: new-grad, swe2 Two stacks - amortized O(1): inbox for pushes, outbox for pops/peeks. Transfer only when outbox empty. Each element moves at most twice total, giving amortized O(1). One stack with recursion: Pop all elements recursively to reach the bottom (front), perform operation, re-push everything. Elegant but O(n) per operation. Implement a Min Stack in Python that retrieves the minimum element in O(1). Covers auxiliary min stack and tuple-pair approaches with test cases. Topics: stack, design-patterns Companies: amazon, google, meta, microsoft, bloomberg, uber, apple Level: new-grad, swe2, swe3 Auxiliary min stack: Two stacks: main stack and min_stack. min_stack top always holds the minimum of the current stack state. Store (val, min) pairs: Each stack element is a tuple (value, current_min). Avoids a second stack, same time/space asymptotically. Implement a Max Stack in Python with O(log n) popMax using a max-heap and lazy deletion. Also covers the simpler two-stack O(n) approach. Topics: stack, design-patterns, heap, linked-list Companies: amazon, google, meta, bloomberg, stripe Level: swe3, senior, staff Heap + DLL with lazy deletion: DLL maintains stack order. Max-heap stores (-val, uid). popMax: pop heap lazily skipping deleted nodes, remove DLL node via uid lookup. Two stacks (O(n) popMax): Two stacks: main and max_stack (tracks max at each level). popMax is O(n): pop to temp until max found, push back. Simpler code. Solve Sliding Window Maximum in Python using a monotonic decreasing deque for O(n) time. Includes full walkthrough and test cases. Topics: deque, sliding-window, monotonic-stack, array Companies: amazon, google, meta, microsoft, bloomberg, uber, bytedance Level: swe3, senior, staff Monotonic decreasing deque: Deque stores indices in decreasing order of nums value. Front = current max index. Pop back when new element is larger; pop front when out of window. Brute force O(n*k): For each window position, take the max of k elements. Simple but too slow for large inputs. Solve Sliding Window Minimum in Python using a monotonic increasing deque for O(n) time. Includes sparse table RMQ alternative and test cases. Topics: deque, sliding-window, monotonic-stack, array Companies: amazon, google, microsoft, bloomberg, palantir Level: swe2, swe3, senior Monotonic increasing deque: Deque stores indices in increasing order of nums value (front = min). Pop back when new element is smaller; pop front when index falls outside window. Segment tree approach: Build a segment tree for range minimum queries. Each window query is O(log n), total O(n log n). Overkill here but demonstrates the general pattern. Find the first unique character in a character stream in Python using OrderedDict or a lazy-eviction deque. Full solutions with test cases. Topics: design-patterns, queue, hash-map, strings, deque Companies: amazon, google, meta, microsoft, twitter, bloomberg Level: swe2, swe3, senior OrderedDict + count: OrderedDict preserves insertion order. Count dict tracks frequency. showFirstUnique scans OrderedDict for first key with count 1. Deque with lazy eviction: Deque stores all added chars. count dict tracks frequency. showFirstUnique pops from front while count > 1 (lazy), then returns front or # if empty. Implement a HashMap from scratch in Python using separate chaining with prime buckets or a direct address table. Full solutions with test cases. Topics: hash-map, design-patterns, array, linked-list Companies: amazon, google, meta, microsoft, bloomberg, oracle Level: new-grad, swe2 Separate chaining with prime buckets: Array of 1009 buckets (prime reduces clustering). Each bucket is a list of (key, value) pairs. Operations scan the small chain list. Direct address table (for small key range): Use a fixed-size array of size max_key+1. Direct index gives O(1) for all operations. Only feasible when key range is small. Implement a HashSet from scratch in Python using separate chaining or a bytearray bitset. Full solutions with add, remove, contains and test cases. Topics: sets, design-patterns, hash-map, array Companies: amazon, google, microsoft, bloomberg, oracle, adobe Level: new-grad, swe2 Separate chaining with lists: Array of 1009 buckets, each a list of keys. add/remove/contains scan the small bucket list. Bitset / boolean array: Boolean array of size max_key+1. add sets True, remove sets False, contains returns the boolean. O(1) all operations. Implement a CombinationIterator in Python using itertools, a lazy bitmask generator, or a backtracking generator. Full solutions with test cases. Topics: design-patterns, backtracking, recursion, array Companies: google, amazon, meta, microsoft, bloomberg, palantir Level: swe2, swe3, senior Pre-generated list (itertools): Generate all combinations at init using itertools.combinations. Store as list in reverse for O(1) pop-from-back in lexicographic order. Lazy bitmask generator: Iterate all 2^n bitmasks in order; yield those with exactly k set bits. Builds combinations lazily without storing all upfront. Backtracking generator: Use a Python generator with backtracking to yield combinations lazily one at a time. next() calls next() on the generator object. Solve N-ary Tree Level Order Traversal in Python using BFS queue and recursive DFS with depth tracking. Includes full code with test cases. Topics: binary-tree, bfs, queue Companies: google, amazon, microsoft Level: new-grad, swe2 BFS with queue: Use a queue. Snapshot the queue size at each level, process exactly that many nodes, push all children. O(n) time and space. Recursive DFS: DFS with depth tracking. Pass the current depth and append the node value to result[depth]. O(n) time, O(h) stack space where h is height. Find the maximum depth of an N-ary tree in Python using recursive DFS and iterative BFS. Includes complexity analysis and test cases. Topics: binary-tree, dfs, bfs Companies: amazon, facebook, google Level: new-grad Recursive DFS: Recursively compute 1 + max depth of all children. If no children, return 1. If root is None, return 0. Iterative BFS: BFS level by level, counting levels. Return the total level count. Solve Diameter of Binary Tree in Python with DFS height tracking. Includes iterative post-order solution, complexity analysis, and test cases. Topics: binary-tree, dfs, recursion Companies: amazon, google, facebook, microsoft, apple Level: new-grad, swe2 DFS with global max: For each node compute height of left and right subtrees. The local diameter = left_h + right_h. Track global max. Return height = 1 + max(left_h, right_h). Iterative post-order: Iterative post-order traversal using a stack. Store heights in a dict keyed by node. Update diameter at each node. Find the LCA of deepest leaves in a binary tree using Python DFS. Two clean approaches with full code and complexity analysis. Topics: binary-tree, dfs, recursion Companies: google, amazon, facebook Level: swe2, swe3 DFS returning (node, depth): Each recursive call returns (LCA candidate, max depth in subtree). If left depth == right depth, current node is LCA. Otherwise recurse into the deeper side. Two-pass: find depth then LCA: First DFS to find max depth. Second DFS to find LCA of all nodes at max depth. Check if a binary tree is complete using Python BFS with None sentinel and array index approaches. Full code and test cases included. Topics: binary-tree, bfs Companies: amazon, facebook, google, microsoft Level: swe2, swe3 BFS with None sentinel: BFS. Once a None is dequeued, set a flag. If any subsequent non-None node is dequeued, return False. Array index check: Number nodes with BFS index (root=1, left=2i, right=2i+1). The tree is complete iff count of nodes equals max index. Replace each node with the sum of its cousins using Python BFS. Level-sum and sibling-sum trick explained with full code. Topics: binary-tree, bfs, dfs, hash-map Companies: google, amazon Level: swe2, swe3 BFS two-pass: BFS. At each level compute total level sum. Then for each parent node, sibling sum = left.val + right.val. Assign each child: cousin_sum = level_sum - sibling_sum. Validate an Even-Odd tree using Python BFS with level-by-level parity and ordering checks. Full code with test cases. Topics: binary-tree, bfs Companies: amazon, google, microsoft Level: swe2 BFS level validation: BFS. At each level, check: even level -> values must be odd and strictly increasing. Odd level -> values must be even and strictly decreasing. Find shortest directions between two binary tree nodes in Python using root-to-node paths and LCA prefix removal. Full code included. Topics: binary-tree, dfs, strings Companies: google, amazon, facebook Level: swe2, swe3 Root-to-node paths + LCA trick: Find path from root to start and root to dest. Strip common prefix (which is path to LCA). Answer = "U"*len(remaining_start) + remaining_dest. Count pseudo-palindromic root-to-leaf paths using Python DFS with XOR bitmask. Includes iterative solution and full test cases. Topics: binary-tree, dfs, bit-manipulation Companies: amazon, google, adobe Level: swe2, swe3 DFS with bitmask: XOR bitmask tracks odd/even frequency of each digit. At a leaf, check if at most one bit is set using mask & (mask-1) == 0. Iterative DFS with stack: Iterative DFS using explicit stack storing (node, mask) pairs. Same bitmask logic at leaves. Sum all nodes whose grandparent has even value using Python DFS with parent tracking. BFS alternative also included. Topics: binary-tree, dfs, bfs Companies: amazon, google Level: swe2 DFS with parent/grandparent tracking: Recursive DFS passing parent and grandparent values. Add current node value when grandparent is even. BFS with grandchildren tracking: BFS. For each even-valued node, add the values of all its grandchildren (children of children). Build a binary tree from parent-child descriptions using Python hash map. Find root by tracking child set. Full code with test cases. Topics: binary-tree, hash-map, dfs Companies: amazon, google, facebook Level: swe2, swe3 Hash map + child set: Build all nodes in a dict. Track all child values in a set. Root is the node whose value never appears as a child. Count nodes where value equals floor average of subtree using Python post-order DFS. Full code with complexity analysis and test cases. Topics: binary-tree, dfs, recursion Companies: amazon, google, microsoft Level: swe2 Post-order DFS: Each call returns (total_sum, count). At the node, total = left_sum + right_sum + node.val, cnt = left_cnt + right_cnt + 1. Check node.val == total // cnt. Find the level with maximum sum in a binary tree using Python BFS. Simple level-order traversal with sum tracking. Topics: binary-tree, bfs Companies: amazon, google, facebook Level: new-grad, swe2 BFS level sum: BFS. At each level compute sum. Track max sum and corresponding level. Return that level. Reverse values at odd levels of a perfect binary tree using Python BFS and DFS mirror swap. Full code with test cases. Topics: binary-tree, bfs, dfs Companies: google, amazon, microsoft Level: swe2, swe3 BFS with value reversal at odd levels: BFS. At odd levels collect all nodes, reverse their values (not the nodes themselves). Continue BFS normally. DFS mirror swap: DFS with two symmetric nodes. At odd levels swap their values. Recurse with outer-outer and inner-inner child pairs. Count good nodes in a binary tree where no ancestor has a greater value. Python DFS with max tracking. Iterative and recursive solutions. Topics: binary-tree, dfs Companies: google, amazon, facebook, microsoft Level: new-grad, swe2 DFS with max tracking: DFS from root, carrying max value along the path. Count the node if node.val >= max. Update max before recursing. Iterative DFS with stack: Iterative DFS using explicit stack of (node, max_so_far). Count good nodes as we go. Solve 3D Trapping Rain Water using Python min-heap BFS. Process border cells outward, accumulate trapped water. Full code with complexity analysis. Topics: matrix, heap, bfs, greedy Companies: google, amazon, facebook, microsoft, bloomberg Level: swe3, senior, staff Min-heap BFS (3D water fill): Push all border cells into a min-heap. BFS inward always processing the lowest boundary cell. Water at interior cell = max(0, boundary_height - cell_height). Update boundary to max(boundary_height, cell_height). Find the largest square of 1s in a binary matrix using Python DP. Includes O(mn) and O(n) space solutions with full code. Topics: dynamic-programming, matrix Companies: amazon, google, facebook, microsoft, apple, bloomberg Level: swe2, swe3, senior DP 2D table: dp[i][j] = max side when bottom-right is (i,j). Transition: min of three neighbors + 1. Track global max side. DP O(n) space: Use a 1D dp array and a prev variable to store dp[i-1][j-1]. Reduces space to O(n). Find the maximal rectangle of 1s in a binary matrix using Python histogram with monotonic stack. DP left/right approach also included. Topics: dynamic-programming, stack, matrix, monotonic-stack Companies: amazon, google, facebook, microsoft, bloomberg, goldman-sachs Level: swe3, senior Histogram + monotonic stack: Convert each row into heights (running count of consecutive 1s above). Apply largest-rectangle-in-histogram with a monotonic stack for each row. DP left/right/height arrays: For each cell track: height (consecutive 1s above), left boundary (leftmost contiguous 1 in current row), right boundary. Area = height*(right-left). Find the longest consecutive sequence in O(n) using Python hash set. Union-Find alternative included. Full code with test cases. Topics: array, hash-map, sets Companies: amazon, google, facebook, microsoft, linkedin, uber Level: swe2, swe3 Hash set O(n): Build a set. For each num where num-1 is not in the set (sequence start), count consecutive nums. Each element is visited at most twice. Union-Find approach: Union each num with num+1 if both exist. Track component sizes. Max size is the answer. Find the first missing positive integer in O(n) time O(1) space using cyclic sort and index marking in Python. Complete solutions with test cases. Topics: array, sorting Companies: amazon, google, facebook, microsoft, bloomberg, stripe Level: swe3, senior Cyclic sort: For each index, swap nums[i] into its correct position (index nums[i]-1) while 1 <= nums[i] <= n and nums[i] != nums[nums[i]-1]. Then find the first index where nums[i] != i+1. Index marking (sign flip): First pass: replace non-positives and out-of-range with n+1. Second pass: for each value v in [1,n], negate nums[v-1]. Third pass: first non-negative index+1 is the answer. Solve Text Justification in Python using greedy line packing and space distribution. Full simulation with edge cases and test output. Topics: strings, greedy Companies: google, amazon, facebook, microsoft, bloomberg, uber Level: swe3, senior Greedy line packing: Group words greedily. For each non-last line compute total extra spaces, distribute left to right. Last line is left-justified with single spaces and trailing spaces. Solve Jump Game VI with max score using Python DP and monotonic deque for O(n) sliding window max. Full code with test cases. Topics: dynamic-programming, deque, sliding-window Companies: amazon, google, microsoft, linkedin Level: swe2, swe3 DP + monotonic deque: dp[i] = nums[i] + max(dp[i-k..i-1]). Maintain a max-deque of dp values within the window. Deque front is always the max. DP + segment tree (for clarity): Use a segment tree for range max queries. dp[i] = nums[i] + range_max(dp, i-k, i-1). O(n log n). Solve minimum cost stick cutting using Python interval DP. Both bottom-up table and top-down memoized recursion explained with full code. Topics: dynamic-programming, interval Companies: amazon, google, facebook, bloomberg Level: swe3, senior Interval DP: Sort cuts, add 0 and n as boundaries. dp[i][j] = min cost to cut the segment [cuts[i], cuts[j]]. For each sub-segment try every cut as the last one. Memoized recursion: Top-down DP. rec(i, j) = min cost for all cuts strictly inside [cuts[i], cuts[j]]. Try each cut as the first cut in that segment. Find the largest color value along any path in a directed graph using Python topological sort and DP. Cycle detection included. Topics: graph, topological-sort, dynamic-programming, hash-map Companies: google, amazon, facebook, coinbase Level: senior, staff Kahn's topological sort + DP: Build adjacency list and in-degree. Kahn's BFS topological sort. dp[u][c] = max color-c count on path ending at u. Propagate: dp[v][c] = max(dp[v][c], dp[u][c] + (colors[v]==c)). Answer = max over all nodes and colors. If not all nodes processed, cycle exists. Find minimum completion time for parallel courses using Python topological sort and critical path DP. Full code with test cases. Topics: graph, topological-sort, dynamic-programming Companies: google, amazon, facebook, linkedin, databricks Level: senior, staff Topological sort critical path: Kahn's BFS topological sort. dp[i] = earliest completion time. When processing course u, update each dependent v: dp[v] = max(dp[v], dp[u] + time[v-1]). Answer = max(dp). Count valid vowel strings of length n using Python DP state transitions and matrix exponentiation. Full code with modular arithmetic. Topics: dynamic-programming, math, combinatorics Companies: google, amazon, facebook Level: swe3, senior DP on vowel states: Track count of strings ending with each vowel. Update using the allowed transitions (reversed: which vowels can precede each vowel). Iterate n-1 times. Matrix exponentiation: Model transitions as a 5x5 matrix. Use fast matrix exponentiation for very large n. O(26^3 * log n) but with only 5 vowels it is O(5^3 * log n). Solve Strange Printer with minimum turns using Python interval DP. Merge matching characters to reduce turns. Full code with test cases. Topics: dynamic-programming, interval, recursion Companies: google, amazon, facebook, bloomberg Level: senior, staff Interval DP bottom-up: dp[i][j] = min turns for s[i..j]. Base: dp[i][i]=1. For each character s[k] in (i,j] where s[k]==s[i], dp[i][j] = min(dp[i][j], dp[i+1][k] + dp[k][j]) (s[i] merges with s[k]). Memoized recursion: Top-down DP. Deduplicate consecutive chars first. rec(i,j) = min turns for s[i..j]. Try merging s[i] with each matching s[k]. Find minimum days to disconnect an island grid using Python DFS. Exploit the observation that the answer is always 0, 1, or 2. Topics: graph, dfs, matrix Companies: google, amazon, facebook Level: senior, staff Observation: answer <= 2 + brute force check: Count islands. If != 1 return 0. Try removing each land cell and re-count islands; if any gives != 1 return 1. Otherwise return 2. Minimize total robot travel distance to factories using Python DP with expanded slots or memoized recursion. Full code with test cases. Topics: dynamic-programming, sorting, greedy Companies: google, amazon, facebook, palantir Level: senior, staff Sort + DP on expanded factories: Sort robots and factories. Expand each factory position by its limit into individual slots. dp[i][j] = min cost to assign first i robots to first j slots. dp[i][j] = min(dp[i-1][j-1]+|r[i]-slot[j]|, dp[i][j-1]). Memoized recursion: Top-down DP with lru_cache on (robot_idx, factory_idx, capacity_used). Sort both arrays first. Minimize the max pair difference using Python binary search and greedy pair counting on a sorted array. Full code with complexity analysis. Topics: binary-search, greedy, sorting Companies: amazon, google, microsoft, bloomberg Level: swe2, swe3 Binary search + greedy pair count: Sort nums. Binary search on answer mid. Greedy: scan sorted nums, if nums[i+1]-nums[i] <= mid, take pair and skip i+1, else move forward. If pairs >= p, mid might be feasible. Count all palindromic substrings using Python expand-around-center O(n^2) and Manacher's O(n) algorithm. Full code with test cases. Topics: strings, dynamic-programming, two-pointers Companies: amazon, google, facebook, microsoft, linkedin Level: swe2, swe3 Expand around center: For each of the 2n-1 centers, expand outward while characters match. Count palindromes found. Manacher's algorithm O(n): Manacher's algorithm computes palindrome radii in O(n). Sum the ceiling of each radius+1 to count palindromes. Find the shortest palindrome by prepending characters using Python KMP failure function. O(n) solution with full explanation and test cases. Topics: strings, string-matching, two-pointers Companies: google, amazon, facebook, bloomberg Level: senior, staff KMP failure function: Construct t = s + "#" + reverse(s). Run KMP to find the longest prefix of t that is also a suffix, which gives the longest palindromic prefix of s. Two-pointer + recursion: Find the longest palindrome starting from index 0 greedily. Reverse the rest and prepend. Recurse on remaining middle part. Implement wildcard pattern matching with ? and * in Python using 2D DP and greedy two-pointer. Full solutions with complexity analysis. Topics: dynamic-programming, strings, greedy, recursion Companies: amazon, google, facebook, microsoft, bloomberg Level: swe3, senior DP 2D table: dp[i][j] = does p[:j] match s[:i]. Handle "*" by either matching empty (dp[i][j-1]) or one character (dp[i-1][j]). Greedy two-pointer: Track last "*" position in pattern and last match position in s. When mismatch, backtrack to last "*" and advance s. Implement regular expression matching with . and * in Python using 2D DP and memoized recursion. Full code with all edge cases. Topics: dynamic-programming, strings, recursion Companies: google, amazon, facebook, microsoft, bloomberg, uber Level: senior, staff DP 2D table: dp[i][j] = match. "*" can mean zero (dp[i][j-2]) or extend if preceding element matches (dp[i-1][j]). "." matches any character. Recursive with memoization: Top-down recursion. Base cases: empty pattern, empty string. Handle "*" by trying zero or one match. Cache results. Compute the minimum edit distance (Levenshtein) between two strings using Python 2D DP and space-optimized O(n) version. Full code with test cases. Topics: dynamic-programming, strings Companies: amazon, google, facebook, microsoft, linkedin, uber, bloomberg Level: swe2, swe3, senior DP 2D table: Classic DP. dp[i][j] = Levenshtein distance for word1[:i] and word2[:j]. Three transitions: insert, delete, replace. DP O(n) space: Use a single row dp array, updating in place. Track the diagonal value with a prev variable. Find all sentence breakdowns of a string using a word dictionary in Python with memoized backtracking and DP pruning. Full code with test cases. Topics: dynamic-programming, backtracking, memoization, trie, strings Companies: amazon, google, facebook, microsoft, bloomberg, apple Level: swe3, senior Backtracking with memoization: Recursive backtrack from index i. Try all dict words that match at i. Memoize (index -> list of sentences from that index). DP precompute + backtrack: First DP pass checks if s[i:] is breakable. Then backtrack only on reachable indices (pruning invalid branches). Find all concatenated words formed from shorter words using Python DP Word Break and Trie DFS. Full code with test cases. Topics: dynamic-programming, trie, dfs, strings Companies: amazon, google, facebook, microsoft Level: senior, staff DP word break per word: Sort words by length. Maintain a set of shorter words. For each word, run Word Break DP: dp[i]=True if s[:i] can be formed from shorter words. A word is concatenated if dp[n] is True and it uses at least 2 pieces. Trie + DFS: Build a Trie of all words. For each word, DFS through trie matching characters. On end-of-word node, recursively check remainder. Count segments; if >= 2, it is a concatenated word. Count distinct subsequences of s equal to t using Python 2D DP and O(n) space optimized version. Full code with test cases. Topics: dynamic-programming, strings Companies: amazon, google, facebook, bloomberg Level: swe3, senior DP 2D table: dp[i][j] = ways to form t[:j] using s[:i]. Match: use dp[i-1][j-1] (use s[i]) + dp[i-1][j] (skip s[i]). No match: dp[i-1][j] (skip s[i]). DP O(n) space: Use a 1D dp array, update right to left to avoid overwriting values needed for current row. Check if s3 is an interleaving of s1 and s2 using Python 2D DP and O(n) space optimization. Full code with test cases. Topics: dynamic-programming, strings, recursion Companies: amazon, google, facebook, microsoft, bloomberg Level: swe2, swe3 DP 2D table: dp[i][j] = is s3[:i+j] an interleaving of s1[:i] and s2[:j]. Transition uses either s1[i-1] or s2[j-1] to extend s3[i+j-1]. DP O(n) space: Optimize to a 1D dp array by noting that dp[i][j] only depends on dp[i-1][j] and dp[i][j-1]. Find all shortest word ladder transformation sequences using Python BFS with parent map and backtracking. Bidirectional BFS also included. Topics: graph, bfs, backtracking, hash-map, strings Companies: amazon, google, facebook, microsoft, bloomberg, uber Level: senior, staff BFS layer-by-layer + backtrack: BFS layer by layer. For each word at current layer, find all one-letter neighbors in wordList. Record parent->children. Stop after finding endWord level. Backtrack from endWord using parent map. Bidirectional BFS + backtrack: Expand from both beginWord and endWord simultaneously, meeting in the middle. Significantly reduces the BFS frontier. Then backtrack through the merged parent map.Reverse a String - Python Solution | Engineers of AI
Count Vowels in a String - Python Solution | Engineers of AI
Check Palindrome - Python Solution | Engineers of AI
FizzBuzz - Python Solution | Engineers of AI
Find Duplicates in a List - Python Solution | Engineers of AI
Flatten a Nested List - Python Solution | Engineers of AI
List Comprehension Filter and Transform - Python | Engineers of AI
Word Frequency Counter - Python Solution | Engineers of AI
Implement a Stack Using a List - Python Solution | Engineers of AI
Implement a Queue Using Deque - Python Solution | Engineers of AI
BankAccount Class - Python OOP Solution | Engineers of AI
Decorator: Timing Function - Python Solution | Engineers of AI
Fibonacci Generator - Python Solution | Engineers of AI
Context Manager for File Handling - Python Solution | Engineers of AI
Filter Evens with Lambda and Filter - Python Solution | Engineers of AI
Email Validator with Regex - Python Solution | Engineers of AI
String Formatting: Format a Receipt - Python Solution | Engineers of AI
Read and Count Lines from a File - Python Solution | Engineers of AI
Custom Exception Classes - Python Solution | Engineers of AI
Type-Hinted Stack Implementation - Python Solution | Engineers of AI
Zip and Enumerate Together - Python Solution | Engineers of AI
Default Mutable Argument Bug - Python Solution | Engineers of AI
*args and **kwargs Variadic Functions - Python Solution | Engineers of AI
Closure Counter - Python Solution | Engineers of AI
Inheritance: Shape Hierarchy - Python Solution | Engineers of AI
Abstract Base Class: Animal - Python Solution | Engineers of AI
Custom Iterator: Countdown - Python Solution | Engineers of AI
Property Decorator: Temperature Converter - Python Solution | Engineers of AI
Named Tuples: Point and Distance - Python Solution | Engineers of AI
Dataclass: Student Registry - Python Solution | Engineers of AI
Two Sum - Python Hash Map Solution | Engineers of AI
Best Time to Buy and Sell Stock - Greedy Python Solution | Engineers of AI
Contains Duplicate - Python Set Solution | Engineers of AI
Product of Array Except Self - Python Solution | Engineers of AI
Maximum Subarray - Kadane's Algorithm Python | Engineers of AI
Maximum Product Subarray - Python Solution | Engineers of AI
Find Minimum in Rotated Sorted Array - Python Solution | Engineers of AI
Search in Rotated Sorted Array - Python Solution | Engineers of AI
Three Sum - Python Two Pointers Solution | Engineers of AI
Container With Most Water - Python Two Pointers | Engineers of AI
Valid Anagram - Python Solution | Engineers of AI
Group Anagrams - Python Solution | Engineers of AI
Longest Common Prefix - Python Solution | Engineers of AI
Valid Parentheses - Python Stack Solution | Engineers of AI
Reverse Words in a String - Python Solution | Engineers of AI
String Compression - Python Solution | Engineers of AI
Rotate Array - Python Three Reverses Solution | Engineers of AI
Missing Number - Python Math and XOR Solutions | Engineers of AI
Single Number XOR Trick - Python Solution | Engineers of AI
Move Zeroes - Python Two Pointers Solution | Engineers of AI
Merge Intervals - Python Sort Solution | Engineers of AI
Insert Interval - Python Solution | Engineers of AI
Spiral Matrix - Python Boundary Simulation | Engineers of AI
Set Matrix Zeroes - Python O(1) Space Solution | Engineers of AI
Longest Substring Without Repeating Characters - Python | Engineers of AI
Minimum Window Substring - Python Sliding Window | Engineers of AI
Find All Anagrams in a String - Python Sliding Window | Engineers of AI
Subarray Sum Equals K - Python Prefix Sum Solution | Engineers of AI
Trapping Rain Water - Python Two Pointers Solution | Engineers of AI
Jump Game - Python Greedy Solution | Engineers of AI
Reverse Linked List - Python Iterative and Recursive | Engineers of AI
Detect Cycle in Linked List - Python Floyd's Algorithm | Engineers of AI
Find Middle of Linked List - Python Slow/Fast Pointers | Engineers of AI
Merge Two Sorted Lists - Python Solution | Engineers of AI
Remove Nth Node from End of List - Python Solution | Engineers of AI
Palindrome Linked List - Python Solution | Engineers of AI
Intersection of Two Linked Lists - Python Solution | Engineers of AI
Remove Duplicates from Sorted List - Python Solution | Engineers of AI
Insert into Circular Linked List - Python Solution | Engineers of AI
Delete Node in Linked List - Python Solution | Engineers of AI
Add Two Numbers Linked List - Python Solution | Engineers of AI
Reverse Nodes in k-Group - Python Solution | Engineers of AI
Copy List with Random Pointer - Python Solution | Engineers of AI
LRU Cache - Python Doubly Linked List Solution | Engineers of AI
Sort List (Merge Sort on Linked List) - Python Solution | Engineers of AI
Reorder List - Python Solution | Engineers of AI
Swap Nodes in Pairs - Python Solution | Engineers of AI
Partition List - Python Solution | Engineers of AI
Flatten Multilevel Doubly Linked List - Python Solution | Engineers of AI
Rotate List - Python Solution | Engineers of AI
Binary Tree Inorder Traversal - Python Recursive and Iterative | Engineers of AI
Binary Tree Level Order Traversal - Python BFS | Engineers of AI
Maximum Depth of Binary Tree - Python Solution | Engineers of AI
Symmetric Tree - Python Recursive Solution | Engineers of AI
Invert Binary Tree - Python Solution | Engineers of AI
Diameter of Binary Tree - Python DFS Solution | Engineers of AI
Path Sum - Python DFS Solution | Engineers of AI
Lowest Common Ancestor of BST - Python Solution | Engineers of AI
Validate Binary Search Tree - Python DFS with Bounds | Engineers of AI
Kth Smallest Element in BST - Python Inorder Solution | Engineers of AI
Convert Sorted Array to BST - Python Solution | Engineers of AI
Binary Tree Maximum Path Sum - Python DFS Solution | Engineers of AI
Serialize and Deserialize Binary Tree - Python Solution | Engineers of AI
Binary Tree Right Side View - Python BFS Solution | Engineers of AI
Sum Root to Leaf Numbers - Python DFS Solution | Engineers of AI
Subtree of Another Tree - Python DFS Solution | Engineers of AI
Balanced Binary Tree - Python Post-Order DFS | Engineers of AI
Implement Trie (Prefix Tree) - Python Solution | Engineers of AI
Flatten Binary Tree to Linked List - Python Solution | Engineers of AI
Construct Binary Tree from Preorder and Inorder - Python | Engineers of AI
Number of Islands - Python DFS BFS Solution | Engineers of AI
Clone Graph DFS BFS - Python | Engineers of AI
Course Schedule Topological Sort - Python | Engineers of AI
Pacific Atlantic Water Flow BFS - Python | Engineers of AI
Word Ladder BFS Shortest Path - Python | Engineers of AI
Graph Valid Tree Union Find DFS - Python | Engineers of AI
Number of Connected Components - Python Union Find | Engineers of AI
Alien Dictionary Topological Sort - Python | Engineers of AI
Shortest Path in Binary Matrix BFS - Python | Engineers of AI
Surrounded Regions DFS - Python | Engineers of AI
Rotting Oranges Multi-Source BFS - Python | Engineers of AI
Find if Path Exists in Graph - Python | Engineers of AI
Max Area of Island DFS - Python | Engineers of AI
Network Delay Time Dijkstra - Python | Engineers of AI
Find the Town Judge - Python | Engineers of AI
Is Graph Bipartite BFS 2-Coloring - Python | Engineers of AI
Kruskal's Minimum Spanning Tree - Python | Engineers of AI
Accounts Merge Union Find - Python | Engineers of AI
Redundant Connection Union Find - Python | Engineers of AI
Walls and Gates Multi-Source BFS - Python | Engineers of AI
Climbing Stairs DP - Python | Engineers of AI
House Robber DP - Python | Engineers of AI
House Robber II Circular DP - Python | Engineers of AI
Longest Increasing Subsequence DP Binary Search - Python | Engineers of AI
Coin Change DP - Python | Engineers of AI
Word Break DP - Python | Engineers of AI
Unique Paths DP - Python | Engineers of AI
Jump Game Greedy DP - Python | Engineers of AI
Jump Game II Minimum Jumps - Python | Engineers of AI
Longest Common Subsequence DP - Python | Engineers of AI
Edit Distance DP - Python | Engineers of AI
Partition Equal Subset Sum DP - Python | Engineers of AI
Target Sum DP DFS - Python | Engineers of AI
Decode Ways DP - Python | Engineers of AI
Best Time to Buy and Sell Stock III - Python | Engineers of AI
Palindrome Partitioning II Minimum Cuts - Python | Engineers of AI
Wildcard Matching DP - Python | Engineers of AI
Regular Expression Matching DP - Python | Engineers of AI
Maximum Product Subarray DP - Python | Engineers of AI
Triangle Minimum Path Sum DP - Python | Engineers of AI
Minimum Path Sum Grid DP - Python | Engineers of AI
Burst Balloons Interval DP - Python | Engineers of AI
0/1 Knapsack DP - Python | Engineers of AI
Rod Cutting DP - Python | Engineers of AI
Egg Drop Problem DP - Python | Engineers of AI
Merge Sort Implementation - Python | Engineers of AI
Quick Sort Implementation - Python | Engineers of AI
Heap Sort Implementation - Python | Engineers of AI
Find K-th Largest Element - Python Heap Quickselect | Engineers of AI
Sort Colors Dutch National Flag - Python | Engineers of AI
Merge Intervals - Python | Engineers of AI
Insert Interval - Python | Engineers of AI
Search in Rotated Sorted Array - Python | Engineers of AI
Find Peak Element Binary Search - Python | Engineers of AI
Search a 2D Matrix Binary Search - Python | Engineers of AI
Median of Two Sorted Arrays - Python | Engineers of AI
Find Minimum in Rotated Sorted Array - Python | Engineers of AI
H-Index - Python | Engineers of AI
Meeting Rooms II Min Heap - Python | Engineers of AI
Largest Number Custom Sort - Python | Engineers of AI
3Sum Two Pointers - Python | Engineers of AI
4Sum Two Pointers - Python | Engineers of AI
Container With Most Water Two Pointers - Python | Engineers of AI
Trapping Rain Water Two Pointers DP - Python | Engineers of AI
Minimum Window Substring Sliding Window - Python | Engineers of AI
Longest Substring Without Repeating - Python | Engineers of AI
Permutation in String Sliding Window - Python | Engineers of AI
Find All Anagrams in a String - Python | Engineers of AI
Longest Repeating Character Replacement - Python | Engineers of AI
Max Consecutive Ones III Sliding Window - Python | Engineers of AI
Fruit Into Baskets Sliding Window - Python | Engineers of AI
Subarrays with K Different Integers - Python | Engineers of AI
Minimum Size Subarray Sum Sliding Window - Python | Engineers of AI
Longest Subarray of 1s After Deleting One Element - Python | Engineers of AI
Count Nice Subarrays - Python | Engineers of AI
Valid Parentheses Stack - Python | Engineers of AI
Min Stack Design - Python | Engineers of AI
Evaluate Reverse Polish Notation Stack - Python | Engineers of AI
Daily Temperatures Monotonic Stack - Python | Engineers of AI
Largest Rectangle in Histogram Stack - Python | Engineers of AI
Implement Queue Using Stacks - Python | Engineers of AI
Implement Stack Using Queues - Python | Engineers of AI
Sliding Window Maximum Monotonic Deque - Python | Engineers of AI
Next Greater Element Monotonic Stack - Python | Engineers of AI
Basic Calculator II Stack - Python | Engineers of AI
Single Number XOR Bit Manipulation - Python | Engineers of AI
Number of 1 Bits Hamming Weight - Python | Engineers of AI
Reverse Bits - Python | Engineers of AI
Missing Number Math XOR - Python | Engineers of AI
Power of Two Bit Manipulation - Python | Engineers of AI
Counting Bits DP Bit Manipulation - Python | Engineers of AI
Sum of Two Integers Bit Manipulation - Python | Engineers of AI
Reverse Integer - Python | Engineers of AI
Palindrome Number - Python | Engineers of AI
Integer to Roman Numeral - Python | Engineers of AI
Roman to Integer - Python | Engineers of AI
Excel Sheet Column Number - Python | Engineers of AI
Happy Number Cycle Detection - Python | Engineers of AI
Sqrt(x) Binary Search - Python | Engineers of AI
Greatest Common Divisor of Strings - Python | Engineers of AI
Single Number - XOR Bit Manipulation Python | Engineers of AI
Single Number II - Bit Manipulation Every Element 3 Times | Engineers of AI
Single Number III - Two Unique Numbers XOR Python | Engineers of AI
Hamming Weight Number of 1 Bits Python | Engineers of AI
Reverse Bits 32-bit Integer Python | Engineers of AI
Missing Number XOR Gauss Formula Python | Engineers of AI
Power of Two Bit Manipulation Python | Engineers of AI
Counting Bits DP Python Solution | Engineers of AI
Sum of Two Integers Without Plus Operator Python | Engineers of AI
Reverse Integer Python with Overflow Check | Engineers of AI
Palindrome Number Python Without String | Engineers of AI
Integer to Roman Numeral Python | Engineers of AI
Roman to Integer Python Solution | Engineers of AI
Excel Sheet Column Number Python Base-26 | Engineers of AI
Happy Number Cycle Detection Python | Engineers of AI
Sqrt(x) Binary Search Newton Method Python | Engineers of AI
GCD LCM Euclidean Algorithm Python | Engineers of AI
Sieve of Eratosthenes Count Primes Python | Engineers of AI
Fast Power Exponentiation Python O(log n) | Engineers of AI
Multiply Strings Python Grade School Algorithm | Engineers of AI
Add Binary Strings Python | Engineers of AI
Add Two Numbers Strings Python Without int() | Engineers of AI
Count Digit 1 in Range 0 to N Python | Engineers of AI
Nth Ugly Number DP Three Pointers Python | Engineers of AI
Perfect Squares Minimum Count DP BFS Python | Engineers of AI
Merge Sort Python Implementation | Engineers of AI
Quick Sort Randomized Pivot Python | Engineers of AI
Heap Sort Python Implementation | Engineers of AI
Find Kth Largest Element Python - Heap and Quickselect | Engineers of AI
Sort Colors Dutch National Flag Python | Engineers of AI
Merge Intervals Python Solution | Engineers of AI
Insert Interval Python Solution | Engineers of AI
Search in Rotated Sorted Array Python | Engineers of AI
Find Peak Element Binary Search Python | Engineers of AI
Search 2D Matrix Binary Search Python | Engineers of AI
Median of Two Sorted Arrays Python O(log n) | Engineers of AI
Find Minimum Rotated Sorted Array Python | Engineers of AI
H-Index Python Solution | Engineers of AI
Meeting Rooms II Python Min Heap | Engineers of AI
Largest Number Custom Sort Python | Engineers of AI
Count Smaller Numbers After Self Python Merge Sort | Engineers of AI
Sort Linked List Merge Sort Python | Engineers of AI
Top K Frequent Elements Python Heap Bucket Sort | Engineers of AI
Top K Frequent Words Python Heap | Engineers of AI
Find K Closest Elements Binary Search Python | Engineers of AI
Kth Smallest in Sorted Matrix Python Heap Binary Search | Engineers of AI
Find K Pairs Smallest Sums Python Min Heap | Engineers of AI
Sort Characters By Frequency Python | Engineers of AI
Wiggle Sort II Python | Engineers of AI
Relative Ranks Python | Engineers of AI
3Sum Two Pointers Python | Engineers of AI
4Sum Python Two Pointers | Engineers of AI
Container With Most Water Two Pointers Python | Engineers of AI
Trapping Rain Water Python Two Pointers | Engineers of AI
Minimum Window Substring Python Sliding Window | Engineers of AI
Longest Substring Without Repeating Characters Python | Engineers of AI
Permutation in String Sliding Window Python | Engineers of AI
Find All Anagrams in String Python | Engineers of AI
Longest Repeating Character Replacement Python | Engineers of AI
Max Consecutive Ones III Sliding Window Python | Engineers of AI
Fruit Into Baskets Sliding Window Python | Engineers of AI
Subarrays with K Different Integers Python | Engineers of AI
Minimum Size Subarray Sum Python Sliding Window | Engineers of AI
Longest Subarray of 1s After Deleting One Element Python | Engineers of AI
Count Nice Subarrays with K Odd Numbers Python | Engineers of AI
Subarray Product Less Than K Sliding Window Python | Engineers of AI
Minimum Operations Reduce X to Zero Python | Engineers of AI
Maximum Erasure Value Sliding Window Python | Engineers of AI
Substrings Containing All Three Characters Python | Engineers of AI
Replace Substring for Balanced String Python | Engineers of AI
Sliding Window Median Python Two Heaps | Engineers of AI
Maximum Points from Cards Sliding Window Python | Engineers of AI
Longest Subarray Absolute Diff at Most Limit Python | Engineers of AI
Grumpy Bookstore Owner Sliding Window Python | Engineers of AI
Minimum K Consecutive Bit Flips Python | Engineers of AI
Valid Parentheses Stack Python | Engineers of AI
Min Stack Design Python O(1) | Engineers of AI
Evaluate Reverse Polish Notation Stack Python | Engineers of AI
Daily Temperatures Monotonic Stack Python | Engineers of AI
Largest Rectangle in Histogram Stack Python | Engineers of AI
Implement Queue Using Stacks Python | Engineers of AI
Implement Stack Using Queues Python | Engineers of AI
Sliding Window Maximum Monotonic Deque Python | Engineers of AI
Next Greater Element I Monotonic Stack Python | Engineers of AI
Next Greater Element II Circular Array Python | Engineers of AI
Basic Calculator Stack Python | Engineers of AI
Basic Calculator II Stack Python | Engineers of AI
Remove Duplicate Letters Greedy Stack Python | Engineers of AI
Remove K Digits Smallest Number Python | Engineers of AI
132 Pattern Monotonic Stack Python | Engineers of AI
Score of Parentheses Stack Python | Engineers of AI
Asteroid Collision Stack Python | Engineers of AI
Online Stock Span Monotonic Stack Python | Engineers of AI
Sum of Subarray Minimums Monotonic Stack Python | Engineers of AI
Maximal Rectangle Matrix Stack Python | Engineers of AI
Car Fleet Stack Python | Engineers of AI
Decode String Stack Python | Engineers of AI
Maximum Width Ramp Monotonic Stack Python | Engineers of AI
Number of Visible People in Queue Stack Python | Engineers of AI
Minimum Add Make Parentheses Valid Python | Engineers of AI
Kth Largest Element Heap Python | Engineers of AI
Find Median from Data Stream Two Heaps Python | Engineers of AI
Merge K Sorted Lists Heap Divide Conquer Python | Engineers of AI
Task Scheduler Greedy Heap Python | Engineers of AI
Reorganize String No Adjacent Duplicates Python | Engineers of AI
K Closest Points to Origin Heap Python | Engineers of AI
Smallest Range Covering K Lists Python | Engineers of AI
Ugly Number II DP Three Pointers Python | Engineers of AI
Super Ugly Number DP Python | Engineers of AI
IPO Maximize Capital Two Heaps Python | Engineers of AI
Furthest Building Reach Greedy Heap Python | Engineers of AI
Single Threaded CPU Heap Simulation Python | Engineers of AI
Skyline Problem Heap Python | Engineers of AI
Employee Free Time Intervals Python | Engineers of AI
Minimum Cost Hire K Workers Python | Engineers of AI
Seat Reservation Manager Min Heap Python | Engineers of AI
Maximum Subsequence Score Greedy Heap Python | Engineers of AI
Minimum Refueling Stops Greedy Heap Python | Engineers of AI
Kth Smallest Prime Fraction Heap Python | Engineers of AI
Minimize Deviation in Array Heap Python | Engineers of AI
Maximum Performance of Team Heap Sort Python | Engineers of AI
Kth Largest in Stream Min Heap Python | Engineers of AI
Top K Frequent from Stream Design Python | Engineers of AI
Process Tasks Using Servers Two Heaps Python | Engineers of AI
Swim in Rising Water Dijkstra Binary Search Python | Engineers of AI
LRU Cache OrderedDict Python | Engineers of AI
LFU Cache O(1) Python Implementation | Engineers of AI
Thread-Safe Singleton Metaclass Python | Engineers of AI
Observer Pattern Python OOP | Engineers of AI
Python Iterator Protocol __iter__ __next__ | Engineers of AI
Python Context Manager __enter__ __exit__ | Engineers of AI
Python Retry Decorator Exponential Backoff | Engineers of AI
Memoization Decorator LRU Python | Engineers of AI
Python flatten Generator Nested Lists | Engineers of AI
Python Lazy Property Descriptor | Engineers of AI
Python Dataclass Validation __post_init__ | Engineers of AI
Abstract Base Class Payment System Python | Engineers of AI
Python __getattr__ __setattr__ Tracking | Engineers of AI
Python Protocol Comparable Structural Typing | Engineers of AI
Asyncio Producer Consumer Queue Python | Engineers of AI
asyncio gather Semaphore Python | Engineers of AI
Token Bucket Rate Limiter Python | Engineers of AI
Python ThreadPoolExecutor concurrent.futures | Engineers of AI
Custom defaultdict Python __missing__ | Engineers of AI
Trie Python Implementation with Autocomplete | Engineers of AI
Graph Class BFS DFS Topological Sort Python | Engineers of AI
MinHeap from Scratch Python | Engineers of AI
Circular Buffer Ring Buffer Python | Engineers of AI
Bloom Filter Python Implementation | Engineers of AI
Consistent Hash Ring Python | Engineers of AI
Design LRU Cache O(1) Python | Engineers of AI
Design LFU Cache Python O(1) | Engineers of AI
Design Hit Counter Last 5 Minutes Python | Engineers of AI
Design Rate Limiter Sliding Window Python | Engineers of AI
Design Twitter Post Tweet News Feed Python | Engineers of AI
Design File System In-Memory Python | Engineers of AI
Key-Value Store with TTL Python | Engineers of AI
Design In-Memory Database Python | Engineers of AI
Design URL Shortener Python Base62 | Engineers of AI
Design Leaderboard Top K Python | Engineers of AI
Design Parking Lot OOP Python | Engineers of AI
Vending Machine State Pattern Python | Engineers of AI
Design Elevator System SCAN Algorithm Python | Engineers of AI
Library Management System OOP Python | Engineers of AI
Restaurant Reservation System Python OOP | Engineers of AI
Movie Ticket Booking System Python OOP | Engineers of AI
Design Chat System Python OOP | Engineers of AI
Autocomplete System Trie Python | Engineers of AI
Log Aggregator K-Way Merge Python | Engineers of AI
Priority Task Scheduler Python | Engineers of AI
Design Pub/Sub Message Queue Python | Engineers of AI
Event Sourcing System Python | Engineers of AI
Circuit Breaker Pattern Python | Engineers of AI
API Gateway Design Python Middleware | Engineers of AI
Search Suggestions Trie Binary Search Python | Engineers of AI
KMP String Search Algorithm Python | Engineers of AI
Rabin-Karp Rolling Hash Python | Engineers of AI
Z-Algorithm Pattern Matching Python | Engineers of AI
Longest Palindromic Substring Manacher's Python | Engineers of AI
Palindrome Partitioning Backtracking Python | Engineers of AI
Merge Intervals - Python Solution | EngineersOfAI
Insert Interval - Python Solution | EngineersOfAI
Non-overlapping Intervals - Python Greedy | EngineersOfAI
Meeting Rooms I - Python Solution | EngineersOfAI
Meeting Rooms II - Python Min-Heap Solution | EngineersOfAI
Employee Free Time - Python Solution | EngineersOfAI
Interval List Intersections - Python Two Pointers | EngineersOfAI
Remove Covered Intervals - Python Sorting | EngineersOfAI
Video Stitching - Python Greedy Solution | EngineersOfAI
Minimum Arrows to Burst Balloons - Python Greedy | EngineersOfAI
My Calendar I - Python Binary Search | EngineersOfAI
My Calendar II - Python Double Booking | EngineersOfAI
My Calendar III - Python Difference Array | EngineersOfAI
Data Stream as Disjoint Intervals - Python | EngineersOfAI
Range Module - Python Interval Design | EngineersOfAI
Count of Range Sum - Python Merge Sort | EngineersOfAI
Falling Squares - Python Interval Heights | EngineersOfAI
Rectangle Area II - Python Sweep Line | EngineersOfAI
Minimum Interval to Include Each Query - Python Heap | EngineersOfAI
Number of Flowers in Full Bloom - Python Binary Search | EngineersOfAI
Find Right Interval - Python Binary Search | EngineersOfAI
Partition Labels - Python Greedy Solution | EngineersOfAI
Task Scheduler - Python Greedy & Math | EngineersOfAI
Car Fleet - Python Monotonic Stack Solution | EngineersOfAI
Jump Game VII - Python Prefix Sum | EngineersOfAI
Koko Eating Bananas - Python Binary Search | EngineersOfAI
Capacity to Ship Packages Within D Days - Python Binary Search | EngineersOfAI
Minimum Days to Make m Bouquets - Python Binary Search | EngineersOfAI
Split Array Largest Sum - Python Binary Search | EngineersOfAI
Magnetic Force Between Two Balls - Python Binary Search | EngineersOfAI
Find in Mountain Array - Python Binary Search | EngineersOfAI
Search in Rotated Sorted Array II - Python | EngineersOfAI
Find the Duplicate Number - Python Floyd Cycle | EngineersOfAI
First Bad Version - Python Binary Search | EngineersOfAI
Find Smallest Letter Greater Than Target - Python | EngineersOfAI
Count Negative Numbers in Sorted Matrix - Python | EngineersOfAI
Kth Smallest Element in Sorted Matrix - Python Binary Search | EngineersOfAI
Find Kth Smallest Pair Distance - Python Binary Search | EngineersOfAI
Kth Smallest in Multiplication Table - Python Binary Search | EngineersOfAI
Random Pick with Weight - Python Binary Search | EngineersOfAI
Time Based Key-Value Store - Python Binary Search Design | EngineersOfAI
Online Election - Python Binary Search | EngineersOfAI
Peak Index in Mountain Array - Python Binary Search | EngineersOfAI
Search a 2D Matrix II - Python Staircase | EngineersOfAI
Sqrt(x) - Python Binary Search | EngineersOfAI
H-Index II - Python Binary Search | EngineersOfAI
Minimum Speed to Arrive on Time - Python Binary Search | EngineersOfAI
Minimum Time to Complete Trips - Python Binary Search | EngineersOfAI
Maximum Candies Allocated to K Children - Python Binary Search | EngineersOfAI
Minimum Limit of Balls in a Bag - Python Binary Search | EngineersOfAI
Binary Tree Maximum Path Sum - Python DFS | EngineersOfAI
Binary Tree Cameras - Python Greedy DFS | EngineersOfAI
Distribute Coins in Binary Tree - Python DFS | EngineersOfAI
Maximum Width of Binary Tree - Python BFS | EngineersOfAI
Count Complete Tree Nodes - Python O(log^2 n) | EngineersOfAI
Sum Root to Leaf Numbers - Python DFS | EngineersOfAI
Path Sum III - Python Prefix Sum Hash Map | EngineersOfAI
Flatten Binary Tree to Linked List - Python O(1) Space | EngineersOfAI
Binary Tree Right Side View - Python BFS | EngineersOfAI
Find Duplicate Subtrees - Python Serialization | EngineersOfAI
LRU Cache Python - O(1) OrderedDict & Doubly Linked List Solution
LFU Cache Python - O(1) Least Frequently Used Cache Implementation
Design Twitter Python - News Feed with Heap Merge Solution
Design Snake Game Python - Deque and Set Solution
Design Hit Counter Python - Circular Buffer and Queue Solutions
Design Phone Directory Python - Set and Queue Solutions
Design In-Memory File System Python - Trie Solution
Implement Trie Prefix Tree Python - Insert Search StartsWith
Add and Search Word Python - Trie with Wildcard Dot Support
Word Search II Python - Trie + DFS Backtracking Solution
Implement Stack Using Queues Python - One and Two Queue Solutions
Implement Queue Using Stacks Python - Amortized O(1) Solution
Min Stack Python - O(1) getMin with Auxiliary Stack Solution
Max Stack Python - O(log n) Solution with Heap and Lazy Deletion
Sliding Window Maximum Python - Monotonic Deque O(n) Solution
Sliding Window Minimum Python - Monotonic Deque O(n) Solution
First Unique Character in Stream Python - OrderedDict and Deque Solutions
Design HashMap Python - Separate Chaining and Direct Address Solutions
Design HashSet Python - Chaining and Bitset Solutions
Iterator for Combination Python - Lazy Generator and Bitmask Solutions
N-ary Tree Level Order Traversal - Python BFS Solution
Maximum Depth of N-ary Tree - Python DFS and BFS Solutions
Diameter of Binary Tree - Python DFS Solution with Examples
Lowest Common Ancestor of Deepest Leaves - Python DFS Solution
Check Completeness of a Binary Tree - Python BFS Solution
Cousins in Binary Tree II - Python BFS Solution
Even Odd Tree - Python BFS Level Validation Solution
Step-By-Step Directions From a Binary Tree Node to Another - Python
Pseudo-Palindromic Paths in a Binary Tree - Python Bitmask DFS
Sum of Nodes with Even-Valued Grandparent - Python DFS Solution
Create Binary Tree From Descriptions - Python Hash Map Solution
Count Nodes Equal to Average of Subtree - Python DFS Solution
Maximum Level Sum of Binary Tree - Python BFS Solution
Reverse Odd Levels of Binary Tree - Python BFS and DFS Solutions
Count Good Nodes in Binary Tree - Python DFS Solution
Trapping Rain Water II - Python Min-Heap BFS Solution
Maximal Square - Python DP Solution with O(n) Space Optimization
Maximal Rectangle - Python Monotonic Stack and DP Solutions
Longest Consecutive Sequence - Python O(n) Hash Set Solution
First Missing Positive - Python Cyclic Sort O(n) O(1) Solution
Text Justification - Python Greedy String Simulation Solution
Jump Game VI - Python Deque DP Sliding Window Solution
Minimum Cost to Cut a Stick - Python Interval DP Solution
Largest Color Value in a Directed Graph - Python Topological DP
Parallel Courses III - Python Topological Sort Critical Path
Count Vowels Permutation - Python DP and Matrix Exponentiation
Strange Printer - Python Interval DP Solution
Minimum Number of Days to Disconnect Island - Python DFS
Minimum Total Distance Traveled - Python DP Robot Factory Solution
Minimize the Maximum Difference of Pairs - Python Binary Search
Count Palindromic Substrings - Python Expand Center and Manacher
Shortest Palindrome - Python KMP O(n) Solution
Wildcard Matching - Python DP and Greedy Solutions
Regular Expression Matching - Python DP and Recursion Solutions
Edit Distance - Python DP Levenshtein Distance Solution
Word Break II - Python Backtracking with Memoization Solution
Concatenated Words - Python DP and Trie DFS Solutions
Distinct Subsequences - Python DP Solution with Space Optimization
Interleaving String - Python DP Solution with Space Optimization
Word Ladder II - Python BFS Backtrack All Shortest Paths
