51 Amazon .NET Developer Interview Questions & Answers

I would group the strings by a normalized key. For each word, I sort its characters in ascending order. Anagrams produce the same sorted key, so I use a Dictionary<string, List<string>> where each key represents one anagram class and each value stores the original words in that class. I process every word and add it to its matching bucket. For n words with average length k, the expected time is O(n * k log k), and the auxiliary space is O(n * k).

The input is a list of strings. We need to put strings into the same group when they contain exactly the same characters with the same counts, even if those characters appear in a different order. For example, "ada" and "aad" belong together. The main idea is to sort the characters of every word. This gives all anagrams the same comparison key. We store each original word under that key in a dictionary. After every word is processed, the dictionary values contain the required anagram groups.

1. Should character comparison be case-sensitive?
2. Does the order of the groups matter?
3. Should the original order of words inside each group be preserved?
4. Can the input contain empty strings or repeated identical strings?

The example input is {ada, mnj, kkl, mjn, aad}. We must return groups of the original strings. The diagram shows the valid result {{ada, aad}, {mnj, mjn}, {kkl}}. We return the strings themselves, not their positions. The question does not require one unique ordering of the groups, so the displayed result is one valid ordering.

For each word, sort its characters in ascending order. The sorted text becomes a canonical key. Canonical means one standard representation used for comparison. For example, "ada" becomes "aad". The word "aad" also becomes "aad", so both strings belong in the same group. We use Dictionary<string, List<string>>. Each dictionary key is a sorted character sequence, and each value is the list of original strings that produced that sequence.

Start with an empty dictionary. There are no groups yet. Process the input from left to right. For each word, create its sorted key. If that key is not already in the dictionary, create a new empty list for it. Then append the original word to that list.

Step 1: Read "ada". Sorting its characters gives "aad". The dictionary is empty, so create key "aad" and add "ada". State after the step: aad -> [ada].

Step 2: Read "mnj". Sorting gives "jmn". That key is new, so create it and add "mnj". State after the step: aad -> [ada], jmn -> [mnj].

Step 3: Read "kkl". Sorting gives "kkl". That key is new, so create it and add "kkl". State after the step: aad -> [ada], jmn -> [mnj], kkl -> [kkl].

Step 4: Read "mjn". Sorting gives "jmn". That key already exists, so append "mjn" to its list. State after the step: aad -> [ada], jmn -> [mnj, mjn], kkl -> [kkl].

Step 5: Read "aad". Sorting gives "aad". That key already exists, so append "aad" to its list. Final state: aad -> [ada, aad], jmn -> [mnj, mjn], kkl -> [kkl].

All five words have now been processed. We collect the dictionary values. The diagram's final result is {{ada, aad}, {mnj, mjn}, {kkl}}.

Two strings are anagrams exactly when they contain the same characters with the same counts. Sorting those characters creates the same canonical form for both strings. Therefore, all anagrams receive the same dictionary key. Strings that are not anagrams receive different sorted keys. Every original string is added to exactly one bucket, so each bucket contains one anagram class and no input string is lost.

For every word, the code converts the string to a char array, sorts the array with Array.Sort, and creates a new string from the sorted characters. That string is the dictionary key. TryGetValue checks whether the dictionary already has a bucket for that key. If not, the code creates a new List<string> and stores it. Then it adds the original word to the bucket. After the loop, the dictionary values are copied into the final result and returned. Main runs the exact example shown in the diagram.

Let n be the number of words and k be the average word length. Sorting one word costs O(k log k). Doing this for all words gives O(n * k log k) expected total time. Dictionary lookup and insertion are O(1) on average, apart from the cost of hashing the string key, and sorting remains the dominant operation. Auxiliary space is O(n * k) because normalized keys are stored and the groups grow with the input. Empty input returns an empty result. One word creates one group. Repeated identical words stay together. The diagram keeps comparison case-sensitive unless the requirements say to normalize case first.

The key insight is that every anagram class can be represented by one canonical key. We create that key by sorting each string's characters. For example, both "ada" and "aad" become "aad", while both "mnj" and "mjn" become "jmn". A Dictionary<string, List<string>> maps each sorted key to the original strings that produced it. The central invariant is that every string stored in one bucket has exactly the same sorted character sequence. Therefore, every bucket contains only anagrams, and all anagrams are placed together.

Let n be the number of input words and k be the average number of characters in one word. Sorting the characters of one word costs O(k log k). We do that for every word, so the expected total time is O(n * k log k). Dictionary lookup and insertion are O(1) on average, although creating and hashing string keys also depends on their length. The sorting cost remains the main term. Auxiliary space is O(n * k) because the dictionary stores normalized keys and the grouped input grows with the total number of characters.

One mistake is using the original string as the dictionary key instead of its sorted form. Another is storing the sorted key as the output and losing the original string. A candidate may also overwrite an existing bucket instead of appending another matching word. Repeated strings must remain in the same group rather than being removed. Another common mistake is claiming O(n) time and ignoring the O(k log k) sort performed for each word. Case handling should also follow the stated requirement instead of being changed silently.

Explain one pair before writing the full code. For example, show that "mnj" becomes "jmn" and "mjn" also becomes "jmn". Then say that the sorted string is the dictionary key. This quickly explains why both original strings enter the same bucket.

I would scan the array from right to left and use a monotonic stack of indices. The stack keeps useful candidates whose values are in decreasing order. For each value, I pop every stack value that is smaller than or equal to it. Then the remaining top, if one exists, is the first greater value to the right. I store that result and push the current index. Each index is pushed and popped at most once, so time is O(n) and auxiliary space is O(n).

The input is an array of integers. For each position, we need the first value to its right that is strictly larger. If no larger value exists, we return -1 for that position. For example, the diagram uses [4, 5, 2, 25, 7, 8] and returns [5, 25, 25, -1, 8, -1]. We scan from right to left because answers come from values on the right. A stack helps us remove values that can never be useful again.

1. By "next bigger," do you mean the first strictly greater value to the right of each element?
2. Should I return -1 when no greater value exists?
3. Are duplicate values allowed, and should equal values be excluded because the answer must be strictly greater?

The input is an integer array. The output is another integer array of the same size. Each output position contains the first strictly greater value found to the right of the matching input position. We return values, not indices. If no greater value exists, that result stays -1.

For the diagram example: Input: [4, 5, 2, 25, 7, 8] Output: [5, 25, 25, -1, 8, -1]

I use a stack of indices and scan from right to left. Each stored index points to a value that may be the next greater value for an element farther left. Before using the stack top, I remove indices whose values are less than or equal to the current value. Those values cannot be the next strictly greater answer for the current element or for an earlier element when the current value is an equal or better candidate.

The important invariant is that the stack contains useful indices from the right side, with their values in decreasing order from bottom to top. After the removals, the top value is the nearest remaining value that is greater than the current value.

Create a result array with the same length as the input and fill every position with -1. This already represents the correct answer when no greater value exists. Create an empty Stack<int>. The stack stores indices, not the values themselves. Start at the last index and move toward index 0.

At index 5, the current value is 8. The stack is empty, so result[5] stays -1. Push index 5. The stack represents value [8].

At index 4, the current value is 7. The top value is 8. Since 8 is greater than 7, result[4] becomes 8. Push index 4. The stack now represents values [8, 7].

At index 3, the current value is 25. Values 7 and 8 are both less than or equal to 25, so pop both indices. The stack becomes empty. There is no greater value to the right, so result[3] stays -1. Push index 3. The stack now represents [25].

At index 2, the current value is 2. The top value is 25. It is greater than 2, so result[2] becomes 25. Push index 2. The stack represents [25, 2].

At index 1, the current value is 5. The top value 2 is not greater than 5, so pop index 2. The new top value is 25, which is greater than 5. Set result[1] to 25. Push index 1. The stack represents [25, 5].

At index 0, the current value is 4. The top value is 5. It is greater than 4, so result[0] becomes 5. Push index 0. The final stack represents [25, 5, 4], and the final result is [5, 25, 25, -1, 8, -1].

Before we choose an answer, every value on the stack that is less than or equal to the current value is removed. Such a value cannot be a strictly greater answer. The remaining top, if one exists, is greater than the current value and is the nearest useful candidate to its right. Equal values are also popped, so duplicates never incorrectly count as a strictly greater answer.

The code creates the result array and fills it with -1. It creates Stack<int> to store indices. The for loop moves from the last index to the first. The while loop removes indices while their values are less than or equal to the current value. If the stack still has an index, its value becomes the current answer. Then the current index is pushed so it can help positions farther left. Finally, the method returns the result array.

The time complexity is O(n). Each index is pushed once and can be popped at most once. The auxiliary stack space is O(n), and the returned result array also contains n values. A strictly increasing array gives the next element as the answer for each position except the last. A strictly decreasing array returns -1 everywhere. Equal values are popped because the answer must be strictly greater. A one-element array returns [-1], and an empty array returns an empty result.

The key idea is to scan from right to left while keeping a monotonic stack of indices. Each index on the stack represents a value that is still useful as a possible next greater value for elements farther left. For the current value, remove stack entries whose values are less than or equal to it. They cannot be a strictly greater answer. After those removals, the stack top, if present, is the nearest useful greater value. Then push the current index. The invariant is that the stack keeps useful right-side candidates in decreasing value order from bottom to top.

Let n be the number of elements. The time complexity is O(n). Although there is a while loop inside the for loop, each index is pushed onto the stack once and popped at most once. So the total number of stack operations grows linearly with n. The auxiliary stack space is O(n) because the stack can hold up to n indices. The returned result array also uses O(n) storage because it contains one answer for each input element.

A common mistake is looking for the largest value anywhere to the right instead of the first greater value to the right. Another mistake is using < instead of <= in the pop condition. That can incorrectly treat an equal duplicate as greater. Candidates may also store values without understanding that the diagram's stack stores indices. Another error is scanning left to right while using this exact stack logic. Finally, it is incorrect to call the nested loops O(n²). Each index is pushed once and popped at most once, so the total time is O(n).

While coding, say the stack invariant out loud: after I pop every value less than or equal to the current value, the remaining top is the nearest useful strictly greater value on the right. That one sentence explains both the pop condition and why the answer is correct.

I would sort the array first, then compare only adjacent values. In sorted order, the minimum absolute difference must appear between two neighbors. I keep a minDiff value and a result list. If I find a smaller difference, I replace the previous result. If I find the same difference, I add that pair. For [4, 2, 8, 1, 7], the result is [[1, 2], [7, 8]]. Time is O(n log n), with O(1) auxiliary space excluding the output.

We are given distinct integer values and need every pair whose absolute difference is as small as possible. The main idea is to put the values in increasing order first. After sorting, values that are closest must be next to each other. So we only compare neighboring values instead of checking every possible pair. We keep the smallest difference seen so far and collect every neighboring pair that has that difference. This gives all required pairs in sorted order and matches the example shown in the diagram.

1. Should each returned pair contain the values rather than their original indices?
2. Should all pairs with the same minimum difference be returned in sorted order?

The input is an array of distinct integers. We return the values themselves, not their original indices. We must return every pair whose absolute difference equals the global minimum difference. Each pair has the smaller value first, and the result is in sorted order. For the diagram example, the input is [4, 2, 8, 1, 7] and the final result is [[1, 2], [7, 8]].

First, sort the array in ascending order. The example becomes [1, 2, 4, 7, 8]. Set minDiff to a very large value and create an empty result list. The important rule is that, after sorting, a globally closest pair must appear as two adjacent values.

Compare each neighboring pair from left to right. For each pair, calculate arr[i + 1] - arr[i]. Because the array is sorted, this value is non-negative and is the absolute difference between those two values. If the new difference is smaller than minDiff, update minDiff, clear the old result, and store the new pair. If it equals minDiff, add the pair without clearing the previous matches.

Start with sorted array [1, 2, 4, 7, 8], minDiff set to a very large value, and an empty result.

At i = 0, compare (1, 2). The difference is 1. Since 1 is smaller than the current minDiff, set minDiff to 1, clear the result, and add [1, 2]. The result is now [[1, 2]].

At i = 1, compare (2, 4). The difference is 2. Since 2 is greater than 1, do nothing. The result stays [[1, 2]].

At i = 2, compare (4, 7). The difference is 3. Since 3 is greater than 1, do nothing. The result still stays [[1, 2]].

At i = 3, compare (7, 8). The difference is 1. Since it equals minDiff, add [7, 8]. The final result becomes [[1, 2], [7, 8]].

In a sorted array, the minimum absolute difference must occur between adjacent values. If two selected values are not adjacent, at least one sorted value lies between them, creating an adjacent gap that is no larger than their full gap. Therefore, scanning all adjacent pairs is enough to find the global minimum. Keeping every pair whose difference equals minDiff returns all ties.

The code sorts the input with Array.Sort. It stores minDiff as long so subtraction remains safe even when integer values are far apart. It then loops from index 0 through the second-to-last element. Each iteration calculates the adjacent difference, updates or extends the result list, and finally returns all collected pairs.

Sorting costs O(n log n), and the adjacent scan costs O(n), so the total time is O(n log n). The diagram reports O(1) auxiliary space excluding the output. If the input has fewer than two values, there is no pair, so the returned list is empty. Negative values work because sorting makes every adjacent subtraction non-negative. Multiple pairs with the same minimum difference are all returned.

The key insight is to sort the values first. After sorting, the smallest absolute difference between any two values must occur between two adjacent elements. This avoids checking every possible pair. The invariant is: after each adjacent pair is processed, minDiff is the smallest difference seen so far, and result contains exactly the processed pairs whose difference equals minDiff. A smaller difference replaces the previous best and clears old pairs. An equal difference adds another tied pair. Scanning all adjacent pairs therefore finds the global minimum and every pair that reaches it.

Let n be the number of values. Sorting the array takes O(n log n) time. After sorting, the code checks n - 1 adjacent pairs, which takes O(n) time. The total time is O(n log n). The diagram treats the in-place sort as O(1) auxiliary space excluding the returned result. The output list itself can grow when several pairs have the same minimum difference, so output storage depends on the number of returned pairs.

A common mistake is checking every possible pair, which takes O(n²) time even though sorting allows an adjacent scan. Another mistake is forgetting to clear the result when a new smaller difference is found. A candidate may also return only one pair and miss ties. Another error is returning original indices when this solution returns the values themselves. Finally, subtracting two int values before converting to long can overflow for extreme integer values.

After sorting, state the key proof idea before coding: the minimum difference must occur between adjacent values. Then explain the two update cases separately. A smaller difference resets the result, while an equal difference adds another pair.

I would use a hash map that stores each earlier value and its index. For each number, I calculate its complement, which is target minus the current value. I check for that complement before storing the current number, so I never reuse the same element. When I find the complement, I return the earlier index and the current index. I process each item at most once and stop when the answer is found. This gives O(n) expected time and O(n) auxiliary space.

We are given a list of whole numbers and a target number. We need to find two different positions whose numbers add up to that target. We return the positions, not the numbers themselves. The question guarantees that exactly one matching pair exists. We may return the two positions in either order. I will remember each number I have already seen and its position. For every new number, I first check whether the number needed to reach the target was seen earlier. This lets me stop as soon as the matching pair is found.

1. Should I return the two indices in any order? The question says yes.
2. Is exactly one valid pair guaranteed? The question says yes.
3. Can the array contain duplicate, negative, or zero values? The hash-map method can handle them.

The input is an integer array called nums and an integer called target. The output is two indices. The values stored at those two indices must add up to target. I must not use one array element twice. The problem guarantees one valid pair, and the two returned indices can appear in either order.

I use a C# Dictionary<int, int> as a hash map. Each key is a value seen earlier in the array. Each dictionary value is the earlier index where that number appeared. For the current value x, I calculate need = target - x. I check whether need is already in the dictionary before inserting x. This order is important because it prevents the current element from matching with itself. The central invariant is that the dictionary contains only values from earlier indices.

I start with an empty dictionary. Then I move from left to right through the array. Before processing index 0, the dictionary is empty because no earlier values exist.

The diagram uses nums = [2, 7, 11, 15] and target = 26.

At index 0, x = 2. The needed value is 26 - 2 = 24. The dictionary is empty, so 24 is not found. I store 2 -> 0.

At index 1, x = 7. The needed value is 26 - 7 = 19. The dictionary is {2 -> 0}, so 19 is not found. I store 7 -> 1.

At index 2, x = 11. The needed value is 26 - 11 = 15. The dictionary is {2 -> 0, 7 -> 1}, so 15 is not found. I store 11 -> 2.

At index 3, x = 15. The needed value is 26 - 15 = 11. The dictionary is {2 -> 0, 7 -> 1, 11 -> 2}. The value 11 is found at index 2. I return [2, 3] and stop immediately. nums[2] + nums[3] = 11 + 15 = 26.

Before processing index i, the dictionary contains only values from indices smaller than i. If the needed complement is present, its stored index is therefore different from the current index. The two values add to target because need was calculated as target - x. If the complement is not present, storing the current value makes it available for later elements. With the guaranteed solution, this process eventually finds the valid pair.

The code creates a Dictionary<int, int>. It loops through nums from left to right. For each index, it calculates the complement and calls TryGetValue before inserting the current value. If the complement exists, TryGetValue gives its earlier index and the method returns the two indices. Otherwise, the current value and index are stored. The fallback return is defensive only because the stated problem guarantees a solution.

Dictionary lookup and insertion are O(1) on average, so the overall expected time is O(n). We process the input at most once because the method returns immediately when the pair is found. The dictionary can grow to O(n) entries, so auxiliary space is O(n). Duplicate values work because lookup happens before insertion. Negative numbers and zero also work because complement arithmetic does not depend on values being positive.

The key idea is to remember numbers that appeared earlier so we can quickly ask whether the current number has a partner. For each current value x, calculate complement = target - x. The hash map stores value -> earlier index. Check for the complement before storing x. If the complement exists, return [map[complement], currentIndex]. Otherwise, store the current value and index and continue. The central invariant is that the map contains only values from earlier indices. This both preserves the original indices and prevents reuse of the current element. A nested-loop approach would compare many pairs, while the dictionary gives average O(1) lookup and makes the overall expected time O(n).

Let n be the number of elements in nums. We process the input at most once and may stop early when the pair is found. C# Dictionary<TKey, TValue> lookup and insertion are O(1) on average, with normal hashing and collision caveats. Therefore, the overall expected time is O(n). The dictionary may store up to n earlier values and their indices, so the auxiliary space is O(n). This is the standard optimal expected-time approach for this problem.

A common mistake is returning the two values instead of their indices. Another mistake is inserting the current value before checking its complement, which can allow the same element to be reused. Sorting the array without preserving original indices is also wrong for this output contract. Candidates may also keep processing after finding the pair instead of returning immediately. Finally, saying the method has guaranteed O(n) time is too strong because Dictionary lookup and insertion are O(1) on average, so the overall O(n) bound is expected time.

State the dictionary invariant before writing the loop: it stores only values from earlier indices. Then say that you calculate the complement, check it before insertion, and return immediately when it is found. This makes the no-reuse rule and the correctness of the returned indices easy to explain.

I would use a HashSet to remember values that have already appeared. I keep two node references, prev and curr. If curr.Value is new, I add it to the set and move prev forward. If the value is already in the set, I remove that node by setting prev.Next to curr.Next. Then I continue with curr.Next. This preserves the first occurrence and keeps the list connected. The expected time is O(n), and the auxiliary space is O(n).

The input is a linked list that may contain the same value more than once. We must remove later repeated nodes and keep the first time each value appears. The remaining nodes must stay in their original order and remain connected. For the example 1 → 2 → 3 → 2 → 4 → 3 → 5, the result is 1 → 2 → 3 → 4 → 5. A set works well because it can quickly tell us whether a value has already appeared.

1. Should I preserve the first occurrence of each value and keep the original order?
2. Is it acceptable to modify the existing linked list in place?
3. Can the input list be empty?

We receive the head node of a singly linked list. We must remove nodes whose values have already appeared earlier in the list. We keep the first node for each value. We return the head of the modified list.

The diagram uses this example: Input: 1 → 2 → 3 → 2 → 4 → 3 → 5 Output: 1 → 2 → 3 → 4 → 5

I use a HashSet<int> named seen. It stores every value that has already been kept in the list.

I also use a dummy node before the real head. The dummy node gives prev a safe starting position before the head. The variable prev points to the last node that remains in the list. The variable curr points to the node currently being checked.

The main invariant is that seen contains exactly the values that have already been kept before curr. prev points to the last kept node.

Create an empty HashSet<int>. Create a dummy node whose Next points to head. Set prev to dummy and curr to head.

At the start, seen is empty because no real node has been processed yet.

Start with 1 → 2 → 3 → 2 → 4 → 3 → 5 and seen = {}.

Step 1: curr is 1. The set does not contain 1. Add 1 to seen. Move prev to node 1. Then move curr to node 2. seen becomes {1}.

Step 2: curr is 2. The set does not contain 2. Add 2. Move prev to node 2. Move curr to node 3. seen becomes {1, 2}.

Step 3: curr is 3. The set does not contain 3. Add 3. Move prev to node 3. Move curr to the next node, which has value 2. seen becomes {1, 2, 3}.

Step 4: curr is the second node with value 2. The set already contains 2. This node is a duplicate. Keep prev on the first 3 and set prev.Next = curr.Next. This bypasses the duplicate 2 without losing the rest of the list. Then move curr forward.

Step 5: curr is 4. The set does not contain 4. Add 4. Move prev to node 4. Move curr forward. seen becomes {1, 2, 3, 4}.

Step 6: curr is the second node with value 3. The set already contains 3. Keep prev on node 4 and set prev.Next = curr.Next. This bypasses the duplicate 3 and reconnects node 4 directly to node 5. Then move curr forward.

Step 7: curr is 5. The set does not contain 5. Add 5 to seen. Move prev to node 5. Then move curr forward. seen becomes {1, 2, 3, 4, 5}.

Step 8: curr becomes null. The loop stops. Return dummy.Next. The final list is 1 → 2 → 3 → 4 → 5.

A value is added to seen only when its first node is kept. If the same value appears again, that later node is bypassed. Because prev stays on the last kept node during duplicate removal, prev.Next can safely reconnect the list to curr.Next. Therefore the first occurrence of every value remains, later duplicates are removed, original order is preserved, and the list stays connected.

The method creates a HashSet<int>, a dummy node, and the prev and curr references. The while loop processes nodes until curr is null. Contains checks whether the current value was seen before. A duplicate is removed with prev.Next = curr.Next. A new value is added to the set and prev moves to curr. curr then advances to curr.Next. Finally, dummy.Next is returned.

HashSet lookup and insertion are O(1) on average, so processing n nodes takes O(n) expected time. The set may contain up to n different values, so auxiliary space is O(n).

An empty list returns null. A one-node list stays unchanged. If every node has a unique value, the list stays unchanged. If every node has the same value, only the first node remains. Negative values and zero work normally because HashSet<int> supports them.

The key idea is to remember which values have already been kept. A HashSet<int> is a good fit because membership checks and insertions are O(1) on average. The invariant is that seen contains the values of all kept nodes before curr, and prev points to the last kept node. When curr has a new value, we add it to seen and move prev to curr. When curr is a duplicate, prev does not move. Instead, prev.Next is changed to curr.Next, which removes the duplicate while preserving the rest of the linked list. This keeps the first occurrence of each value and preserves the original order.

Let n be the number of nodes. We visit each node once. HashSet<int> lookup and insertion are O(1) on average, so the total expected time is O(n). This is expected rather than guaranteed worst-case time because it depends on hash-table behavior. The HashSet may store up to n unique values, so the auxiliary space is O(n). The dummy node and the prev and curr references use only constant extra space.

A common mistake is moving prev when curr is a duplicate. prev must stay on the last kept node so prev.Next can bypass the duplicate. Another mistake is changing the wrong Next reference, which can disconnect part of the list. Candidates may also forget to add a first occurrence to the HashSet, so a later duplicate is not detected. Another error is advancing prev for both branches instead of only for kept nodes. Finally, candidates should not describe the HashSet-based O(n) time as a guaranteed worst-case bound. It is expected O(n) because HashSet operations are O(1) on average.

State the invariant before coding: seen contains the values already kept, prev points to the last kept node, and curr points to the node being checked. Then explain that duplicates are removed by changing prev.Next while prev itself stays in place.

I would scan the lockers in their given order. I skip any locker that is unavailable or smaller than the package. If I find an exact-size locker, I return its id immediately. Otherwise, I keep the fitting locker with the smallest wasted space. If there is a tie, I prefer the smaller locker size, then the smaller id. If nothing fits, I return -1. This takes O(n) time and O(1) auxiliary space.

The function receives a list of lockers and one package size. Each locker has an id, a size, and an availability flag. We only consider lockers that are available and large enough for the package. An exact-size locker is best, so we return it immediately. If there is no exact fit, we choose the locker that leaves the least unused size. If nothing can hold the package, we return -1. This method is simple because one pass is enough and we only keep the current best locker.

1. Should an exact-size locker be returned immediately when it is found?
2. If two non-exact lockers waste the same amount of space, should I use the smaller locker size and then the smaller locker id?
3. Should invalid package sizes, an empty locker array, or no valid fit return -1?

The input is an array of lockers and one package size. A locker has an integer id, an integer size, and a Boolean Available value. The output is the id of the chosen locker. If no locker can be used, the function returns -1.

Start with bestId = -1. This means no locker has been selected yet. Set bestSize and minWasted to very large integer values. These values will be replaced when we find the first usable non-exact locker.

For each locker, first check availability. If it is not available, skip it. Then check size. If the locker is smaller than the package, skip it. If its size exactly matches the package size, return that locker id immediately. Otherwise calculate wasted space as locker.Size - packageSize.

The package size is 7. Locker 1 has size 6, so it cannot fit the package and is skipped. Locker 2 has size 9, so it fits with wasted space 2. It becomes the current best. Locker 3 has size 12 but is unavailable, so it is skipped. Locker 4 has size 10, so its wasted space is 3. That is worse than 2, so locker 2 stays best. Locker 5 has size 8, so its wasted space is 1. That is better than 2, so bestId becomes 5. Locker 6 has size 15, so its wasted space is 8. Locker 5 stays best. The final result is locker id 5.

At every point, bestId represents the best usable non-exact locker seen so far. minWasted stores its wasted space. We replace the best locker only when the new locker wastes less space, or when the tie-break rules prefer it. An exact fit wastes zero, so the algorithm returns immediately when one is found.

The code validates the input first. It then loops through the locker array once. It skips unavailable and too-small lockers. It returns immediately for an exact fit. For larger fitting lockers, it computes wasted space and updates bestId, bestSize, and minWasted when the candidate is better. After the loop, it returns bestId, which is still -1 if no locker fit.

With n lockers, the loop examines each locker at most once, so the time complexity is O(n). The algorithm stores only a few integer variables, so auxiliary space is O(1). Important edge cases are no fitting locker, no available locker, an exact fit, an empty array, and an invalid package size.

Use one linear scan over the locker array. The key rule is to ignore lockers that are unavailable or too small. If an available locker has exactly the package size, return its id immediately. For larger valid lockers, calculate wasted space as locker size minus package size. Keep the candidate with the smallest wasted space. If needed, break ties by smaller locker size and then smaller id. The invariant is that after each processed locker, bestId is the best valid non-exact locker seen so far.

Let n be the number of lockers. We process each locker at most once, so the time complexity is O(n). The function may stop earlier if it finds an exact fit. It uses only bestId, bestSize, minWasted, and a few temporary values. These do not grow with n, so the auxiliary space complexity is O(1).

Common mistakes are forgetting to skip unavailable lockers, allowing a locker that is smaller than the package, comparing the wrong quantity when choosing the best fit, ignoring the stated tie-break rules, continuing after an exact fit even though the shown algorithm returns immediately, and claiming auxiliary space is O(n) even though this implementation stores only constant-size state.

State the selection rule before coding: available and large enough first, exact fit returns immediately, otherwise minimize wasted space and apply the tie-breakers. Then keep that same rule visible in the update condition.

I would build a prefix-sum array of the same size as the input. I copy the first value directly, then move from index 1 to the end. At each index, I add the current array value to the previous prefix sum. This works because each previous prefix sum already contains the total of all earlier values. The algorithm takes O(n) time and uses O(n) space for the separate prefix-sum array.

The input is a one-dimensional integer array. We need to create another array of the same size. Each position in the new array stores the total of all input values from index 0 through that position. For example, the diagram uses arr = [3, -1, 4, 2, -2]. The result is prefixSum = [3, 2, 6, 8, 6]. We can build this result from left to right because the previous prefix sum already contains the total we need for the next calculation.

1. Should I return a new prefix-sum array instead of modifying the input array?
2. Should an empty input array return an empty result?

The input is an integer array arr. The output is another integer array called prefixSum with the same length. For every index i, prefixSum[i] must equal arr[0] + arr[1] + ... + arr[i].

For the diagram example: arr = [3, -1, 4, 2, -2] prefixSum = [3, 2, 6, 8, 6]

The first output value is 3 because it contains only arr[0]. The next output value is 2 because 3 + (-1) = 2.

We process the array from left to right. We store each running total directly in prefixSum. The important idea is that prefixSum[i - 1] already contains the sum of every value from index 0 through index i - 1. Therefore, for i >= 1, we only need to add arr[i].

The recurrence is: prefixSum[i] = prefixSum[i - 1] + arr[i]

This avoids adding all earlier values again for every position.

Let n be arr.Length. Create prefixSum with n elements. If n is 0, return the empty prefixSum array. Otherwise, set prefixSum[0] = arr[0].

For the example, prefixSum[0] = 3. This is correct because the sum from index 0 through index 0 is simply 3.

At index 0, arr[0] is 3. We set prefixSum[0] to 3.

At index 1, arr[1] is -1. The previous running total is 3. We calculate 3 + (-1) = 2, so prefixSum[1] becomes 2.

At index 2, arr[2] is 4. The previous running total is 2. We calculate 2 + 4 = 6, so prefixSum[2] becomes 6.

At index 3, arr[3] is 2. The previous running total is 6. We calculate 6 + 2 = 8, so prefixSum[3] becomes 8.

At index 4, arr[4] is -2. The previous running total is 8. We calculate 8 + (-2) = 6, so prefixSum[4] becomes 6.

After the last index is processed, the final result is [3, 2, 6, 8, 6].

The invariant is that after processing index i, prefixSum[i] contains the sum of arr[0] through arr[i]. The first position is correct because prefixSum[0] equals arr[0]. For every later position, we take the already-correct sum through index i - 1 and add arr[i]. Therefore every output position contains the required prefix sum.

The code first creates the result array. It handles an empty array by returning that empty result. It copies arr[0] into prefixSum[0]. Then a for loop starts at index 1. Each iteration calculates prefixSum[i] from prefixSum[i - 1] and arr[i]. After the loop finishes, the code returns prefixSum.

The loop processes each element once, so the time complexity is O(n). The separate prefixSum result contains n integers, so the space used for the result is O(n). An empty array returns an empty result. A one-element array returns that one value. Positive, negative, and zero values all work with the same calculation.

The key insight is to reuse the running total that has already been calculated. After index i - 1 is processed, prefixSum[i - 1] equals arr[0] + arr[1] + ... + arr[i - 1]. To calculate the next position, we only add arr[i]. Therefore prefixSum[i] = prefixSum[i - 1] + arr[i]. The central invariant is that each completed prefixSum position stores the exact sum of the input values from index 0 through that position. This gives a simple left-to-right O(n) solution.

Let n be the number of elements in arr. The time complexity is O(n) because we move through the array once and perform one addition for each position after the first. The diagram counts the separate prefixSum result array as O(n) space because it contains n integers. Apart from that returned array, the algorithm uses only a few local variables.

A common mistake is starting the loop at index 0 and then trying to read prefixSum[i - 1], which would use an invalid index. Another mistake is forgetting to initialize prefixSum[0] with arr[0]. Candidates may also recalculate arr[0] through arr[i] for every output position, which makes the solution unnecessarily slow. Another mistake is assuming negative values need special handling. They do not. It is also important to handle an empty array before accessing arr[0] and to account for the O(n) space of the separate result array.

Explain the invariant before writing the loop: prefixSum[i - 1] already contains the total through the previous index, so the next value needs only one addition. Then trace one or two positions from the example before coding.

I would use one greedy pass. I keep a total balance to check whether the full circuit is possible, and a tank balance for the current candidate start. At each station, I add gas[i] - cost[i]. If tank becomes negative, no station in that failed segment can be a valid start, so I move start to i + 1 and reset tank. At the end, I return start if total is non-negative, otherwise -1. This takes O(n) time and O(1) auxiliary space.

We have gas stations arranged in a circle. Each station gives us some gas, and moving to the next station costs some gas. We start with an empty tank. We need to find a station where we can start, travel clockwise around the whole circle, and return to the same place. The main idea is to keep track of the gas balance while moving forward. If that balance becomes negative, the current starting area cannot work. We also track the total balance to know whether the full trip is possible.

1. Can I assume gas and cost have the same length?
2. Should I return -1 when the total gas is less than the total cost?
3. If more than one starting station works, is returning any valid starting index acceptable?

The input is two integer arrays, gas and cost. gas[i] is the gas available at station i. cost[i] is the gas needed to travel from station i to the next station. We start with an empty tank. We must return a valid starting station index that lets us complete one clockwise circuit. If no starting station works, we return -1.

For each station, I calculate diff = gas[i] - cost[i]. I keep two balances. total is the net gas across all stations. tank is the gas balance from the current candidate start. The key rule is that if tank becomes negative at station i, no station from the current candidate start through i can be a valid start. Therefore, the next candidate becomes i + 1.

I start with total = 0, tank = 0, and start = 0. total will tell me whether the complete circuit has enough gas. tank tells me whether the current candidate start can continue. start stores the current candidate index.

The diagram uses gas = [1, 2, 3, 4, 5] and cost = [3, 4, 5, 1, 2].

At index 0, diff = 1 - 3 = -2. total becomes -2 and tank becomes -2. Since tank is negative, start becomes 1 and tank resets to 0.

At index 1, diff = 2 - 4 = -2. total becomes -4 and tank becomes -2. Since tank is negative, start becomes 2 and tank resets to 0.

At index 2, diff = 3 - 5 = -2. total becomes -6 and tank becomes -2. Since tank is negative, start becomes 3 and tank resets to 0.

At index 3, diff = 4 - 1 = 3. total becomes -3 and tank becomes 3. tank is not negative, so start stays 3.

At index 4, diff = 5 - 2 = 3. total becomes 0 and tank becomes 6. tank remains non-negative. The final total is 0, so a solution exists. We return start = 3. Starting at index 3 gives the route 3 -> 4 -> 0 -> 1 -> 2 -> back to 3.

If tank becomes negative at station i, the current candidate cannot reach station i + 1. No station in that failed segment can be a valid start, so it is safe to skip the whole segment and try i + 1. The variable total contains the sum of every gas[i] - cost[i]. If total is negative, all stations together do not provide enough gas to pay all travel costs, so no starting station can complete the circuit. If total is non-negative, the final candidate start is valid.

The loop processes the stations from index 0 to n - 1. At each station, it calculates diff, adds diff to total, and adds diff to tank. If tank becomes negative, the code sets start = i + 1 and resets tank to 0. After the loop, total decides whether the full circuit is possible. If total is non-negative, the method returns start. Otherwise, it returns -1.

The algorithm takes O(n) time because each station is processed once. It uses O(1) auxiliary space because it keeps only a few variables. For one station, index 0 works when gas[0] is at least cost[0]. If all values are zero, index 0 is valid. If total gas is less than total cost, the answer is -1. If input values can make the running totals exceed the range of int, the balance variables can be changed to long without changing the algorithm.

The solution uses a greedy running-balance idea. For each station, compute gas[i] - cost[i]. The variable tank represents the balance from the current candidate start. The invariant is that while tank is non-negative, the current candidate can reach the next processed station. If tank becomes negative at station i, no station from the current candidate start through i can be a valid start, so the next candidate is i + 1 and tank resets to zero. The separate variable total checks global feasibility. If total is negative, no starting station can complete the circuit. If total is non-negative, the final candidate start is valid.

Time complexity is O(n), where n is the number of gas stations. The loop visits each station once and does constant work at each station. Auxiliary space is O(1). Auxiliary space means extra memory used by the algorithm. Only total, tank, start, diff, and the loop index are stored, so the extra memory does not grow with n.

A common mistake is resetting the candidate start without resetting tank to zero. Another mistake is tracking only tank and forgetting total, which is needed to detect when the whole circuit is impossible. Some candidates return a gas value instead of the required station index. Another mistake is testing every possible starting station separately, which can take O(n^2) time. It is also incorrect to claim that the returned start must be the only valid start, because the question only asks for a valid starting index.

Explain total and tank as two separate jobs. tank decides when the current candidate start has failed. total decides whether the complete circuit is possible at all. This makes the greedy proof much easier to explain.

I would keep the lowest stock price from an earlier day and the best profit found so far. I initialize minPrice with prices[0], then start from Day 1 so the buy day is always before the sell day. For each day, I calculate prices[i] - minPrice, update maxProfit, and then update minPrice for future days. If no positive profit exists, maxProfit stays 0. This takes O(n) time and O(1) auxiliary space.

We have an array of stock prices, where each position represents one day. We may buy the stock once and sell it once on a later day. We want the largest positive difference between a later price and an earlier price. If every valid transaction would lose money or make no money, we return 0. The solution makes one left-to-right pass. It remembers the lowest price from an earlier day and the best valid profit found so far.

1. Should I return only the maximum profit, not the buy and sell indices?
2. If the array is empty or contains only one day, should I return 0?
3. Is only one buy followed by one later sell allowed?

The input is an integer array named prices. prices[i] is the stock price on Day i. We return one integer: the maximum profit from buying on one day and selling on a different later day. We do not return the day indices or the prices. If no positive profit is possible, we return 0.

We scan the prices from left to right. Before evaluating Day i as a possible sell day, minPrice is the lowest price among the earlier days 0 through i - 1. This is the central invariant. It guarantees that the buy day is always before the sell day. maxProfit stores the best valid profit found so far.

If prices is null or contains fewer than two values, we return 0 because we cannot make a valid buy followed by a later sell. Otherwise, we set minPrice = prices[0] and maxProfit = 0. Day 0 is only used for initialization. We start evaluating possible sell days at Day 1.

The diagram uses prices = [7, 1, 5, 3, 6, 4]. We start with minPrice = 7 and maxProfit = 0.

Day 0 is initialization only. No sell transaction is evaluated.

Day 1 has price 1. Before this day, minPrice is 7. The possible profit is 1 - 7 = -6. maxProfit stays 0. Then minPrice becomes 1 for future days.

Day 2 has price 5. The possible profit is 5 - 1 = 4. maxProfit becomes 4. minPrice stays 1.

Day 3 has price 3. The possible profit is 3 - 1 = 2. maxProfit stays 4. minPrice stays 1.

Day 4 has price 6. The possible profit is 6 - 1 = 5. maxProfit becomes 5. minPrice stays 1.

Day 5 has price 4. The possible profit is 4 - 1 = 3. maxProfit stays 5. minPrice stays 1.

The final answer is

5. The best transaction shown in the diagram is to buy on Day 1 at price 1 and sell on Day 4 at price
6. The profit is 6 - 1 = 5.

Before each sell day is evaluated, minPrice contains only a price from an earlier day. Therefore, every calculated transaction buys before it sells. For each possible sell day, minPrice gives the cheapest valid earlier buy price, so prices[i] - minPrice is the best profit that can end on that sell day. maxProfit keeps the largest of these valid profits. After the final day, maxProfit is therefore the maximum valid single-transaction profit.

The code first handles null input and arrays with fewer than two prices. It initializes minPrice from prices[0] and maxProfit to

1. The loop starts at index
2. On each iteration, it first calculates profit using the earlier minPrice. It then updates maxProfit. Only after evaluating the current day as a sell day does it update minPrice so the current price can be considered as a buy price for future days. Finally, it returns maxProfit.

The algorithm processes each price after Day 0 once, so the time complexity is O(n). It stores only a few integer variables, so the auxiliary space complexity is O(1). Empty input and one-day input return 0. Strictly decreasing prices return 0. Equal prices return 0. With increasing prices, the first price remains the minimum and later prices are evaluated as possible sell prices.

The key idea is to remember the lowest price from an earlier day instead of comparing every pair of days. Before evaluating Day i, minPrice is the smallest price among Days 0 through i - 1. We calculate the best profit that can end on Day i as prices[i] - minPrice. maxProfit stores the largest valid profit seen so far. After evaluating the current sell opportunity, we update minPrice with prices[i] so the current day can become a possible buy day for a future sell. This processing order preserves the rule that the buy day must be earlier than the sell day.

Let n be the number of prices. The time complexity is O(n) because the algorithm makes one left-to-right pass through the array, starting at Day 1. Each iteration performs only constant-time arithmetic and comparisons. The auxiliary space complexity is O(1) because the algorithm stores only a few integers such as minPrice, maxProfit, profit, and the loop index. The amount of extra memory does not grow with n.

A common mistake is using two nested loops and getting O(n^2) time when a running minimum is enough. Another mistake is treating Day 0 as a valid sell day even though no earlier buy day exists. Candidates may also update minPrice before calculating the current day's profit, which breaks the stated invariant that the sell calculation uses an earlier-day minimum, even though the final numeric answer may still happen to remain correct for this particular return contract. Another mistake is returning a negative profit for decreasing prices instead of 0. Candidates should also avoid confusing stock prices with day indices.

State the invariant before writing the loop: before Day i is evaluated as a sell day, minPrice is the lowest price from earlier days only. Then keep the code in the same order as the diagram: calculate profit, update maxProfit, and finally update minPrice for future days.