21 Microsoft JavaScript Frontend Developer Interview Questions & Answers

I would use two stacks. The main stack stores every pushed value. A second stack, minStack, stores the minimum value for each matching stack depth. On push, I add the new value to the main stack and add the smaller of that value and the previous minimum to minStack. On pop, I pop both stacks. Then top reads the main stack, while getMin reads minStack. Every operation is O(1), and the retained space is O(n).

The task is to build a stack that can return both its top value and its smallest current value without searching through all stored values. We need push, pop, top, and getMin. The diagram uses two synchronized stacks. The main stack stores the real values. minStack stores the minimum value for every matching stack depth. This means its top always tells us the current minimum. Each operation does only a constant amount of work, while the two stacks together use O(n) retained space.

1. Can I assume pop(), top(), and getMin() are called only when the stack is non-empty? Yes. The problem guarantees this.
2. Do duplicate minimum values need to work correctly? Yes. Duplicate minimum values are allowed.

The class has four methods. push(value) adds one signed 32-bit integer. pop() removes the current top value and does not need to return it. top() returns the current top value. getMin() returns the smallest value currently stored. We cannot scan the full stack during any operation. Every method must run in O(1) time.

The main stack stores every value. minStack has one entry for every entry in the main stack. Each minStack entry stores the minimum value at that exact depth. Therefore, both stacks always have the same length. The top of minStack is always the minimum of all values currently in the main stack.

When both stacks are empty, push(-2) adds -2 to the main stack. There is no previous minimum, so minStack also receives -2. The state is stack = [-2] and minStack = [-2]. Next, push(0) adds 0 to the main stack. The previous minimum is -2, so min(0, -2) is -2. The state becomes stack = [-2, 0] and minStack = [-2, -2]. Then push(-3) adds -3. min(-3, -2) is -3, so the state becomes stack = [-2, 0, -3] and minStack = [-2, -2, -3].

After push(-2), push(0), and push(-3), getMin() reads the top of minStack and returns -3. Then pop() removes the top entry from both stacks. The main stack becomes [-2, 0], and minStack becomes [-2, -2]. Now top() reads the main stack and returns 0. Finally, getMin() reads the top of minStack and returns -2.

The invariant is that minStack[i] is the minimum value among stack[0] through stack[i]. Every push preserves this invariant because it stores the smaller of the new value and the previous minimum. Every pop removes the same depth from both stacks. Therefore, after a pop, the new top of minStack is exactly the minimum for the remaining main stack. Duplicate minimums also work because every depth stores its own minimum value.

The constructor creates two empty arrays. push(value) first adds value to stack. It then calculates the minimum for the new depth. If minStack is empty, that minimum is value itself. Otherwise, it uses Math.min(value, previousMinimum). It pushes that result to minStack. pop() removes one entry from each stack. top() returns the last main-stack value. getMin() returns the last minStack value.

push(), pop(), top(), and getMin() each perform only a constant number of array operations, so each method runs in O(1) time. The main stack can contain n entries, and minStack contains exactly one matching entry for each depth, so retained space is O(n). Duplicate minimums work naturally. Negative values, positive values, and zero also work. The problem guarantees that pop(), top(), and getMin() are never called on an empty stack.

Use two synchronized stacks. The main stack stores the actual values. minStack stores the minimum value for each corresponding depth. The central invariant is: minStack[i] equals the minimum of stack[0..i]. On push, store the new value in stack and store min(value, previous minimum) in minStack. If this is the first value, store the value itself as the minimum. On pop, remove one entry from both stacks. Because both stacks remain aligned by depth, the top of minStack is always the current minimum. This avoids an O(n) rescan.

Every method runs in O(1) time. push() performs one push to the main stack, one constant-time minimum calculation, and one push to minStack. pop() performs one pop from each stack. top() and getMin() directly read the last array element. The retained space is O(n). If the main stack contains n values, minStack also contains n minimum values, so total stored data grows linearly with n.

A common mistake is storing only the newest minimum instead of the minimum for every stack depth. Then the previous minimum can be lost after a pop. Another mistake is pushing into the main stack without also pushing a matching minimum into minStack, which breaks the depth alignment. Candidates may also pop only one of the two stacks. Another mistake is scanning the entire main stack inside getMin(), which makes getMin() O(n). Finally, claiming O(1) total space is incorrect because both arrays grow with the number of stored values.

State the invariant first: minStack[i] stores the minimum of stack[0..i]. Then trace the two arrays together for -2, 0, and -3. This makes it easy to show why getMin() is a direct O(1) lookup and why popping both stacks restores the previous minimum correctly.

I would use counting sort because every value is a bounded integer from 0 through maxValue. I create a count array where count[v] stores how many times value v appears. I count every input value, then scan values from 0 through maxValue and write each value into a new result array count[v] times. This preserves duplicates and produces nondecreasing order without changing the input. The time is O(n + maxValue), with O(maxValue) auxiliary space besides the result.

We need to return a new array containing the same numbers arranged from smallest to largest. Every number is between 0 and maxValue, so we can use each number itself as a position in a count array. First, we count how many times every number appears. Then we visit the possible values from 0 upward and copy each value into the result the recorded number of times. This naturally keeps duplicates and gives sorted order. The original values array stays unchanged, and we do not use the built-in sort method.

1. Can I rely on every entry being an integer in the inclusive range 0..maxValue?
2. Should I keep the original values array unchanged?
3. Is O(maxValue) auxiliary memory, not counting the returned array, acceptable?

The function receives values and maxValue. values may be empty and may contain duplicate numbers. Every entry is an integer from 0 through maxValue. maxValue is a safe integer from 0 through 1,000,000. We must return a new array containing all input values in nondecreasing order. We must not change values, call Array.prototype.sort, or create count entries outside the stated range.

For the diagram example, values is [4, 1, 3, 1, 0] and maxValue is 4. The required result is [0, 1, 1, 3, 4].

I use counting sort. The main data structure is an occurrence array named count. Its index represents an input value. count[v] means how many times value v appears in values.

The important invariant is that after the counting loop finishes, count[v] is exactly the number of occurrences of v in the input. Because the reconstruction loop visits v from 0 through maxValue, writing each v exactly count[v] times produces all original values in sorted order.

For maxValue = 4, the count array has length maxValue + 1 = 5. It starts as [0, 0, 0, 0, 0], with indices 0, 1, 2, 3, and 4.

We process the input [4, 1, 3, 1, 0]. For each current value, we increment count[currentValue]. After all five input elements are counted, count is [1, 2, 0, 1, 1]. This means 0 appears once, 1 appears twice, 2 appears zero times, 3 appears once, and 4 appears once.

We create a new result array with the same length as values. We also keep idx as the next position to fill.

At i = 0, count[0] is 1, so we write 0 once. The result begins [0].

At i = 1, count[1] is 2, so we write 1 twice. The filled part of the result becomes [0, 1, 1].

At i = 2, count[2] is 0, so the code writes nothing.

At i = 3, count[3] is 1, so we write 3 once. The filled part becomes [0, 1, 1, 3].

At i = 4, count[4] is 1, so we write 4 once. The final result is [0, 1, 1, 3, 4].

Every input value increments exactly one matching count entry. Therefore the count array records every input occurrence exactly once. During reconstruction, each value i is written exactly count[i] times. No original occurrence is lost, and no extra value is added. Because i is visited from 0 through maxValue, every smaller value is written before every larger value. Therefore the returned array contains the same values in nondecreasing order.

The code first reads values.length into n. Empty input returns a new empty array. Otherwise it creates count with maxValue + 1 zeroes. The first loop increments count[values[i]] for every input element. The code then creates result and starts idx at 0. The second outer loop visits i from 0 through maxValue. It reads c = count[i]. When c is greater than zero, the inner loop writes i exactly c times and advances idx after every write. Finally, it returns result without changing values.

Let n be values.length. Counting takes O(n) time. The reconstruction loop visits every possible value from 0 through maxValue and performs exactly n total writes into the result. The total time is O(n + maxValue). The count array uses O(maxValue) auxiliary space. The result itself uses O(n) output space and is separate from that auxiliary-space bound.

Relevant edge cases shown by the diagram are empty input, all values being the same, maxValue equal to 0, a large maxValue up to 1,000,000, and the stated guarantee that every input value is in 0..maxValue.

The key insight is that every input is an integer from a known bounded range. That lets us use the value itself as an array index instead of comparing values with one another. count[v] stores the exact frequency of v. After counting, the invariant is that count[v] equals the number of times v appears in values. We then visit possible values in increasing order and emit each one exactly count[v] times. This reconstructs the same multiset in nondecreasing order and gives the required O(n + maxValue) time.

Let n be values.length. The first loop processes n input elements, so counting costs O(n). The reconstruction loop visits every possible integer from 0 through maxValue, which costs O(maxValue), and its inner loops perform n total writes because every input occurrence is written once. The total time is therefore O(n + maxValue). The count array has maxValue + 1 entries, so auxiliary space is O(maxValue). The returned result has n entries and uses O(n) output space, which is separate from the requested auxiliary-space bound.

One common mistake is creating only maxValue count slots instead of maxValue + 1, which leaves no slot for the value maxValue. Another is confusing input indices with values and incrementing the wrong count entry. Candidates may also forget to emit duplicate values count[i] times. Mutating values or calling Array.prototype.sort breaks the required contract. It is also incorrect to claim O(n) time while ignoring the scan through 0..maxValue, or to call the growing count array O(1) auxiliary space.

Define count[i] before writing the loops: index i is the actual value, and count[i] is its frequency. Then explain that scanning those indices from 0 upward is what makes the reconstructed result sorted.

I would use two pointers, one from each end of the string. I move each pointer inward until it reaches an ASCII letter or digit. Then I compare those two characters after converting uppercase ASCII letters to lowercase. If they differ, I return false immediately. If they match, I move both pointers inward and continue. When the pointers meet or cross, I return true. This takes O(n) time and O(1) auxiliary space because I never build a cleaned copy.

The input is one JavaScript string with at most 100,000 ASCII code units. It can contain letters, digits, whitespace, punctuation, or no alphanumeric characters. We compare only ASCII letters and digits and ignore letter case. The function returns true when the retained characters read the same from both ends. It returns false when one compared pair differs. A string with no retained characters is a palindrome. Two pointers fit this problem because they compare both ends directly without constructing a cleaned copy.

1. Can I assume the input is always a JavaScript string, since non-string input is outside the contract?
2. Should I compare only ASCII A-Z, a-z, and 0-9?
3. Should a string with no retained ASCII letters or digits return true?

The input is text, a JavaScript string of at most 100,000 ASCII code units. We retain only ASCII letters and digits. We ignore whitespace, punctuation, and every other character. We also ignore letter case. The output is a Boolean. If there are no retained characters, the answer is true.

Use a left pointer and a right pointer. The left pointer starts at index 0. The right pointer starts at text.length - 1. Each pointer skips characters that are not ASCII letters or digits. When both pointers are on retained characters, compare them after ASCII case normalization. This avoids constructing a fully cleaned string.

For the example A man, a plan, a canal: Panama, the string length is 30. So left = 0 and right = 29. The invariant is that every retained character outside the current pointer range has already been matched correctly with its partner from the other end. Characters that were skipped were not part of the comparison contract.

At indices 0 and 29, A and a match after case normalization, so the pointers become 1 and 28. Index 1 is a space, so left becomes 2. At 2 and 28, m matches m. At 3 and 27, a matches a. At 4 and 26, n matches n. Left skips the comma at 5 and the space at 6. At 7 and 25, a matches a. Left skips the space at 8. At 9 and 24, p matches P after normalization. Right skips the space at 23 and the colon at 22. At 10 and 21, l matches l. At 11 and 20, a matches a. At 12 and 19, n matches n. Left skips the comma at 13 and the space at 14. At 15 and 18, a matches a. Left then skips the space at 16 and becomes 17. Now left = 17 and right = 17, so the pointers have met and the function returns true.

Before every comparison, both pointers are on retained ASCII letters or digits. Anything already outside the pointer range has either been ignored because it is not retained or has already matched correctly with its partner. Therefore, the first unequal retained pair proves the string is not a palindrome. If the pointers meet or cross without a mismatch, every required pair has matched, so the string is a palindrome.

isAsciiAlnum checks the ASCII ranges for digits, uppercase letters, and lowercase letters. toLowerAscii converts uppercase ASCII letters to lowercase by adding 32 to their character code. The main function skips unwanted characters from both ends. It compares the normalized retained characters. A mismatch returns false immediately. A match moves both pointers inward. When the pointers meet or cross, the function returns true.

The time complexity is O(n) because the left pointer moves only right and the right pointer moves only left. The auxiliary space is O(1) because only a constant number of variables are used. Important cases are an empty string, a punctuation-only string such as !!!, a single retained character, mixed letter case, and a non-palindrome such as race a car.

The key idea is to compare retained characters directly from both ends instead of creating a cleaned copy. Start left at the beginning and right at the end. Move left rightward while its character is not an ASCII letter or digit. Move right leftward for the same reason. When both pointers are valid, normalize uppercase ASCII letters to lowercase and compare their character codes. Return false on the first mismatch. Otherwise move both pointers inward. The invariant is that every retained character outside the current pointer range has already been matched correctly. When left >= right, no unmatched pair remains, so returning true is correct.

Let n be text.length. The time complexity is O(n). The left pointer only moves right, and the right pointer only moves left, so the input is processed at most a constant number of times. The algorithm may also stop early if it finds a mismatch. Auxiliary space is O(1) because it stores only two pointers and a few character-code values. It does not create a cleaned string, array, map, set, or any other structure that grows with the input.

A common mistake is constructing a fully cleaned string first, which uses O(n) auxiliary space instead of the required O(1). Another mistake is accepting non-ASCII Unicode letters or digits even though the contract keeps only ASCII A-Z, a-z, and 0-9. Candidates can also forget to ignore case, move the wrong pointer while skipping punctuation, or forget to move both pointers after a successful comparison. Another mistake is returning false for an empty or punctuation-only string. With no retained characters, the pointers meet or cross without a mismatch, so the correct result is true.

State the invariant before coding: everything outside the current left and right pointers has already been either ignored because it is not retained or matched correctly with its opposite-side character. Then explain that both pointers move only inward. This makes the correctness argument and the O(n) time, O(1) auxiliary-space analysis easy to justify.

I would use a sliding window with two pointers, left and right, plus a Map called lastSeen. The Map stores each character and its most recent index. I move right through the string. If the current character was seen at or after left, I move left just past that earlier index. Then I update the Map and the best window length. The window always contains unique characters. This gives O(n) expected time and O(k) auxiliary space.

We need to find the length of the longest continuous part of the string that has no repeated character. We return only the length, not the substring. The input is an ASCII string with length from 0 to 100,000. It may be empty and may contain repeated characters. Instead of trying every possible substring, we keep one valid range and move through the string from left to right. A Map remembers the most recent position of each character, which lets us move the left side forward when a repeat appears.

1. Can I assume the input always follows the stated ASCII string contract?
2. Should I return only the length and not the actual substring?
3. Is O(n) expected time with O(k) auxiliary space the required target?

The input is one ASCII string called text. Its length can be from 0 to 100,000. We return the number of characters in the longest contiguous substring that contains no repeated character. We do not return the substring itself, and we do not change the input.

For the diagram example, text is "abcabcbb". The answer is 3. Valid substrings of length 3 include "abc", "bca", and "cab".

I use a sliding window with two boundaries. left is the first index of the current valid window. right is the index of the character currently being processed. The Map lastSeen stores each previously seen character and its most recent index.

The main invariant is that after handling the current character, the window from left through right contains no repeated character.

Start with left = 0 and maxLen = 0. lastSeen starts as an empty Map. Then move right from index 0 through text.length - 1.

At each index, read c = text[right]. If c is already in lastSeen and its stored index is greater than or equal to left, the previous copy is inside the active window. Move left to lastSeen.get(c) + 1. Then store the current index for c.

At right = 0, the character is "a". It has not been seen. The window is "a". Its length is 1, so maxLen becomes 1.

At right = 1, the character is "b". It has not been seen. The window becomes "ab". Its length is 2, so maxLen becomes 2.

At right = 2, the character is "c". It has not been seen. The window becomes "abc". Its length is 3, so maxLen becomes 3.

At right = 3, the character is "a". The previous "a" is at index

1. Since 0 >= left, that earlier "a" is inside the active window. Move left from 0 to
2. After storing the new index of "a", the valid window is "bca". Its length is 3.

At right = 4, the character is "b". Its previous index is

1. Since 1 >= left, move left to
2. The valid window is "cab". Its length is 3.

At right = 5, the character is "c". Its previous index is

2. Since 2 >= left, move left to
3. The valid window is "abc". Its length is 3.

At right = 6, the character is "b". Its previous index is

4. Since 4 >= left, move left to
5. The valid window becomes "cb". Its length is 2.

At right = 7, the character is "b" again. Its previous index is 6. Since 6 >= left, move left to 7. The valid window becomes "b". Its length is 1. maxLen stays 3.

When a repeated character appears inside the current window, left moves just past that character's previous occurrence. This removes the duplicate from the active window. Therefore, after each iteration, the current window contains unique characters. We measure every valid window ending at right, and maxLen keeps the largest valid length seen so far. For "abcabcbb", the maximum length is 3.

The JavaScript code uses a Map from character to most recent index. For each right index, it checks whether the current character was previously seen inside the active window. If it was, left moves forward. The code then records the character's newest index, calculates the current window length as right - left + 1, and updates maxLen when this window is larger. After the loop finishes, it returns maxLen.

The expected time is O(n). The right pointer processes each character once. JavaScript Map lookup and insertion are O(1) on average. Auxiliary space is O(k), where k is the number of distinct characters tracked in lastSeen. An empty string returns

1. A string such as "bbbbb" returns
2. If every character is unique, the answer is the full string length.

The key idea is to maintain one sliding window that contains only unique characters. right expands the window one character at a time. lastSeen maps each previously seen character to its most recent index. If the current character has a previous index greater than or equal to left, that previous copy is still inside the active window. We move left to one position after that index. Then we update lastSeen and calculate the current window length. The central invariant is that text[left..right] contains no repeated character after the duplicate check is handled.

Expected time is O(n). The right pointer visits each position once. Each JavaScript Map lookup and insertion is O(1) on average, so the full algorithm takes O(n) expected time. Auxiliary space is O(k), where k is the number of distinct characters tracked in lastSeen. Because the input is ASCII, k is bounded by the ASCII character set, but the required complexity is still expressed as O(k) extra space.

A common mistake is moving left backward when a character was seen earlier but is no longer inside the active window. The stored index must be checked with >= left before moving left. Another mistake is forgetting to update lastSeen with the current index. Some candidates calculate the window length before removing the duplicate, which can count an invalid window. Another error is treating a substring like a subsequence and allowing skipped characters. It is also incorrect to describe JavaScript Map operations as guaranteed O(1) worst-case operations.

State the invariant before writing the loop: after handling the current character, text[left..right] contains no duplicates. Then explain every left update using that rule. This makes the condition lastSeen.get(c) >= left easy to justify and helps avoid moving left backward.

I would use two pointers. The read pointer scans the array from left to right, and the write pointer marks the earliest position for the next nonzero value. When values[read] is not zero, I swap it with values[write] and move write forward. Zero values are skipped. This preserves the relative order of the nonzero values and leaves the zeroes at the end. The algorithm runs in O(n) time and uses O(1) auxiliary space.

The supplied array must be changed directly. Every numeric zero must move behind all nonzero values, while the nonzero values keep their original relative order. We cannot create another array whose size grows with the input. I use two positions called read and write. The read position checks each element from left to right. The write position marks where the next nonzero value belongs. When read finds a nonzero value, I swap it into the write position. This gives the required O(n) time and O(1) auxiliary space.

1. Should I mutate the supplied array instead of returning a new array? Yes. The stated contract requires in-place mutation.
2. Must the relative order of the nonzero values stay unchanged? Yes.
3. Is the function's return value important? No. Only the final contents of the supplied array are assessed.

The input is an owned JavaScript array containing 0 through 100,000 signed safe integers. Duplicates, negative values, and any number of zeroes are allowed. We must move every numeric 0 to the end. We must preserve the relative order of all nonzero values. The array length must stay unchanged, and we cannot allocate a second array proportional to the input.

For the diagram's example, the input is [0, 1, 0, 3, 12]. After the function runs, the same array must contain [1, 3, 12, 0, 0].

I use two indices named read and write. read moves from left to right through the whole array. write marks the earliest position where the next nonzero value should be placed.

The central invariant is: before each new read step, every index before write contains the nonzero values already processed, in their original relative order. The processed positions from write through read - 1 contain zeroes.

If values[read] is 0, I skip it. If values[read] is nonzero, I swap values[read] with values[write], then increase write. Because read discovers nonzero values from left to right and write also moves only from left to right, the nonzero order is preserved.

Set write = 0. The loop starts read at index 0. No nonzero values have been placed yet, so index 0 is the correct first write position.

Start with [0, 1, 0, 3, 12], read = 0, and write = 0.

At read = 0, the current value is 0. The condition values[read] !== 0 is false. We skip it. The array stays [0, 1, 0, 3, 12], and write stays 0.

At read = 1, the current value is 1. It is nonzero. Swap positions write = 0 and read = 1. The array becomes [1, 0, 0, 3, 12]. Then write becomes 1.

At read = 2, the current value is 0. We skip it. The array stays [1, 0, 0, 3, 12], and write stays 1.

At read = 3, the current value is 3. It is nonzero. Swap positions 1 and 3. The array becomes [1, 3, 0, 0, 12]. Then write becomes 2.

At read = 4, the current value is 12. It is nonzero. Swap positions 2 and 4. The array becomes [1, 3, 12, 0, 0]. Then write becomes 3.

The loop ends when read reaches values.length. The final array is [1, 3, 12, 0, 0]. Its length is still 5, and the nonzero order 1, 3, 12 is preserved.

read processes the array from left to right. Each time it finds a nonzero value, that value is the next nonzero value from the original order. write points to the earliest place where that value belongs. Swapping the two positions extends the correct nonzero prefix by one. Any zero displaced by the swap stays behind that prefix. When the loop finishes, all nonzero values are at the front in the same relative order, and all remaining positions contain zeroes.

The function keeps one variable, write, outside the loop. The for loop creates read and moves it from 0 through values.length - 1. The strict condition values[read] !== 0 checks whether the current value should be moved into the nonzero prefix. JavaScript destructuring assignment swaps values[write] and values[read] in place. After the swap, write increases by one. There is no explicit return because the supplied array itself is mutated and the return value is not assessed.

The read pointer visits every array position once, so the time complexity is O(n), where n is the array length. The algorithm uses only a constant number of index variables, so the auxiliary space complexity is O(1).

An empty array needs no work. An array containing only zeroes stays unchanged. An array containing no zeroes keeps the same order, although the implementation may perform harmless self-swaps. Duplicates and negative values also work because the algorithm only distinguishes numeric zero from nonzero values.

The key idea is stable in-place compaction with two pointers. read discovers values from left to right. write marks the earliest position for the next nonzero value. The central invariant is that indices before write contain exactly the processed nonzero values in their original relative order, while processed positions from write through read - 1 contain zeroes. When read finds a nonzero value, swapping it with values[write] extends the correct nonzero prefix by one. This preserves order, mutates the original array, and needs no second array proportional to the input.

Let n be the number of elements in the array. The read pointer visits each of the n positions once, so the time complexity is O(n). The algorithm stores only a few index variables and performs swaps inside the supplied array. Its extra memory does not grow with n, so the auxiliary space complexity is O(1).

A common mistake is creating a second output array, which breaks the O(1) auxiliary-space requirement. Another is moving write when the current value is zero. That breaks the pointer invariant. A candidate can also accidentally change the relative order of the nonzero values by moving them in a different order. Using splice, repeated removal, or repeated shifting can make the solution slower than O(n). Another mistake is adding a separate zero-filling pass even though this swap-based version already leaves zeroes behind the nonzero prefix.

State the invariant before coding: write always marks the earliest position for the next nonzero value. Then trace one zero case and one nonzero case. This makes both pointer movement and the swap easy to justify.

I would use a JavaScript Set called seen. I process the array from left to right. Before adding each value, I check whether it is already in the Set. If it is, that value appeared earlier, so I return it immediately. Otherwise, I add it to seen and continue. 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 need to return any number that appears more than once in the array. The array contains from 2 to 100,000 safe integers, and values may be negative. At least one repeated value is guaranteed. We must not sort or change the input. A simple solution is to remember values we have already visited. When we see a value that is already remembered, we return it immediately. A JavaScript Set is a good fit because membership checks and insertions are O(1) on average.

1. If several values are duplicated, may I return any repeated value?
2. Can the array contain negative numbers?
3. Should I keep the original array unchanged and avoid sorting it?

The input is an array named values. Its length is from 2 to 100,000. Every element is a JavaScript safe integer, so values may range from Number.MIN_SAFE_INTEGER to Number.MAX_SAFE_INTEGER. Negative values are allowed. At least one value appears more than once. We return a repeated value, not an index. If several duplicates exist, any one is valid. We must not mutate or sort the input.

Use a Set named seen. It stores the distinct values that appeared at earlier positions. The central invariant is: before checking the current value, seen contains only values processed earlier. Therefore, if seen.has(x) is true, x has already appeared and is a valid duplicate.

Start with seen as an empty Set. Process the array from left to right. For each value x, check seen.has(x) before inserting x. If the check is true, return x immediately. If the check is false, add x to seen and continue. If the loop somehow finishes, return null as a defensive fallback. The stated guarantee means that fallback is not expected to run.

For values = [7, 2, 5, 2, 9], start with seen = {}. At index 0, x = 7. It is not in seen, so add 7. Now seen = {7}. At index 1, x = 2. It is not in seen, so add 2. Now seen = {7, 2}. At index 2, x = 5. It is not in seen, so add 5. Now seen = {7, 2, 5}. At index 3, x = 2. The Set already contains 2, so return 2 immediately. Index 4, which contains 9, is not processed. The diagram also shows [4, 1, 4, 1], where either 4 or 1 is a valid result because the problem allows any duplicate.

The Set contains only distinct values seen earlier in the traversal. When the current value is already in the Set, that same value must have appeared before. Therefore, returning it is correct. The problem guarantees that at least one duplicate exists, so the normal execution path finds a repeated value and stops.

The implementation creates a Set, loops through values, checks seen.has(x), returns x when a repeat is found, and otherwise calls seen.add(x). JavaScript Set lookup and insertion are O(1) on average, so the total expected time is O(n). The Set may grow with the number of distinct values, so auxiliary space is O(n). The same approach works for negative safe integers, the minimum valid length such as [5, 5], large inputs up to the stated limit, and arrays with several different duplicated values.

Use a Set to remember values that have already appeared. The key invariant is that, before checking the current value, seen contains the distinct values from earlier positions only. Check seen.has(x) before inserting x. If the value is present, it appeared earlier, so it is a valid duplicate and can be returned immediately. Otherwise, add it to seen. This keeps the input unchanged, avoids sorting, and matches the required O(n) expected-time approach.

Let n be values.length. We process the array at most once because the function can return as soon as it finds a duplicate. JavaScript Set lookup with has() and insertion with add() are O(1) on average, so the total expected time is O(n). This is an expected bound rather than a guaranteed worst-case O(n) bound. The Set may store up to O(n) distinct values, so the auxiliary space is O(n).

1. Adding x to the Set before checking seen.has(x). That would make the current element appear to duplicate itself.
2. Sorting the input. The question explicitly says not to sort or mutate the array.
3. Returning an index instead of the repeated value. This problem asks for the number itself.
4. Continuing to process later elements after finding a duplicate. The shown algorithm returns immediately, so 9 in the main example is not processed.
5. Claiming guaranteed O(n) time. Because the solution depends on average O(1) Set operations, the correct wording is O(n) expected time.

State the invariant before writing the loop: seen contains the distinct values from earlier positions. Then emphasize that you check the Set before inserting the current value. That makes both the correctness and the early return easy to explain.

I keep references to the important existing nodes instead of creating replacement nodes. I move curr to index a while before stays one node behind. Then I move after past index b, find the tail of list2, and reconnect the links. If a is zero, list2 becomes the new head. This preserves every retained node. The time complexity is O(n + m), and the auxiliary space is O(1).

We have two singly linked lists. We must remove the nodes from position a through b in list1, including both ends. Then we put the existing nodes of list2 into that gap. We must keep the original node objects and only change their next links. The main idea is to save the node before the removed range, the node after it, and the tail of list2. Then we reconnect those saved node references without losing the rest of the list.

1. Are a and b zero-based and inclusive? The problem says yes.
2. May I mutate existing next links? The problem says yes, but I must not create replacement list nodes or copy node values into new nodes.
3. If a is 0, should the head of list2 become the returned head? Yes.

list1 and list2 are non-cyclic singly linked lists. Each node has a numeric val and a next reference. We remove the inclusive range a..b from list1, insert the existing nodes of list2, and return the resulting head. For the example, list1 = [0,1,2,3,4,5], a = 3, b = 4, and list2 = [1000000,1000001,1000002]. The result is [0,1,2,1000000,1000001,1000002,5].

Start with before = null and curr = list1. Move curr forward until it reaches index a. Each time curr moves, set before to the node that curr is leaving. In the example, curr ends at the node with value 3, which is index 3, and before ends at the node with value 2, which is index 2. If a is 0, before remains null.

Set after = curr. The removed range contains b - a + 1 nodes. Here that is 4 - 3 + 1 = 2. Move after two links. It moves from value 3 to value 4, then from value 4 to value 5. Now after points to the first node that must remain after the removed range. If b is the final index, after becomes null.

Start tail at the head of list2 and follow next until tail.next is null. In the example, the tail is the node with value 1000002. Because before exists, set before.next = list2. This connects value 2 to value 1000000. Then set tail.next = after. This connects value 1000002 to value 5. The resulting chain is 0 -> 1 -> 2 -> 1000000 -> 1000001 -> 1000002 -> 5.

Before rewiring, before is either null when a = 0 or the existing node at index a - 1. after is the existing node at index b + 1, or null when b is the tail. These references are saved before links are changed. Connecting before to list2 when before exists, and connecting the tail of list2 to after, preserves every retained node and inserts every node of list2 exactly once.

The first loop positions before and curr. The second loop moves after across the inclusive removed range. The while loop finds the last node of list2. If before exists, before.next becomes list2. The tail of list2 always points to after. Finally, the function returns list1 when the original head remains. If a is 0, it returns list2 because list2 is the new head.

Let n be the length of list1 and m be the length of list2. Traversing the required parts of list1 takes O(n) time in the worst case, and finding the tail of list2 takes O(m) time. Total time is O(n + m). The function stores only a constant number of node references, so auxiliary space is O(1). Important cases are a = 0, b = n - 1, a = b, and a one-node list2.

The key idea is to save every boundary reference needed for the splice before changing any links. before is the existing node just before index a, unless a is zero. curr reaches the first node being removed. after is moved to the first node after index b. tail is the last node of list2. The central invariant is that these references identify existing nodes whose identities are preserved. Once the references are known, only the boundary links need to change, so no replacement nodes or copied values are needed.

Let n be the number of nodes in list1 and m be the number of nodes in list2. Moving through list1 to locate the splice boundaries takes O(n) time in the worst case. Finding the last node of list2 takes O(m) time. Therefore total time is O(n + m). The algorithm stores only a constant number of references such as before, curr, after, and tail, plus loop counters. Their number does not grow with the input, so auxiliary space is O(1).

A common mistake is changing links before saving the node after index b. That can lose the remaining suffix of list1. Another mistake is moving after the wrong number of times and forgetting that a..b is inclusive. Candidates may also forget the a = 0 case and try to use before.next when before is null. Another error is finding the wrong tail of list2. Creating replacement nodes or copying values inside mergeInBetween also violates the required node-identity constraint.

Before writing the rewiring code, say what each reference means: before is the node before the removed range, curr is the first removed node, after is the first retained node after the range, and tail is the last node of list2. Once those references are correct, the two boundary connections are easy to verify.

I would keep two synchronized views of the records. A doubly linked list stores every fruit in ascending weight order, and an insertion counter keeps older records first when weights are equal. A Map stores each fruit name with a sorted array of references to the same nodes. Each add updates both structures without sorting the whole collection again. Construction is O(n^2), add is O(n + k), getByName is O(k), all is O(n), and retained internal space is O(n).

The class receives fruit names and weights. It must always keep all fruits ordered from the smallest weight to the largest. When two records have the same weight, the older record stays first. We can add new records without sorting everything again. We also need two safe queries. One returns all records for one exact fruit name in weight order. The other returns every record in global weight order. Neither query may expose the class's internal mutable arrays. The diagram solves this with one globally sorted doubly linked list and one Map containing sorted node references for each fruit name.

1. Should equal weights keep their original insertion order? Yes. The problem requires stable ordering.
2. Can duplicate names and duplicate weights appear? Yes. Both are allowed.
3. Must getByName and all return new arrays instead of internal storage? Yes. Internal mutable arrays must not be exposed.

The constructor receives an array of [name, weight] pairs. Each name is a non-empty string, and each weight is a finite number. The constructor must not modify this input array. add(name, weight) inserts one new record. getByName(name) returns all exact-name matches in ascending weight order. all() returns every record in global ascending weight order. Both query methods return fresh arrays.

The first structure is a doubly linked list containing every record. It is sorted by (weight, order). The first value is the fruit weight. The second value is an increasing insertion number. This second value keeps equal weights stable because an older record has a smaller insertion number.

The second structure is a Map. Each key is a fruit name. Each value is an array of node references for that name. That array is also sorted by (weight, order). Both structures therefore use the same ordering rule.

Start with an empty linked list, an empty Map, and orderCounter = 0. Process the constructor input in its original order. The example inserts ['apple',1], then ['orange',2], then ['pineapple',4]. Their insertion orders are 0, 1, and 2.

The initial global list is apple:1(0) -> orange:2(1) -> pineapple:4(2). The Map has apple -> [1], orange -> [2], and pineapple -> [4]. The constructor reads the supplied array but never changes it.

For add('apple', 3), create a new node with order 3. Scan the global linked list until reaching the first node whose (weight, order) pair is greater. pineapple:4(2) is the first greater node, so insert apple:3(3) before it. The global list becomes apple:1(0) -> orange:2(1) -> apple:3(3) -> pineapple:4(2). Insert the same node reference into the apple array after weight 1, so the apple weights become [1,3].

For add('apple', 4), create a node with order 4. The existing pineapple:4(2) has the same weight but a smaller insertion order, so it stays first. No later global node exists, so append apple:4(4) at the tail. The final list is apple:1(0) -> orange:2(1) -> apple:3(3) -> pineapple:4(2) -> apple:4(4). The apple array becomes [1,3,4].

getByName('apple') reads the already-sorted apple node array. It creates new pair arrays and returns [['apple',1],['apple',3],['apple',4]].

all() walks the linked list from head to tail. It creates new pair arrays and returns [['apple',1],['orange',2],['apple',3],['pineapple',4],['apple',4]].

Neither method returns the internal Map arrays or the internal linked-list nodes.

After every insertion, the linked list is sorted by (weight, order). A new node is inserted before the first node with a greater pair. This keeps smaller weights first and keeps older equal-weight records before newer ones.

Each fruit's Map array is maintained with the same rule. Therefore getByName is already in the required weight order. The linked list gives the required global order for all(). Both queries build new arrays, so callers cannot modify the class's internal structures.

Let n be the total number of records and k be the number of records for one fruit name. Construction is O(n^2) worst-case time because it performs repeated ordered insertions. One add takes O(n + k) worst-case time. getByName takes O(k), and all takes O(n). Retained internal space is O(n).

The same logic handles duplicate names, duplicate weights, negative weights, zero weights, finite decimal weights, and an empty initial collection.

The key idea is to maintain two ordered views of the same Node objects. The doubly linked list gives the required global order. The Map gives direct access to all records for one exact fruit name. Both structures use the same ordering key: first weight, then the increasing insertion order. This is the central invariant. After every insertion, the global linked list is sorted by (weight, order), and every per-name array is also sorted by (weight, order). The insertion counter makes duplicate weights stable. This avoids sorting the entire collection again after every call to add.

Let n be the total number of stored records. Let k be the number of records for the relevant fruit name. Construction takes O(n^2) worst-case time because every constructor record is inserted in order, and each insertion may scan records already stored. One add takes O(n + k) worst-case time: up to O(n) to find the linked-list position and up to O(k) to find and insert into that fruit's array. Since k <= n, the total is also O(n) in big-O terms. getByName takes O(k) time because it creates one returned pair for each matching record. all takes O(n) time because it walks the full linked list. Retained internal space is O(n): one Node is stored for every record, and the per-name arrays together hold one Node reference for every record. The returned arrays use O(k) output space for getByName and O(n) output space for all, but those copies are not retained internal state.

A common mistake is sorting the full collection again inside every add, instead of inserting only the new record. Another mistake is comparing only weights and forgetting the insertion-order tie breaker, which can break stability for equal weights. A candidate may update the linked list but forget to update the per-name Map array, so the two views no longer describe the same records. Pointer rewiring can also disconnect part of the doubly linked list if prev or next references are changed incorrectly. Another mistake is returning the internal Map array directly instead of building a defensive copy. Finally, splice can shift O(k) array elements, so that cost must be included in insertion complexity.

State the invariant before writing the pointer code: the global linked list and every per-name array are both sorted by (weight, insertion order). Then show how one insertion preserves that rule in both places. This makes stable duplicate handling, query correctness, and the complexity explanation much easier to defend.

I would process the users in display order and each user’s stories in playback order. For every story, I convert intervalInSec to milliseconds, await a Promise backed by setTimeout, and then log that story’s id exactly once. Because each await completes before the next loop iteration starts, waits and logs never overlap. After the final story is logged, the async function finishes and its Promise fulfills with undefined. The time complexity is O(T), with O(1) auxiliary space.

The goal is to play every story one after another. Users already have a display order, and each user’s stories already have a playback order. Before each story, we wait for that story’s delay. Then we print its id exactly once. We do not start the next wait until the current wait and log are complete. This preserves the required order and prevents overlap. Nested for...of loops with await match this behavior directly.

1. Should an empty users array simply finish immediately with undefined?
2. If one user has no stories, should that user be skipped and processing continue with the next user?
3. Should the delay always be interpreted in seconds and converted to milliseconds before calling the browser timer?

The input is an array called users. Each user has a stories array. Each story has an id and intervalInSec. We process users from first to last. Inside each user, we process stories from first to last. Before logging a story id, we wait intervalInSec * 1000 milliseconds. Each id is logged exactly once. After all stories finish, the returned Promise fulfills with undefined.

I use two nested for...of loops. The outer loop preserves user order. The inner loop preserves story order. For every story, I await one timer Promise before logging its id. The central invariant is that the current story’s wait and log both finish before the next story starts. Because of this, waits and logs never overlap.

The first user has stories A and B. The second user has story C. All three intervalInSec values are 0. First, we wait 0 ms for A and then log A. Next, we wait 0 ms for B and then log B. After the first user is complete, we move to the second user. We wait 0 ms for C and then log C. The console order is A, then B, then C.

The code multiplies intervalInSec by 1000 because setTimeout takes milliseconds. The wait helper returns a Promise that resolves after the browser timer fires. Await pauses this async function until that Promise resolves. Only after the wait finishes does console.log(story.id) run. The loop then moves to the next story.

The nested loops preserve the exact required traversal order. The await inside the inner loop makes each story a complete sequential step: wait first, then log. The next story cannot begin before that step is finished. Therefore, there are no overlapping waits or logs. After C is logged in the example, both loops finish. The function has no explicit return value, so its Promise fulfills with undefined.

The wait helper wraps setTimeout in a Promise. The outer for...of loop reads users in display order. The inner for...of loop reads stories in playback order. For each story, the code awaits wait(story.intervalInSec * 1000), then calls console.log(story.id). There is no forEach with an asynchronous callback, so the required sequential control flow is explicit.

Let T be the total number of stories across all users. Each story is processed once, so the algorithmic time complexity is O(T), apart from the real elapsed timer delays. Auxiliary space is O(1) because no data structure grows with the input. Empty users or empty story arrays produce no logs and finish with undefined. Zero delays still preserve order because every timer Promise is awaited. A single user or single story follows the same logic.

The key idea is to make each story one complete sequential asynchronous step: wait, then log. Two nested for...of loops preserve the required traversal order. The outer loop processes users from first to last. The inner loop processes that user’s stories from first to last. For each story, a Promise-backed setTimeout is awaited before console.log runs. The central invariant is: before the next story begins, the current story’s wait and log are already complete. This invariant guarantees the required order and prevents overlapping waits or logs.

Let T be the total number of stories across all users. The code handles each story exactly once, so its algorithmic time complexity is O(T). The real elapsed time also includes the requested timer delays. Auxiliary space is O(1). The function keeps only the current loop values and timer Promise. It does not create an array, map, queue, or other structure whose size grows with the number of stories.

A common mistake is using forEach with an async callback. forEach does not wait for those callback Promises, so waits can overlap and the required order can break. Another mistake is logging before awaiting the delay. Starting every timer together with Promise.all is also wrong because the waits overlap. Candidates may also forget to multiply intervalInSec by 1000 before calling setTimeout. Finally, returning a non-undefined value would violate the required fulfillment result.

State the invariant before writing the code: “For each story, I finish its wait and log before starting the next story.” Then use nested for...of loops with await. That makes both the implementation and the correctness argument easy to follow.