35 Meta Java Developer Interview Questions & Answers

I would use two pointers, one at each end of the string. While the characters match, I move both pointers inward. At the first mismatch, I try the only two valid choices: skip the left character or skip the right character. A helper checks whether the remaining range is a palindrome. If either check succeeds, I return true. This works in O(n) time and uses O(1) auxiliary space.

The problem gives us a string and asks whether it can become a palindrome after removing at most one character. A palindrome reads the same from left to right and right to left. We do not need to actually build a new string. We compare characters from both ends. If they match, we continue inward. At the first mismatch, there are only two useful choices: remove the left character or remove the right character. We check both remaining ranges and return true if either range is a palindrome.

1. Does deleting zero characters also count as valid? Yes, because the problem says at most one deletion.
2. Should I treat the string exactly as given, including its character case? Yes, unless the interviewer gives a different rule.

The input is one string. The output is a boolean value. We return true when the string is already a palindrome or can become one after deleting one character. Otherwise, we return false.

The diagram uses the example s = "abca". The expected output is true.

I use two pointers. The left pointer starts at index 0. The right pointer starts at the last index.

The important idea is that, before the first mismatch, every pair that we already compared matches. This is the invariant. We keep moving toward the center while this remains true.

At the first mismatch, any valid one-deletion solution must delete either the character at left or the character at right. There is no third useful choice because all characters outside this pair already match.

For s = "abca", the characters and indices are:

Index 0 = 'a' Index 1 = 'b' Index 2 = 'c' Index 3 = 'a'

We start with left = 0 and right = 3.

Step 1: left = 0 and right = 3. We compare 'a' and 'a'. They match, so we move both pointers inward. The new state is left = 1 and right = 2.

Step 2: we compare 'b' and 'c'. They do not match. This is the first mismatch.

Now we test the two possible deletion choices. The Java expression first checks the skip-left range [2, 2]. That range contains only 'c'. A single character is a palindrome, so the helper returns true.

Because the first helper call succeeds, Java short-circuits the OR expression. The skip-right helper call for range [1, 1] is not executed in this run. The main method stops and returns true.

Before the mismatch, all outer character pairs already match. At the first mismatch, the only characters that can prevent the string from being a palindrome are the two mismatching characters. Since we may delete at most one character, a valid solution must skip either the left mismatching character or the right mismatching character. If either remaining range is a palindrome, the original string can be fixed with one deletion.

The main method keeps left and right pointers and compares characters while left < right. A matching pair moves both pointers inward. A mismatch immediately calls isPalindromeRange for the two possible remaining ranges using a short-circuit OR expression. The helper uses the same two-pointer idea inside the selected range. It returns false on any mismatch and true when the pointers meet or cross. If the main loop finishes without a mismatch, the original string is already a palindrome, so the method returns true.

The time complexity is O(n). The main scan moves inward through the string, and at most one mismatch causes palindrome checks over the remaining range. Even if both helper calls are needed, the total amount of work is still linear in the string length. The auxiliary space complexity is O(1) because the algorithm only stores a few integer variables and does not create another string.

Relevant edge cases are an empty string, one character, an already valid palindrome such as "racecar", a string such as "abc" that cannot be fixed with one deletion, and repeated characters such as "deeee".

The key insight is to compare matching positions from the two ends of the string. As long as the characters match, both pointers safely move inward. The invariant is that every pair outside the current left and right pointers already matches. When the first mismatch appears, any valid solution using at most one deletion must remove either the left mismatching character or the right mismatching character. We therefore check those two remaining ranges with a palindrome helper. If either range is valid, the answer is true. No extra data structure is needed.

Let n be the length of the string. The time complexity is O(n). The main two-pointer scan moves inward through the string. At the first mismatch, the algorithm may check up to two remaining ranges, and each helper check is linear in the remaining length. The total work is still O(n). The auxiliary space complexity is O(1). Auxiliary space means extra memory used by the algorithm. We only store pointer variables and do not copy substrings or build another data structure.

A common mistake is allowing another deletion after the first mismatch. The problem allows at most one deletion total. Another mistake is moving only one pointer when the current characters already match. Both pointers should move inward after a match. Candidates may also check only one deletion choice instead of allowing both skip-left and skip-right possibilities. Another mistake is creating new substring objects unnecessarily, which loses the O(1) auxiliary-space benefit. Finally, do not describe work after an early return as though it was executed.

When you reach the first mismatch, say clearly: "Any valid one-deletion answer must remove either this left character or this right character." That sentence explains why checking exactly two remaining ranges is complete and correct.

I would scan the array once and use reservoir sampling for the maximum values. I keep the current maximum, how many times that maximum has appeared, and one selected index. If I find a larger value, I reset all three values. If I find the same maximum again, I choose its index with probability 1 divided by the new count. This keeps every maximum index equally likely. The time complexity is O(n), and the auxiliary space is O(1).

The input is an integer array. I need to return an index, not the maximum value itself. If the largest value appears more than once, every index containing that value should have the same chance of being returned. I can do this while reading the array from left to right. I remember the largest value seen so far, how many times it has appeared, and one randomly selected index. This avoids storing every maximum index and still gives each maximum position an equal chance.

1. Can I assume the array is non-empty?
2. Should every position containing the maximum value have exactly the same selection probability?

The input is an int[]. The result must be an index. For the example nums = [5, 1, 7, 7, 3, 7], the maximum value is 7. It appears at indices 2, 3, and 5. Any of those indices is valid, but each one must have probability 1/3.

I use a small form of reservoir sampling. Reservoir sampling means I keep one random choice from a group without storing the whole group. I track maxValue, maxCount, and answerIndex. After processing the values seen so far, answerIndex is uniformly random among the seen indices whose value equals maxValue.

The first value is 5, so I start with maxValue = 5, maxCount = 1, and answerIndex = 0. Traversal then begins at index 1.

At index 1, the value is 1. Since 1 < 5, nothing changes. The state stays (5, 1, 0).

At index 2, the value is 7. Since 7 > 5, this is a new maximum. I set maxValue = 7, reset maxCount = 1, and set answerIndex = 2. The state becomes (7, 1, 2).

At index 3, the value is also 7. I increment maxCount to 2. The walkthrough uses rand.nextInt(2) = 1, so I keep index 2. The state becomes (7, 2, 2).

At index 4, the value is 3. Since 3 < 7, nothing changes. The state stays (7, 2, 2).

At index 5, the value is 7. I increment maxCount to 3. The walkthrough uses rand.nextInt(3) = 0, so I replace the selected index with 5. The final state is (7, 3, 5). This walkthrough therefore returns index 5.

When a larger value appears, every earlier smaller value becomes irrelevant, so resetting the selected index is correct. When the k-th occurrence of the current maximum appears, I select it with probability 1/k. This keeps every one of the k maximum positions equally likely. For the three maximum positions in the example, indices 2, 3, and 5 each have probability 1/3.

The loop starts at index 1 because index 0 initializes the state. A strictly larger number resets the maximum state. An equal maximum increments maxCount first. Then rand.nextInt(maxCount) == 0 decides whether the new index replaces the current sample. After all elements are processed, the method returns answerIndex.

The algorithm processes each array element at most once, so the time complexity is O(n). It stores only three integer state variables plus the random generator, so the auxiliary space is O(1). One element returns index 0. Negative values and zero work normally. If all values are equal, every index is still selected uniformly.

The key idea is to combine maximum tracking with reservoir sampling. I do not need to store a list of every index containing the maximum. I keep only maxValue, maxCount, and answerIndex. The invariant is: after processing the values seen so far, answerIndex is uniformly random among the processed indices whose value equals the current maxValue. A larger value resets the reservoir because earlier smaller values cannot be final answers. For the k-th equal maximum, selecting the new index with probability 1/k keeps all k maximum indices equally likely.

The time complexity is O(n) because the algorithm goes through the array from left to right and processes each element at most once. If the array has n elements, the amount of work grows directly with n. The auxiliary space is O(1) because the algorithm keeps only a fixed amount of extra state: maxValue, maxCount, answerIndex, and a Random object. It does not create a list containing all maximum positions.

A common mistake is returning the maximum value 7 instead of an index such as 2, 3, or 5. Another mistake is replacing answerIndex on every tie, which would always favor the last maximum. Candidates may also call rand.nextInt(maxCount) before incrementing maxCount; that gives the wrong probabilities. Another mistake is failing to reset maxCount to 1 when a strictly larger maximum appears. Finally, storing every maximum index in a list works but loses the O(1) auxiliary-space benefit of this reservoir-sampling approach.

State the invariant before coding: after every processed element, answerIndex is uniformly random among the processed indices containing the current maximum. Then explain that a new maximum resets the reservoir, while the k-th equal maximum replaces the current sample with probability 1/k.

I would use a running prefix sum and a HashMap that stores each earlier prefix sum and how many times it has appeared. I start the map with 0 mapped to 1. For each number, I update the prefix sum, compute prefixSum - k, and add its stored frequency to the answer. Then I store the current prefix sum. This counts every valid contiguous subarray. The solution takes O(n) expected time and O(n) auxiliary space.

The problem asks us to count how many continuous parts of the array add up exactly to k. A continuous part means the numbers must stay next to each other in the original array. We do not need to return the parts themselves. We only return the total count. The main idea is to keep a running total while moving from left to right. We remember earlier running totals so we can quickly tell whether the numbers between an earlier position and the current position add up to k.

1. Should I return only the number of matching subarrays, not their indices or values?
2. Can the array contain negative numbers and zeros?
3. Can multiple different subarrays have the same sum k?

The input is an integer array nums and an integer k. We must return the number of contiguous subarrays whose sum is exactly k. For the diagram example, nums = [1, 2, 1, 2, 1] and k = 3. The correct result is 4 because the valid index ranges are 0..1, 1..2, 2..3, and 3..4.

I keep a running value called prefixSum. It is the sum from the start of the array through the current position. I also keep a HashMap called prefixCount. Its key is an earlier prefix sum. Its value is the number of times that prefix sum has appeared. Before I store the current prefix sum, the map contains only prefix sums from earlier positions.

If the current prefix sum is currentPrefix, then I need an earlier prefix sum equal to currentPrefix - k. The difference between those two prefix sums is k. Each stored occurrence of that needed prefix sum represents one valid subarray ending at the current index.

I start with prefixSum = 0 and count = 0. I also put 0 -> 1 into prefixCount. This initial entry represents the empty prefix before index 0. It lets the algorithm count a valid subarray that starts at index 0.

At index 0, the value is 1. prefixSum becomes 1. needed = 1 - 3 = -2. The map is {0:1}, so there is no match. count stays 0. Then I store prefix sum 1, giving {0:1, 1:1}.

At index 1, the value is 2. prefixSum becomes 3. needed = 3 - 3 = 0. The map contains 0 once, so I add 1 to count. count becomes 1. This represents subarray 0..1. Then I store prefix sum 3, giving {0:1, 1:1, 3:1}.

At index 2, the value is 1. prefixSum becomes 4. needed = 4 - 3 = 1. Prefix sum 1 appeared once earlier, so count becomes 2. This represents subarray 1..2. Then I store prefix sum 4, giving {0:1, 1:1, 3:1, 4:1}.

At index 3, the value is 2. prefixSum becomes 6. needed = 6 - 3 = 3. Prefix sum 3 appeared once earlier, so count becomes 3. This represents subarray 2..3. Then I store prefix sum 6, giving {0:1, 1:1, 3:1, 4:1, 6:1}.

At index 4, the value is 1. prefixSum becomes 7. needed = 7 - 3 = 4. Prefix sum 4 appeared once earlier, so count becomes 4. This represents subarray 3..4. Then I store prefix sum 7, giving {0:1, 1:1, 3:1, 4:1, 6:1, 7:1}. After the loop, I return 4.

Before storing the current prefix sum, prefixCount contains frequencies of prefix sums from earlier positions only. If an earlier prefix sum equals currentPrefix - k, then currentPrefix minus that earlier sum is exactly k. Therefore the elements between those positions form a valid contiguous subarray. Every valid subarray is counted exactly when its ending index is processed.

The Java code keeps prefixSum and count as integers and uses HashMap<Integer, Integer> for prefix frequencies. For each number, it updates prefixSum, reads the frequency of prefixSum - k, adds that frequency to count, and only then updates the frequency of the current prefix sum. HashMap lookup and insertion are O(1) on average, so the overall expected time is O(n). The map can hold O(n) different prefix sums, so auxiliary space is O(n). Negative numbers, zeros, repeated values, multiple matching starts, and an empty array are handled naturally.

The key insight is to turn each subarray-sum check into a difference between two prefix sums. If the current running sum is currentPrefix, then a subarray ending at the current index has sum k when an earlier prefix sum equals currentPrefix - k. The HashMap stores prefixSum -> frequency, not just whether a prefix sum exists, because the same prefix sum can appear more than once and each occurrence can represent a different valid starting point. The central invariant is that, before the current prefix sum is inserted, the map contains frequencies only for earlier prefix sums. This lets every valid subarray be counted exactly when its ending index is processed.

Let n be the number of elements in nums. We move from left to right through the array once. Each HashMap lookup and insertion is O(1) on average in Java, with normal hashing and collision caveats. Therefore the overall expected time is O(n). The HashMap may store up to O(n) different prefix sums, so the auxiliary space is O(n). Auxiliary space means extra memory used by the algorithm.

A common mistake is forgetting the initial 0 -> 1 entry. Then a valid subarray that starts at index 0 may not be counted. Another mistake is storing the current prefix sum before checking prefixSum - k. In particular, when k is 0, that can incorrectly count the current prefix against itself. The correct order is lookup first, then update the map. Candidates also sometimes store only whether a prefix sum exists instead of its frequency. That fails when the same prefix sum appears multiple times. Another mistake is using a sliding window even though negative numbers can appear. Finally, do not claim guaranteed O(n) time. Java HashMap operations are O(1) on average, so the overall time is O(n) expected time.

State the invariant before coding: before I insert the current prefix sum, the map contains frequencies of prefix sums from earlier positions only. Then say the key equation out loud: earlierPrefix = currentPrefix - k. That makes the lookup order and the frequency counting easy to justify.

I would use three pointers, one for each sorted array, and one write index for the result. At each step, I compare the current available values and append the smallest one. Then I advance only the pointer for the array that supplied that value. This keeps duplicates and preserves sorted order. I stop when all three arrays are exhausted. The time complexity is O(nA + nB + nC), with O(1) auxiliary space beyond the output array.

The problem gives three arrays whose values are already sorted. We need to create one new sorted array that contains every value from all three inputs. Repeated values must stay in the result. The main idea is to look only at the next unused value from each array, choose the smallest available value, copy it to the result, and move only that array's pointer. Because each input is already sorted, we never need to move backward or sort the values again.

1. Should duplicate values be preserved in the merged result?
2. Can any of the three input arrays be empty?
3. Should the inputs remain unchanged, with the merged values written into a new array?

We have three individually sorted integer arrays. In the diagram, A is [1, 4], B is [1, 3, 5], and C is [2, 4]. We need one sorted result containing every occurrence from all three arrays. The expected result is [1, 1, 2, 3, 4, 4, 5]. These are values, not indices.

I use three read pointers: i for A, j for B, and k for C. I also use r as the write position in the merged array. At every step, I choose the smallest current value among the non-exhausted arrays. The important invariant is that merged[0..r-1] is already sorted and contains the smallest values processed so far.

The result array has size A.length + B.length + C.length, which is 7 for this example. We start with i = 0, j = 0, k = 0, and r = 0. The current heads are A[0] = 1, B[0] = 1, and C[0] = 2. No input value has been copied yet.

Step 1: The heads are 1, 1, and 2. The comparison uses a deterministic <= tie rule, so A supplies the first 1. We write 1 and move i from 0 to 1. Result: [1].

Step 2: The heads are now 4, 1, and 2. B has the smallest value, 1. We write it and move j from 0 to 1. Result: [1, 1].

Step 3: The heads are 4, 3, and 2. C has the smallest value, 2. We write it and move k from 0 to 1. Result: [1, 1, 2].

Step 4: The heads are 4, 3, and 4. B has the smallest value, 3. We write it and move j from 1 to 2. Result: [1, 1, 2, 3].

Step 5: The heads are 4, 5, and 4. A and C both have 4. The <= rule chooses A first. We write 4 and move i from 1 to 2, so A is exhausted. Result: [1, 1, 2, 3, 4].

Step 6: Only B and C remain available, with heads 5 and 4. We write C's 4 and move k from 1 to 2. C is now exhausted. Result: [1, 1, 2, 3, 4, 4].

Step 7: Only B remains, with value 5. We write 5 and move j from 2 to 3. Now all three arrays are exhausted. Final result: [1, 1, 2, 3, 4, 4, 5].

Each array is sorted, so its current pointer always identifies its smallest unused value. Therefore, the smallest value among the three available heads is also the smallest value that has not yet been copied from any input. Appending that value keeps the result sorted. Moving only the pointer that supplied the value also makes sure every occurrence, including duplicates, is copied exactly once.

The Java code first creates the output array and initializes i, j, k, and r to zero. The loop continues while at least one input still has values. Bounds checks make exhausted arrays unavailable for comparison. The first condition chooses A when its current value is no larger than the other available heads. The second condition does the same for B. Otherwise C supplies the next value. After writing a value, only the matching input pointer and the result index move.

If the array lengths are nA, nB, and nC, every input element is copied exactly once. The time complexity is O(nA + nB + nC). The algorithm uses only the four pointer variables in addition to the required result array, so auxiliary space is O(1). The code also handles one empty array, all empty arrays, duplicate values, and negative values because the same bounds checks and comparisons still work.

The key insight is that because all three inputs are already sorted, the next value in the merged result must be the smallest current head among the non-exhausted arrays. We therefore keep one pointer per input and compare only those three current values. After choosing the smallest value, we append it and advance only the pointer that supplied it. The invariant is: merged[0..r-1] is sorted and contains the smallest values processed so far. This gives a direct linear merge without sorting the combined data again.

Let nA, nB, and nC be the lengths of the three arrays. Each value is read and copied exactly once, so the total time is O(nA + nB + nC). The algorithm keeps only i, j, k, and r as extra working state, so auxiliary space is O(1). The returned merged array needs O(nA + nB + nC) space, but that is required output space rather than extra working memory.

A common mistake is advancing more than one input pointer when two head values are equal. That can lose duplicate values. Another mistake is comparing an array after its pointer has reached the end, which can cause an index error. Candidates may also move the wrong pointer after selecting a value, which breaks the invariant. Another mistake is forgetting that the output size must be the sum of all three input lengths. Finally, do not claim the algorithm uses O(1) total space without explaining that the result array itself still requires linear output space.

State the invariant before coding: the output prefix is always sorted, and each input pointer marks that array's smallest unused value. Then your comparison and pointer movements are much easier to justify.

I would use breadth-first search with a queue. Each queue entry stores a tree node and its vertical column number. I start the root at column 0, move left children to column minus 1, and right children to column plus 1. A hash map stores the values for each column in BFS order. I also track the leftmost and rightmost columns. Then I read those columns from left to right. This takes O(n) expected time and O(n) auxiliary space.

The task is to place tree values into vertical groups. The root starts in the middle. Every move to a left child moves one group left. Every move to a right child moves one group right. Values in the same group must stay from top to bottom. If two values are at the same height and in the same group, the left one must appear first. I process the tree level by level, from left to right, because that naturally keeps this required order while I collect values for each group.

1. If two nodes have the same row and column, should their left-to-right tree order be preserved?
2. Should an empty tree return an empty list?

The input is a binary tree. The output is a list of vertical columns from left to right. Each column contains node values from top to bottom. The example tree is [3, 9, 8, 4, 0, 1, 7], with 3 as the root, 9 and 8 as its children, 4 and 0 under 9, and 1 and 7 under 8. The required result is [[4], [9], [3, 0, 1], [8], [7]].

I use breadth-first search, or BFS. A queue performs the BFS. Each queue item stores a node reference and its column number. I also use a HashMap<Integer, List<Integer>>. Its key is a column number. Its value is the list of node values already visited in that column. The central invariant is that columnTable[c] stores the visited values for column c in BFS order.

BFS fits the ordering rule because it processes higher rows before lower rows. I enqueue the left child before the right child. Therefore, when two nodes share both a row and a column, their left-to-right tree order is preserved.

The root starts at column 0. The initial queue is [(3, 0)]. The column map is empty. Both minCol and maxCol start at 0. These values track the leftmost and rightmost columns reached during the traversal.

Step 1: Dequeue 3@0. Add 3 to column 0. Enqueue 9@-1 first and 8@1 second. The queue becomes [(9,-1),(8,1)]. The map is {0:[3]}. The current range is -1 through 1.

Step 2: Dequeue 9@-1. Add 9 to column -1. Enqueue 4@-2 and 0@0. The queue becomes [(8,1),(4,-2),(0,0)]. The map is {-1:[9], 0:[3]}. The leftmost column becomes -2.

Step 3: Dequeue 8@1. Add 8 to column 1. Enqueue 1@0 and 7@2. The queue becomes [(4,-2),(0,0),(1,0),(7,2)]. The map is {-1:[9], 0:[3], 1:[8]}. The rightmost column becomes 2.

Step 4: Dequeue 4@-2. Add 4 to column -2. It has no children. The queue becomes [(0,0),(1,0),(7,2)]. The map is {-2:[4], -1:[9], 0:[3], 1:[8]}.

Step 5: Dequeue 0@0. Append 0 to column 0. The queue becomes [(1,0),(7,2)]. Column 0 is now [3,0].

Step 6: Dequeue 1@0. Append 1 to column 0. The queue becomes [(7,2)]. Column 0 is now [3,0,1].

Step 7: Dequeue 7@2. Add 7 to column 2. The queue becomes empty. The final map is {-2:[4], -1:[9], 0:[3,0,1], 1:[8], 2:[7]}.

Now minCol is -2 and maxCol is 2. Reading columns -2, -1, 0, 1, and 2 gives [[4], [9], [3, 0, 1], [8], [7]].

Every queue entry carries the exact column of its node. Therefore, every value is added to the correct column. BFS processes nodes level by level, so higher nodes are appended before lower nodes. Because left children are enqueued before right children, nodes tied on both row and column keep their required left-to-right order. Every node is dequeued once, so every node appears exactly once.

The Java code uses a small NodeCol class to store a TreeNode and its column. An ArrayDeque is the BFS queue. A HashMap stores each column and its list of values. computeIfAbsent creates a list when a column is first seen. A left child receives col - 1. A right child receives col + 1. The code updates minCol and maxCol as children are added. After BFS finishes, it reads every column from minCol through maxCol.

Each node enters the queue once and leaves the queue once. Hash map lookup and insertion are O(1) on average, so the total expected time is O(n). The queue and column storage require O(n) auxiliary space. Important cases are an empty tree, a single-node tree, a left- or right-skewed tree that creates many columns, and several nodes that belong to the same column.

The key idea is to combine breadth-first search with a column number for every node. The root is column 0. Following a left edge changes the column by -1. Following a right edge changes it by +1. A hash map stores column number -> list of visited node values. The central invariant is that columnTable[c] contains the values already visited for column c in BFS order. This works because BFS processes higher rows before lower rows, and adding the left child before the right child preserves left-to-right order for nodes tied on the same row and column. Tracking minCol and maxCol lets us build the final answer directly from the leftmost column to the rightmost column.

Let n be the number of nodes. Each node is added to the queue once and removed once. Each node is also appended to exactly one column list. Java HashMap lookup and insertion are O(1) on average, so the total expected time is O(n). Building the final result visits the stored column values once more, which is still O(n) overall. Auxiliary space is O(n) because the queue and the stored column lists can contain information proportional to the number of nodes.

A common mistake is using plain DFS without recording enough row and ordering information, which can place nodes in the wrong order inside a column. Another mistake is putting only node values in the queue and losing the column number associated with each node. Candidates may also reverse the column direction by adding 1 for a left child or subtracting 1 for a right child. Enqueuing the right child before the left child can break the required tie order. Finally, do not claim guaranteed O(n) time when the implementation relies on average O(1) HashMap operations.

State the invariant early: each queue entry knows its exact column, and each map list receives values in BFS order. Then use column 0 becoming [3, 0, 1] to show why level-order traversal and left-before-right queue order matter.

I would first clarify that the graph is a directed acyclic graph, because the longest-path problem changes when cycles are allowed. For a DAG, I build an adjacency list and use DFS with memoization. memo[u] stores the longest path length starting at node u. Each node computes the best value from its outgoing neighbors only once, and later calls reuse it. I take the maximum over all starting nodes. The time is O(V + E), and the auxiliary space is O(V), including memo and recursion.

The problem asks for one integer: the largest number of edges in any valid path. The diagram uses a directed acyclic graph, so there are no cycles. I can start from every node, follow its outgoing edges, and remember the best remaining path from each node. Reusing those saved answers avoids solving the same suffix again. For the shown graph with six nodes and seven directed edges, the longest path contains 3 edges, so the required returned integer is 3.

1. Can I assume the graph is directed and acyclic?
2. Is the path length measured in edges, as shown here?
3. If cycles are allowed, do you mean the longest simple path with no repeated nodes?
4. Can the graph be disconnected?

The input is n nodes and a list of directed edges. The output is one integer: the maximum number of edges in a path. In the diagram, n = 6 and edges = [[0,1],[0,2],[1,3],[2,3],[2,4],[3,5],[4,5]]. The expected answer is 3. Two valid longest paths are 0 → 1 → 3 → 5 and 0 → 2 → 4 → 5.

I build an adjacency list. For each node u, memo[u] means the longest path length that starts at u. DFS explores the outgoing neighbors of u. For every neighbor v, the candidate length is 1 + dfs(v). I keep the largest candidate. If memo[u] is already known, I return it immediately. This is safe because the graph is acyclic.

The adjacency list is 0:[1,2], 1:[3], 2:[3,4], 3:[5], 4:[5], and 5:[]. The memo array starts as [-1,-1,-1,-1,-1,-1]. A value of -1 means that node has not been solved yet. A sink node has no outgoing edges, so its longest path length is 0.

Start with dfs(0). It first follows node 1, then node 3, then node 5. Node 5 is a sink, so memo[5] becomes 0. Returning to node 3 gives 1 + memo[5] = 1, so memo[3] becomes 1. Returning to node 1 gives 1 + memo[3] = 2, so memo[1] becomes 2.

Next dfs(0) explores node 2. When node 2 checks node 3, memo[3] is already 1, so that branch gives candidate 2. Node 2 then calls dfs(4). Node 4 reaches node 5, whose memo value is already 0, so memo[4] becomes 1. Node 2 now compares the two candidates, 2 through node 3 and 2 through node 4, so memo[2] becomes 2.

Finally, node 0 compares 1 + memo[1] = 3 and 1 + memo[2] = 3. Therefore memo[0] becomes 3. The outer loop still checks the remaining starting nodes, but their memo values are already solved. The global answer stays 3.

After dfs(u) returns, memo[u] is the correct longest path length starting at u. A sink returns 0. For any other node, every valid path from u must first take one outgoing edge to some neighbor v. The best path from u is therefore the maximum of 1 + dfs(v) over all outgoing neighbors. Because the graph is acyclic, recursion always reaches a sink, and memoization stores each solved suffix once.

The Java code first builds the adjacency list. It fills memo with -1. Then it calls dfs from every node and keeps the largest returned value. The helper returns a cached value when available. Otherwise, it checks every outgoing neighbor, computes 1 + dfs(next), stores the maximum in memo[node], and returns it. This is the same state and traversal used in the diagram.

Each node is fully solved once, and each directed edge is examined when its source node is solved, so the time is O(V + E). The memo array uses O(V) extra space. The recursion stack can also use O(V) space in the worst case. Relevant cases are an isolated node, sink nodes, disconnected DAGs, and multiple different longest paths with the same maximum length. If arbitrary cycles are allowed, this DAG memoization solution does not directly solve the longest simple path problem.

The key idea is to turn repeated graph traversal into reusable subproblems. Define memo[u] as the longest path length, in edges, starting at node u. For a sink, that value is 0. For any other node, memo[u] = max(1 + memo[v]) over every outgoing neighbor v. DFS computes these values naturally from the end of the graph back toward the start. The invariant is: after dfs(u) returns, memo[u] is final and correct. Memoization avoids recomputing shared suffixes such as nodes 3 and 5.

Let V be the number of nodes and E be the number of directed edges. Each node is fully computed once because its answer is stored in memo. During that computation, its outgoing edges are checked once. So the total time is O(V + E). The memo array uses O(V) extra memory. The recursion stack can also grow to O(V) in the worst case, such as one long chain. Therefore the auxiliary space is O(V).

A common mistake is applying this memoized DFS directly to a graph with cycles. The recurrence is valid here because the graph is a DAG. Another mistake is forgetting to try every node as a starting node, which can miss the answer in a disconnected graph. Candidates may also forget that a sink returns 0 because path length is counted in edges. Finally, do not recompute an already solved node. Return memo[node] immediately when it is available.

Define memo[u] out loud before coding: “memo[u] is the longest path length starting at u.” Then explain the recurrence as “one edge to a neighbor plus that neighbor’s best suffix.” This makes the DFS, base case, and O(V + E) reasoning much easier to follow.

I would use two pointers, one for the word and one for the abbreviation. I move through both from left to right. When the abbreviation has a letter, it must match the current word character. When it has digits, I parse all consecutive digits as one skip count and move the word pointer forward by that amount. A number cannot start with zero. The abbreviation is valid only if both pointers finish together. The time is O(n + m) and the auxiliary space is O(1).

The input has a full word and an abbreviation string. The abbreviation can contain letters and numbers. A letter must be the same as the matching letter in the word. A number tells us how many letters of the word to skip. A number cannot start with zero. I use one position for the word and one position for the abbreviation. I move both positions from left to right. The answer is true only when the abbreviation describes the complete word and both positions finish at the same time.

1. Can I assume the abbreviation contains only letters and digits?
2. Should a number that starts with zero always be treated as invalid?
3. Does a skip that goes past the end of the word make the abbreviation invalid?

We receive word and abbr. We return true when abbr correctly represents the whole word. Otherwise, we return false.

A normal letter in abbr must exactly match the current letter in word. A group of digits represents one number. That number tells us how many letters to skip in word. For example, 12 means skip twelve letters. It does not mean two separate skips of one and two.

A number cannot start with 0. The final check is also important. Both strings must be completely consumed.

I use i for the current position in word and j for the current position in abbr.

The main invariant is simple: before each new step, word[0..i-1] has already been correctly represented by abbr[0..j-1].

If abbr[j] is a letter, I compare it with word[i]. If the letters are different, the answer is immediately false. If they match, I move both pointers forward by one.

If abbr[j] is a digit, I first reject a leading zero. Then I read every consecutive digit and build one skipCount. I add that number to i.

I start with i = 0 and j = 0. This means no part of either string has been processed yet.

The example is: word = "internationalization" abbr = "i12iz4n"

The word length is 20. The abbreviation length is 7.

Step 1 starts at (i=0, j=0). The abbreviation character is i. It matches word[0], which is also i. I advance both pointers. The new state is (i=1, j=1).

Step 2 starts at (i=1, j=1). The abbreviation starts the number 12. I parse both digits together, so skipCount = 12. After reading the two digits, j becomes 3. I move i from 1 to 13. The new state is (i=13, j=3).

Step 3 reads abbr[3] = 'i'. It matches word[13] = 'i'. I advance both pointers to (i=14, j=4).

Step 4 reads abbr[4] = 'z'. It matches word[14] = 'z'. I advance both pointers to (i=15, j=5).

Step 5 reads the number 4. I parse it as skipCount = 4. I move j to 6 and move i from 15 to 19. The new state is (i=19, j=6).

Step 6 reads abbr[6] = 'n'. It matches word[19] = 'n'. I advance both pointers to (i=20, j=7).

Now i == word.length() and j == abbr.length(). Both strings finished together, so the method returns true.

The invariant is that the processed part of the abbreviation correctly represents the processed part of the word. A letter step keeps the invariant because the two characters must match exactly. A number step keeps it because the word pointer moves forward by exactly the parsed skip count.

For i12iz4n, i matches word[0], 12 skips word[1..12], i matches word[13], z matches word[14], 4 skips word[15..18], and n matches word[19]. Both pointers then reach their ends together.

The Java method keeps integer pointers i and j. Its loop runs while both pointers are still inside their strings. A letter is checked directly against word.charAt(i). A digit starts number parsing. The code rejects 0 before parsing because a number cannot have a leading zero.

The inner loop builds a complete number with skipCount = skipCount * 10 + digit. After the number is parsed, the code adds skipCount to i. The final return checks that both pointers reached their exact string lengths.

Let n be the length of word and m be the length of abbr. The pointers move only forward, so the running time is O(n + m). The algorithm only stores a few integer and character variables, so the auxiliary space is O(1).

Important cases are a leading zero such as w02d, a multi-digit number such as 12, a skip that moves past the end of the word, and an abbreviation that contains the exact full word with no digits.

The key idea is to represent progress with two pointers. Pointer i tells us how much of word has been represented. Pointer j tells us how much of abbr has been read. The invariant is that word[0..i-1] is correctly represented by abbr[0..j-1]. A letter keeps this invariant only when it matches the current word character. A number keeps it by moving i forward by exactly the parsed skip count. Parsing all consecutive digits together is important because a value such as 12 is one skip. Rejecting a leading zero prevents invalid forms such as 02. Finally, checking both pointer positions prevents accepting an abbreviation that covers too little or too much of the word.

Let n be word.length() and m be abbr.length(). The time complexity is O(n + m), matching the algorithm in the diagram. Both pointers only move forward. The abbreviation pointer advances through at most m positions, and the word pointer never moves backward. Each abbreviation position is advanced past once, although a character can be inspected a constant number of times while the code decides whether it is a letter or part of a number. The algorithm may also stop early when it finds a mismatch. The auxiliary space is O(1) because it uses only a few variables such as i, j, current, and skipCount. The extra memory does not grow with the input size.

A common mistake is reading each digit separately. For example, 12 must be parsed as one number, not as skips of 1 and 2. Another mistake is allowing a number to start with 0, such as 02. Candidates also sometimes move the wrong pointer after parsing a number. The abbreviation pointer moves while the digits are parsed, and then the word pointer moves by the completed skip count. Finally, returning true without checking both final pointer positions can incorrectly accept an abbreviation that leaves characters unprocessed or skips past the word.

While coding, say what each pointer means and trace the multi-digit 12 case out loud. Showing that i moves from 1 to 13 after parsing 12 makes the main idea and the pointer updates easy for the interviewer to verify.

I would model the computers and their existing connections as an undirected graph. I would build an adjacency list, then run DFS from each computer that has not been visited yet. Each new DFS finds one connected component. If there are C components, I need C - 1 additional connections to join them into one network. The full algorithm takes O(n + e) time and uses O(n + e) auxiliary space for the graph, visited array, and recursion stack.

We are given computers and pairs that show which computers already have a direct connection. The goal is to find how many new connections are needed so every computer belongs to one connected network. I first find groups of computers that are already connected, including connections through other computers. Then I count those separate groups. If there are three groups, two new links can join them into one network. DFS fits this problem because one DFS can visit every computer in one connected group.

1. Should I treat each connection as two-way, so the network is undirected?
2. Are the computers numbered from 0 to n - 1?
3. Do you only need the number of additional connections, not the actual new connection pairs?

The input is the number of computers n and a list of existing connection pairs. Each pair [u, v] means computer u is connected to computer v. The diagram treats these connections as undirected, so the relationship works both ways. The output is one integer: the number of additional connections required to make the whole network connected.

For the example, n = 6 and connections = [[0,1], [0,2], [3,4]]. Computers 0, 1, and 2 form one group. Computers 3 and 4 form another group. Computer 5 is alone. There are 3 connected components, so the answer is 3 - 1 = 2.

I use an adjacency list to represent the graph. For each connection [u, v], I add v to u's neighbor list and u to v's neighbor list because the graph is undirected.

I also use a boolean visited array. visited[i] tells me whether computer i has already been reached by DFS.

The important idea is that one DFS starting from an unvisited computer visits every computer in that connected component. Therefore, every time the outer loop finds an unvisited computer and starts DFS, I have found exactly one new component.

For n = 6, the adjacency list is 0:[1,2], 1:[0], 2:[0], 3:[4], 4:[3], and 5:[].

The visited array starts as [false, false, false, false, false, false]. The component count starts at 0. The outer loop starts at computer 0.

The invariant is: after DFS starts from an unvisited computer, every computer in that same connected component becomes visited.

At node 0, no computer has been visited. Node 0 is unvisited, so I increase components from 0 to 1 and start DFS from 0. DFS reaches 0, 1, and 2. The visited computers are now {0,1,2}.

At node 1, it is already visited, so I skip it. The visited state stays {0,1,2}, and components stays 1.

At node 2, it is already visited, so I skip it. Components stays 1.

At node 3, it is unvisited. I increase components to 2 and start DFS from

3. DFS reaches 3 and
4. The visited computers become {0,1,2,3,4}.

At node 4, it is already visited, so I skip it. Components stays 2.

At node 5, it is unvisited. I increase components to 3 and start DFS from 5. Computer 5 has no neighbors, so it forms a one-computer component. The visited computers become {0,1,2,3,4,5}.

The scan is complete. I return components - 1, which is 3 - 1 = 2.

DFS marks every computer reachable from its starting computer. Because the outer loop starts DFS only from an unvisited computer, each DFS launch represents a different connected component. A component cannot be counted twice because all of its computers become visited during its first DFS.

If there are C disconnected components, one new connection can join two components and reduce the number of separate groups by one. Repeating this C - 1 times joins all components. Therefore, the required number of new connections is C - 1.

The code first creates one adjacency list entry for each computer. It adds every existing connection in both directions. It then creates the visited array and sets components to 0.

The outer loop checks every computer from 0 to n - 1. When it finds an unvisited computer, it increases components and calls DFS. DFS marks the current computer visited and recursively visits each neighbor that is still unvisited.

After the loop finishes, the method returns Math.max(0, components - 1). For the diagram's example, components is 3, so the method returns 2.

Let n be the number of computers and e be the number of existing connections. Creating the adjacency list and traversing the graph take O(n + e) time. DFS visits each computer once and examines the stored connections.

The adjacency list uses O(n + e) memory. The visited array uses O(n), and the recursive DFS can use O(n) call-stack space in the worst case. Therefore, the total auxiliary space is O(n + e).

Important cases from the diagram are an already connected network, which returns 0, one computer, which returns 0, no existing connections among n computers, which requires n - 1 connections, and isolated computers, which each count as separate components.

The key insight is to count connected components instead of choosing the new connections directly. I represent the undirected network with an adjacency list and use DFS to discover each component. The outer loop checks every computer. If a computer is still unvisited, it belongs to a component that has not been counted yet, so I increment the component count and run DFS from it. The central invariant is that after a DFS finishes, every computer in that connected component is marked visited. If there are C components, exactly C - 1 new connections are needed to join them into one connected network.

Let n be the number of computers and e be the number of existing connections. The time complexity is O(n + e). We create n adjacency lists, add the e undirected connections, and DFS visits every computer while examining the stored edges. The auxiliary space complexity is O(n + e). The adjacency list stores the graph, the visited array stores one boolean for each computer, and recursive DFS may use up to O(n) call-stack space in the worst case.

A common mistake is treating the connections as directed and storing only u -> v instead of both directions. Another mistake is starting DFS from every computer without first checking visited, which counts the same connected component more than once. Candidates may also mark a node visited too late, causing repeated recursive visits when the graph has cycles. Another mistake is returning the number of components instead of components - 1. It is also incorrect to claim O(n) auxiliary space while ignoring the O(n + e) adjacency list.

Explain the invariant before coding: whenever the outer loop finds an unvisited computer, that computer starts one new connected component, and DFS marks that entire component visited. Once that is clear, the final components - 1 calculation is easy to justify.

I would use a stack to track the currently running functions and a prevTime variable to track the first uncounted time unit. I process the logs in order. When a new function starts, I charge the current top function for the time since prevTime, then push the new function. When a function ends, I include the end timestamp, pop it, and move prevTime forward. This takes O(m) time and O(n) auxiliary space.

The input contains start and end records for functions that can call other functions. We need to calculate how long each function itself runs. Time spent inside a child call must not also count toward its parent. Calls can be nested, so the most recently started function is the one currently running. We therefore keep the active calls in their nesting order and remember the first time unit that has not been counted yet. This lets us give each unit of execution time to exactly one function.

1. Are the logs already ordered by timestamp?
2. Are end timestamps inclusive, so an end at time 5 includes time 5?
3. Can the same function id appear in more than one call?

We have n functions. Each log has the form id:start|end:timestamp. The result is an int array. result[i] stores the exclusive running time of function i. Exclusive means we do not count time that the function spends waiting while a nested child function runs.

For the example, n = 2 and logs = ["0:start:0", "1:start:2", "1:end:5", "0:end:6"]. The required result is [3, 4]. Function 0 runs at times 0, 1, and 6. Function 1 runs at times 2, 3, 4, and 5.

I use a stack of function ids. The top of the stack is the function that is running now. The stack also keeps the nested call order. I use prevTime to mean the first time unit that has not yet been assigned to a function.

The main invariant is that the stack stores the current active call path, and every time before prevTime has already been counted exactly once.

Start with answer = [0, 0], stack = [], and prevTime = 0. No function has received any running time yet. The stack is empty because no function has started.

Step 1 processes 0:start:0. The stack is empty, so there is no active function to charge. Push function 0. The stack becomes [0]. answer stays [0, 0]. Set prevTime to 0.

Step 2 processes 1:start:2. Function 0 is currently on top. It ran from time 0 until just before time 2. Add 2 - 0 = 2 to answer[0]. answer becomes [2, 0]. Push function 1, so the active call path is [0, 1]. Set prevTime to 2.

Step 3 processes 1:end:5. Function 1 is on top. End timestamps are inclusive, so add 5 - 2 + 1 = 4 to answer[1]. answer becomes [2, 4]. Pop function 1. Function 0 is active again. Set prevTime to 5 + 1 = 6 because time 5 has already been counted.

Step 4 processes 0:end:6. Function 0 is on top again. Add 6 - 6 + 1 = 1 to answer[0]. answer becomes [3, 4]. Pop function 0 and set prevTime to 7. All four logs are now processed, so return [3, 4].

Before a child function starts, we give the parent exactly the elapsed time since prevTime. When a function ends, we give it time through the inclusive end timestamp. Then we move prevTime past that timestamp. Because only the function at the top of the stack receives time, nested time is never counted for both parent and child. Every time unit is assigned exactly once.

The Java code keeps the answer array, a Deque<Integer> used as a stack, and prevTime. It parses every log into id, type, and time. A start event may first charge the current top function, then pushes the new function. An end event charges the top function including the end timestamp, pops it, and moves prevTime to time + 1. After every log has been processed, the code returns the answer array.

If m is the number of log entries, the loop processes each log once, so the time complexity is O(m). The result array and call stack use O(n) space in the worst case shown in the diagram. Important cases include one function, deeply nested calls, repeated calls using the same function id, and a function that starts and ends at the same timestamp. Empty or null logs can also be handled defensively by returning a zero-filled result array if that behavior is desired.

The key idea is to always give elapsed execution time to the function at the top of the stack. That function is the one currently running. When a child starts, the parent must stop receiving time, so we first add time - prevTime to the parent and then push the child. When the top function ends, we add time - prevTime + 1 because the end timestamp is inclusive. We then pop it and move prevTime to time + 1. The invariant is that the stack contains the active call path and prevTime is the first uncounted time unit.

Let m be the number of log entries. We process each log once, so the time complexity is O(m). The diagram's solution uses an answer array and a stack for active calls. It gives O(n) auxiliary space in the worst case shown in the diagram.

A common mistake is forgetting that an end timestamp is inclusive. The end calculation needs +1. Another mistake is setting prevTime to time instead of time + 1 after an end event, which double-counts the end unit. Candidates may also forget to charge the current parent before pushing a child. Another error is adding elapsed time to the new function instead of the current stack top. Finally, the stack must follow the exact push and pop order of the nested calls.

Explain the meaning of prevTime before writing code: it is the first time unit that has not been counted yet. Then show why a start uses time - prevTime but an end uses time - prevTime + 1. That makes the inclusive timestamp rule and the stack logic much easier to follow.