Meta Python Developer Interview Questions & Answers

I would scan the values once while keeping the current maximum, one selected index, and the number of maximum values seen. A larger value resets the selected index and count. A tied value replaces the selected index with probability one divided by the updated count. This gives every maximum index an equal chance and uses constant extra space.

The practical solution is to apply reservoir sampling only to indexes whose values equal the largest value seen so far. During one scan, keep the current maximum, the selected index, the number of tied maximums seen, and a flag that records whether the iterable contained an item.

1. Should I focus on Python language behavior, or also explain the runtime and standard library?
2. Which Python version and execution environment should I assume?
3. Would you like a small code example together with production tradeoffs and edge cases?

The first value becomes the current maximum. When a later value is larger, it becomes the new maximum, its index becomes the selected index, and the count resets to one. When a value equals the current maximum, increase the count and replace the selected index with probability one divided by that count. In Python, calling randrange with the count and checking whether the result is zero gives exactly that probability.

For values [4, 9, 2, 9, 9], indexes 1, 3, and 4 each have probability one third. The function works with lists, generators, and other one pass iterables because it never reads an item twice. Empty input raises ValueError. Values must support consistent greater than and equality comparisons. Floating point NaN needs an explicit policy because its normal comparisons do not define a usable maximum. The algorithm takes linear time and constant extra memory.

The function uses enumerate to obtain each value and its zero based index during one iteration. The first item initializes the current maximum, selected index, and maximum count. A larger value replaces the current maximum and resets the count to one because all earlier candidates are no longer maximum values. An equal value increases the count. The new index replaces the previous selection only when randrange returns zero. After k tied maximum values have been processed, each matching index has probability one divided by k of being selected. Only a fixed number of variables are stored, so the extra memory cost remains constant.

A common mistake is storing every maximum index in a list. That is correct for selection fairness but can use linear extra memory. Another mistake is replacing the chosen index with probability one half for every tie. That makes later indexes more likely. Candidates may also forget to reset the count when a larger value appears, scan the iterable twice, return the maximum value instead of its index, or ignore empty input. Another mistake is assuming NaN follows ordinary maximum comparison rules.

State the invariant clearly. After processing any prefix with k occurrences of its maximum value, each of those k indexes has probability one divided by k of being selected. Then explain the reset for a larger value, the replacement rule for a tie, and the linear time with constant extra memory.

I would use breadth first search with collections.deque because every allowed move has the same cost. I would keep a predecessor dictionary that records which cell discovered each new cell and also acts as the visited set. When the target is reached, I would follow those links backward, reverse the result, and return both the number of cells in the shortest path and the path coordinates.

Use breadth first search because every allowed move has the same cost. Assume zero means open, one means blocked, movement is allowed in eight directions, and distance counts the cells in the returned path. Python deque supports efficient removal from the left, so cells are processed in first in first out order. The first time breadth first search discovers a cell, it has found a shortest route to that cell. Store every discovered coordinate in a predecessor dictionary. Its value is the coordinate that led to it. Dictionary membership also marks the cell as visited, so each cell enters the queue only once. When the target is reached, follow predecessor links backward, reverse the collected coordinates, and return the path length with the path. Return negative one and an empty list for an empty matrix, blocked endpoints, or an unreachable target. The function raises ValueError for rows with different lengths. For r rows and c columns, time is O(r times c), since each cell checks at most eight neighbors. Memory is O(r times c) for the queue, predecessor dictionary, and returned path. The function does not modify or copy the matrix. Weighted moves require a weighted shortest path algorithm.

1. Should I focus on Python language behavior, or also explain the runtime and standard library?
2. Which Python version and execution environment should I assume?
3. Would you like a small code example together with production tradeoffs and edge cases?

The function treats zero as open and one as blocked. It allows horizontal, vertical, and diagonal movement. It first handles an empty matrix and verifies that every row has the same length. It returns negative one with an empty path when the start or target is blocked. A deque processes coordinates in breadth first order. The predecessor dictionary maps each discovered cell to the cell that discovered it. Membership in that dictionary prevents duplicate visits. Once the target is removed from the queue, the function follows predecessor links back to the start, reverses the collected coordinates, and returns len(path) as the distance. The matrix is only read and is not copied or modified. For the included matrix, the result is distance three with the path [(0, 0), (1, 1), (2, 2)].

Common mistakes include using a list with pop(0), which shifts all remaining items, marking a cell visited only after removing it from the queue, forgetting diagonal movement, changing the input matrix without stating that behavior, counting moves while the code returns cells, and failing to check blocked endpoints. Another mistake is storing only distances, because distances alone do not provide the predecessor links needed to reconstruct the route. A candidate may also overwrite a predecessor after a cell was already discovered, which can add duplicate work and make the path logic harder to reason about.

State the assumptions first. Explain that equal move costs make breadth first search correct. Then show how deque provides efficient queue behavior, how the predecessor dictionary also acts as the visited set, and how following parent links reconstructs the path. Finish with O(r times c) time and O(r times c) memory.

I would build a prefix sum list once. Each position stores the number of ones before that position. Then getOne returns prefix[end_idx + 1] minus prefix[start_idx], so every valid query takes O(1) time. Building the prefix list takes O(n) time and O(n) extra memory.

The practical solution is to preprocess the binary list into a prefix sum list. The prefix list has one extra leading zero. Each later value stores the total number of ones seen so far. For the input [1, 0, 1, 1, 0], the prefix list is [0, 1, 1, 2, 3, 3]. To count ones from index 1 through index 3, compute prefix[4] minus prefix[1]. The result is 3 minus 1, which is 2.

1. Should I focus on Python language behavior, or also explain the runtime and standard library?
2. Which Python version and execution environment should I assume?
3. Would you like a small code example together with production tradeoffs and edge cases?

Python list indexing takes constant time, so each query performs two lookups and one subtraction. Preprocessing visits every input value once, so it takes O(n) time. The prefix list contains n plus one integers, so it uses O(n) extra memory.

The implementation should reject noninteger indexes, negative indexes, indexes outside the list, and ranges where start_idx is greater than end_idx. It should also validate that each input item is exactly the integer 0 or 1. The counter stores a snapshot of the totals, so later changes to the original list do not update the counter. This design is best for fixed data with many queries. Frequent value changes would require rebuilding the prefix data.

The RangeOneCounter constructor validates that every input item is exactly the integer 0 or 1. It then creates a prefix sum list with one extra leading zero. For each input item, it appends the previous total plus the current value. The getOne method validates both indexes and returns prefix[end_idx + 1] minus prefix[start_idx]. Construction takes O(n) time and O(n) extra memory. Each valid getOne call takes O(1) time. The stored totals are independent of later changes to the original input list.

A common mistake is summing a slice during every query. That makes each query take time proportional to the requested range and also allocates a new list for the slice. Another mistake is forgetting that end_idx is inclusive, which causes the wrong prefix position to be used. Candidates may also forget the leading zero, accidentally allow Python negative indexes, accept Boolean or floating point values as binary integers, fail to reject start_idx greater than end_idx, or assume later changes to the original list automatically update the stored prefix totals.

State the tradeoff first. Spend O(n) time and O(n) memory once, then answer every valid inclusive range query in O(1) time. Show the formula prefix[end_idx + 1] minus prefix[start_idx], explain the leading zero, and mention that updates require rebuilding the prefix data.

I would use binary search and return the index of any local minimum. I compare the middle value with each neighbor that exists. If it is smaller than both existing neighbors, I return its index. If the left neighbor is smaller, I search the left half. Otherwise, I search the right half. A boundary value is compared with only its existing neighbor. The solution takes O(log n) time and O(1) extra space.

The practical solution is to return the index of any local minimum with binary search. I assume the list is not empty and adjacent values are different. A value is a local minimum when it is smaller than every neighbor that exists. Therefore, the first and last positions need only one comparison. A list with one value has a local minimum at index zero.

1. Should I focus on Python language behavior, or also explain the runtime and standard library?
2. Which Python version and execution environment should I assume?
3. Would you like a small code example together with production tradeoffs and edge cases?

The function keeps inclusive left and right indexes. On each loop, it calculates the middle index without creating a new list. It checks the left neighbor only when the middle index is greater than zero. It checks the right neighbor only when the middle index is less than the final index. These conditions prevent invalid access.

If the middle value is smaller than both existing neighbors, the function returns it. If the left neighbor is smaller, a local minimum exists somewhere from the current left boundary through the left neighbor, so the search moves left. Otherwise, the search moves right. Each loop removes about half of the remaining indexes.

For [9, 7, 3, 5, 8], the function returns index 2, whose value is 3. The time cost is O(log n), and the extra memory cost is O(1).

The function returns the index of any strict local minimum. It raises ValueError for an empty sequence because no valid index exists. It keeps inclusive left and right boundaries and examines the middle position. A missing neighbor is treated as satisfying that side of the local minimum test, which safely handles index zero, the final index, and a sequence with one value. If the middle value is smaller than every existing neighbor, the function returns its index. If the left neighbor is smaller than the middle value, the function continues in the left half. Otherwise, it continues in the right half. For [9, 7, 3, 5, 8], it returns index 2, and the value at that index is 3.

Common mistakes include reading the left or right neighbor before checking whether that index exists. Another mistake is requiring two neighbors for the first or last value. Candidates also move the wrong search boundary after finding a smaller neighbor, which can remove the side that contains the guaranteed local minimum. List slicing is unnecessary because it creates new lists and increases memory use. Another error is ignoring the assumption that adjacent values are different. Without that assumption, equal values can make the chosen direction ambiguous.

State the strict local minimum definition and the input assumptions first. Then explain the boundary checks, the direction rule, and why each loop removes about half of the remaining indexes. Finish with O(log n) time and O(1) extra space.

I would use two pointers, one at each end of the string. While the characters match, I move both pointers inward. At the first mismatch, I try skipping either the left character or the right character. A helper checks whether the remaining range is a palindrome. If either check succeeds, I return True. This works because only one deletion is allowed. The solution takes O(n) time and O(1) auxiliary space.

The problem asks whether a string is already a palindrome or can become one after deleting at most one character. A palindrome reads the same in both directions. A two-pointer method fits because we can compare mirrored characters from the two ends. When the first mismatch appears, only the two mismatching characters can be candidates for the one deletion.

1. What input sizes, value ranges, and edge cases should the solution handle?
2. What output should be returned for empty, invalid, or duplicate input?
3. Should I prioritize execution time or memory use, and may I use the standard library?

The input is one string named s.

The output is a Boolean value. Return True when s is already a palindrome or can become one after deleting at most one character. Otherwise, return False.

For the diagram's example, s = "abca". The expected result is True because deleting 'b' at index 1 produces "aca".

Set left to the first index and right to the last index.

Compare s[left] with s[right]. If they match, move both pointers inward.

The central invariant is that every character outside the current inclusive range [left, right] has already matched its mirrored character. At most one deletion is still available until the first mismatch is handled.

For s = "abca", the indices are 0, 1, 2, and 3.

The characters are 'a', 'b', 'c', and 'a'.

Start with left = 0 and right = 3.

The helper is_palindrome(i, j) checks whether the inclusive range s[i:j + 1] is a palindrome. It also uses two pointers and does not create a new substring.

First, compare s[0] = 'a' with s[3] = 'a'.

They match, so move inward. The new state is left = 1 and right = 2.

Next, compare s[1] = 'b' with s[2] = 'c'.

They do not match. Because only one deletion is allowed, there are two possible choices. Skip the left mismatching character or skip the right mismatching character.

The code first calls is_palindrome(2, 2). This represents skipping 'b' at index 1.

The checked range contains only 'c'. A one-character string is a palindrome, so the helper returns True.

Python stops evaluating the or expression after this successful check. The second helper call is not executed for this example. The method returns True immediately.

All mirrored pairs before the first mismatch already match and can stay in the final palindrome.

At the first mismatch, one of the two mismatching characters must be removed. Deleting a different character would leave the current mismatch unresolved.

Therefore, checking the range after skipping the left character and the range after skipping the right character covers every possible valid one-deletion repair.

If either range is a palindrome, the original string can become a palindrome after at most one deletion.

The nested helper checks one inclusive range of the original string. It returns False at the first unequal mirrored pair. If its pointers meet or cross, the range is a palindrome and it returns True.

The main loop performs the same check on the complete string. Matching characters move both pointers inward.

At the first mismatch, the method returns the result of the two possible helper checks. This also stops any later processing.

If the main loop finishes without finding a mismatch, the original string is already a palindrome, so the method returns True.

The time complexity is O(n), where n is the string length. The main scan is linear. After the first mismatch, the helper examines at most the remaining range. The total work is still proportional to n.

The auxiliary space complexity is O(1). The algorithm stores only a few pointer variables and does not copy substrings.

Relevant edge cases include an empty string, a one-character string, an existing palindrome such as "racecar", a string fixed by one deletion such as "abca", and a string such as "abc" that cannot be fixed with only one deletion.

Use two pointers to compare mirrored characters from the outside inward. The invariant is that every character outside the current inclusive range [left, right] has already matched correctly. When the current characters match, move both pointers inward. At the first mismatch, one of those two mismatching characters must be the deleted character. Check the remaining range after skipping the left character and after skipping the right character. If either range is a palindrome, return True. Otherwise, return False.

The time complexity is O(n), where n is the length of the string. The main loop compares characters from both ends. If it finds a mismatch, one or two helper checks may examine the remaining range. Even in the worst case, the total number of comparisons is only a constant multiple of n, so the time remains O(n). The auxiliary space complexity is O(1) because the algorithm uses only pointer variables and does not create copied substrings.

A common mistake is checking only one deletion choice at the first mismatch. Candidates may always skip the left character or always skip the right character, but either choice can be wrong. Another mistake is moving the pointers before saving the mismatch positions. Some solutions create sliced strings, which adds extra memory. It is also incorrect to continue processing after the helper has found a valid result or to say that both helper calls always execute, because Python's or uses short-circuit evaluation.

When you reach the first mismatch, explain why the deleted character must be one of those two mismatching characters. Then test the two inclusive ranges (left + 1, right) and (left, right - 1).

I track the lowest price seen so far and the best profit found so far. I process the prices from left to right. For each price, I update the running minimum, calculate the profit from selling at the current price, and keep the larger profit. This preserves the buy-before-sell rule because the minimum comes only from processed days. The algorithm takes O(n) time and uses O(1) auxiliary space.

The input is a list of daily stock prices. We need the largest profit from one buy followed by one sell. If no profitable trade exists, we return 0. The best approach is to track the cheapest price seen so far and treat each current price as a possible selling price. This avoids checking every possible pair.

1. What input sizes, value ranges, and edge cases should the solution handle?
2. What output should be returned for empty, invalid, or duplicate input?
3. Should I prioritize execution time or memory use, and may I use the standard library?

Each list value is a stock price, and its index represents the day.

We must buy before we sell. The function returns the maximum profit, not the buy and sell indices.

For [7, 1, 5, 3, 6, 4], the best trade is:

• Buy at price 1, which is at index 1.
• Sell at price 6, which is at index 4.
• Profit is 6 - 1 = 5.

The returned result is 5.

I use two main variables:

• min_price stores the cheapest price seen so far.
• max_profit stores the largest valid profit found so far.

The invariant is that after processing index i, min_price is the minimum price in prices[0..i], and max_profit is the best one-transaction profit that can be made using the processed days.

A brute-force solution would compare every possible buy and sell pair. That takes O(n²) time. The running-minimum approach takes O(n) time.

Set min_price to infinity. This allows the first real price to become the first running minimum.

Set max_profit to 0. This is correct when prices only decrease because making no profitable trade should return 0.

Traversal begins at index 0.

At index 0, the price is 7.

• Minimum before: infinity.
• Update min_price to 7.
• Current profit: 7 - 7 = 0.
• Best profit remains 0.

At index 1, the price is 1.

• Minimum before: 7.
• Update min_price to 1.
• Current profit: 1 - 1 = 0.
• Best profit remains 0.

At index 2, the price is 5.

• The running minimum remains 1.
• Current profit: 5 - 1 = 4.
• Update the best profit to 4.

At index 3, the price is 3.

• The running minimum remains 1.
• Current profit: 3 - 1 = 2.
• This does not beat 4, so the best profit remains 4.

At index 4, the price is 6.

• The running minimum remains 1.
• Current profit: 6 - 1 = 5.
• Update the best profit to 5.

At index 5, the price is 4.

• The running minimum remains 1.
• Current profit: 4 - 1 = 3.
• This does not beat 5.

All six prices are processed. The function returns 5.

For each possible selling day, min_price represents the cheapest buying price from the processed days.

The algorithm calculates the profit from selling on the current day after using that running minimum. A positive profit can only come from a lower price on an earlier day. Therefore, it never uses a future price as the buy price.

Because every day is considered as a possible selling day and max_profit keeps the largest valid result, the final answer is the maximum one-transaction profit.

The loop visits prices from left to right.

First, it updates min_price with the current price. Next, it calculates current_profit by subtracting min_price from the current price. Then it updates max_profit if the current profit is larger.

After all prices are processed, the function returns max_profit.

The loop processes each price once, so the time complexity is O(n).

The algorithm stores only a few variables, so the auxiliary space complexity is O(1).

An empty list or a list with one price returns 0. A strictly decreasing list also returns 0. Equal and repeated prices are handled correctly.

The key insight is to treat every current price as a possible selling price. To find the best profit for that day, we only need the cheapest price seen so far. The algorithm keeps that value in min_price and keeps the largest calculated profit in max_profit. The invariant is that after processing index i, min_price is the minimum value in prices[0..i], and max_profit is the best valid one-buy, one-sell profit from the processed days. This produces the same result as checking all pairs but reduces the time from O(n²) to O(n).

The time complexity is O(n), where n is the number of prices. The loop processes each price once. The auxiliary space complexity is O(1) because the algorithm uses only min_price, current_profit, and max_profit. The amount of extra memory does not grow when the input becomes larger.

A common mistake is using a future price as the buying price. The running minimum must contain only the current and earlier processed prices. Another mistake is returning a negative profit when all prices decrease instead of keeping the answer at 0. Some candidates confuse the prices 1 and 6 with their indices 1 and 4. Others use nested loops and produce an unnecessary O(n²) solution. It is also incorrect to reset the best profit when a later current profit is smaller.

Explain the invariant before coding: min_price is the cheapest processed price, and max_profit is the best valid profit from the processed days. Then make each code line match that invariant.

I first sort the intervals by their start value. Then I keep a merged list and compare each next interval with the last merged interval. If the next start is less than or equal to the last end, the intervals overlap or touch, so I extend the last end. Otherwise, I append a new interval. Sorting makes possible overlaps adjacent. The total time is O(n log n), and the result uses O(n) space in the worst case.

The problem gives a list of intervals and asks us to combine all overlapping intervals. The result must cover exactly the same ranges without overlaps. The main idea is to sort the intervals by their start value. After sorting, any interval that can overlap the current merged range appears next to it, so we can build the answer with one forward traversal.

1. What input sizes, value ranges, and edge cases should the solution handle?
2. What output should be returned for empty, invalid, or duplicate input?
3. Should I prioritize execution time or memory use, and may I use the standard library?

The input is a list of intervals. Each interval contains a start value and an end value.

The example input is [[8,10], [1,3], [15,18], [2,6]].

The expected output is [[1,6], [8,10], [15,18]]. The output covers exactly the same ranges as the input, but it is sorted and contains no overlapping intervals.

The diagram treats endpoints as inclusive. Therefore, touching intervals also merge. For example, [1,4] and [4,5] merge into [1,5].

Sort the intervals by their start value. The sorted order is [[1,3], [2,6], [8,10], [15,18]].

Create a list named merged. Put a copy of the first sorted interval into it. The initial state is [[1,3]].

The central invariant is that merged is always sorted, non-overlapping, and equal to the exact union of all intervals processed so far.

For each next interval [start, end], compare start with the end of the last interval in merged.

If start <= merged[-1][1], the intervals overlap or touch. Update the last end to max(merged[-1][1], end).

If start > merged[-1][1], there is a gap. Append [start, end] as a new merged interval.

Start with merged = [[1,3]].

Process [2,6]. The state before is [[1,3]]. Check 2 <= 3. The condition is true, so the intervals overlap. Set the last end to max(3,6), which is 6. The state becomes [[1,6]].

Process [8,10]. The state before is [[1,6]]. Check 8 <= 6. The condition is false, so there is a gap. Append [8,10]. The state becomes [[1,6], [8,10]].

Process [15,18]. The state before is [[1,6], [8,10]]. Check 15 <= 10. The condition is false, so append [15,18]. The final state is [[1,6], [8,10], [15,18]].

Sorting places possible overlaps beside each other. Because merged is already sorted and non-overlapping, a new interval only needs to be compared with the last merged interval.

When the next start is less than or equal to the last end, extending the last end preserves the full covered range. When the next start is greater than the last end, no earlier merged interval can overlap the new interval, so appending it is safe.

After every step, the invariant remains true. Therefore, the final list is sorted, non-overlapping, and covers exactly the same ranges as the input.

The function first handles an empty input by returning an empty list. It sorts the input list in place using each interval's start value.

It initializes merged with a copy of the first sorted interval. The loop then processes every remaining interval in sorted order. It reads the end of the last merged interval, checks the overlap condition, and either updates that end or appends a new interval.

After all intervals are processed, the function returns merged.

Sorting takes O(n log n) time. The merge traversal takes O(n) time. Therefore, the total time is O(n log n).

The returned merged list may contain up to n intervals, so it uses O(n) space when the output is counted, matching the diagram.

Important edge cases are an empty input, one interval, completely disjoint intervals, nested intervals such as [1,10] and [2,5], and touching intervals such as [1,4] and [4,5].

Sort all intervals by their start value. This places intervals that may overlap next to each other. Maintain a list named merged. Its invariant is that it is sorted, contains no overlaps, and represents the exact union of every interval processed so far. Compare each new interval only with the last merged interval. If the new start is less than or equal to the last end, extend the last end to the larger end value. Otherwise, append a new interval.

Let n be the number of intervals. Sorting takes O(n log n) time. The merge loop processes the intervals in one forward pass, which takes O(n) time. The total time is therefore O(n log n). The merged result may contain n intervals when none overlap, so the diagram reports O(n) space for the output. The input list itself is sorted in place.

A common mistake is forgetting to sort by the start value. Another is comparing the new interval with something other than the last merged interval. Using start < last_end instead of start <= last_end would fail to merge touching intervals under the diagram's inclusive-endpoint rule. Replacing the last end with end instead of max(last_end, end) fails for nested intervals. Candidates may also forget the empty-input case or incorrectly claim O(n) total time while ignoring sorting.

Before writing code, state the invariant clearly: merged is always sorted, non-overlapping, and covers exactly all intervals processed so far.

I would use Python’s OrderedDict to store each key-value pair and track its usage order. The leftmost key is the least recently used, and the rightmost key is the most recently used. On a successful get, I move the key to the right end and return its value. On put, I insert or update the key, move it to the right end, and remove the leftmost key if capacity is exceeded. Both operations take O(1) average time, with O(capacity) auxiliary space.

The problem asks us to build a cache with a fixed capacity. get(key) must return the stored value or -1. put(key, value) must insert or update a key. When the cache becomes too large, it must remove the least recently used key. Python’s OrderedDict fits because it stores key-value pairs in order and supports moving and removing entries in O(1) average time.

1. What input sizes, value ranges, and edge cases should the solution handle?
2. What output should be returned for empty, invalid, or duplicate input?
3. Should I prioritize execution time or memory use, and may I use the standard library?

The cache stores at most capacity entries.

get(key) returns the stored value when the key exists. It returns -1 when the key is missing.

put(key, value) inserts a new key or updates an existing key. It returns None. If the cache size becomes greater than capacity, it removes the least recently used key.

The OrderedDict stores key to value pairs.

Its order represents usage order. The leftmost entry is the least recently used entry. The rightmost entry is the most recently used entry.

The main invariant is that each cached key appears exactly once, and the dictionary order is always LRU to MRU.

First, check whether the key exists.

If it is missing, return -1. The cache order stays unchanged.

If it exists, call move_to_end(key). This moves the key to the right end, so it becomes the most recently used key. Then return its stored value.

If the key already exists, move it to the right end. Then store the new value.

If the key is new, assigning the value inserts it at the right end.

After the assignment, compare the cache size with capacity. If the size is too large, call popitem(last=False). The argument last=False removes the leftmost entry, which is the least recently used entry.

The capacity is 3.

Start with an empty cache: {}.

put(1,10) gives {1:10}.

put(2,20) gives {1:10, 2:20}.

put(3,30) gives {1:10, 2:20, 3:30}.

get(2) returns 20. Key 2 moves to the MRU position. The order becomes {1:10, 3:30, 2:20}.

put(4,40) first creates four entries. Key 1 is the leftmost and least recently used key, so it is removed. The cache becomes {3:30, 2:20, 4:40}.

get(1) returns -1 because key 1 is no longer present. The state remains {3:30, 2:20, 4:40}.

The final LRU-to-MRU key order is [3, 2, 4]. The final MRU-to-LRU key order is [4, 2, 3].

Every successful get moves its key to the right end. Every put also places its key at the right end. Therefore, the rightmost key is always the most recently used key.

The leftmost key is the key that has gone the longest without being accessed or updated. When the cache exceeds capacity, removing the leftmost entry removes exactly the least recently used key.

OrderedDict lookup, assignment, move_to_end, and popitem take O(1) average time. Therefore, get and put each take O(1) average time.

The cache stores at most capacity entries, so the auxiliary space is O(capacity).

Important cases include a missing key, updating an existing key, capacity 1, and repeated gets on the same key.

The key insight is to store both values and recency order in one OrderedDict. The central invariant is that entries are ordered from LRU on the left to MRU on the right. A successful get moves its key to the right end. A put inserts or updates a key and also places it at the right end. If the size exceeds capacity, removing the leftmost entry evicts exactly the least recently used key. This is more suitable than a plain dictionary because OrderedDict directly supports moving a key and removing the oldest entry in O(1) average time.

Each get operation takes O(1) average time. It performs an OrderedDict lookup and may move one key to the end. Each put operation also takes O(1) average time. It assigns one value, may move one key, and may remove one leftmost entry. These OrderedDict operations are constant time on average, not guaranteed constant time in every worst case. The cache stores at most capacity entries, so the auxiliary space is O(capacity).

A common mistake is returning a value without moving the accessed key to the MRU position. Another mistake is evicting the rightmost key instead of the leftmost key. Some candidates remove an entry before the cache size actually exceeds capacity. Others forget that updating an existing key must also make it most recently used. It is also incorrect to claim guaranteed O(1) worst-case time because OrderedDict operations are O(1) on average.

State the invariant before writing code: the leftmost entry is LRU, and the rightmost entry is MRU. Then explain each operation using that rule. A successful get moves right, a put places the key right, and overflow removes one key from the left.

I would use breadth-first search with a deque. I process the tree one level at a time from left to right. At each level, I append the value of the last node removed from the queue because that node is visible from the right side. I add each node’s left child before its right child. Every node is enqueued and dequeued once, so the time complexity is O(n). The auxiliary space is O(w), where w is the maximum tree width.

The input is the root of a binary tree. We must return one node value from each level, representing what is visible from the right side. Breadth-first search fits this problem because it naturally visits the tree level by level. By processing each level from left to right, the last node processed at that level is the visible node.

1. What input sizes, value ranges, and edge cases should the solution handle?
2. What output should be returned for empty, invalid, or duplicate input?
3. Should I prioritize execution time or memory use, and may I use the standard library?

The input is a reference to the root of a binary tree. The tree is not assumed to be a binary search tree.

The output is a list of node values. It contains one visible value from every level, ordered from the root level to the deepest level.

For the displayed tree, the levels are [1], [2, 3], [4, 5, 7], and [6]. The returned right-side view is [1, 3, 7, 6].

I use breadth-first search, also called BFS. BFS processes the tree one level at a time.

A deque stores nodes that are waiting to be processed. It supports efficient removal from the front and insertion at the back.

The central rule is that nodes in each level are processed from left to right. Therefore, the final node removed at that level is the rightmost visible node.

I create an empty list named result.

If root is None, the tree is empty, so I return result immediately.

Otherwise, I place the root in the deque. For the example, the initial queue is [1], and the initial result is [].

At level 0, the queue is [1]. The level size is 1. I remove node 1. It is the last node in this level, so I append 1. I then add its left child 2 and right child 3. The result is [1].

At level 1, the queue is [2, 3]. The level size is 2. I remove node 2 and add its children 4 and 5. I then remove node 3. It is the last node in the level, so I append 3. I add its right child 7. The result is [1, 3].

At level 2, the queue is [4, 5, 7]. The level size is 3. I process node 4, then node 5, then node 7. Node 5 adds its left child 6. Node 7 is the last node in this level, so I append 7. The result is [1, 3, 7].

At level 3, the queue is [6]. The level size is 1. I remove node 6. It is the last node in the level, so I append 6. The result becomes [1, 3, 7, 6].

The queue is now empty, so the traversal stops and the function returns [1, 3, 7, 6].

At the start of each outer-loop iteration, the queue contains the nodes of the next level in left-to-right order.

The inner loop removes exactly those nodes. Because the final removed node is the rightmost node in that level, appending its value records the correct visible value.

Repeating this for every level produces the complete right-side view from top to bottom.

The outer while loop continues while the deque contains nodes.

At the start of a level, level_size stores the current queue length. This separates the current level from children added for the next level.

The inner loop removes exactly level_size nodes. When i equals level_size - 1, the current node is the final node in that level, so its value is appended to result.

The code adds the left child before the right child. This preserves left-to-right processing order.

The time complexity is O(n), where n is the number of nodes. Every node is added to the deque once and removed once.

The auxiliary space complexity is O(w), where w is the maximum number of nodes stored in the queue at one level.

An empty tree returns []. A tree with one node returns [root.val]. In a left-skewed or right-skewed tree, every node appears in the result because each level contains one node.

The key insight is to process the binary tree level by level with BFS. A deque stores the nodes waiting to be visited. At the beginning of each level, its current length gives the number of nodes that belong to that level. The algorithm removes those nodes from left to right and records the value of the final removed node. The invariant is that the queue presents each current level in left-to-right order, so its last processed node is exactly the node visible from the right side.

The time complexity is O(n), where n is the total number of nodes. Each node enters the deque once and leaves it once. The auxiliary space complexity is O(w), where w is the maximum number of nodes stored in the queue at one level. A wide tree may therefore use more queue memory than a narrow tree.

A candidate may record the first node at each level, which produces the left-side view. Another mistake is to let the inner loop use a changing queue length instead of saving level_size first. Some candidates add right children before left children but still record the final node, which changes the meaning of the invariant. Using list.pop(0) instead of deque.popleft() makes front removal slower. It is also incorrect to assume that the input follows binary search tree ordering.

State the invariant before writing code: because each level is processed from left to right, the last node removed from that level is the node visible from the right side.

I would use a min heap. I place the first value from each non-empty sorted array into the heap as a tuple containing the value, array index, and element index. Each next() call removes the smallest tuple, returns its value, and pushes the next value from the same array when one exists. The heap therefore always exposes the next global minimum. Initialization is O(k), each next() call is O(log k), all N values take O(N log k), and extra space is O(k).

The class receives k arrays that are already sorted. It must return one smallest remaining value on every next() call. A min heap fits this problem because it quickly exposes the smallest current candidate. We keep only one candidate from each unfinished array, so the values are produced lazily instead of building the complete merged list first.

1. What input sizes, value ranges, and edge cases should the solution handle?
2. What output should be returned for empty, invalid, or duplicate input?
3. Should I prioritize execution time or memory use, and may I use the standard library?

The input is a list of k sorted integer arrays.

For the example:

A0 = [1, 4, 4] A1 = [1, 3, 5] A2 = [2, 6]

The class returns one value per next() call. Consecutive calls return:

[1, 1, 2, 3, 4, 4, 5, 6]

After every value has been returned, another call to next() raises StopIteration.

Python heapq implements a min heap. This means the smallest tuple is always available at the top.

Each heap entry is:

(value, array_index, element_index)

The value controls the heap order. The array index identifies the source array. The element index identifies the value's position inside that array.

The central invariant is that the heap contains the smallest not-yet-returned value from every array that still has remaining elements.

We save the input arrays and create an empty heap.

For every non-empty array, we add its first value. For the example, the initial logical heap contents are:

(1, A0, 0), (1, A1, 0), (2, A2, 0)

In the Python code, A0, A1, and A2 are represented by array indices 0, 1, and 2. Empty arrays are skipped. We then call heapify to build the min heap.

Step 1 starts with [(1,A0,0), (1,A1,0), (2,A2,0)]. We pop (1,A0,0), so next() returns 1. The next value in A0 is A0[1] = 4, so we push (4,A0,1). The heap becomes [(1,A1,0), (2,A2,0), (4,A0,1)].

Step 2 pops (1,A1,0). We return 1. The next value in A1 is A1[1] = 3, so we push (3,A1,1). The heap becomes [(2,A2,0), (3,A1,1), (4,A0,1)].

Step 3 pops (2,A2,0). We return 2. The next value in A2 is A2[1] = 6, so we push (6,A2,1). The heap becomes [(3,A1,1), (4,A0,1), (6,A2,1)].

Step 4 pops (3,A1,1). We return 3. The next value in A1 is A1[2] = 5, so we push (5,A1,2). The heap becomes [(4,A0,1), (5,A1,2), (6,A2,1)].

Step 5 pops (4,A0,1). We return 4. The next value in A0 is A0[2] = 4, so we push (4,A0,2). The heap becomes [(4,A0,2), (5,A1,2), (6,A2,1)].

Step 6 pops (4,A0,2). We return 4. A0 has no later value, so nothing is pushed. The heap becomes [(5,A1,2), (6,A2,1)].

Step 7 pops (5,A1,2). We return 5. A1 is exhausted, so nothing is pushed. The heap becomes [(6,A2,1)].

Step 8 pops (6,A2,1). We return 6. A2 is exhausted, so nothing is pushed. The heap becomes empty.

The final sequence is [1, 1, 2, 3, 4, 4, 5, 6]. All eight input values appear exactly once in nondecreasing order.

Before every next() call, the heap contains the smallest remaining value from each unfinished array. Any later value in one of those arrays cannot be smaller than its current candidate because each array is sorted.

Therefore, the smallest value in the heap is also the smallest value remaining across all arrays. After removing it, we add the next value from the same array. This restores the invariant for the following call.

The constructor stores the arrays and builds a heap containing the first value from every non-empty array.

The next() method first checks whether the heap is empty. If it is empty, there are no remaining values, so it raises StopIteration.

Otherwise, the method removes the smallest tuple. It calculates next_index = element_index + 1. If that position exists in the same array, it pushes the successor into the heap. It then returns the popped value.

Let k be the number of input arrays and N be the total number of values.

Initialization takes O(k) time because we inspect each array, add at most one item from it, and heapify at most k entries. Each next() call performs one heappop and at most one heappush. These operations take O(log k), so returning all N values takes O(N log k) time.

The heap contains at most one entry per unfinished array, so auxiliary space is O(k).

Empty arrays are skipped. Duplicate values are handled correctly. One non-empty array is returned in its original order. Calling next() after the heap is empty raises StopIteration.

The key idea is to keep only the smallest remaining candidate from each unfinished array. A min heap is suitable because it exposes the smallest candidate in O(log k) time when it is removed. Each heap entry stores the value, its source array, and its position in that array. After removing the smallest entry, we add only the next value from the same sorted array. The invariant is that the heap always contains the smallest remaining value from every unfinished array. This produces the merged order lazily and keeps the heap size at most k.

Let k be the number of arrays and N be the total number of values. Initialization takes O(k) time because the code visits each array, stores at most one initial item from it, and heapifies at most k items. Each next() call performs one heap removal and at most one heap insertion. Each operation takes O(log k), so one next() call is O(log k). Returning all N values takes O(N log k) total time. The heap stores at most k tuples, so auxiliary space is O(k).

A common mistake is adding every value from every array to the heap. That uses O(N) extra space and removes the lazy streaming benefit. Another mistake is storing only the value, which loses the source array and position needed to find its successor. Candidates may also forget to push the next value from the same array, fail to skip empty arrays, or forget to raise StopIteration after exhaustion. It is also incorrect to claim O(1) time per next() call or O(1) auxiliary space.

State the invariant before writing code: the heap contains one smallest remaining candidate from every unfinished array. Then explain how each pop and optional push restores that invariant.