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 root node is a leaf. Deleting it returns null, leaving the tree completely empty.
Lesson: Delete from a BSTTime complexity is O(n) visiting each node once. Space complexity is O(h) for recursion stack memory.
Lesson: Validate a BSTA HashSet uses O(n) space. Two BST iterators emulate two pointers and consume only O(h) auxiliary memory.
Lesson: Using sorted orderIf node.val is less than low, left subtree is skipped. If node.val is greater than high, right subtree is skipped.
Lesson: Floor, ceiling and LCA in a BSTA rotation swaps ancestor-child roles while maintaining that left subtrees stay smaller and right subtrees stay larger.
Lesson: Why balance mattersThe median element divides the remaining elements into two equal halves, ensuring both subtrees have equal sizes.
Lesson: Build a balanced BSTIf duplicates are permitted in the right subtree, yes. However, standard strict BST definitions require distinct keys.
Lesson: Build a balanced BSTThey maintain sorted active window elements, supporting dynamic insertions, deletions, and nearest value searches in O(log k).
Lesson: TreeMap in problem solvingReverse inorder visits keys in descending order, allowing a running sum to accumulate greater values first.
Lesson: Practice: BSTsThe formula is (i - 1) / 2 using integer division. It maps both left child 2i + 1 and right child 2i + 2 to i.
Lesson: What a heap isMoving the last element preserves the complete binary tree structure and enables O(log n) repair without shifting.
Lesson: Build a heap yourselfA max-heap puts the largest item at root index 0 to swap it to the end.
Lesson: Heap sortA sliding min-heap of size k + 1 sorts the array in O(n log k) time.
Lesson: Heap sortBoth take O(n) linear time because finding an arbitrary element requires scanning the unsorted array.
Lesson: PriorityQueue in JavaThe max-heap tracks the farthest candidate among the k points, enabling O(1) peek and O(log k) eviction.
Lesson: Top k problemsThe max-heap size must equal the min-heap size or exceed it by exactly one element.
Lesson: Two heaps: running medianSorting takes O(n log n) and heap insertions take O(n log n), yielding O(n log n) overall.
Lesson: Scheduling with heapsA trie walks the prefix in O(L) time, whereas a hash set scans all N strings.
Lesson: TriesAutocomplete systems, spell checkers, IP routing tables (radix trees), and search engine query suggesters.
Lesson: TriesIt speeds queries to O(P + k) at the cost of O(k * nodes) pointer memory.
Lesson: Trie applicationsThe trie finds the shortest matching prefix root immediately without testing all possible word substrings.
Lesson: Practice: heaps and triesIn-degree is the count of incoming edges pointing into a node; out-degree is the count of outgoing edges.
Lesson: What a graph isAdjacency lists use O(V + E) memory, avoiding the quadratic O(V^2) overhead of mostly empty matrices.
Lesson: Storing graphs in JavaA queue preserves first-in-first-out order, visiting nodes level-by-level in order of distance from source.
Lesson: Breadth-first searchTrack parent pointers. If a visited neighbour is not the immediate parent, a cycle exists.
Lesson: Breadth-first searchBecause a stack is LIFO, pushing in reverse order ensures the first neighbour is popped and processed first.
Lesson: Depth-first searchExactly c - 1 edges are needed to connect c disconnected components into a single connected graph.
Lesson: Connected componentsDirection arrays eliminate duplicated code blocks and allow clean looping over 4 or 8 neighbours.
Lesson: Grids as graphsTrack the parent of each vertex; if an already visited neighbour is not the parent, a cycle exists.
Lesson: Cycle detectionIf the number of nodes processed by Kahn's algorithm is less than V, the graph contains a cycle.
Lesson: Cycle detectionYes, provided every disconnected component independently satisfies the 2-colouring requirement.
Lesson: Bipartite graphsBFS finds shortest paths in unweighted graphs, while DFS handles deep exploration, backtracking, and topological sort.
Lesson: Practice: graph traversalIt takes O(N * M^2) time, where N is word count and M is word length.
Lesson: Shortest path with BFSAdd a virtual source connected by 0-weight edges to every actual starting origin vertex.
Lesson: Multi-source BFSTo ensure vertices at distance d are processed before any vertices at distance d + 1.
Lesson: 0-1 BFSIt assumes finalised nodes cannot be reached via cheaper paths, which negative edges violate.
Lesson: Dijkstra algorithmCycles create contradictory circular dependencies where no vertex can be scheduled first.
Lesson: Topological sortVertices with in-degree 0 at any stage have satisfied dependencies and can run on concurrent threads.
Lesson: Topological sortUnion-Find updates connectivity incrementally in near O(1) time without re-traversing the full graph.
Lesson: Disjoint set unionAdd a virtual node 0 connected to each vertex with the vertex cost, then compute standard MST.
Lesson: Minimum spanning treesIt flattens trees so subsequent root queries execute in amortized O(alpha(N)) nearly constant time.
Lesson: Graph algorithms practiceConnect a virtual source to every graph vertex with directed edges of weight 0, or initialise all vertex distances to 0 instead of infinity before relaxing edges.
Lesson: Bellman-FordFloyd-Warshall takes O(V^3) time and O(V^2) space, excelling on dense graphs (E ≈ V^2) and small V <= 400. On sparse graphs, Johnson's algorithm runs faster in O(V^2 log V + V * E).
Lesson: Floyd-WarshallTopological ordering guarantees that every vertex is visited only after all its incoming dependencies have finalised. A single relaxation pass over vertices in topological order settles all shortest paths.
Lesson: Shortest and longest paths in a DAGVertices in the cycle maintain non-zero in-degrees and never enter the queue in Kahn's algorithm. The resulting topological list contains fewer than V vertices, signaling a cycle.
Lesson: Shortest and longest paths in a DAGBitmasks represent subsets using a single primitive integer. They require zero heap allocations, execute in O(1) time via bitwise operations, and allow direct array indexing.
Lesson: Graphs hidden in problemsIf a directed cycle existed between super-nodes, all vertices in those super-nodes could mutually reach each other. By definition, they would form a single larger SCC rather than distinct ones.
Lesson: Strongly connected componentsFor bridges, strict inequality low[v] > tin[u] proves v cannot reach u even via an alternative back edge. For cut vertices, low[v] == tin[u] means v can loop back to u but cannot bypass u to reach ancestors.
Lesson: Bridges and articulation pointsAn Euler path visits every edge in the graph exactly once and can be found in linear O(V + E) time. A Hamiltonian path visits every vertex exactly once, which is an NP-complete problem.
Lesson: Euler paths and circuitsIt seeks the shortest tour visiting every edge at least once. If all vertex degrees are even, an Euler circuit solves it. If odd vertices exist, it duplicates the minimum-weight matching of odd-degree vertices.
Lesson: Euler paths and circuitsWith unit capacity from source to workers, workers to tasks, and tasks to sink, each worker can match at most one task and each task can receive at most one worker, directly maximising matches.
Lesson: Maximum flow and matching (overview)Undirected edges (u, v) appear in both directions. Without skipping the parent, the return edge to parent would be falsely classified as a back edge, missing the bridge.
Lesson: Practice: advanced graphsGreedy picks 4 for amount 6, yielding three coins (4 + 1 + 1). The true optimum uses two coins (3 + 3).
Lesson: What greedy meansUse Integer.compare(a[1], b[1]) instead of subtraction (a[1] - b[1]). Subtraction can overflow if coordinates span negative and positive extremes.
Lesson: Activity selectionUse Math.max(current[1], next[1]) when merging. If next is fully inside current, current[1] remains unchanged.
Lesson: Merge and insert intervalsMeeting Rooms I checks if any meetings overlap. Meeting Rooms II computes the peak number of overlapping meetings across the entire schedule.
Lesson: Meeting roomsWe only need to track the single maximum reachable index. Maintaining a boolean array is redundant because reachable ranges are contiguous.
Lesson: Jump game and gas stationJump Game models reachability in a directed graph. Each index has edges to its forward reach.
Lesson: Jump game and gas stationO(N log N) to sort workers by ratio, and O(N log K) to maintain the quality max-heap.
Lesson: Greedy with heapsSort by costA - costB ascending. Sending the first n people to A maximises the relative savings compared to sending them to B.
Lesson: Fractional knapsack and the limits of greedyEach lesson has quizzes, practice and more interview questions on the same topic.
Open the first lesson