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
node.next?1. It cannot delete the tail node, because node.next is null. 2. It copies node.next's value into node and unlinks node.next, which breaks external references to node.next.
SinglyLinkedList, which end should push and pop?Run both push and pop at head (addFirst and removeFirst). Both take O(1) time and do not even need a tail reference.
geTail.next = null; at the end of the loop essential?We reuse the original nodes in place. The last node added to the >= x chain may still point to an earlier < x node. Forgetting geTail.next = null creates an infinite cycle.
insertGreatestCommonDivisors (Practice 5), why do we advance curr = nextOrig instead of curr = curr.next?curr.next was just set to the new GCD node. Advancing curr = nextOrig steps directly onto the next original node.
reverseBetween(head, left, right) when left == right?The loop for (int i = 0; i < right - left; i++) runs 0 times and returns dummy.next (head) unchanged.
middleNodeFirst(head) vs middleNodeSecond(head) when the list has only 2 nodes (1 -> 2 -> null)?middleNodeFirst starts fast = head.next and returns 1, so splitting at slow.next gives [1] and [2]. middleNodeSecond lands on 2, which would leave [1, 2] and [] in Merge Sort.
removeNthFromEnd(head, n) is called with an invalid n > length in production code?Inside the for (int i = 0; i <= n; i++) lead loop, check if (fast == null) throw new IllegalArgumentException("n exceeds list length"); before fast = fast.next.
ArrayDeque or ArrayList in real Java systems?Use a doubly linked list when you need O(1) middle removal or reordering given a node reference. Classic examples are LRU Cache and LFU Cache, where a HashMap<Key, DNode> stores node references. If you only touch the two ends, ArrayDeque is faster.
LFU evicts the key with the lowest access frequency freq, breaking ties by least recently used. Keep keyToNode, freqToList mapping each frequency to its own LRU list, and minFreq tracking the minimum frequency.
When every tree node has a .parent link, the paths from p and q form two linked lists. Writing a = (a == null) ? q : a.parent; b = (b == null) ? p : b.parent; finds the LCA in O(h) time and O(1) space.
First, leaving a dangling .next pointer on the new tail (forgetting greaterTail.next = null or slow.next = null). Second, forgetting to advance curr = curr.next in one branch of an if / else loop.
All three operations take O(1) time. They manipulate only the top element without scanning the rest of the collection.
Lesson: Stacks: last in, first outUnderflow occurs when attempting to pop or peek an empty stack. It should be handled by throwing an exception or returning a sentinel value.
Lesson: Build a stack yourselfPush each opening bracket onto a stack. When reading a closing bracket, pop and ensure it matches the opener. Return true if the stack is empty at the end.
Lesson: Balanced bracketsYes, recursive descent parsing uses the JVM call stack to match brackets. However, deep nesting risks StackOverflowError.
Lesson: Balanced bracketsIt returns null without throwing an exception. In contrast, remove throws NoSuchElementException on an empty queue.
Lesson: Queues: first in, first outAllocate a larger array and copy elements starting from head up to size. Reset head to 0 and tail to the old size.
Lesson: Build a circular queueYes. You can store pairs of value and current-min, or store difference values relative to the running minimum.
Lesson: Min stack and a queue from stacksSubtraction and division are non-commutative. The first popped element is the right operand, and the second is the left operand.
Lesson: Evaluating expressionsEach element is pushed to the stack once and popped at most once. The total count of all push and pop operations across the entire algorithm is bounded by 2n.
Lesson: Monotonic stackIt maintains an increasing stack of indices. A shorter bar triggers pops, revealing height and width limits in O(1) time.
Lesson: Largest rectangle in a histogramO(R * C) where R is the number of rows and C is the number of columns. Each row takes O(C) time to update heights and O(C) to evaluate the histogram.
Lesson: Largest rectangle in a histogramIt safely returns null without throwing an exception, making it ideal for defensive boundary checks.
Lesson: DequesAsteroids moving in the same direction never collide. They are simply pushed onto the stack as survivors.
Lesson: Practice: stacks and queuesDifferent hash codes place equal keys in different buckets, causing search to fail.
Lesson: How hashing worksIt traverses the chain. If the key exists, it overwrites the value; otherwise it appends a new node.
Lesson: Build a hash map with chainingSetting a slot to null breaks probe chains. Subsequent searches stop early at the null, missing later keys.
Lesson: Open addressingLoad factor is the ratio of stored elements to array capacity. It is calculated as size divided by capacity.
Lesson: Load factor and resizingTree bins protect against hash collisions where many keys map to one bucket. They cap worst-case lookup at O(log n).
Lesson: Inside Java's HashMapHashMap has undefined iteration order that shifts after resizing. LinkedHashMap guarantees iteration matches insertion order.
Lesson: Inside Java's HashMapMutating a key changes its hash code. The map then searches the wrong bucket, losing the entry.
Lesson: hashCode and equals in practiceIt maps keys and nodes to a circular ring. Adding or removing a node affects only its adjacent neighbors.
Lesson: Hashing in the real worldStress testing verifies that rehashing across multiple doublings correctly moves all nodes without data loss.
Lesson: Practice: hash tablesSorting n elements distinguishes among n. permutations. A binary decision tree of n. leaves has height at least Omega(n log n).
Lesson: Why sorting mattersSelection sort performs at most n - 1 swaps. In contrast, bubble and insertion sort perform up to O(n²) writes.
Lesson: Bubble, selection and insertion sortThe array is split strictly in half at every level, creating log₂(n) levels. Merging each level takes O(n) total time.
Lesson: Merge sortIt eliminates allocating new arrays on every recursive call, reducing garbage collection pressure and allocation overhead.
Lesson: Merge sortYes. A Fenwick tree with coordinate compression updates counts and queries prefix sums in O(n log n) time.
Lesson: Counting inversionsLomuto is simpler and places the pivot at its exact boundary index. Hoare performs three times fewer swaps on average.
Lesson: Quick sortRandom pivot selection balances subproblem sizes with high probability across any input ordering.
Lesson: QuickselectTime is O(n + k) and auxiliary space is O(n + k), where k is the key range.
Lesson: Counting and radix sortPrimitives do not require stability, so fast Dual-Pivot Quicksort is used. Objects require stable TimSort.
Lesson: How Java sortsTwo pivots create three partitions, reducing tree depth and memory writes while improving CPU cache locality.
Lesson: How Java sortsThe greedy choice of picking the earliest finishing meeting leaves maximum remaining time for future meetings.
Lesson: Problems solved by sorting firstWhen sorting large datasets with small bounded integer key ranges, running in pure linear O(n) time.
Lesson: Practice: sortingWhen each node has only one child, the tree becomes a linked list with linear O(n) search.
Lesson: Trees and tree wordsTime complexity is O(n) visiting each node once. Space complexity is O(h) matching call stack depth.
Lesson: Preorder, inorder and postorderOn deep or skewed trees, recursion consumes call stack frames, exceeding thread stack memory limits.
Lesson: Traversals with a stackAvoid Morris traversal in multithreaded systems where concurrent readers might observe threaded pointer mutations.
Lesson: Traversals with a stackBFS expands outward layer by layer, halting immediately upon reaching the first shallowest leaf.
Lesson: Level order traversalTop-down recomputes heights redundantly in O(n²). Bottom-up combines height and balance in O(n) using -1 signals.
Lesson: Height, diameter and balanceYou append the current node value before recursing. After both child recursive calls return, you remove the node.
Lesson: Paths in treesThe time complexity is O(n) because each node in the tree is visited at most once.
Lesson: Lowest common ancestorLeft view selects the element at index 0 of each level. Right view selects the element at index size - 1.
Lesson: Tree views, boundary and vertical orderThe root is the only node. It is treated as the entire boundary without duplicate leaf additions.
Lesson: Tree views, boundary and vertical orderIn postorder, the root comes last and the right subtree precedes it, matching the decreasing index order.
Lesson: Build and serialize treesYes. By checking left and right depths, complete subtrees have 2^h - 1 nodes, running in O(log^2 n) time.
Lesson: Practice: binary treesThe worst case is O(n) when keys are inserted in sorted order, forming a skewed linked list structure.
Lesson: The BST ruleRecursive insert is concise but risks StackOverflowError on skewed trees. Iterative insert uses O(1) auxiliary memory.
Lesson: Insert into a BSTRemoving a two-child node would detach both child subtrees. We must replace it with a successor to preserve tree structure.
Lesson: Delete from a BSTEach lesson has quizzes, practice and more interview questions on the same topic.
Open the first lesson