Loading...
Loading...
Loading...
Java interview guide
Arrays, linked lists, trees, graphs, sorting, searching and complexity. Every answer is short enough to say aloud, and every question links to the lesson that teaches it.
60 questionsLast updated
The left pass handles ascending slopes. The right pass handles descending slopes. Math.max at peaks satisfies both sides.
Lesson: Practice: greedy and intervalsGreedy algorithms commit to a single local choice without considering future implications. Dynamic programming evaluates all valid subproblem transitions while preventing exponential computation through memoization.
Lesson: What dynamic programming isPrimitive arrays provide direct memory addressing with cache locality and O(1) access. They avoid object allocation overhead, garbage collection pressure, and hash collision penalties.
Lesson: MemoizationTabulation executes inside iterative loops within a single function stack frame. It completely avoids allocating new call stack frames for each subproblem.
Lesson: TabulationWhen a transition depends only on a fixed number of preceding values, discard earlier history. Rolling variables can hold the necessary prior states without keeping the entire table.
Lesson: TabulationDynamic programming requires evaluating subproblems in topological order. Any cyclic dependency causes infinite loops or chicken-and-egg deadlocks, invalidating standard DP.
Lesson: The DP recipeWhen the array contains only a single house. The subproblem slices become invalid or empty, so you must directly return nums[0].
Lesson: Climbing stairs and house robberGreedy selects 4 first, leaving 2 which requires two 1s for 3 coins total. Dynamic programming discovers two 3-cent coins for 2 coins total.
Lesson: Coin changeThe empty string requires zero words and is trivially valid. It provides the initial foundation for matching the first word of the string.
Lesson: Decode ways and word breakPatience sorting overwrites tail values greedily to minimize future thresholds. This alters earlier sequence history while maintaining exact length.
Lesson: Longest increasing subsequenceWhen state transitions depend strictly on a fixed number of immediately preceding cells. A constant number of rolling variables can track and shift these values.
Lesson: Saving space in DPThey eliminate heap allocations and garbage collection overhead. Rolling variables frequently fit directly inside CPU registers, maximizing execution speed.
Lesson: Saving space in DPDeducting the fee once per completed buy-sell cycle yields mathematically equivalent net total profit.
Lesson: Best Time to Buy and Sell StockMaintain two parallel arrays tracking maximum subsequence length and path count ending at each index.
Lesson: 1D Dynamic Programming PracticeObstacles break symmetry and make subproblem path counts dependent on specific coordinates, requiring dynamic programming.
Lesson: Grid paths0/1 knapsack iterates capacity backward to prevent reuse. Unbounded knapsack iterates forward to allow multiple uses.
Lesson: 0/1 knapsackAlgebraic manipulation of P - N = T and P + N = sum yields P = (sum + T) / 2, reducing the problem to counting subsets.
Lesson: The subset sum familyBackward iteration prevents using the same array element multiple times within the same subproblem step.
Lesson: The subset sum familyMaintain a firstCut[n] array storing the optimal cut choice for each length. Backtrack from n by subtracting firstCut[len].
Lesson: Unbounded knapsackWith only insert and delete, minimum edits equals (len(s1) - LCS) + (len(s2) - LCS).
Lesson: Longest common subsequenceMatching characters already align without modification. Replacing modifies a character to achieve alignment, incurring 1 operation.
Lesson: Edit distanceUse Expand Around Center when querying only the longest substring in O(1) space. Use 2D DP when embedding palindrome checks into another recurrence.
Lesson: Palindrome DPUse backtracking depth-first search along with the precomputed boolean palindrome table to collect all valid palindrome lists.
Lesson: Palindrome DPAdding any positive number to Integer.MAX_VALUE causes integer overflow into negative numbers, corrupting Math.min choices.
Lesson: Solving a new DP problemIn real applications, values are taken modulo a large prime such as 10^9 + 7, or stored in 64-bit long integer variables.
Lesson: Practice: 2D DPTime complexity is typically O(n^3) because there are O(n^2) interval states and each state iterates through O(n) possible split points. Space complexity is O(n^2) for the 2D table.
Lesson: Interval dynamic programmingBecause it memoizes states by (visited_subset, current_city). Two completely different visit orders of the same 10 cities ending at city 5 collapse into a single optimal subproblem state.
Lesson: Bitmask dynamic programmingA tree has exactly n - 1 edges and no cycles. Any edge removal splits the tree into two disjoint subtrees, making subproblems independent.
Lesson: Tree dynamic programmingStore edges in an adjacency list List<List<Integer>>. In DFS, iterate through all neighbor nodes skipping the immediate parent parameter (if (v == parent) continue).
Lesson: Tree dynamic programmingConvert N into its representation in base B. Set the digit choice loop to iterate from 0 up to min(limit, B - 1). All transition and memoization logic remains completely identical.
Lesson: Digit dynamic programmingIt states that any impartial game under normal play convention is mathematically equivalent to a Nim pile of size equal to its Grundy value G(state) = mex({G(nextState)}). Multiple simultaneous independent games can be solved by XOR-summing their Grundy values.
Lesson: Game theory dynamic programmingIf two envelopes have the same width, neither can fit inside the other. Sorting heights descending ensures that when computing Longest Increasing Subsequence on heights, at most one envelope of any given width can be chosen.
Lesson: Classic hard dynamic programmingUse prefix sums when the transition operation is invertible like addition or XOR, allowing range queries in O(1). Use a monotonic queue when the transition asks for an extremum (min or max) over a sliding window where values cannot be subtracted.
Lesson: DP optimisations: prefix sums and monotonic queuesMonotonic queues handle negative values without issue because comparisons between candidate DP values remain fully valid. Unlike two-pointer sliding windows that rely on non-negative monotonicity, the deque maintains exact relative value order.
Lesson: DP optimisations: prefix sums and monotonic queuesStore matrix cells as 64-bit primitive longs. Since multiplying two 32-bit values can reach ~10^18, taking modulo inside the inner accumulation loop prevents exceeding Long.MAX_VALUE (9 * 10^18).
Lesson: Matrix exponentiation: linear recurrences in logarithmic timeCheck if completing an operation on an element splits the remaining problem into two completely independent left and right subproblems with no cross-boundary interactions, as seen in Matrix Chain Multiplication, Balloon Bursting, and Stick Cutting.
Lesson: Comprehensive advanced DP practiceNaive search discards all information about characters successfully matched prior to a mismatch, rewinding the text pointer and re-comparing characters. KMP and rolling hash eliminate redundant comparisons.
Lesson: Searching textA spurious hit occurs when two different substrings yield the exact same hash value modulo P (a hash collision). Rabin-Karp detects and discards spurious hits by comparing the actual characters whenever hashes match.
Lesson: Rolling hash and Rabin-KarpWhen a mismatch occurs after matching j characters, KMP uses the precomputed LPS table to determine the longest prefix of the pattern that matches a suffix of the characters already seen, sliding the pattern forward without rewinding the text pointer.
Lesson: The KMP algorithmBy maintaining the rightmost matching window [L, R]. When checking index i <= R, precomputed values from Z[i - L] are reused. New character comparisons occur only when expanding past the right boundary R, bounding total comparisons to 2N.
Lesson: The Z-algorithmIf for some index i dividing N, we have Z[i] == N - i, then the suffix starting at i matches the prefix of length N - i. Because i divides N, this implies the block S[0..i-1] repeats N / i times.
Lesson: The Z-algorithmPalindrome partitioning finds the minimum cuts to partition string S into palindromes. Precomputing palindrome validity using expand-around-centre in O(N^2) time allows 1D DP dp[i] = min(dp[j-1] + 1) to run in O(N^2) instead of O(N^3).
Lesson: Palindrome algorithmsMaintain a frequency array of size 26 for pattern P and a sliding window of size |P| across text T. Each step increments the incoming character count and decrements the outgoing character count in O(1), identifying anagrams whenever arrays match.
Lesson: Practice: string algorithmsA single point update at index i alters all subsequent prefix values pref[i+1..N], requiring O(N) operations to maintain. Mixing Q updates with Q queries degrades total runtime to O(Q * N).
Lesson: The range query problemIf N is not a power of 2, the bottom level can extend to height ceil(log2 N) + 1. The maximum 1-based index required can reach 4N - 5. Sizing to 4N guarantees safety against array index out-of-bounds exceptions.
Lesson: Segment treesBefore visiting children during a query or update, pushDown applies the pending tag to both children's aggregates, passes the tags down to the children's lazy buffers, and clears the parent's tag, ensuring children are always up to date.
Lesson: Lazy propagationEach 1-based index i covers the interval (i - lowbit(i), i], where lowbit(i) = i & (-i). Indices that are powers of two cover all elements from 1 to i, while odd indices cover only themselves.
Lesson: Fenwick treesSort unique elements and replace each value with its 1-based rank (1 to U <= N). This maps arbitrary values up to 10^9 into compact array indices [1, N], allowing the Fenwick tree to operate in O(N) memory.
Lesson: Fenwick treesBy performing an Euler tour of the tree, the LCA of two nodes u and v corresponds exactly to the node with the minimum depth visited between the first appearances of u and v in the Euler tour traversal. Because depths are static, an RMQ Sparse Table over the Euler tour array answers any LCA query in strictly O(1) time after O(N log N) preprocessing.
Lesson: Sparse table: O(1) static range minimum queriesAll O(1) requires a doubly linked list of Bucket nodes sorted by frequency count, where each Bucket contains a HashSet of string keys with that count, and a HashMap mapping each key to its corresponding Bucket. When incremented or decremented, a key moves to an adjacent bucket in O(1). getMaxKey reads from the tail bucket and getMinKey reads from the head bucket in O(1).
Lesson: Designing complex composite data structuresIt maintains two lists: one for all booked intervals and one for double bookings (the intersection intervals created when two bookings overlap). When a new interval arrives, it first checks if it intersects any interval in the double bookings list; if so, a triple booking would occur, and it is rejected. Otherwise, it calculates intersections with existing bookings, adds them to double bookings, and records the new booking.
Lesson: Advanced data structures in practiceArrayDeque is backed by a circular array, providing superior CPU cache locality and zero node allocation overhead. In contrast, LinkedList allocates a separate Node object with object headers and pointers for every single element, causing memory bloat and frequent CPU cache misses. ArrayDeque is faster and consumes far less memory.
Lesson: Topic set: lists, stacks and queuesAll numbers are placed in a HashSet in O(N) time. We iterate through the set and only attempt to expand a streak from number x if x - 1 is NOT present in the set (ensuring x is the true start of a streak). Each number is visited at most twice (once in the outer loop, once in a streak expansion), guaranteeing strictly O(N) total runtime.
Lesson: Topic set: hashing and sortingWe divide the stream into two halves: a max-heap storing the smaller half and a min-heap storing the larger half. Each number is routed through the heaps, maintaining the invariant that sizes differ by at most 1. The median is either the top of the larger heap (for odd counts) or the average of both heap tops (for even counts). Insertion takes O(log N) and finding median takes O(1).
Lesson: Topic set: trees, heaps and triesChoose BFS when searching for the shortest path or minimum number of transformations in unweighted graphs, as BFS guarantees discovering target nodes in minimal levels. Choose DFS when you need to explore all complete paths, perform exhaustive backtracking, count connected components, or detect cycles in directed graphs.
Lesson: Topic set: graphsBy using an 'exchange argument' (proof by contradiction). Assume there exists an optimal solution that differs from the greedy choice at the first step. Show that you can swap the non-greedy choice with the greedy choice without reducing the total solution value. Repeating this exchange transforms the optimal solution into the greedy solution, proving greedy is optimal.
Lesson: Topic set: greedy and DPBecause houses form a circle, the first and last houses are adjacent and cannot both be robbed. We split the problem into two linear subproblems: 1) rob houses from index 0 to N - 2 (excluding the last house), and 2) rob houses from index 1 to N - 1 (excluding the first house). The answer is the maximum of the two independent linear DP runs in O(N) time.
Lesson: Topic set: greedy and DPJava PriorityQueue does not support O(log N) arbitrary element removal; its remove(Object) takes O(N) linear time to find the item. Lazy removal marks items as deleted in a hash map without immediately removing them from the heap. When the marked item reaches the heap root, it is pruned in O(log N). This preserves logarithmic performance.
Lesson: Mixed sets: choose the structureIn Java, thread stacks default to ~1MB, accommodating roughly 5,000 to 10,000 stack frames before throwing StackOverflowError. If problem constraints specify N = 100,000, recursive linear traversals will crash. You must rewrite linear recursions iteratively using loops or explicit stacks.
Lesson: DSA revision sheetIt runs in O(V + E) time. Every vertex is enqueued and colored at most once. Every edge is traversed at most twice (once from each endpoint). The BFS/DFS traversal visits all connected components and checks for odd cycles in linear time without redundant operations.
Lesson: DSA checkpointEach lesson has quizzes, practice and more interview questions on the same topic.
Open the first lesson