39 Microsoft Java Developer Interview Questions & Answers

I would rotate the array in place using three reversals. First, I normalize k with k % n. Then I reverse the whole array, reverse the first k elements, and reverse the remaining n - k elements. This moves the last k values to the front while restoring the correct order inside both parts. A one-step rotation uses the same method with k = 1. The time complexity is O(n), and the auxiliary space is O(1).

The goal is to move the last k values of the array to the front without creating another array. The values that were at the front move to the right, and their order must stay correct. For example, rotating [1, 2, 3, 4, 5, 6, 7] to the right by 3 gives [5, 6, 7, 1, 2, 3, 4]. The in-place reversal method fits because it changes the same array while using only a few temporary variables. A one-step rotation uses the same process with k = 1.

1. Should the rotation be to the right, as shown in the problem?
2. Should I modify the original array instead of returning a new array?
3. Can k be larger than the array length?

The input is an integer array nums and an integer k. We rotate nums to the right by k positions. The array itself is changed in place. For the example nums = [1, 2, 3, 4, 5, 6, 7] and k = 3, the final array is [5, 6, 7, 1, 2, 3, 4]. A one-step rotation is the same operation with k = 1.

Let n be the array length. First reduce k with k = k % n. This handles values of k that are larger than the array. Then perform three reversals: reverse [0..n-1], reverse [0..k-1], and reverse [k..n-1]. The reverse helper uses two positions, left and right. It swaps the values at those positions and moves both positions toward the center.

For the example, nums starts as [1, 2, 3, 4, 5, 6, 7]. The indices are [0, 1, 2, 3, 4, 5, 6]. We have n = 7 and k = 3, so k % n is still 3. The three reverse ranges are [0..6], [0..2], and [3..6]. The central invariant is that each reverse operation swaps symmetric endpoints inside its selected range until left is no longer less than right.

Step 1 starts with [1, 2, 3, 4, 5, 6, 7]. We reverse the full range [0..6]. The array becomes [7, 6, 5, 4, 3, 2, 1].

Step 2 starts with [7, 6, 5, 4, 3, 2, 1]. We reverse the first k = 3 positions, range [0..2]. The values [7, 6, 5] become [5, 6, 7]. The array is now [5, 6, 7, 4, 3, 2, 1].

Step 3 starts with [5, 6, 7, 4, 3, 2, 1]. We reverse the remaining range [3..6]. The values [4, 3, 2, 1] become [1, 2, 3, 4]. The final array is [5, 6, 7, 1, 2, 3, 4]. Processing stops after these three reversals.

Reversing the whole array moves the original suffix of length k to the front, but that suffix is backwards. Reversing the first k positions restores that suffix to its original order. The original prefix is also backwards after the full reversal, so reversing the remaining n - k positions restores that part too. Both blocks are now in the correct order and in their rotated positions.

The rotate method first reads nums.length. If the array is empty, it returns immediately. It then normalizes k with k % n. If k becomes 0, the array already has the required order, so it returns. Otherwise, it calls reverse three times using exactly the ranges from the walkthrough. The reverse method swaps nums[left] and nums[right], increments left, and decrements right while left < right.

Each reversal touches only part of the array, and the three reversals together do O(n) total work. The algorithm uses O(1) auxiliary space because it swaps values inside the original array using only a few variables. An empty array returns immediately. A one-element array stays unchanged. If k is 0, or k % n is 0, no rotation is needed. If k is larger than n, k % n reduces it to the equivalent rotation. For k = 1, the same method performs a one-step rotation.

The key idea is to turn the right rotation into three in-place reversals. After reversing the whole array, the last k values from the original array are at the front, but their order is reversed. Reversing the first k positions restores that block. Reversing the remaining n - k positions restores the other block. The invariant inside the reverse helper is that each swap places the two current symmetric endpoint values into their correct positions for the reversed range. This method fits the problem because it changes the original array and needs only constant extra memory.

The time complexity is O(n). Reversing the whole array takes O(n) work. The next two reversals operate on two separate parts whose total length is n. Therefore, all three reversals together still take linear time. The auxiliary space is O(1). Auxiliary space means extra memory used by the algorithm. The code only keeps variables such as n, k, left, right, and temp. It does not create another array whose size grows with the input.

A common mistake is forgetting to reduce k with k % n, which causes incorrect ranges when k is larger than the array length. Another mistake is taking k % n before checking whether the array is empty, which would divide by zero when n is 0. Candidates also sometimes reverse the ranges in the wrong order or use the wrong boundary, such as starting the last reversal at k - 1 instead of k. Another mistake is creating a second array and then claiming O(1) auxiliary space. Finally, some candidates rotate left even though the required operation is a right rotation.

Explain the three array states while you code: reverse all, reverse the first k values, then reverse the remaining n - k values. With the diagram's example, the ranges [0..6], [0..2], and [3..6] make every step easy to verify.

I would use binary search on the rotated array. At each step, I find the middle, check whether the left half or the right half is sorted, and then keep only the half that can still contain the target. That makes the search logarithmic because the range gets cut down by about half each time. The time is O(log n), and the extra space is O(1).

This question asks me to find a target in a list that was sorted first and then rotated, so the order wraps around in the middle. I still need to return the index of the target, or -1 if it is not there. The best idea is to look at the middle, find which half is already sorted, and then keep only the half that can still hold the target. Each step removes the part that cannot work, so the search stays fast and matches the diagram. java-developer-microsoft-coding…

1. Are all numbers distinct, as shown in the diagram?
2. Should I return -1 if the target is not present?

The input is a rotated sorted array and a target value. The output is the index of the target, or -1 if the target is missing.

At every step, I check the middle element. One side around the middle is always sorted. I use that fact to decide which side can still contain the target.

I start with left at 0 and right at n - 1. This means the whole array is still in the search range. The middle index is computed from those bounds.

Using [4, 5, 6, 7, 0, 1, 2] and target 0, the first middle is 3, so nums[mid] is 7. The left half [4, 5, 6, 7] is sorted, but 0 is not inside it. So I move to the right half. Then the next middle leads me to 0 at index 4, and I stop immediately.

The key rule is that the target, if it exists, always stays inside the current search range. Each step removes the half that cannot contain the target. That is why the answer is still correct after every move.

The code does the same checks as the diagram. It compares nums[mid] with target first. Then it checks which half is sorted. After that, it moves left or right to keep only the useful half. If nothing matches, it returns -1.

The search runs in O(log n) time because each step removes about half of the range. The extra space is O(1) because I only use a few variables. Important edge cases are a one-element array, an already sorted array, and a target that is not present.

The key insight is that a rotated sorted array still has one sorted half at every middle position. I compare the left bound, middle, and right bound to find that sorted half. Then I check whether the target fits inside that half. If it does, I keep searching there. If it does not, I discard that half and search the other one. The invariant is simple: if the target exists, it always stays inside the current search range.

We do not scan the whole array. Each loop removes about half of the remaining range. So the time is O(log n). We only keep a few index variables like left, right, and mid. So the extra space is O(1).

A common mistake is returning nums[mid] instead of the index mid. Another mistake is checking the wrong half and moving the pointers in the wrong direction. Some candidates forget that only one half is sorted at a time. Another error is turning the search into a full linear scan, which loses the logarithmic time. It is also easy to forget the early return when the target is found.

Say the invariant out loud: one half is always sorted, and you only keep the half that can still contain the target.

I would merge the arrays with a min-heap. I keep the smallest current item from each array in the heap, so the heap size never grows past k. Each time I remove the smallest value, I add it to the result and then push the next value from the same array. Because every array is already sorted, this always gives the next global smallest value. The total time is O(N log k), and the extra space is O(k).

This problem asks me to combine several already sorted arrays into one sorted array. I do not sort everything again at the end. I keep the smallest current number from each array in a small helper structure. That lets me choose the next smallest number quickly, then replace it with the next number from the same array. The helper structure is a min-heap, also called a priority queue. It fits well here because each array is already sorted, so the next smallest value in the whole input must be one of those front items.

1. Should I handle empty arrays too?
2. Do you want only the merged values, or do you also want to know which array each value came from?

The input is k sorted arrays. The output is one sorted list with all values from all arrays. The diagram uses:

• A0 = [1, 4, 7, 10]
• A1 = [2, 5, 8, 11]
• A2 = [3, 6, 9, 12]

The final output is: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]

I use a min-heap, also called a priority queue. Each heap item stores:

• value
• arrayIndex
• elementIndex

The key idea is simple. The heap always contains the smallest unmerged candidate from each array. Because each array is sorted, the smallest remaining value must be one of those heap items.

I start by putting the first element of each non-empty array into the heap:

• (1, 0, 0)
• (2, 1, 0)
• (3, 2, 0)

The result list starts empty. The invariant is: the heap holds the next best candidate from each array that still has work left.

Now I repeat the same action:

1. Remove the smallest heap item.
2. Add its value to the result.
3. Push the next value from the same array, if one exists.

For the diagram example:

• Remove 1, then push 4 from A0.
• Remove 2, then push 5 from A1.
• Remove 3, then push 6 from A2.
• Remove 4, then push 7 from A0.
• Remove 5, then push 8 from A1.
• Remove 6, then push 9 from A2.
• Remove 7, then push 10 from A0.
• Remove 8, then push 11 from A1.
• Remove 9, then push 12 from A2.
• Remove 10, 11, and 12. After that, all arrays are done and the heap becomes empty.

The output grows in sorted order the whole time.

The heap always gives me the smallest current candidate. Since each array is sorted, the next number from the same array is the only new candidate that can matter after I remove one item. So the heap never misses a smaller value, and the result list is built in sorted order.

The Java code creates a small Node class with value, array index, and element index. It uses PriorityQueue, which is a min-heap in Java. The code:

• inserts the first item from each non-empty array
• repeatedly polls the smallest node
• appends that value to the result
• pushes the next item from the same array
• stops when the heap is empty

If N is the total number of values and k is the number of arrays, each heap push and pop costs O(log k). We do that once per value, so the total time is O(N log k). The heap holds at most one item per array, so extra space is O(k).

Useful edge cases are:

• an empty input list
• empty arrays inside the input
• arrays with different lengths
• duplicate values
• negative values or zero

The heap always holds the smallest unmerged candidate from each array. Because each array is sorted, the smallest remaining value in the whole input must be one of those heap entries. So the heap top is always the correct next output value. After I remove that value, I push the next item from the same array. This keeps the invariant true until all arrays are empty.

Let N be the total number of values across all arrays, and let k be the number of arrays. The heap never has more than k items. Each insert or remove takes O(log k) time. We do that once for each value, so the total time is O(N log k). The extra memory is O(k) for the heap, plus the output list.

A common mistake is to put every value into the heap at once. That works, but it loses the O(k) heap size and is not the intended approach here.

Another mistake is to store only the value in the heap. You also need the array index and element index so you know where the next value comes from.

A third mistake is to remove a value and forget to push the next value from the same array. That breaks the invariant and makes the output incomplete.

A fourth mistake is to use the wrong complexity. This is not O(N) time. It is O(N log k) because every heap operation costs O(log k).

A final mistake is to compare values from the wrong arrays when duplicate values appear.

When you explain it, keep repeating one sentence: “The heap stores one candidate from each array.” That makes the invariant easy to remember and easy to defend.

I would split the problem into four pieces. For the LRU cache, I use a HashMap plus a doubly linked list so get and put are O(1) expected. For the custom hash map, I use buckets with separate chaining. For the quadtree, I split space when a leaf gets full. For the queue, I use a lock and two conditions so put waits when full and take waits when empty. The cache and queue are O(1) expected, the hash map is average O(1), and the quadtree is average O(log n) with O(n) worst case. Extra space is O(n).

This question asks me to build a few storage pieces and explain how they work when more than one thread uses them. One piece keeps the newest item easy to reach. One piece keeps keys in buckets. One piece splits space into smaller parts for points. One piece lets one side add items and the other side remove items safely. The goal is to show the right state after each step, keep the order correct, and make the shared pieces safe. I would use the same sample values from the diagram so every section stays consistent.

1. Should I assume the queue is bounded and blocking, as the diagram shows?
2. Should the custom hash map resize when the load factor gets too high?
3. Should I treat the quadtree as one point per leaf before it splits?

The sample in the diagram uses an LRU capacity of 3, a hash map with 5 buckets, a quadtree with root capacity 1, and a queue with capacity 3. The goal is not one single trick. It is to show the right state for each structure after each operation.

The LRU cache uses a HashMap for direct access and a doubly linked list for recency order. The custom hash map uses buckets and separate chaining so colliding keys stay reachable. The quadtree uses spatial splits so each point goes to the right area. The bounded queue uses a lock and two conditions so put waits when the queue is full and take waits when it is empty.

Start with empty buckets, an empty cache list with dummy head and tail nodes, an empty quadtree root, and an empty bounded queue. That is the correct starting point because every later change is small and easy to trace.

For the cache, insert 1, 2, and 3. Then read 1, which moves it to the front. Then insert 4, which evicts 2. The final order is [4, 1, 3]. For the hash map, keys 1, 6, 11, and 16 all land in bucket 1 when the bucket count is 5. For the quadtree, the inserted points make the root split and send points into the right child regions. For the queue, put 1, 2, and 3. Then take 1. Then put 4. Then take 2, 3, and 4. The taken order is 1, 2, 3, 4.

The key invariant is simple. The cache list always stays in most-recent to least-recent order. The hash map keeps each key in the right bucket chain. The quadtree keeps each point in the correct space region. The queue count always stays between 0 and capacity. Because these rules stay true after every operation, the final state is correct.

The Java code follows the same order as the diagram. The cache uses a map plus a doubly linked list. The map gives fast lookup. The list gives fast move-to-front and eviction. The custom hash map uses an array of buckets and linked entries. The quadtree inserts a point, splits when a leaf is full, and sends old points back down after the split. The bounded queue uses a circular buffer, a lock, and two conditions. put waits when the buffer is full. take waits when the buffer is empty. This matches the sample runner the prompt asks for.

The cache get and put operations are O(1). The custom hash map operations are average O(1), with a worse case of O(n) in one bucket if many keys collide. The quadtree insert and query operations are average O(log n), but they can fall to O(n) if many points crowd into one area. The queue put and take operations are amortized O(1). Relevant edge cases include duplicate keys, a full cache, an empty queue, repeated points, and very uneven point clusters.

The simplest correct idea is to give each structure one strong invariant. The LRU cache uses the map for direct access and the doubly linked list for recency order. The custom hash map uses buckets and separate chaining so colliding keys are still easy to find. The quadtree keeps each leaf small and splits space when a region gets full. The bounded queue uses a lock and two conditions so put waits when full and take waits when empty. This is better than a plain list or shared array because it keeps the state fast to read and safe to update.

The cache get and put operations are O(1) expected because the HashMap gives direct access and the linked list moves nodes in constant time. The custom hash map is average O(1), and one bad bucket can make it O(n) in the worst case. The quadtree insert and query operations are average O(log n), but they can fall to O(n) if many points land in one region. The bounded queue put and take operations are amortized O(1). Extra space is O(n) for stored nodes, buckets, points, and queue slots.

A common mistake is to use a plain list for the cache and scan it every time. That makes the cache too slow. Another mistake is to forget to move a touched cache entry to the front. That breaks recency. A third mistake is to use if instead of while around queue waits. That can fail when a thread wakes up at the wrong time. A fourth mistake is to split the quadtree but forget to push the old point back down into the new child region.

I would name the invariant first, then show one operation that changes it. For example, I would say the cache list always goes from most recent to least recent, and then show how get and put keep that order.

I would use BFS with a queue and process the tree one level at a time. For each level, I save the current queue size. I process the right child before the left child, so the first node removed from the queue at that level is the node visible from the right side. I add only that first value to the result. Each node is visited once, so time is O(n). The queue uses O(w) auxiliary space, where w is the maximum tree width.

The input is the root of a binary tree. We need to return the values that a person would see when looking at the tree from its right side, from the top level to the bottom level. I process the tree one level at a time. For each node, I add its right child before its left child. This makes the first node processed on the next level the value visible from the right side. The final list contains one visible value for each level.

1. Should an empty tree return an empty list?
2. Do you want the visible node values from top to bottom?

The input is the root node of a binary tree. The output is a list of node values. We need one value from each level. That value must be the node visible from the right side.

For the example tree, the level values are: Level 0: [1] Level 1: [2, 3] Level 2: [5, 4]

The visible result is [1, 3, 4].

I use breadth-first search, or BFS. BFS processes the tree one level at a time. A queue stores the nodes that still need to be processed.

The important rule is that I enqueue the right child before the left child. Because of this, the queue holds each next level in right-to-left processing order. The first node removed for a level is therefore the node visible from the right side.

If root is null, I return an empty result list.

Otherwise, I create an empty result list and a queue. I put the root node into the queue.

For the example, the initial state is: queue = [1] result = []

At the start of every level, I save queue.size(). This tells me exactly how many nodes belong to that level.

At level 0, the queue is [1]. The level size is 1. Node 1 is the first node in this level, so i == 0. I add 1 to the result. I enqueue its right child 3 first, then its left child 2. The queue becomes [3, 2]. The result is [1].

At level 1, the queue starts as [3, 2]. Node 3 is processed first. Because i == 0, I add 3. Node 3 has right child 4, so I enqueue 4. The queue is now [2, 4]. Next I process node 2. It is not the first node of the level, so I do not add it. Node 2 has right child 5, so I enqueue 5. The queue for the next level becomes [4, 5]. The result is [1, 3].

At level 2, the queue starts as [4, 5]. Node 4 is first, so I add 4. It has no children. Then I process node 5, but I do not add it because it is not first in the level. The queue becomes empty. The final result is [1, 3, 4].

At the start of each level, the queue contains that level's nodes in right-to-left processing order. Therefore, the first node removed from the queue is the rightmost node for that level. I add only that first node. Repeating this for every level gives exactly the right-side view from top to bottom.

The outer while loop runs while the queue has nodes. At the start of each level, levelSize stores the number of nodes currently in the queue. The for loop processes exactly those nodes. When i == 0, the current node is the first node of that level, so its value is added to the result. The code then adds node.right before node.left. After all levels are processed, it returns the result.

Every node is removed from the queue and processed once, so the time complexity is O(n), where n is the number of nodes. The queue can hold up to one full level, so auxiliary space is O(w), where w is the maximum width of the tree. In the worst case, w can be O(n).

Important edge cases are an empty tree, a single-node tree, a left-skewed tree, and a right-skewed tree. An empty tree returns []. A single node returns [root.val]. In either skewed tree, every level still contributes one visible node.

The key idea is to process the tree level by level with BFS while keeping each level in right-to-left processing order. A queue is a good fit because it naturally separates one level from the next. Before processing a level, I record its current size. I enqueue each node's right child before its left child. The invariant is: at the start of each level, the queue contains that level's nodes in right-to-left order. Therefore, the first node removed from the queue is the rightmost visible node, and only that value is added to the result.

The time complexity is O(n), where n is the number of nodes in the tree. Every node enters the queue once, leaves the queue once, and is processed once. The auxiliary space is O(w), where w is the maximum number of nodes on any one level of the tree. The queue may need to hold that whole level. In the worst case, the maximum width can grow to O(n).

A common mistake is enqueueing the left child before the right child while still adding the first node of each level. That would produce the left-side view instead. Another mistake is forgetting to save levelSize before processing the level. If the loop uses the changing queue size, nodes from the next level can be mixed into the current level. A candidate may also add every node instead of only the node where i == 0. Another mistake is claiming O(1) extra space even though the queue can grow with the tree width. Finally, remember to handle a null root before adding it to ArrayDeque.

State the invariant before writing the loop: because I enqueue right before left, the first node processed at every level is the rightmost visible node. Then make the code follow that statement directly with levelSize and the i == 0 check.

I’d use the BST ordering to walk down from the root. If both target values are smaller than the current node, I move left. If both are larger, I move right. Otherwise, the paths split or the current node matches one target, so I return the current node as the LCA. This takes O(h) time and O(1) extra space. For a general binary tree, I would recursively search both subtrees, which takes O(n) time and O(h) recursion-stack space.

We need to return the lowest node whose subtree contains both target nodes. A target node can also be the answer itself. In a BST, smaller values are on the left and larger values are on the right. That ordering lets us choose only one subtree when both targets are on the same side. We stop when the targets split across the current node, or when the current node matches one target. In the shown example, we start at 6, move left to 2, and return node 2.

1. Can I assume both target nodes are present in the tree?
2. Should I return the node reference rather than only its value?

The input is the root of a binary search tree and two target nodes, p and q. We must return the lowest node whose subtree contains both targets. A node can be an ancestor of itself. In the diagram, root is 6, p is node 2, q is node 4, and the returned LCA is node 2.

A BST keeps smaller values on the left and larger values on the right. If both p.val and q.val are smaller than current.val, both targets are in the left subtree, so we move left. If both are larger, both targets are in the right subtree, so we move right. Otherwise, the paths split at current or current matches one target, so current is the LCA.

Set current to root. In the example, current starts at node 6. The invariant is that current remains an ancestor candidate for both targets. We move to one child only when both targets are known to be on that same side.

At current = 6, p = 2 and q = 4 are both less than 6. The algorithm moves left, so current becomes 2. At current = 2, p.val equals current.val. Therefore, neither same-side condition holds. The algorithm returns current and stops. The returned node is 2.

If both targets are strictly on the same side of current, their lowest common ancestor must also be on that side, so moving there is safe. The first node where the targets are not both strictly on one side is either their split point or one of the targets itself. That node is the lowest node whose subtree contains both targets. Here, node 2 is an ancestor of itself and node 4.

The Java code keeps one current pointer and uses a loop. It compares p.val and q.val with current.val, moves left or right only when both targets are on the same side, and otherwise returns current. For a general binary tree, value ordering is unavailable. Use recursive postorder search instead. If root is null, p, or q, return root. Search left and right. If both calls return non-null nodes, root is the LCA. Otherwise, return the non-null side.

For the BST solution, time is O(h), where h is the tree height, and auxiliary space is O(1). A balanced BST gives O(log n) time, while a skewed BST can take O(n). Relevant cases include p being an ancestor of q, q being an ancestor of p, both targets starting in the same subtree, and a skewed tree. For the general binary tree approach, time is O(n) and recursion-stack space is O(h).

The key insight is to use the BST ordering instead of searching both subtrees. At each current node, compare both target values with current.val. If both are smaller, move left. If both are larger, move right. Otherwise, return current because the target paths split there or current matches one target. The central invariant is that current remains an ancestor candidate for both targets. This gives a single root-to-answer traversal. In a general binary tree, this ordering rule does not exist, so recursive postorder search of both subtrees is needed.

For the BST solution, the algorithm follows only one path down the tree. If the tree height is h, the time is O(h). In a balanced BST, h is O(log n). In a skewed BST, h can be O(n). The iterative solution keeps only one current pointer, so auxiliary space is O(1). For the general binary tree method shown in the diagram, we may visit every node, so time is O(n). Its recursion stack can grow to the tree height, so auxiliary space is O(h).

A common mistake is searching both subtrees even though BST ordering lets us choose one side. Another is moving left when only one target is smaller, or moving right when only one target is larger. Both targets must be strictly on the same side before moving. Candidates can also forget that one target may itself be the LCA, as node 2 is for nodes 2 and 4. Another mistake is claiming the BST solution always takes O(log n); a skewed BST can require O(n) time.

Say the three-way rule before writing code: both smaller means go left, both larger means go right, otherwise return current. Then trace 6 to 2 to show why a target node can itself be the LCA.

I would use Dijkstra’s algorithm with a min-heap and a dist table. I always pop the cell with the smallest total cost, then try its four neighbors and relax a neighbor only when I find a cheaper path. Because every move cost is non-negative, the first time I pop the goal, that cost is final. The time is O(mn log(mn)) and the extra space is O(mn).

This problem asks me to move from the top-left square to the bottom-right square in a grid. Every square has a cost, and some squares may be blocked. I need the cheapest total cost to reach the end, or -1 if there is no safe path. The best way is to always look at the cheapest place I know about next. That fits this diagram because every cost is non-negative, so once the goal is picked first, its cost is already final.

1. Are blocked cells marked with -1, and should I return -1 if the start or goal is blocked?
2. Should I count the cost of the starting square in the total?

The input is a grid of non-negative costs. Some cells may be blocked. The output is the minimum total cost from (0, 0) to (m - 1, n - 1), or -1 if there is no path.

I use Dijkstra’s algorithm because all costs are non-negative. I store each state as (cost, row, col). The heap always gives me the next cheapest state. The dist table stores the best cost I have found so far for each cell.

I set every dist cell to INF. Then I set dist[0][0] to the start cost and push the start state into the min-heap. This is the correct start because the path begins at the top-left cell.

The diagram uses one 4 x 4 grid. The start is (0, 0). The goal is (3, 3). I pop the cheapest state first. I check four directions. I skip blocked cells and cells outside the grid. When a new path is cheaper, I update dist and push the new state.

The key rule is simple. The heap always gives the smallest current cost first. Because costs never go down, the first time I pop the goal, that cost cannot be beaten later. That is why I can stop early.

The Java code creates the same 4 x 4 example grid, builds dist, and uses a PriorityQueue for the heap. It skips stale heap entries. It stops right away when it pops the goal. If the heap becomes empty first, it returns -1.

There are m * n cells in the grid. Each useful relaxation may push a state into the heap. That gives O(mn log(mn)) time and O(mn) extra space. The important edge cases are a 1 x 1 grid, zero-cost cells, blocked start or goal cells, and no reachable path.

I model each cell as a state. Dijkstra’s algorithm fits because all cell costs are non-negative. The dist table stores the best cost found so far for each cell. The min-heap always exposes the state with the smallest current cost. That is the central invariant. When I pop the goal from the heap, that is the final minimum cost, because no later path can be cheaper.

There are m * n cells in the grid. Dijkstra may put a cell into the heap more than once, but each heap push and pop costs log(mn). So the total time is O(mn log(mn)). The dist table uses O(mn) space, and the heap can also hold O(mn) states, so the extra space is O(mn).

A common mistake is to use BFS. BFS does not work here because the grid has weights, not equal steps. Another mistake is to forget that the start cell cost counts in the total. A third mistake is to skip the stale-entry check, which can make the heap process old paths again. Another easy mistake is to ignore blocked cells or to return a cost before the goal is actually popped from the heap.

Say the invariant out loud: the heap always gives the cheapest known cell first, so the first popped goal is final.

I would use two indices, one at the start and one at the end of the list. While left is smaller than right, I swap the two values and move both indices toward the center. Each swap places two elements into their final reversed positions. When the indices meet or cross, the same list is fully reversed. For an array-backed list such as ArrayList, this takes O(n) time and uses O(1) auxiliary space.

The task is to change the existing list so its values appear in the opposite order. We must not create another list for the reversed result. I would start with one position at each end of the list, exchange those two values, and then move both positions toward the center. Each exchange puts two values directly into their correct reversed positions. Because the original list is changed directly and only a few temporary variables are needed, this method satisfies the in-place requirement.

1. Can I assume the input list is mutable and supports indexed get and set operations?
2. Can I assume efficient indexed access, such as an ArrayList, when discussing the O(n) time complexity?

The input is one mutable list. The goal is to reverse that same list without allocating another list for the answer. In the diagram, the example starts as [10, 20, 30, 40, 50]. After the method finishes, that same list contains [50, 40, 30, 20, 10]. The method does not need to return a new list because it changes the input list directly.

I use two indices called left and right. left starts at index

1. right starts at list.size() -
2. The central invariant is that every element outside the current [left, right] window is already in its final reversed position. Each swap makes that completed area larger.

For [10, 20, 30, 40, 50], left starts at 0 and right starts at 4. The value at index 0 is 10. The value at index 4 is 50. The loop continues while left < right. This means there is still a pair of positions that needs to be exchanged.

Step 1 starts with [10, 20, 30, 40, 50]. left is 0 and right is 4. Save the value 10 in temp. Put 50 into index 0. Then put temp, which contains 10, into index 4. The list becomes [50, 20, 30, 40, 10]. Then left becomes 1 and right becomes 3.

Step 2 starts with [50, 20, 30, 40, 10]. left is 1 and right is 3. Save 20 in temp. Put 40 into index 1. Then put 20 into index 3. The list becomes [50, 40, 30, 20, 10]. Then left becomes 2 and right becomes 2.

Now left == right, so the condition left < right is false. The loop stops. The middle value 30 stays at index 2 because it is already in its correct reversed position.

After each swap, the elements at the current left and right positions are placed into their final reversed positions. Then the unfinished [left, right] window becomes smaller. Because the two indices keep moving toward the center, they eventually meet or cross. At that point, every position contains the value that belongs there in the reversed list.

The method keeps three pieces of temporary state: left, right, and temp. temp saves the current left value before that position is overwritten. The right value is written into the left position, and then the saved value is written into the right position. After the swap, left is incremented and right is decremented. The method returns void because the supplied List object has already been modified.

For an array or ArrayList, the algorithm takes O(n) time. It performs at most n/2 swaps, and indexed get and set operations are constant time. Auxiliary space is O(1) because it stores only left, right, and temp. An empty list performs no swaps. A one-element list is already reversed. An even-length list swaps all elements in pairs. An odd-length list leaves the middle element in place. Duplicate and negative values work correctly because the algorithm only exchanges positions. On LinkedList, the same indexed code is slower because get and set by index require traversal.

The key idea is to reverse the list from the outside toward the center. left starts at the first index and right starts at the last index. The values at those positions are swapped, and then left moves right while right moves left. The invariant is that all elements outside the current [left, right] window are already in their final reversed positions. When left reaches or passes right, no unreversed pair remains. This method is a good fit because it changes the original list directly and uses only a constant amount of extra memory.

For an array or ArrayList, the time complexity is O(n). The method performs at most n/2 swaps, and each indexed read or write takes O(1) time. Auxiliary space is O(1). Auxiliary space means extra memory used by the algorithm. The amount of extra memory does not grow with n because the method stores only left, right, and one temporary value. For a LinkedList, this exact index-based implementation can take O(n^2) time because each indexed get or set may require walking through part of the list.

One common mistake is overwriting the left value before saving it in temp. That loses the value needed for the right position. Another mistake is forgetting to move both left and right after a swap, which can cause an infinite loop. Candidates may also create a second list, which breaks the in-place requirement. Using left <= right is unnecessary because the middle element does not need to swap with itself. Another mistake is claiming the indexed implementation is O(n) for every List type. That claim is correct for ArrayList, but not for LinkedList.

State the invariant while you code: everything outside the current [left, right] window is already in its final reversed position. Then each swap and pointer movement has a clear reason.

I treat the column label like a base-26 number, but each letter uses values 1 through 26 instead of 0 through 25. I start with result equal to 0 and read the label from left to right. For each character, I compute its value with ch - 'A' + 1, then update result as result * 26 + value. After all characters are processed, I return result. This takes O(n) time and O(1) auxiliary space.

A spreadsheet uses letters to identify columns instead of showing ordinary column numbers. A means column 1, Z means column 26, and after Z the labels continue with two letters such as AA. We need to turn one of these labels into its matching number. The useful idea is to build the answer from left to right. Each letter adds its own value, while the value already built must move one position before the next letter is added. This gives the correct number without extra storage.

1. Can I assume the input is a valid non-empty uppercase spreadsheet column label?
2. Should the returned column number always fit in a Java int?

The input is a spreadsheet-style column label such as "A", "Z", or "AA". The output is its 1-indexed column number. Spreadsheet letters use values from 1 through 26. A is 1, B is 2, and Z is 26.

I read the label from left to right. The running result represents the value of the prefix already processed. For each new character, I first multiply the previous result by 26. This shifts the previous value one spreadsheet position to the left. Then I add the 1-based value of the current letter.

The update is: result = result * 26 + value

The current letter value is: value = ch - 'A' + 1

The central invariant is that after processing any prefix of the label, result equals the spreadsheet column number represented by that prefix.

I start with result = 0. Traversal begins at index 0. No extra data structure is needed. The integer result stores the numeric value of the prefix processed so far.

The diagram uses the input "AA" and the expected result 27.

At index 0, the character is A. Its numeric value is 1. The result before processing it is 0. I calculate 0 * 26 + 1, so result becomes 1. The processed prefix "A" therefore represents column 1.

At index 1, the character is again A. Its numeric value is 1. The result before processing it is 1. I calculate 1 * 26 + 1, so result becomes 27. All characters have now been processed, so the function returns 27.

The same result can be verified using place values: 1 * 26^1 + 1 * 26^0 = 26 + 1 = 27.

After each iteration, result equals the value of the prefix processed so far. Multiplying by 26 moves that prefix one base-26 position to the left. Adding the current letter value puts the new letter into the final position. Therefore, when all characters have been processed, result equals the numeric value of the complete spreadsheet label.

The Java method loops through the characters from left to right. It converts each uppercase letter to a value from 1 through 26 and applies result = result * 26 + value. After the last character, it returns result. The time complexity is O(n), where n is the label length. The auxiliary space is O(1) because only a few primitive variables are used. Relevant examples are A -> 1, Z -> 26, AA -> 27, and AZ -> 52. The shown solution assumes a valid non-empty uppercase spreadsheet label.

The key insight is to interpret the label using spreadsheet base-26 place values, where A = 1 through Z = 26. We keep one running integer called result. For every character, multiplying result by 26 shifts the value already built one position to the left. We then add the current character's 1-based value. The invariant is: after processing a prefix of the string, result equals the spreadsheet column number represented by that prefix. After the final character, the processed prefix is the whole label, so result is the required answer.

Let n be the number of characters in the column label. The algorithm takes O(n) time because it visits each character once and performs a constant amount of work for that character. It uses O(1) auxiliary space because the extra memory does not grow with n. It only keeps a loop index, the current character, its numeric value, and the running result.

A common mistake is mapping A to 0 instead of 1. Spreadsheet labels use A = 1 through Z = 26. Another mistake is updating the running value in the wrong order. The correct operation is result = result * 26 + value, because the previous prefix must first move one base-26 position. Candidates may also forget that the position of each character matters and process the letters as independent values. Another mistake is claiming O(n) extra space even though the algorithm uses only a fixed number of primitive variables.

Use "AA" to explain the update before writing code. After the first A, result is 1. For the second A, calculate 1 * 26 + 1 = 27. That small trace makes both the base-26 idea and the loop update easy to explain.