34 Amazon Java Developer Interview Questions & Answers

I would use a HashMap to count how many times each character appears in the source string. Then I would scan the target from left to right. For each target character, I check its remaining count. If the count is zero, I return false immediately. Otherwise, I decrease the count by one. If every target character is processed, I return true. This takes O(s + t) expected time and O(k) auxiliary space.

The problem gives me a source string and a target word. I need to decide whether the source has enough copies of every letter needed by the target. A letter may appear more than once, so I must count how many copies are available. For example, target "apple" needs two p characters. The source "appple" has three p characters, so it has enough. I can store these counts and reduce them as I use letters from the target.

1. Should character matching be case-sensitive?
2. Can I assume both strings are non-null?
3. Should repeated characters in the target require the same number of copies in the source?

The input is two strings: source and target. I return true when source contains every character needed by target with enough frequency. Otherwise, I return false. I am checking character counts, not positions or substrings.

For the diagram example, source is "appple" and target is "apple". The expected result is true.

The source characters by index are 0:a, 1:p, 2:p, 3:p, 4:l, 5:e. The target characters are 0:a, 1:p, 2:p, 3:l, 4:e.

I use a HashMap<Character, Integer>. Each key is a character. Each value is the number of unused copies of that character that are still available from source.

I first count all source characters. Then I scan target. For each target character, I check its count in the map. If the count is zero or the character is missing, the target cannot be built. Otherwise, I consume one copy by decreasing the count.

The main invariant is simple: before each target step, the map stores exactly how many unused copies of every source character are still available.

The map starts empty. I scan source from index 0 to the end.

For source "appple", the map changes like this: S0 reads a: {} becomes {a:1}. S1 reads p: {a:1} becomes {a:1, p:1}. S2 reads p: {a:1, p:1} becomes {a:1, p:2}. S3 reads p: {a:1, p:2} becomes {a:1, p:3}. S4 reads l: {a:1, p:3} becomes {a:1, p:3, l:1}. S5 reads e: {a:1, p:3, l:1} becomes {a:1, p:3, l:1, e:1}.

Now the map is the complete inventory of available characters.

I now scan target "apple" from left to right.

At T0, the current character is a. The map is {a:1, p:3, l:1, e:1}. The count for a is 1, so I use one a. The map becomes {a:0, p:3, l:1, e:1}. Processing continues.

At T1, the current character is p. The count for p is 3. I use one p. The map becomes {a:0, p:2, l:1, e:1}.

At T2, the current character is p again. The count for p is still 2 before the update, so the second p is valid. I decrease it to 1. The map becomes {a:0, p:1, l:1, e:1}.

At T3, the current character is l. Its count is 1. I decrease it to 0. The map becomes {a:0, p:1, l:0, e:1}.

At T4, the current character is e. Its count is 1. I decrease it to 0. The map becomes {a:0, p:1, l:0, e:0}.

All five target characters were matched, so the method returns true.

Before every target step, the map tells me how many unused copies of each source character remain. Every successful match consumes exactly one required copy. If a needed character has count 0, there is no unused copy left, so building the target is impossible. If I finish the target without failing, every required character has been matched. Therefore, returning true is correct.

The method first handles two simple cases. An empty target returns true. If source is shorter than target, it returns false because source cannot provide enough total characters.

Next, the first loop builds the frequency map from source. The second loop reads each target character. It gets the remaining count with getOrDefault. If that value is 0, it returns false immediately. Otherwise, it stores remaining minus one. If the loop completes, it returns true.

Let s be source.length() and t be target.length(). Building the map processes source once. Checking the target processes each target character at most once. Java HashMap lookup and insertion are O(1) on average, so the expected time is O(s + t).

The map stores one entry for each distinct source character. If k is the number of distinct characters in source, the auxiliary space is O(k).

Important edge cases are an empty target, a source shorter than the target, repeated characters, a missing character, and extra source characters. Extra characters do not hurt because they can simply remain unused.

The key idea is to treat the source string as an inventory of available characters. A HashMap stores character -> remaining count. I first count every source character. Then I consume one count for every character required by target. The invariant is that before each target step, the map contains exactly the unused copies still available from source. If a required count is 0, the answer is false. If every target character is consumed, the answer is true. This fits repeated characters correctly because it checks frequency, not only presence.

Let s be the length of source and t be the length of target. We process source once to build the frequency map. We then process target at most once and may stop early if a needed character is unavailable. HashMap lookup and insertion are O(1) on average, so the expected time is O(s + t). If k is the number of distinct characters stored from source, the extra memory is O(k). This is auxiliary space, meaning memory used in addition to the input.

A common mistake is checking only whether each character exists in source. That fails when frequency matters. For example, "aple" contains p, but it does not contain the two p copies required by "apple". Another mistake is forgetting to decrement a character's count after using it. Candidates may also build the frequency map from target instead of source even though the diagram's algorithm stores the remaining source inventory. Another mistake is continuing after a required count is 0 instead of returning false immediately. Finally, do not claim guaranteed O(s + t) time because Java HashMap lookup and insertion are O(1) on average.

State the map meaning before you code: character -> unused copies remaining in source. Then explain that each target character consumes one copy. This makes repeated-character handling and the correctness invariant easy to follow.

I would use a prefix balance and a hash map. I treat each letter as +1 and each digit as -1. The map stores each balance and the earliest index where it appeared. If the same balance appears again, the substring between those positions has equal letters and digits. I scan from left to right and keep the longest such substring. This gives O(n) expected time because HashMap operations are O(1) on average, with O(n) auxiliary space.

The input is a string containing letters and digits. We need to return the longest continuous part of the string where the number of letters equals the number of digits. For the example "A1BC23D4E", the answer is "A1BC23D4". It contains four letters and four digits. The main idea is to keep a running balance. A letter adds one and a digit subtracts one. When the same balance appears at two positions, the substring between those positions is balanced. A hash map remembers the earliest position for each balance.

1. Can I assume the input contains only alphabetic characters and digits?
2. If several longest balanced substrings have the same length, should I keep the earliest one?

The input is a string. The output is the longest contiguous substring with the same number of letters and digits. Contiguous means the characters must stay next to each other in the original string. For the example "A1BC23D4E", the result is "A1BC23D4", which covers indices 0 through 7.

I keep a running value called balance. A letter changes balance by +1. A digit changes it by -1. I also use a HashMap named firstSeen. It stores balance -> earliest index. The key idea is that if the same balance appears at two positions, the substring between them has a net balance of zero. That means it contains equal numbers of letters and digits.

Before reading any character, balance is 0. I put 0 -> -1 into firstSeen. This represents a zero balance before the string starts. I also set bestStart = 0 and maxLen = 0. Storing index -1 is important because it lets a balanced substring starting at index 0 be measured correctly.

For s = "A1BC23D4E": At i = 0, 'A' is a letter, so balance becomes 1. Balance 1 is new, so store 1 -> 0. At i = 1, '1' is a digit, so balance returns to 0. Balance 0 was first seen at -1. The length is 1 - (-1) = 2, so the best substring becomes "A1". At i = 2, 'B' makes balance 1. It was first seen at 0. The candidate length is 2, so the current best stays "A1". At i = 3, 'C' makes balance 2. It is new, so store 2 -> 3. At i = 4, '2' makes balance 1. Balance 1 was first seen at 0. The candidate length is 4, so the best becomes "1BC2". At i = 5, '3' makes balance 0. Balance 0 was first seen at -1. The candidate length is 6, so the best becomes "A1BC23". At i = 6, 'D' makes balance 1. The candidate length is 6. This ties the current best, so no update is made. At i = 7, '4' makes balance 0. The candidate length is 8, so the best becomes "A1BC23D4". At i = 8, 'E' makes balance 1. The candidate length is 8. This is another tie, so the earlier answer remains. The final result is "A1BC23D4".

Balance means letters minus digits. If the balance has the same value at two positions, the change in balance between those positions is zero. Therefore, that substring added the same number of +1 values as -1 values, so it contains the same number of letters and digits. Keeping the earliest index for every balance gives the longest possible candidate ending at the current position. Taking the longest candidate over the whole scan gives the global longest balanced substring.

The Java code creates firstSeen and starts it with 0 -> -1. It scans the string from left to right. Character.isLetter tells us whether to add 1 or subtract 1. If the current balance already exists in the map, the code gets the earliest index prev and calculates len = i - prev. If len is larger than maxLen, it updates maxLen and bestStart. If the balance is new, the code stores the current index. After the loop, it returns s.substring(bestStart, bestStart + maxLen).

The expected time is O(n). Each character is processed once, and Java HashMap lookup and insertion are O(1) on average, with hashing and collision caveats. The auxiliary space is O(n) because the map can store many different balance values. For an empty string, one character, all letters, or all digits, the returned substring is empty. If several longest answers tie, this code keeps the earliest one because it updates only when len > maxLen.

The key insight is to convert the problem into a prefix-balance problem. Define balance as letters minus digits. Each letter contributes +1 and each digit contributes -1. If the balance at index i is the same as it was at an earlier index prev, then the net balance from prev + 1 through i is zero. Therefore, that substring contains equal numbers of letters and digits. The HashMap stores balance -> earliest index. Keeping only the earliest index is important because it creates the longest possible candidate when that balance appears again. The invariant is that every map entry stores the earliest index where its prefix balance occurred.

Let n be the number of characters in the string. The expected time is O(n). We process each character once. For each character, we do a HashMap lookup and sometimes an insertion. Java HashMap lookup and insertion are O(1) on average, although hashing and collisions mean this is an expected-time statement rather than a guaranteed worst-case bound. The auxiliary space is O(n) because firstSeen may store a different balance for many positions.

A common mistake is treating this as a subsequence problem. The answer must be a contiguous substring. Another mistake is storing the latest index for a balance instead of the earliest one, which can lose a longer answer. Candidates may also forget the initial map entry 0 -> -1, which is needed for balanced substrings starting at index 0. Another error is updating on len >= maxLen when the intended behavior is to keep the earliest longest substring. Finally, do not claim guaranteed O(n) time. HashMap operations are O(1) on average, so the overall bound is O(n) expected time.

State the invariant before writing code: firstSeen stores the earliest index for every prefix balance, and seeing the same balance again means the characters between those positions contain equal numbers of letters and digits. Then implement that invariant directly.

I would use a HashSet to remember numbers I have already seen. I scan the list from left to right. For each value, I first check whether it is already in the set. If it is, that value is the duplicate, so I return it immediately. Otherwise, I add it to the set and continue. I process each item at most once. This takes O(n) expected time and O(n) auxiliary space.

The input is a list of numbers where one value appears more than once and the other values are unique. The goal is to return the repeated value, not its index. I can remember every value already processed. When I reach a value that I have seen before, I know that value is the duplicate. A HashSet is a good fit because it can usually check and store a value in constant time on average. The algorithm also stops as soon as the repeated value is found.

1. Is exactly one repeated value guaranteed?
2. Should I return the repeated value itself rather than its index?
3. Can the input contain negative numbers or zero?

The input is a list of numbers. All numbers except one are unique. I need to return the repeated value itself. For the example [4, 1, 7, 1, 9], the correct result is 1 because 1 appears more than once.

I use a HashSet<Integer> named seen. The set stores values from positions I have already processed. The main invariant is simple: before checking the current number, seen contains only values from earlier positions. If the current value is already in seen, that value must have appeared before, so it is the repeated value.

At the start, the array is [4, 1, 7, 1, 9]. The indices are [0, 1, 2, 3, 4]. The set is empty: {}. Traversal begins at index 0 and moves from left to right.

At index 0, the current value is 4. The set is {}. 4 is not present, so I add it. The set becomes {4} and processing continues.

At index 1, the current value is 1. The set is {4}. 1 is not present, so I add it. The set becomes {4, 1}.

At index 2, the current value is 7. The set is {4, 1}. 7 is not present, so I add it. The set becomes {4, 1, 7}.

At index 3, the current value is 1. The set is {4, 1, 7}. This time, 1 is already present. That proves 1 appeared earlier, so I return 1 and stop immediately. Index 4, whose value is 9, is not processed.

The set contains only values from earlier positions. Therefore, when the current value is already in the set, that same value has appeared before. Since the problem asks for the repeated value, returning it is correct. We process each element at most once and stop when the valid result is found.

The Java method creates an empty HashSet<Integer>. It loops through the array from left to right. For each number, it checks seen.contains(num) before inserting the number. If the lookup succeeds, the method returns that number immediately. Otherwise, it adds the number to the set. A defensive -1 return remains after the loop, but it is not the expected path because the stated problem guarantees a repeated value.

HashSet lookup and insertion are O(1) on average. Because the input is processed at most once, the overall expected time is O(n). The set can store up to O(n) values, so auxiliary space is O(n). An early duplicate returns sooner. A value repeated more than twice is detected on its second occurrence. Negative numbers and zero work normally with HashSet.

The key idea is to remember values that appeared earlier. Use a HashSet named seen. Before adding the current value, check whether it is already in the set. If it is present, the value has appeared before, so it is the duplicate and can be returned immediately. If it is not present, add it and continue. The invariant is that seen contains only values from earlier positions. This gives fast average lookup without needing a slower repeated comparison against earlier elements.

Let n be the number of input values. We process the input at most once. A Java HashSet lookup and insertion are O(1) on average, so the overall expected time is O(n). This is expected time rather than a guaranteed worst-case hashing bound. The HashSet can hold up to n values in the worst case before the duplicate is found, so the auxiliary space is O(n).

A common mistake is returning an index instead of the repeated value, because this question asks for the value itself. Another mistake is changing the lookup and insertion logic in a way that no longer matches the explained invariant. Candidates may also continue processing after the duplicate has been found instead of returning immediately. Another common error is claiming guaranteed O(n) time instead of O(n) expected time for a HashSet-based solution. Finally, do not describe the last value 9 as processed in the example because the algorithm stops at the second 1.

State the invariant early: before checking the current number, the HashSet contains only values from earlier positions. Then explain that a successful membership check proves the current value is repeated and allows an immediate return.

I would scan the list from left to right and keep a HashSet of values I have already seen. For each value, I first check the set. If the value is already there, I return it immediately because it is a duplicate. Otherwise, I add it and continue. I process each item at most once and stop when the answer is found. This takes O(n) expected time and O(n) auxiliary space.

The input is a list of integers, and the goal is to return a value that appears more than once. I read the numbers from left to right and remember each earlier value. Before saving the current value, I check whether I have already seen it. If I have, that value is duplicated, so I return it immediately. This avoids comparing every number with every other number. The tradeoff is that we use extra memory to get faster expected running time.

1. Is a duplicate guaranteed to exist, or should I return a fallback value when there is none?
2. If several values are duplicated, should I return the first repeated value detected during a left-to-right scan?
3. Am I allowed to use O(n) extra memory for a HashSet?

The input is a list of integer values. The output is a duplicated value, not an index. In the diagram, the example is nums = [4, 1, 3, 2, 3, 5]. The returned value is 3. The implementation also has a defensive fallback of -1 if the scan finishes without finding a duplicate.

I use a HashSet<Integer> named seen. A set stores unique values. Here, seen represents the distinct values from positions that have already been processed. Before each step, this is the main invariant: seen contains exactly the distinct values from the already processed part of the list. A HashSet is useful because lookup and insertion are O(1) on average.

At the beginning, seen is empty: { }. Traversal starts at index 0. No values have been processed yet, so the empty set correctly represents the initial state.

The example is [4, 1, 3, 2, 3, 5].

At index 0, the current value is 4. seen is { }. The check 4 in seen is false. I add 4. seen becomes {4}, and processing continues.

At index 1, the current value is 1. seen is {4}. The check 1 in seen is false. I add 1. seen becomes {4, 1}, and processing continues.

At index 2, the current value is 3. seen is {4, 1}. The check 3 in seen is false. I add 3. seen becomes {4, 1, 3}, and processing continues.

At index 3, the current value is 2. seen is {4, 1, 3}. The check 2 in seen is false. I add 2. seen becomes {4, 1, 3, 2}, and processing continues.

At index 4, the current value is 3. seen is {4, 1, 3, 2}. The check 3 in seen is true. This proves that 3 appeared earlier, so the algorithm stops and returns 3. The value 3 appears at indices 2 and 4. Five of the six elements were processed. Index 5, whose value is 5, is not processed because the method has already returned.

Before each iteration, seen contains all distinct values from earlier processed positions. If the current value is already in seen, it must have occurred at an earlier position, so it is a duplicate. If the value is not present, adding it keeps the invariant true for the next iteration. Therefore, returning 3 when the second 3 is reached is correct.

The Java method creates a HashSet<Integer>. It uses a for-each loop to read values from left to right. For each value, it calls seen.contains(value) before insertion. If that lookup succeeds, it returns the value immediately. Otherwise, seen.add(value) stores it for later checks. If the loop finishes without finding a duplicate, the implementation returns -1 as a defensive fallback.

HashSet lookup and insertion are O(1) on average, so processing at most n values gives O(n) expected time. The set can hold up to O(n) distinct values, so auxiliary space is O(n). Relevant cases include a duplicate near the beginning, negative values, zero, and all values being the same. If the input is empty or contains no duplicate, this implementation reaches the defensive fallback and returns -1.

The key idea is to remember values that appeared earlier. Use a HashSet<Integer> called seen. Before processing each value, seen contains exactly the distinct values from the already processed positions. Check the current value before inserting it. If seen already contains it, the same value must have appeared earlier, so it is a duplicate and can be returned immediately. Otherwise, add it and continue. This avoids comparing each value with every other value. The tradeoff is extra O(n) memory in exchange for O(n) expected time.

Let n be the number of values in the list. We process the input at most once. Java HashSet lookup and insertion are O(1) on average, with hashing and collision caveats. Therefore, the overall expected time is O(n). The set may store up to n distinct values, so the auxiliary space is O(n). This is the standard optimal expected-time approach for this general solution. The extra memory used by the set is the main tradeoff.

A common mistake is inserting the current value before checking whether it was already present. The correct order is lookup first, then insertion only when the value is new. Another mistake is returning an index even though this problem asks for the duplicated value. Candidates may also continue processing values after the duplicate has already been found instead of returning immediately. Another error is claiming guaranteed O(n) time rather than O(n) expected time for the hash-based approach. Finally, do not claim O(1) auxiliary space because the HashSet can grow with the input.

State the invariant before you code: the HashSet contains only distinct values from earlier processed positions. Then say that you check the current value before inserting it. This makes the duplicate logic and the early return easy to justify.

I would sort the tasks by arrival time while keeping each original index. Then I would use a min heap for all tasks that have already arrived. The heap orders tasks by processing time, then by original index for ties. If the heap is empty, I jump the clock to the next arrival. I repeatedly run the heap's smallest task and advance the clock. The time complexity is O(n log n), and the auxiliary space is O(n).

Each task has an arrival time and a processing time. We have one CPU, so only one task can run at a time. When the CPU becomes free, we choose the shortest task that has already arrived. If two available tasks have the same processing time, we choose the smaller original index. If no task is available, we move the clock directly to the next arrival. The goal is to return the original task indices in the order that the CPU runs them.

1. Should ties in processing time be broken by the smaller original task index?
2. If no task is available, should the CPU stay idle until the next arrival, allowing us to jump the clock directly to that arrival time?
3. Should the returned array contain original task indices rather than the task values?

Each input task is [arrivalTime, processingTime]. I add its original index so each record becomes [arrival, processing, index]. The output is the order of those original indices. For the diagram example, the input is [[1,2],[2,4],[3,2],[4,1]], and the returned order is [0, 2, 3, 1].

First, sort the task records by arrival time. This lets us add newly available tasks in order without repeatedly searching the full input. Keep a Java PriorityQueue as a min heap. The heap contains tasks that have arrived but are not finished. It orders them first by smaller processing time and then by smaller original index. The key invariant is that before choosing the next task, the heap contains exactly the tasks that have arrived and have not yet been processed.

Start with currentTime = 0, i = 0, an empty min heap, and an empty result array. The variable i points to the next task in arrival-sorted order. The heap is empty because no task has been added yet.

At time 0, the heap is empty and the next task arrives at time 1. We jump currentTime to 1. T0 is now available, so we push it into the heap. T0 has processing time 2 and index 0. We pop T0, append index 0, and advance time to 3. The result is [0].

At time 3, T1 and T2 have both arrived. T1 has processing time 4 and index 1. T2 has processing time 2 and index 2. Both are pushed into the heap. T2 is at the top because processing time 2 is smaller than 4. We run T2, advance time from 3 to 5, and the result becomes [0, 2].

At time 5, T3 has arrived. T1 is still waiting. T3 has processing time 1, so the heap chooses T3 before T1. We run T3, advance time from 5 to 6, and the result becomes [0, 2, 3].

At time 6, only T1 remains. We run it for 4 units, so time becomes 10. The final result is [0, 2, 3, 1].

Tasks are inserted into the heap as soon as their arrival time is less than or equal to currentTime. Therefore, the heap contains exactly the runnable tasks when we make each scheduling decision. The heap exposes the smallest processing time. Its comparator uses the smaller original index when processing times are equal. This matches the scheduling rule at every decision point.

The code first copies every task into a three-value record containing arrival time, processing time, and original index. It sorts those records by arrival time. The PriorityQueue comparator uses processing time first and index second. The main loop continues until every task has been added and the heap is empty. When the heap is empty, the code jumps currentTime to the next arrival. It then pushes every task that has arrived, polls the next task, stores its original index, and adds its processing time to the clock.

Sorting takes O(n log n). Every task enters the heap once and leaves the heap once. Those heap operations take O(n log n) in total. The auxiliary space is O(n). Important cases are several tasks arriving at the same time, equal processing times, an idle gap before the next arrival, and an input containing only one task.

The key idea is to separate task availability from task selection. Sorting by arrival time tells us when tasks become available. The min heap tells us which available task should run next. Each stored task record keeps [arrivalTime, processingTime, originalIndex], while the heap comparator orders records by processing time and then original index. The central invariant is: before each task is chosen, the heap contains exactly the tasks that have arrived and have not yet been processed. Because the heap exposes the shortest eligible task and uses the required tie-breaker, every scheduling decision follows the required rule.

Let n be the number of tasks. Sorting the tasks by arrival time costs O(n log n). Each task is pushed into the min heap once and popped once. A heap push or pop costs O(log n), so all heap work is O(n log n). The total time is O(n log n). Auxiliary space is O(n) because the indexed task records and the heap can both grow with the number of tasks.

A common mistake is sorting tasks without keeping their original indices, which makes the returned order wrong. Another mistake is adding future tasks to the heap before their arrival time. Candidates also forget to jump currentTime when the heap is empty. The heap comparator must use processing time first and original index second. Another common error is using only heap complexity and forgetting that sorting also costs O(n log n).

State the heap invariant before writing code: the min heap contains exactly the tasks that have arrived but have not been processed. Then explain that sorting controls when tasks enter the heap, while the comparator controls which available task leaves next.

I would use reservoir sampling with a reservoir of size 10. I first copy the first 10 items into it. For each later item at index i, I draw a random j from 0 through i. If j is less than 10, I replace reservoir[j] with the current item. This keeps every processed position equally likely to remain in the sample. It uses O(n) expected time and O(k) auxiliary space, where k is 10.

We have 10,000 items and need to choose 10 of them fairly. Every input position must have the same chance of appearing in the final sample. We do not need to shuffle the whole list. Reservoir sampling keeps only k selected items while moving through the input from left to right. We first fill the reservoir. Then every later item gets a fair chance to replace one of those k items. This gives the required uniform sample with only k extra storage.

1. Should I return the selected values rather than their original indices?
2. Can I assume the input contains at least 10 items?
3. Is a uniformly random sample without replacement the expected result?

The input contains 10,000 items. The output must contain 10 selected items. Every input position must have the same probability of being included. In the full problem, that probability is 10/10000 = 1/1000 = 0.1%.

The diagram uses a smaller example so every step is visible. The example is [A, B, C, D, E, F, G, H] with k = 3. One valid random execution returns [E, D, H]. Every one of the eight input positions has final inclusion probability 3/8.

I use reservoir sampling. The reservoir is a list that stores the current sample of size k. In the real problem, k = 10. In the example, k = 3.

The central invariant is: after processing index i, the reservoir is a uniform random sample of size k from items[0..i]. This means every processed position has probability k/(i+1) of being in the reservoir.

For the example, k = 3. I copy the first three items into the reservoir, so the starting state is [A, B, C]. Traversal then starts at index 3, which contains D.

For the full problem, I copy the first 10 items into the reservoir and begin processing later items at index 10.

At index 3, the current item is D. The fixed random draw is j = 1. The reservoir before the step is [A, B, C]. Since 1 < 3, D replaces slot 1. The reservoir becomes [A, D, C].

At index 4, the current item is E. The fixed random draw is j = 0. The reservoir before the step is [A, D, C]. Since 0 < 3, E replaces slot 0. The reservoir becomes [E, D, C].

At index 5, the current item is F. The fixed random draw is j = 4. Since 4 >= 3, F is skipped. The reservoir stays [E, D, C].

At index 6, the current item is G. The fixed random draw is j = 6. Since 6 >= 3, G is skipped. The reservoir stays [E, D, C].

At index 7, the current item is H. The fixed random draw is j = 2. Since 2 < 3, H replaces slot 2. The reservoir becomes [E, D, H].

All items have now been processed. The returned sample is [E, D, H]. This is one valid uniformly sampled result, not the only possible result.

When processing index i, j is chosen uniformly from 0 through i. Therefore, the new item enters the reservoir exactly when j < k, which happens with probability k/(i+1).

If the new item enters, j also chooses one of the k reservoir slots uniformly. This replacement probability reduces the survival probability of each earlier item by exactly the right amount. By induction, after every processed index, each processed position has the same probability k/(i+1) of being in the reservoir.

The Java implementation validates the input, creates an ArrayList reservoir, and copies the first k items into it. It then processes each later index i. For the normal method, ThreadLocalRandom.current().nextInt(i + 1) generates j from 0 through i. If j < k, reservoir.set(j, items.get(i)) replaces that slot. Otherwise the reservoir does not change.

The executable example uses the exact fixed draws from the diagram: 1, 0, 4, 6, and 2. That makes the example reproducible and produces the exact diagram result [E, D, H]. The production overload uses ThreadLocalRandom and therefore may return a different valid sample on each run.

The algorithm processes each item at most once, so it uses O(n) expected time under the indexed-access list behavior shown in the diagram. It stores k sampled items, so auxiliary space is O(k). For this problem, k = 10.

If k = 0, the result is empty. If k equals the input size, every item is returned. Duplicate values are fine because input positions are processed independently. If the input contains fewer than k items, the implementation rejects it as invalid input.

The key idea is to maintain a fair sample without shuffling the whole input. Start by copying the first k items into a reservoir. For every later item at index i, choose j uniformly from 0 through i. The item enters the sample only when j < k, and then it replaces reservoir[j]. The invariant is that after processing index i, the reservoir is a uniform random sample of size k from items[0..i]. The current item enters with probability k/(i+1), while uniform replacement keeps the same final inclusion probability for earlier items.

Let n be the number of input items and k be the sample size. We process each item at most once, so the diagram's algorithm uses O(n) expected time when indexed access to the input list is O(1), as it is for the example and an ArrayList-style input. The reservoir stores exactly k selected items, so auxiliary space is O(k). In this interview problem, n = 10,000 and k = 10, so the extra sample storage contains only 10 items.

A common mistake is shuffling all 10,000 items even though only k sampled items are needed. Another mistake is drawing j from the wrong range. It must be uniform from 0 through the current index i. A candidate may also replace a reservoir item on every iteration instead of replacing only when j < k. Another mistake is claiming O(1) auxiliary space even though the reservoir stores k items. It is also wrong to claim that [E, D, H] is the only possible answer. It is only the result of the fixed random run shown in the diagram.

State the invariant before writing the loop: after processing index i, the reservoir is a uniform sample of size k from items[0..i]. Then explain that j < k happens with probability k/(i+1). This connects the random draw directly to the correctness proof.

I would first count how many times each value appears using a HashMap. Then I would try every pair of distinct indices i and j. For each pair, I compute c = a + b using long to avoid integer overflow. I check whether the array contains enough occurrences of c to use a, b, and c as three distinct elements. I return as soon as I find a valid triple. The expected time is O(n²), with O(n) auxiliary space.

The input is an array of numbers. We need to return three values from three distinct array positions where the first two values add up to the third. The third value can appear anywhere in the array, and values may be negative, zero, or repeated. I first count how many times every value appears. Then I try each pair of different positions and calculate their sum. The stored counts tell me whether that sum is available as a separate third element.

1. Should a, b, and c come from three distinct array positions?
2. Can the array contain negative numbers, zero, and duplicate values?
3. What should I return if no valid triple exists?

The input is an integer array. The output is one valid triple of values [a, b, c] where a + b = c. The three values must come from three distinct array elements. For the example [1, 2, 4, 8, 10], one valid answer is [2, 8, 10] because 2 + 8 = 10.

I use a HashMap<Integer, Integer> as a frequency map. A frequency map stores each array value as a key and the number of times that value appears as its value. Then I examine every pair of distinct indices i < j. For each pair, I compute c = a + b and use the frequency map to check whether enough copies of c exist.

The key invariant is that i and j always refer to two different elements. The frequency check then makes sure a third distinct array element can supply c. If c equals a or b, we require an extra occurrence. If c equals both a and b, we require three occurrences.

For nums = [1, 2, 4, 8, 10], the frequency map is {1→1, 2→1, 4→1, 8→1, 10→1}. Pair traversal begins with i = 0 and j = 1. For each pair, a = nums[i] and b = nums[j]. I calculate the sum using long so adding two int values cannot overflow before I check the range.

Step 1 uses i = 0 and j =

1. So a = 1 and b =
2. The sum is
3. frequency[3] is 0, so processing continues.

Step 2 uses i = 0 and j = 2. The sum is 1 + 4 = 5. frequency[5] is 0, so processing continues.

Step 3 uses i = 0 and j = 3. The sum is 1 + 8 = 9. frequency[9] is 0, so processing continues.

Step 4 uses i = 0 and j = 4. The sum is 1 + 10 = 11. frequency[11] is 0, so processing continues.

Step 5 uses i = 1 and j = 2. The sum is 2 + 4 = 6. frequency[6] is 0, so processing continues.

Step 6 uses i = 1 and j = 3. Now a = 2 and b = 8. The sum is 10. Because 10 differs from both selected values, only one occurrence of 10 is required. frequency[10] is 1, so the algorithm returns [2, 8, 10] and stops immediately. The answer is found after 6 pair checks.

Every possible pair of distinct indices i < j is considered until a valid result is found. For each pair, c is calculated as exactly a + b. The frequency map verifies that enough occurrences of c exist to provide a separate third element. This also handles cases where c has the same value as a or b. Therefore every returned triple uses three distinct array elements and satisfies a + b = c.

The code first rejects null arrays and arrays with fewer than three elements. It builds the frequency map in one pass. Two nested loops then enumerate every pair i < j. The sum is calculated as long and skipped if it is outside the int range. The code calculates how many copies of c are required. If the map contains at least that many copies, it returns [a, b, c]. If no pair works, it returns null.

Building the frequency map takes expected O(n) time. There are O(n²) index pairs. Each HashMap lookup is O(1) on average, so the overall expected time is O(n²). The map can store up to n distinct values, so auxiliary space is O(n). Important cases are arrays shorter than three elements, negative values, zero, and duplicates. For example, [0, 0, 0] works because the map confirms that three occurrences of 0 exist.

The key idea is to separate two jobs. First, count how many times every value appears. Second, enumerate every pair of distinct indices i < j and ask whether their sum exists as a third element. The HashMap stores value → occurrence count. For each pair, c = a + b. The central invariant is that i and j already consume two distinct array elements. The frequency check therefore requires enough copies of c to provide a third distinct element. This handles negative numbers, zero, and duplicates without making an ordering assumption about where c appears.

Let n be the number of elements. Building the frequency map takes expected O(n) time because Java HashMap insertion is O(1) on average. The two nested loops examine O(n²) pairs. Each frequency lookup is O(1) on average, so the total expected time is O(n²). The HashMap may contain up to n different values, so the auxiliary space is O(n). Auxiliary space means extra memory used by the algorithm.

A common mistake is checking only whether c exists without checking how many copies are available. If c equals a or b, a separate occurrence is needed for the third element. Another mistake is allowing i and j to refer to the same array position. Candidates may also forget integer overflow when calculating a + b with int values. Another error is claiming guaranteed O(1) HashMap operations instead of average O(1). Finally, do not keep processing pairs after a valid triple has been returned.

Explain the occurrence-count rule before writing the nested loops. Say that i and j already consume two elements, so the map must prove that enough copies of c exist to supply a third distinct element. Using [0, 0, 0] as a quick duplicate example makes this rule easy to explain.

I would use a k-way merge with a min heap. I open each sorted file with a BufferedReader, read one current value from every non-empty file, and put those values into a Java PriorityQueue. I repeatedly remove the smallest value, write it to the output file, and read the next value only from that same source file. The heap always contains the smallest unread value from each active file. The time complexity is O(N log k), and the auxiliary space is O(k) plus small I/O buffers.

The problem gives several very large files that are already sorted. The files are too large to load fully into memory. We need to create one new file containing all records in sorted order. The main idea is to keep only one current value from each file in memory. A min heap tells us which current value is smallest. After writing that value, we read only the next value from the same file. This keeps memory usage small while still producing the correct sorted output.

1. Is every input file already sorted in ascending order?
2. Can I assume each record contains one integer per line, as in the example?
3. Can all input files remain open at the same time, or can k exceed the operating system open-file limit?

The input is k individually sorted files stored on disk. The complete data does not fit in memory. The output is one file containing every input value in ascending order. For the diagram example, File A is [1, 4, 9], File B is [2, 6, 8], and File C is [3, 5, 7, 10]. The final output is [1, 2, 3, 4, 5, 6, 7, 8, 9, 10].

I use a k-way merge. The data structure is a min heap. In Java, PriorityQueue is a min heap when its ordering puts the smallest value first. Each heap entry stores two things: the current value and the file index that produced it. The central invariant is: the heap contains the smallest unread value from each non-empty file. Because of that invariant, the smallest value in the heap is also the smallest value that can appear next in the final output.

I open one BufferedReader for each input file and one BufferedWriter for the output file. I read the first value from every non-empty file. For the example, the first values are A:1, B:2, and C:3. I insert heap entries (1,A), (2,B), and (3,C). The output is initially empty.

Step 1: The heap contains [(1,A), (2,B), (3,C)]. I remove (1,A), write 1, then read the next value from File A, which is 4. I insert (4,A). The heap becomes [(2,B), (3,C), (4,A)].

Step 2: I remove (2,B), write 2, read 6 from File B, and insert (6,B). The heap becomes [(3,C), (4,A), (6,B)].

Step 3: I remove (3,C), write 3, read 5 from File C, and insert (5,C). The heap becomes [(4,A), (5,C), (6,B)].

Step 4: I remove (4,A), write 4, read 9 from File A, and insert (9,A). The heap becomes [(5,C), (6,B), (9,A)].

Step 5: I remove (5,C), write 5, read 7 from File C, and insert (7,C). The heap becomes [(6,B), (7,C), (9,A)].

Step 6: I remove (6,B), write 6, read 8 from File B, and insert (8,B). The heap becomes [(7,C), (8,B), (9,A)].

Step 7: I remove (7,C), write 7, read 10 from File C, and insert (10,C). The heap becomes [(8,B), (9,A), (10,C)].

Step 8: I remove (8,B) and write 8. File B has reached EOF, so I do not insert another heap entry. The heap becomes [(9,A), (10,C)].

Step 9: I remove (9,A) and write 9. File A has reached EOF, so I do not insert another heap entry. The heap becomes [(10,C)].

Step 10: I remove (10,C) and write 10. File C has reached EOF. The heap becomes empty, so processing stops. The merged output is [1, 2, 3, 4, 5, 6, 7, 8, 9, 10].

Before every output step, the heap contains the smallest unread value from each file that still has data. Therefore, any unread value that could be written next is either already in the heap or comes after one of those heap values in its own sorted file. The minimum heap entry is therefore the global smallest unread value. After writing it, I refill only from that same file, which restores the invariant. Repeating this until the heap is empty produces a fully sorted output.

The Java code keeps a BufferedReader for every input file. HeapNode stores a value and the index of its source reader. Initialization reads one value from every non-empty file and inserts it into PriorityQueue. The main loop polls the minimum node, writes its value, then reads one new value from the same reader. If that reader still has data, the new value goes back into the heap. When the heap is empty, every file is exhausted. BufferedReader and BufferedWriter let the program stream data instead of loading complete files into memory.

Let N be the total number of records across all files and k be the number of files. Every record enters and leaves a heap whose size is at most k, so the time complexity is O(N log k). The heap stores at most one current record per non-empty file, so auxiliary memory is O(k), plus the small I/O buffers used by the readers and writer. Empty files are skipped. Duplicate and negative values work naturally. A single input file also works. If k is larger than the operating system open-file limit, the files must be merged in batches across multiple passes.

The key idea is to avoid loading the huge files into memory. Because every file is already sorted, I only need to know the smallest unread value from each file. I keep those current values in a min heap. Each heap entry stores the value and the file it came from. The invariant is that the heap contains the smallest unread value from every non-empty file. The heap minimum is therefore the next global value to write. After removing it, only that same source file needs to provide a replacement. This is the k-way merge pattern shown in the diagram and is well suited to sorted data stored on disk.

Let N be the total number of records in all files, and let k be the number of input files. Each record is inserted into and removed from a min heap whose size is at most k. A heap operation costs O(log k), so the total time is O(N log k). The heap keeps at most one current value for each file, so auxiliary space is O(k). The readers and writer also use small I/O buffers. The complete input data never needs to fit in RAM.

A common mistake is loading all files into memory, which breaks the main requirement. Another mistake is placing many records from every file into the heap instead of keeping only one current value per active file. Candidates can also forget that after polling the minimum, the replacement must come from that same source file. Using max-heap ordering would produce the wrong output order. Another mistake is claiming O(N) time instead of O(N log k). Finally, opening too many files at once can exceed the operating system open-file limit.

State the invariant early: the PriorityQueue contains the smallest unread value from every non-empty file. Then explain that after polling one value, only that value's source file needs to advance. This makes the correctness argument and the O(N log k) complexity easy to explain.

I would model the words as an unweighted graph and use BFS. Each word is a node, and two words are connected when they differ by exactly one character. I keep a queue for BFS, a HashSet for visited words, and a parent map for rebuilding the path. I mark each word visited when I first discover it. I stop when I discover the end word. BFS gives a shortest ladder. The expected time is O(n × L × 26), and auxiliary space is O(n).

We need to build a chain from the start word to the end word. In each move, we can change only one letter. The new word must be in the given dictionary. For the example, we start with "hit" and want to reach "cog". A valid result is ["hit", "hot", "dot", "dog", "cog"]. I use BFS because it checks words in increasing number of changes. I remember where each discovered word came from so I can rebuild the final chain when "cog" is found.

1. Can I assume all usable words have the same length as beginWord and endWord?
2. Should I return an empty list when endWord is not in the dictionary or no ladder can be found?
3. Can beginWord and endWord be the same word?

The input has a beginWord, an endWord, and a list of dictionary words. We need to return a sequence of words from beginWord to endWord. Every neighboring pair in the sequence must differ in exactly one character. Every intermediate word must belong to the dictionary.

The diagram uses this example: beginWord = "hit" endWord = "cog" wordList = ["hot", "dot", "dog", "lot", "cog"]

The returned sequence is ["hit", "hot", "dot", "dog", "cog"]. It has five words and four transformations.

I treat every word as a node in an implicit unweighted graph. Two words have an undirected connection when they differ by exactly one character. I do not build all graph edges in advance. Instead, I generate possible one-letter changes when I process a word.

I use an ArrayDeque as the BFS queue. I use a HashSet called dict for average O(1) dictionary membership checks. I use another HashSet called visited so the same word is not added to the queue more than once. I use a HashMap<String, String> called parent. It stores child word → predecessor word. For example, parent["dog"] = "dot" means we first reached "dog" from "dot".

The central invariant is that every word already placed in the queue has a shortest known path from beginWord. BFS processes words in increasing number of transformations.

First, if beginWord equals endWord, I return [beginWord]. Next, I convert wordList to a HashSet. If endWord is not present, I return an empty list.

For the normal BFS path, the initial state is: queue = [hit] visited = {hit} parent = {hit → null}

The null parent marks the beginning of the reconstructed path.

Step 0: The queue is [hit]. I dequeue "hit". I generate words by changing one position at a time with letters from 'a' through 'z'. The valid unseen dictionary neighbor is "hot". I store parent["hot"] = "hit", mark "hot" visited, and enqueue it. The queue becomes [hot].

Step 1: I dequeue "hot". Its new valid unseen neighbors are "dot" and "lot". I store parent["dot"] = "hot" and parent["lot"] = "hot". I mark both visited and enqueue them. The queue becomes [dot, lot].

Step 2: I dequeue "dot". The new valid unseen neighbor is "dog". I store parent["dog"] = "dot", mark it visited, and enqueue it. The queue becomes [lot, dog].

Step 3: I dequeue "lot". It produces no new unseen dictionary word. The queue becomes [dog]. Processing continues.

Step 4: I dequeue "dog". It discovers "cog". I store parent["cog"] = "dog" and mark it visited. Because "cog" is endWord, I stop BFS immediately. I do not process any later state.

The parent chain is cog ← dog ← dot ← hot ← hit. Following those links backward and reversing the chain gives [hit, hot, dot, dog, cog].

BFS explores an unweighted graph level by level. The first time a word is discovered, BFS has reached it with the fewest transformations from beginWord. We mark a word visited at first discovery, so a longer later route cannot replace that shortest predecessor. The parent map records the predecessor from that first discovery. Therefore, when endWord is first discovered, following the parent links produces a valid shortest ladder.

For each dequeued word, the code copies its characters into a char array. For every position, it tries letters 'a' through 'z'. It skips the original character because that would not create a change. Each generated word is checked against dict. If it is in the dictionary and visited.add(next) succeeds, this is its first discovery. The code stores its parent. If it equals endWord, the code immediately calls buildPath. Otherwise, it is added to the BFS queue. After one character position is processed, the original character is restored.

The buildPath method starts at endWord and repeatedly follows parent links. It adds every word to the front of a LinkedList, so the final list is already in beginWord-to-endWord order.

The diagram gives expected time O(n × L × 26), often written as O(nL), where n is the number of reachable words and L is the word length. HashSet and HashMap operations are O(1) on average. Auxiliary space is O(n) for the dictionary set, visited set, queue, and parent map.

Important edge cases are beginWord equal to endWord, endWord missing from the dictionary, duplicate dictionary words, and a disconnected dictionary with no reachable ladder. A HashSet automatically removes duplicate dictionary entries.

The key idea is to view the problem as shortest-path search in an implicit unweighted graph. Each dictionary word is a node. Two nodes are connected when their words differ by exactly one character. BFS is a good fit because it processes nodes in increasing distance from beginWord. Instead of building every edge first, the algorithm generates one-letter mutations only when a word is dequeued. The queue stores words waiting to be processed. The visited set prevents repeated work. The parent map stores child word → predecessor word. The invariant is that every queued word already has a shortest known path from beginWord. Therefore, the first discovery of endWord gives a shortest ladder, and the parent links can reconstruct it.

The expected time shown in the diagram is O(n × L × 26), often simplified to O(nL). Here, n is the number of reachable words and L is the word length. For every processed word, we try each of its L character positions and the 26 lowercase letters. HashSet and HashMap membership, insertion, and lookup are O(1) on average, so this is an expected-time bound rather than a guaranteed worst-case hashing bound. Auxiliary space is O(n). The dictionary set, visited set, BFS queue, and parent map can all grow with the number of words.

A common mistake is marking a word visited only when it is removed from the queue. That can enqueue the same word more than once. Another mistake is forgetting to store the parent when a word is first discovered, which makes path reconstruction impossible. Candidates may also forget to restore the original character after testing mutations at one position. Another error is continuing BFS after endWord has already been discovered even though the diagram stops immediately. Finally, it is easy to claim guaranteed O(1) HashSet or HashMap operations instead of saying they are O(1) on average.

State the BFS invariant before coding: every word already placed in the queue has a shortest known path from beginWord. Then say that you mark a word visited when it is first discovered and save its parent at the same time. This makes both the shortest-path reasoning and the path reconstruction easy to explain.