Algorithms & Data Structures

Construct a prefix sum array to answer range sum queries in O(1) time.

Combine prefix sums with a hash map to count subarrays with a given target sum.

Explain the core logic of Kadane's algorithm for the maximum subarray problem.

Implement Kadane's algorithm, handling edge cases such as all-negative arrays.

Adapt Kadane's algorithm to track the start and end indices of the maximum subarray.

Apply Kadane's algorithm to variants such as the maximum circular subarray sum.

Solve array partitioning problems using a two-pointer approach (e.g., Dutch National Flag problem).

Implement a fixed-size sliding window to compute aggregates over contiguous subarrays.

Implement the expand-and-shrink logic for variable-size sliding windows to meet a condition.

Apply a variable-size window to solve longest-substring problems with a given constraint.

Apply a variable-size window to solve minimum-window problems with a required set of characters.

Apply opposite-end two pointers to solve pair-sum problems on sorted arrays.

Implement the three-sum pattern by combining sorting with the two-pointer technique.

Apply the opposite-end two-pointer technique to solve the Container with Most Water problem.

Recognize when two pointers or sliding windows can replace nested loops to reduce time complexity.

Reverse a singly linked list iteratively.

Find the middle node of a linked list in a single pass using a fast and slow pointer.

Detect a cycle in a linked list using Floyd's fast and slow pointer algorithm.

Implement the algorithm to find the starting node of a cycle in a linked list.

Explain the intuition behind the algorithm that finds a cycle's starting node.

Determine if a linked list is a palindrome using fast/slow pointers and list reversal.

Apply the cycle detection concept to array problems, such as finding a duplicate number.

Implement iterative preorder traversal of a binary tree using an explicit stack.

Implement iterative inorder traversal of a binary tree using an explicit stack.

Implement iterative postorder traversal of a binary tree using an explicit stack.

Compare iterative versus recursive DFS in terms of space usage and stack overflow risk.

Validate a Binary Search Tree using an iterative inorder traversal.

Find all root-to-leaf paths that sum to a target using iterative DFS.

Extend iterative DFS and BFS traversal patterns to n-ary trees.

Apply a single heap (priority queue) to find the k-th largest element in a stream.

Identify problems where maintaining a max-heap and min-heap simultaneously is advantageous.

Implement the two-heaps pattern to find the median of a data stream.

Devise a strategy for handling element removal from the two heaps (e.g., lazy deletion).

Implement a complete solution for the sliding window median problem using two heaps.

Apply the two-heaps pattern to solve resource allocation problems like the IPO problem.

Analyze the time and space complexity of heap-based solutions.

Explain the backtracking framework in terms of choices, constraints, and goals.

Generate all subsets of a set using a backtracking template.

Modify the subset generation logic to handle duplicates and avoid duplicate results.

Generate all combinations of k elements from a set using backtracking.

Generate combinations that sum to a target, using pruning to optimize the search.

Generate all permutations of a list using backtracking with a used-set or by swapping elements.

Modify the permutation generation logic to handle duplicates and avoid duplicate results.

Estimate the time complexity of backtracking solutions for subsets, combinations, and permutations.

Explain the structure of a trie and when it is preferable to a hash map for string storage.

Implement insert, search, and startsWith operations for a standard trie.

Use a trie to efficiently implement an autocomplete or prefix-matching feature.

Explain how a trie can optimize a backtracking search for words on a 2D grid.

Implement a backtracking function that traverses a grid to find words, using a trie to prune invalid search paths.

Implement wildcard matching in a trie (e.g., a '.' character matching any single letter).

Analyze the time and space complexity of common trie operations.

Explain the Union-Find data structure and its core find and union operations.

Implement the path compression optimization in the find operation.

Implement the union by rank/size optimization to keep the internal tree structures balanced.

Analyze the amortized time complexity of the optimized Union-Find operations.

Apply Union-Find to determine the number of connected components in a graph.

Apply Union-Find to solve redundant connection style problems.

Apply Union-Find to solve entity merging problems, such as 'Accounts Merge'.

Represent a graph using an adjacency list for traversal algorithms.

Implement Dijkstra's algorithm for single-source shortest paths using a min-heap.

Apply Dijkstra's algorithm to solve shortest path problems on explicit and implicit graphs (e.g., grids).

Explain the intuition behind the greedy choices in Minimum Spanning Tree (MST) algorithms.

Implement Prim's algorithm for MST construction using a priority queue.

Implement Kruskal's algorithm for MST construction using Union-Find to detect cycles.

Distinguish between problems that require Dijkstra's algorithm versus an MST algorithm.

Identify Directed Acyclic Graphs (DAGs) and problems requiring topological sorting.

Implement topological sort using Kahn's algorithm (BFS with in-degree tracking).

Implement topological sort using a DFS-based post-order traversal approach.

Apply topological sort to solve problems involving task scheduling or dependency resolution.

Detect a cycle in a directed graph using a modified DFS traversal.

Detect a cycle in a directed graph using Kahn's algorithm.

Identify optimal substructure and overlapping subproblems in a given problem.

Formulate a recurrence relation and implement a top-down DP solution with memoization (e.g., Fibonacci, Climbing Stairs).

Convert a memoized top-down solution into a bottom-up DP solution using a table.

Formulate the 0/1 knapsack recurrence and implement it using a 2D DP table.

Optimize the 0/1 knapsack solution to O(W) space using a 1D DP array.

Apply the 0/1 knapsack pattern to solve the subset sum and partition equal subset sum problems.

Formulate the unbounded knapsack recurrence and apply it to problems like Coin Change.

Derive and implement the Longest Common Subsequence (LCS) recurrence using a 2D DP table.

Reconstruct the LCS from the completed DP table.

Solve the Longest Palindromic Subsequence problem by relating it to the LCS of a string and its reverse.

Solve the Longest Increasing Subsequence problem using a DP approach in O(n^2) time.

Optimize the Longest Increasing Subsequence solution to O(n log n) time using binary search.

Solve the Longest Palindromic Substring problem using the expand-around-center technique.

Distinguish between subsequence and substring problems and select the appropriate DP or two-pointer pattern.