Google .NET Developer Interview Questions & Answers

I would use dynamic programming with a Boolean table. I define dp[i, j] as whether the first i characters of the text match the first j characters of the pattern. I start with dp[0, 0] = true, handle '*' states that can match an empty text, and then fill the table from smaller prefixes to larger ones. Literals and '.' use the diagonal state, while '*' handles zero or more copies. Time is O(m × n), with O(m × n) auxiliary space.

The input has a text string and a simple pattern. The pattern supports normal characters, '.' for any one character, and '*' for zero or more copies of the token immediately before it. We must match the whole text, not search for a matching part. The output is true when the complete text matches the complete pattern and false otherwise. In the diagram, text is "acb" and pattern is "a.*b". The result is true. A dynamic programming table fits because each larger match can be built from smaller prefix matches.

1. Can I assume every '*' has a valid token immediately before it?
2. Should matching cover the entire text rather than search for a matching substring?
3. Are literals, '.', and '*' the only supported pattern features?

Let m = text.Length and n = pattern.Length. Create a Boolean table dp with m + 1 rows and n + 1 columns. The state dp[i, j] means that the first i characters of text match the first j characters of pattern completely.

For the diagram example, text = "acb", so m =

3. The pattern is "a.*b", so n =
4. The final answer is stored in dp[3, 4].

This is full-string matching. A true final cell means the whole input matches. A false final cell means a non-match.

Start with dp[0, 0] = true because an empty text matches an empty pattern.

Then initialize the first row for patterns containing '*'. A '*' can use zero copies of the token before it, so when pattern[j - 1] is '*', the empty-text state is dp[0, j] = dp[0, j - 2].

For this example, pattern[2] is '*'. Therefore dp[0, 3] = dp[0, 1] = false.

The invariant is that every filled dp[i, j] cell correctly describes whether those two complete prefixes match.

Process i from 1 through m and j from 1 through n. Look at pattern[j - 1].

If it is a normal literal, it must equal text[i - 1]. If it is '.', it can match any one current text character. When the current token matches, use dp[i - 1, j - 1]. This removes one character from both prefixes and asks whether the remaining prefixes already match.

For example, dp[1, 1] starts from dp[0, 0]. The current text character is 'a' and the current pattern character is 'a'. They match, and dp[0, 0] is true, so dp[1, 1] becomes true.

Later, dp[2, 2] uses dp[1, 1]. The current text character is 'c' and the current pattern token is '.'. The '.' matches 'c', and dp[1, 1] is true, so dp[2, 2] becomes true.

When pattern[j - 1] is '*', there are two valid cases.

For zero occurrences, skip both '*' and the token before it. Use dp[i, j - 2]. In the example, dp[1, 3] is calculated from dp[1, 1]. Before this step, dp[1, 1] is true. The ".*" part can use zero characters, so dp[1, 3] becomes true.

For one or more occurrences, first check whether the token before '*' matches text[i - 1]. If it does, consume one text character but stay at the same pattern position. Use dp[i - 1, j]. Staying at j is important because '*' may match another character.

For dp[2, 3], the previous pattern token is '.'. It matches text[1] = 'c'. Before this step, dp[1, 3] is true, so extending '*' makes dp[2, 3] true.

For dp[3, 3], '.' also matches text[2] = 'b'. Before this step, dp[2, 3] is true, so extending '*' again makes dp[3, 3] true.

The important true states shown in the diagram are:

1. dp[1, 1] = true because 'a' matches 'a' and dp[0, 0] is true.
2. dp[1, 3] = true because '*' uses zero occurrences and dp[1, 1] is true.
3. dp[2, 2] = true because '.' matches 'c' and dp[1, 1] is true.
4. dp[2, 3] = true because '*' extends the match from dp[1, 3].
5. dp[3, 3] = true because '*' extends the match from dp[2, 3].
6. dp[3, 4] = true because the final pattern character 'b' matches text[2] = 'b' and dp[2, 3] is true.

The final DP grid is: Ø: T F F F F a: F T F T F c: F F T T F b: F F F T T

Therefore dp[3, 4] = true, so "acb" matches "a.*b". The method returns true. If dp[m, n] were false, the correct non-match return value would be false.

The solution is correct because each state follows the definition of dp[i, j]. A literal or '.' consumes exactly one character from the text and one token from the pattern, so it uses dp[i - 1, j - 1]. A '*' covers both legal choices: zero copies with dp[i, j - 2], or one or more copies with dp[i - 1, j] when the previous token matches.

There are O(m × n) table cells, and each cell needs constant work. Therefore the time complexity is O(m × n). The table uses O(m × n) auxiliary space.

Important edge cases include empty text with an empty pattern returning true, empty text matching a pattern such as "a*", '*' representing zero characters, and a non-match such as text = "ab" with pattern = "a*c" returning false.

The key insight is to solve the match for every pair of text and pattern prefixes. The invariant is: dp[i, j] is true exactly when the first i characters of text match the first j characters of pattern completely. This works because each state depends on smaller states that are already known. A matching literal or '.' uses dp[i - 1, j - 1]. A '*' either skips itself and its previous token with dp[i, j - 2], or consumes another matching text character while staying at the same pattern position with dp[i - 1, j]. The final result is dp[m, n].

Let m be text.Length and n be pattern.Length. The algorithm fills a table with (m + 1) × (n + 1) Boolean cells. Each cell needs constant work, so the time complexity is O(m × n). The dynamic programming table grows with both input lengths, so the auxiliary space complexity is O(m × n). Auxiliary space means the extra memory used by the algorithm.

A common mistake is treating the task as substring search instead of full-string matching. Another is forgetting that '*' applies only to the immediately preceding token. Candidates may also use the wrong DP dependency for '*': zero occurrences must use dp[i, j - 2], while one or more occurrences use dp[i - 1, j] only when the previous token matches the current text character. A fourth mistake is forgetting the first-row initialization that lets patterns such as "a*" match an empty text.

Define dp[i, j] clearly before writing the recurrence. Then explain '*' as two separate choices: use zero copies and move back two pattern positions, or consume one matching text character and stay at the same pattern position.

I would build a HashSet from the user’s seen job IDs, then sort candidate jobs by relevance score from highest to lowest. I would scan that ranked list, skip jobs already in the seen set, and use another HashSet so the same job ID cannot be suggested twice. I stop when I collect K valid jobs. The time is O(n log n) because of sorting. With the shown LINQ implementation, auxiliary space is O(n + m + k).

The problem asks us to choose the best job suggestions for a user. We know which job IDs the user has already seen. We also have candidate jobs with relevance scores. Higher scores are better. We must return up to K jobs, ordered from highest score to lowest score. A returned job must not already be in the user history, and the same job ID must not appear twice. We rank the candidates first, then filter them while collecting the first K valid jobs.

1. Is the relevance score already calculated for every candidate job?
2. Should higher scores always appear before lower scores in the result?
3. Can the candidate list contain the same job ID more than once?
4. What should we return when fewer than K unseen jobs exist?

The diagram uses seen job IDs [1, 4, 7], nine candidate jobs, and K = 3. Each candidate has a job ID and a relevance score. We need up to three job IDs that the user has not already seen. The returned IDs must also be unique. The output is ordered by relevance score from highest to lowest.

I use a HashSet<int> called seen for the user history. This gives O(1) average-time membership checks. I sort all candidate jobs by descending relevance score. I also use another HashSet<int> called added. It records job IDs already placed in the result, so duplicate candidate IDs cannot create duplicate suggestions.

The main invariant is simple: the result always contains only unseen, unique job IDs, accepted in descending relevance-score order.

Start with seen = {1, 4, 7}. The result list is empty, and the added set is empty. Sorting the example candidates by score gives job IDs in this order: 1, 2, 3, 4, 5, 6, 7, 8, 9.

Job 1 has score 0.91. Its ID is in seen, so we skip it. The result remains [].

Job 2 has score 0.88. It is not in seen, and its ID has not been added before. We add it. The result becomes [2], and added becomes {2}.

Job 3 has score 0.87. It is unseen and unique, so we add it. The result becomes [2, 3], and added becomes {2, 3}.

Job 4 has score 0.85. Its ID is in seen, so we skip it. The result remains [2, 3].

Job 5 has score 0.83. It is unseen and unique, so we add it. The result becomes [2, 3, 5]. The result count is now equal to K, so processing stops. Jobs 6, 7, 8, and 9 are not processed.

Sorting makes us consider higher-scoring jobs before lower-scoring jobs. The seen set prevents an already-viewed job from entering the result. The added set prevents the same job ID from entering the result more than once. Therefore every accepted job is unseen and unique. Because we stop after the first K valid jobs in descending score order, the example correctly returns [2, 3, 5].

The code creates the seen set, sorts candidates with OrderByDescending, creates result and added, and then scans the ranked candidates. A seen job is skipped. A duplicate job ID is also skipped. Otherwise its ID is appended to the result. When result.Count == k, the loop stops immediately and the result is returned.

Sorting N candidates takes O(N log N) time. The filtering scan is O(N), with O(1) average-time HashSet lookup and insertion. The total time is therefore O(N log N). In the executable implementation below, OrderByDescending(...).ToList() creates a ranked copy, so auxiliary space is O(N + M + K), where M is the history size and K is the number of collected recommendations. Important cases are K <= 0, no candidates, all candidates already seen, fewer than K valid jobs, and duplicate candidate IDs.

The key idea is to separate ranking from filtering. First, sort all candidate jobs from highest relevance score to lowest. Then scan that order and accept a candidate only if its job ID is not in the user's history and has not already been added. The central invariant is that the result always contains only unseen, unique jobs in the same descending-score order in which they were accepted. Once K valid jobs have been collected, later candidates cannot improve the required top-K result, so processing stops.

Let N be the number of candidate jobs, M be the number of job IDs in the user history, and K be the requested number of recommendations. Sorting takes O(N log N) time. The later scan takes O(N) time. HashSet lookup and insertion are O(1) on average, so the total time is O(N log N). In the shown executable C# implementation, the sorted List copy requires O(N) memory. Together with the history set, duplicate-prevention set, and result, auxiliary space is O(N + M + K).

A common mistake is filtering seen jobs but forgetting that candidate data can contain duplicate job IDs. Another mistake is not ranking candidates before selecting the first K valid jobs. It is also wrong to continue processing after K recommendations have already been collected. Candidates may forget to handle K <= 0 or a list with fewer than K valid jobs. Finally, claiming O(N) total time is incorrect for this implementation because sorting costs O(N log N), and ignoring the ranked copy would understate its auxiliary memory.

State the invariant before writing the loop: every item already in the result is unseen, unique, and was encountered in descending score order. That makes the seen check, added check, and early stop at K easy to justify.

I would start from every outer-border cell because water can escape from the border. I put those cells in a min-heap and always process the lowest effective boundary first. I keep a running boundary level. For each unvisited neighbor, I add max(0, boundary level - terrain height), then push that neighbor with its effective height and mark it visited. The algorithm takes O(m × n × log(m × n)) time and O(m × n) auxiliary space.

We are given a grid where each number is the height of one terrain cell. Rain can move up, down, left, or right. Water can escape through the outside border, so border cells form the starting boundary. We need to find how much water remains above lower interior cells after raining. A min-heap fits this problem because it always gives us the lowest current boundary first. From that boundary, we can safely decide whether an unvisited neighboring cell can hold water.

1. Can I assume every terrain height is a non-negative integer?
2. Does water move only in the four directions shown: up, down, left, and right?
3. Should an empty grid or a grid with fewer than three rows or three columns return 0?

The input is an m × n elevation grid. Each number is the terrain height of one cell. The output is one integer: the total units of trapped rain water. Outer-border cells cannot trap water because water can escape directly outside the grid.

The diagram uses this 4 × 6 grid: [1, 4, 3, 1, 3, 2] [3, 2, 1, 3, 2, 4] [2, 3, 3, 2, 3, 1] [1, 2, 1, 2, 1, 2]

The final trapped-water result is 4.

I use a min-heap. In .NET, PriorityQueue<TElement, TPriority> removes an element with the lowest priority first. Each heap element stores an effective height, row, and column. The priority is that effective height.

I also use a visited grid. A cell is marked visited when it is added to the heap. This prevents the same cell from being added more than once.

The main invariant is that the min-heap exposes the lowest effective boundary available, while the running boundary level never decreases.

I add every outer-border cell to the min-heap and mark each one visited. I set water to 0 and maxHeight to 0.

The border is the correct starting point because those cells are where water can leave the terrain. Processing inward from the border lets the algorithm discover how high water may safely rise around each interior cell.

Each time a cell is removed from the min-heap, I update maxHeight with max(maxHeight, poppedHeight). Then I examine the four neighboring positions.

The diagram highlights three positive-water discoveries in this order.

Step 1: Cell (1,2) has terrain height 1. The boundary level is 3. It adds 3 - 1 = 2 units of water.

Step 2: Cell (1,1) has terrain height

2. The boundary level is
3. It adds 3 - 2 = 1 unit of water.

Step 3: Cell (1,4) has terrain height

2. The boundary level is
3. It adds 3 - 2 = 1 unit of water.

All remaining processed cells add 0 water. The min-heap eventually becomes empty. The final total is 2 + 1 + 1 = 4.

The final water-level grid shown by the solution is: [1, 4, 3, 1, 3, 2] [3, 3, 3, 3, 3, 4] [2, 3, 3, 2, 3, 1] [1, 2, 1, 2, 1, 2]

The min-heap always exposes the lowest effective boundary available. The running boundary level never decreases. When an unvisited neighbor is lower than that boundary level, the difference is trapped water. If the neighbor is at least as high as the boundary, it traps no new water and becomes part of the boundary at its own height.

The code first returns 0 for a null, empty, or too-small grid. It creates a visited array and a PriorityQueue. It inserts every border cell exactly once. During processing, it removes a lowest-priority boundary cell, updates maxHeight, checks four neighbors, skips invalid or visited positions, marks each new neighbor visited, adds any trapped water, and pushes that neighbor with effective height max(neighborHeight, maxHeight). The heap stops when no cells remain.

There are m × n cells. Each cell is inserted into and removed from the min-heap at most once. Each heap operation costs O(log(m × n)), so total time is O(m × n × log(m × n)). The visited grid and heap together require O(m × n) auxiliary space.

The diagram's relevant edge cases are an empty or too-small grid, all cells having the same height, and flat or strictly increasing terrain. These cases trap 0 water.

The key idea is to treat the outer border as the first water boundary and expand inward. Water can escape through an outer cell, so the algorithm starts by placing every border cell in a min-heap. The heap exposes a lowest effective boundary next. After a cell is popped, maxHeight becomes max(maxHeight, poppedHeight). For each unvisited neighbor, the algorithm adds max(0, maxHeight - neighborHeight), then pushes that neighbor with effective height max(neighborHeight, maxHeight). The invariant is that the available boundary is processed from low to high while the running boundary level never decreases. Equal-priority heap items do not need a stable order for the final trapped-water total to remain correct.

Let m be the number of rows and n be the number of columns. The grid has m × n cells. Every cell is added to the min-heap at most once and removed from it at most once. A heap operation costs O(log(m × n)), so total time is O(m × n × log(m × n)). The visited grid uses O(m × n) memory, and the heap can also contain O(m × n) cells. Therefore the auxiliary space is O(m × n).

Starting from interior cells instead of the outer boundary is a common mistake. Another mistake is using a normal FIFO queue instead of a min-heap, which loses the lowest-boundary processing rule. Marking a cell visited too late can insert it into the heap more than once. Candidates may also calculate water from only the neighbor height without using the current effective boundary level. Another mistake is pushing a low neighbor with its original terrain height instead of its effective raised height. Finally, O(m × n) time is incorrect because heap insertion and removal add a logarithmic factor.

Explain the boundary invariant before coding: all outer cells enter the min-heap first, the lowest effective boundary is processed next, and any lower unvisited neighbor traps the difference up to the current boundary level.

I would use the Space-Saving heavy-hitter algorithm with a fixed budget of M counters. I keep a Dictionary for fast lookup of tracked items and a min-ordered SortedSet for the counters. For each stream item, I increment its counter, insert it if space remains, or replace the smallest counter when memory is full. This gives an approximate top-K without storing the full history. Processing n items takes O(n log M) expected time, with O(M) auxiliary space.

The stream can continue forever, so storing every item or every exact frequency may eventually use too much memory. We need a method that keeps only a fixed number of counters and still identifies the strongest frequency candidates. The diagram uses the Space-Saving algorithm. It stores at most M counters. Each counter has an item, an estimated count, and an error value. A dictionary finds tracked items quickly, while a min-ordered SortedSet lets us find and replace the smallest counter when memory is full.

1. Is an approximate top-K answer acceptable when the memory budget is strictly limited?
2. Is M guaranteed to be at least K?
3. If two candidates have the same estimated count, can they be returned in any order?

The input is an unbounded stream of elements, a target K, and a fixed memory budget M. We cannot keep the complete history. The output is the current top-K heavy-hitter candidates. Because memory is fixed, the answer is approximate rather than guaranteed exact for every possible stream.

I use the Space-Saving algorithm. It keeps at most M counters. Each counter stores an Item, an Estimate, and an Error. A Dictionary maps each tracked item to its Counter object. A SortedSet orders counters by Estimate and then by a unique Id, so the smallest counter is available quickly. The main invariant is that the algorithm never stores more than M counters. For a tracked item, Estimate - Error is a lower bound on its true frequency, and Estimate is an upper bound.

Start with an empty Dictionary and an empty SortedSet. The capacity is M. No counters are allocated yet. When a new item arrives and fewer than M counters are in use, create a counter with Estimate = 1 and Error = 0.

Use stream [A, A, B, A, C, B, B, D, B, E, A, B], K = 2, and M = 3.

Step 1, A: state {}. A is not tracked and space remains. Insert A(1,0). State becomes {A(1,0)}. Step 2, A: A is tracked. Increment A. State becomes {A(2,0)}. Step 3, B: B is new and space remains. Insert B(1,0). State becomes {A(2,0), B(1,0)}. Step 4, A: increment A. State becomes {A(3,0), B(1,0)}. Step 5, C: C is new and space remains. Insert C(1,0). State becomes {A(3,0), B(1,0), C(1,0)}. Step 6, B: increment B. State becomes {A(3,0), B(2,0), C(1,0)}. Step 7, B: increment B. State becomes {A(3,0), B(3,0), C(1,0)}. Step 8, D: memory is full. C has the minimum Estimate of 1. Replace C with D. Set D.Estimate = 1 + 1 = 2 and D.Error = 1. State becomes {A(3,0), B(3,0), D(2,1)}. Step 9, B: increment B. State becomes {A(3,0), B(4,0), D(2,1)}. Step 10, E: memory is full. D has the minimum Estimate of 2. Replace D with E. Set E.Estimate = 2 + 1 = 3 and E.Error = 2. State becomes {A(3,0), B(4,0), E(3,2)}. Step 11, A: increment A. State becomes {A(4,0), B(4,0), E(3,2)}. Step 12, B: increment B. State becomes {A(4,0), B(5,0), E(3,2)}.

GetTopK sorts the tracked counters by Estimate descending. The returned top 2 is [B, A]. For offline verification of this small example, the true frequencies are B = 5, A = 4, C = 1, D = 1, and E = 1.

Every arrival follows one of three actions. If the item is tracked, its estimate increases. If it is new and capacity remains, it gets a fresh counter. If memory is full, the smallest counter is replaced. The replacement uses new Estimate = old minimum + 1 and Error = old minimum. This keeps memory bounded and preserves the Space-Saving error bound. Frequent items receive repeated increments, so they tend to remain among the strongest candidates.

The code stores counters in a Dictionary<T, Counter> and a SortedSet<Counter>. Because Estimate controls the SortedSet ordering, an existing counter is removed before its Estimate changes and added back afterward. When memory is full, the minimum counter is removed from both structures and replaced according to the Space-Saving rule. GetTopK orders the tracked counters by Estimate descending and returns the first K item, estimate, and error tuples.

For each stream item, Dictionary lookup is O(1) on average. SortedSet removal and insertion are O(log M). Processing n items therefore takes O(n log M) expected time. The persistent streaming state uses O(M) auxiliary space. The shown GetTopK implementation sorts at most M counters, so one query costs O(M log M). Important cases include invalid K, K greater than M, duplicate items, an empty stream, and more distinct values than the memory budget.

The key insight is that exact counting of every distinct value can require memory that grows with the number of distinct items. That does not satisfy a strict fixed-memory requirement. Space-Saving instead keeps only M candidate counters.

If an arriving item is already tracked, its Estimate is incremented. If the item is new and fewer than M counters exist, a new counter starts at Estimate = 1 and Error = 0. If memory is full, the counter with the smallest Estimate is replaced. The replacement gets Estimate = old minimum + 1 and Error = old minimum.

The central invariant is that at most M counters are stored. For each tracked item, Estimate - Error is a lower bound on its true frequency and Estimate is an upper bound. The Dictionary provides average O(1) tracked-item lookup. The SortedSet provides O(log M) maintenance and quick access to the minimum counter.

Let n be the number of stream elements processed so far, and let M be the fixed counter capacity.

For each incoming item, the Dictionary lookup is O(1) on average. Updating the SortedSet costs O(log M). Therefore, processing n stream items takes O(n log M) expected time.

The streaming state stores at most M counters in the Dictionary and SortedSet, so auxiliary space is O(M).

The shown GetTopK method orders at most M tracked counters before taking K of them. That query costs O(M log M) time. Its returned list contains at most K entries, so the output itself uses O(K) space.

One mistake is treating every stored Estimate as an exact frequency after replacements occur. Another is replacing the minimum counter but forgetting that the new Error must equal the old minimum Estimate. In C#, changing Estimate while the Counter is still inside the SortedSet can break its ordering, so remove the counter first and insert it again after the update. Candidates may also incorrectly claim O(1) update time even though ordered-set maintenance is O(log M). Finally, K should not be larger than the configured counter capacity M.

State the memory contract first: "I can keep only M counters, so the result is approximate." Then explain the three update cases in this order: increment an existing counter, insert a new counter when space remains, or replace the minimum counter when memory is full.

I would parse the expression from left to right with a stack of evaluation frames. Each frame stores its current value and the operator waiting for the next value. An opening parenthesis pushes a new frame. A closing parenthesis finishes that frame and applies its result to its parent. Inside each frame, operators run strictly left to right with no normal precedence. The example evaluates to 38. The solution takes O(n) time and O(d) auxiliary space.

The input is one arithmetic string containing numbers, parentheses, and the operators +, -, *, and /. Parentheses may be nested deeply. We must evaluate the innermost parentheses first. Inside one parenthesis level, operators are applied strictly in the order they appear from left to right. Normal multiplication and division precedence does not apply. I keep one small evaluation frame for each active nesting level. When a nested expression closes, its completed value becomes the next value in its parent frame. The final output is one integer result.

1. Should division use integer division that truncates toward zero?
2. Should invalid characters or unmatched parentheses produce an error?
3. Are operators inside each nesting level always evaluated strictly from left to right?

The input is a string expression. The diagram uses 12+(3*(4+5)-6/(1+2))*2. The grouping symbols are round parentheses. They may be nested to any valid depth. The operators are +, -, *, and /. Division is integer division that truncates toward zero. For example, 7 / 2 is 3, and -7 / 2 is -3. The required output is the final integer value. For this example, the result is 38.

I use a stack because the most recently opened parenthesis must be completed first. Each stack entry is a frame. A frame stores an accumulated Value and a pending Op. The frame on top of the stack represents the expression level currently being evaluated. The central invariant is that every completed number or child expression is applied exactly once to the nearest open frame using that frame's pending operator.

Start with one root frame. Its value is 0, and its pending operator is +. Read the string from left to right. When digits are found, read the complete multi-digit number and immediately apply it to the top frame. When an operator is found, save it as the top frame's pending operator. When ( is found, push a fresh frame with value 0 and operator +. Spaces are skipped.

After reading 12 and then +, the root frame is [12, +]. The first ( pushes a new frame. Reading 3 makes that frame's value 3, and * becomes its pending operator. The next ( pushes another frame. Inside it, 4 + 5 becomes 9. Closing that parenthesis pops the value 9 and applies it to the parent, giving 3 * 9 = 27.

The parent frame then reads - 6, so 27 - 6 = 21. It reads / and opens another frame for (1+2). That child frame evaluates 1 + 2 = 3. Closing it applies 3 to the parent, so 21 / 3 = 7. Closing the larger parenthesis applies 7 to the root, giving 12 + 7 = 19. The root then reads * 2, so 19 * 2 = 38. The remaining root frame contains the final result.

At every point, the top frame represents exactly one currently open expression level. A completed value is immediately combined with that frame's accumulated value by using its pending operator. Opening a parenthesis temporarily moves evaluation into a new child frame. Closing it reduces the complete child expression to one value and applies that value to its parent. This preserves both the nesting order and the custom left-to-right operator rule.

The implementation uses Stack<Frame>. Evaluate scans the characters from left to right. Consecutive digits are combined into one number without creating a substring. Apply performs the current frame's pending operation and resets that pending operator to +. An opening parenthesis pushes a frame. A closing parenthesis checks that a child exists, pops its completed value, and applies it to the parent. Invalid characters and unmatched parentheses cause FormatException. Division by zero throws DivideByZeroException.

Let n be the number of characters in the expression. Each character is processed at most once, so the time complexity is O(n). Let d be the maximum active parenthesis nesting depth. The stack contains at most one frame for each active level, so auxiliary space is O(d). Relevant cases include deep nesting, multi-digit numbers, integer division that truncates toward zero, negative intermediate results, division by zero, invalid characters, and unmatched parentheses.

The key idea is to treat every open parenthesis level as its own running calculation. A stack fits this rule because nested groups close in last-opened, first-closed order. Each frame stores an accumulated value and the operator waiting for the next completed value. The top frame always represents the expression level currently being read. Values are applied immediately, so operators inside a frame are evaluated strictly left to right. When a child frame closes, its completed value is applied once to its parent. This invariant preserves the required nesting and evaluation order without building a full expression tree.

Let n be the number of characters in the input string. The parser moves from left to right, and each character is handled at most once, so the time complexity is O(n). Let d be the maximum number of nested parentheses that are open at the same time. The stack needs one frame for each active nesting level, so the auxiliary space complexity is O(d). The solution does not build a separate token list or full expression tree.

A common mistake is using normal arithmetic precedence, which does not match the custom left-to-right rule. Another mistake is applying a parent operation before its nested child expression has finished. Candidates may also pop the root frame when an unmatched ) appears or forget to check for unmatched ( after the scan. Other relevant mistakes are misunderstanding integer division, forgetting division-by-zero handling, accepting invalid characters, or claiming O(1) auxiliary space even though the stack grows with nesting depth.

State the invariant before coding: the stack top is the expression level currently being evaluated, and its pending operator is applied to the next completed value. Then trace (4+5) becoming 9 and show how that 9 is popped and applied to the parent.

I would group the points by y-coordinate and sort the x-values in each row. For every row, I generate every pair of x-values. A dictionary stores the earliest y where each x-pair appeared. If the same pair appears on a later row, those four points form an axis-aligned rectangle, so I calculate width times height and update the maximum. The expected time is O(n log n + sum C(ky, 2)), with O(n + P) auxiliary space.

We need to find four given points that make the biggest rectangle with horizontal and vertical sides. Two points must be on one horizontal row, and two matching x-positions must appear on another row. I group points that share the same y-coordinate. Then I look at every pair of x-values in each row. A dictionary remembers the earliest row where each pair appeared. When the same pair appears again, I can calculate the rectangle area. Keeping the earliest row gives that pair its greatest possible height.

1. Should the answer be 0 if no axis-aligned rectangle can be formed?
2. Can the coordinates be large enough that the area should use a 64-bit integer?
3. Can duplicate point entries appear in the input?

An axis-aligned rectangle has horizontal top and bottom edges and vertical left and right edges. If its columns are x1 and x2 and its rows are y1 and y2, the four corners must be (x1, y1), (x2, y1), (x1, y2), and (x2, y2).

The row-pair method confirms this condition directly. If one row contains the pair (x1, x2), and a different row contains the same pair, all four required corners exist. The equal y-values create horizontal edges, and the equal x-values create vertical edges.

Create rowMap, where each y-coordinate maps to the x-coordinates that occur on that horizontal row. Sort the x-values in each row.

Process the rows in ascending y order. For every row, generate every pair (x1, x2). Create pairRow, where each x-pair maps to the earliest processed y-coordinate containing both x-values.

The central invariant is that pairRow[(x1, x2)] keeps the earliest processed y for that pair. If the pair appears again later, do not overwrite the stored y. The earliest y gives the greatest possible height for a rectangle ending on any later row.

The points are (1,1), (4,1), (1,3), (4,3), (2,1), (2,3), (5,2), and (0,0).

The rows are: y = 0 -> [0] y = 1 -> [1, 2, 4] y = 2 -> [5] y = 3 -> [1, 2, 4]

Start with max = 0 and an empty pairRow.

At y = 0, the row contains only x = 0. No x-pair exists, so pairRow stays unchanged.

At y = 1, the pairs are (1,2), (1,4), and (2,4). They have not appeared before, so store (1,2) -> 1, (1,4) -> 1, and (2,4) -> 1. max is still 0.

At y = 2, the row contains only x = 5. No pair exists, so pairRow stays unchanged.

At y = 3, pair (1,2) was first seen at y = 1. Its width is 2 - 1 = 1. Its height is 3 - 1 = 2. Its area is 1 * 2 = 2, so max becomes 2.

Next, pair (1,4) was first seen at y = 1. Its width is 4 - 1 = 3. Its height is 3 - 1 = 2. Its area is 3 * 2 = 6, so max becomes 6.

Finally, pair (2,4) was first seen at y = 1. Its width is 4 - 2 = 2. Its height is 2. Its area is 4, so max stays 6.

The final answer is 6. The largest rectangle uses (1,1), (4,1), (1,3), and (4,3).

Every axis-aligned rectangle must have the same two x-coordinates on two different horizontal rows. The algorithm generates every x-pair in every row, so it considers the column pair of every possible axis-aligned rectangle.

Because rows are processed from smaller y to larger y, a stored previous y is never above the current row. pairRow keeps the earliest y for each x-pair, so a later occurrence uses the largest possible height available for that pair. Taking the maximum of all calculated areas therefore finds the largest rectangle.

The code first builds rowMap from the input points and sorts each row's x-values. It creates pairRow and sets max to 0. It processes rowMap in ascending y order. Two nested loops generate every x-pair in the current row.

If the pair has not appeared before, the code stores currentY in pairRow. If it has appeared, the code calculates width = x2 - x1, height = currentY - previousY, and area = width * height. It updates max when the area is larger. It does not overwrite previousY.

Let ky be the number of x-values on row y. Sorting all row values costs at most O(n log n). The algorithm generates C(ky, 2) pairs on each row. Dictionary lookup and insertion are O(1) on average, so the expected total time is O(n log n + sum C(ky, 2)).

rowMap needs O(n) space. If pairRow stores P distinct x-pairs, the total auxiliary space is O(n + P).

If fewer than four useful points exist, no pair appears on two different rows and the result stays 0. Points on only one row or only one column also produce 0. Negative coordinates work normally. Duplicate point entries do not change the maximum rectangle, although they can cause redundant pair checks. The area uses long so large coordinate differences are handled more safely.

The key insight is that an axis-aligned rectangle can be identified by an x-pair that occurs on two different y-rows. rowMap groups x-values by y. The algorithm processes rows in ascending y order and generates every pair of x-values in each row. pairRow maps an x-pair to the earliest processed y where that pair occurred. The invariant is that pairRow[(x1, x2)] always stores that earliest y. When the same pair appears later, the four matching points form an axis-aligned rectangle. Using the earliest y gives the greatest possible height for that x-pair ending at the current row.

Let n be the number of points, and let ky be the number of x-values on row y. Sorting the x-values across all rows costs at most O(n log n). A row with ky values creates C(ky, 2) pairs. Dictionary lookup and insertion are O(1) on average, so the expected total time is O(n log n + sum C(ky, 2)). rowMap uses O(n) extra space. If P distinct x-pairs are stored in pairRow, pairRow uses O(P) space. Total auxiliary space is O(n + P).

A common mistake is forgetting the exact corner condition. The same two x-coordinates must occur on two different y-rows. Another mistake is overwriting pairRow when an x-pair appears again. That can lose the earliest row and reduce the height of a future rectangle. Candidates may also process rows in an inconsistent order, mix up x and y, forget the O(ky^2) pair generation on a dense row, or incorrectly claim that all dictionary operations give guaranteed O(1) worst-case time.

Start by saying that an axis-aligned rectangle exists when the same x-pair appears on two different y-rows. Then define pairRow as x-pair to earliest y. That single invariant makes the implementation, area calculation, and correctness proof easy to explain.

I would use recursive DFS. At each node, I first return if the node is null, p, or q. Then I search the left and right subtrees. If both sides return non-null nodes, the current node is the split point, so it is the nearest common ancestor. Otherwise, I propagate the one non-null result upward. This takes O(n) time and O(h) auxiliary space for the recursion stack, where h is the tree height.

We are given a binary tree and two target nodes, p and q. We need to return the nearest node that is an ancestor of both targets. A target node can also be an ancestor of itself. The main idea is to search both sides of each node. If the two targets are found through different child subtrees, that node is their split point. If only one side returns a useful result, we pass that result upward. Recursive DFS fits this tree structure naturally.

1. Are p and q guaranteed to exist in the tree?
2. Are p and q actual node references rather than only integer values?
3. Should a node count as an ancestor of itself?

The input is the root of a binary tree and two target node references, p and q. The output is the TreeNode that is their nearest common ancestor. In the diagram, the tree is rooted at 6. The targets are p = node 3 and q = node 5. The expected result is node 4.

Each recursive call searches one subtree. A null return means that subtree did not produce a target or common-ancestor result. Returning p or q means the current search reached one of the targets. Returning another non-null node means a useful result has already been found lower in that subtree. The current node is the split point when both its left and right recursive results are non-null.

If the current node is null, return null. If the current node is p or q, return that node immediately. This early return also handles the case where one target is an ancestor of the other when both targets are guaranteed to exist. If p is an ancestor of q, reaching p is enough to return p as their nearest common ancestor.

The example tree is rooted at 6. Node 6 has children 2 and 8. Node 2 has children 0 and 4. Node 4 has children 3 and 5. The targets are p = 3 and q = 5.

The executed non-null-node return order shown in the diagram is 0, 3, 5, 4, 2, 8, 6.

At node 0, neither target is found below it, so it returns null. At node 3, the current node equals p, so it returns node 3 immediately. Its child calls are not executed. At node 5, the current node equals q, so it returns node 5 immediately. Its child calls are not executed. At node 4, the left result is 3 and the right result is 5. Both are non-null. Node 4 is therefore the split point, so it returns node 4. At node 2, the left result is null and the right result is 4. The algorithm propagates node 4 upward. At node 8, neither target is found, so it returns null. At root node 6, the left result is 4 and the right result is null. The algorithm propagates node 4. The final result is node 4.

Each call returns p or q when the current node is a target. It returns the current node when both child subtrees return non-null results. Otherwise, it propagates the single non-null result. Therefore, the lowest node where the two target paths split is returned. In the example, node 4 is the node whose left recursive result is 3 and whose right recursive result is 5.

The method first checks the null and target base cases. It then recursively searches the left subtree and the right subtree. If both results are non-null, it returns the current root because that node is the split point. Otherwise, it returns whichever side is non-null. The executable example builds the exact tree from the diagram and prints 4.

The time complexity is O(n), where n is the number of nodes, because each node is visited at most once. The auxiliary space is O(h), where h is the tree height, because recursive calls use the call stack. If p equals q, that node is returned. If one target is an ancestor of the other, the ancestor is returned. If target presence is not guaranteed, this routine alone can propagate one found target even when the other target is missing, so presence must be validated separately.

The key idea is to let every recursive call report the useful result from its subtree. Null means no target or common-ancestor result was found there. Returning p or q means the search reached that target. Returning another non-null node means a common-ancestor result has already been found lower in that subtree. The central invariant is that each call returns the useful target or ancestor result for its subtree. When both left and right return non-null values at the same node, the two target paths come from different child subtrees. That current node is the split point and is returned. If only one side is non-null, that result is propagated upward.

Time complexity is O(n), where n is the number of nodes in the tree. Each node is visited at most once, and a target node returns immediately when reached. Auxiliary space is O(h), where h is the height of the tree. This extra memory comes from the recursion stack. In the worst case of a highly skewed tree, h can be n.

A common mistake is comparing only node values when the inputs are target node references. Another mistake is forgetting the base case that immediately returns p or q, which breaks the ancestor special case. Candidates may also return the current node when only one recursive side is non-null. The current node is a split point only when both sides are non-null. Another mistake is claiming O(1) auxiliary space and forgetting the O(h) recursion stack. Finally, if target presence is not guaranteed, do not assume this routine proves that both targets were found.

Define the meaning of a recursive return value before writing code: null means no useful result from that subtree, one non-null side means propagate that result, and two non-null sides mean the current node is the split point. This makes the code and the ancestor special case much easier to explain.

I would process the people in arrival order and build one current elevator ride at a time. I add each destination floor to the current ride. When that ride reaches four people, I add it to the result and start a new ride. After the loop, I add the final partial ride if it is not empty. This preserves arrival order and never exceeds capacity. The time is O(n), and auxiliary space is O(1) beyond the returned rides.

The input is a list of destination floors in the order people are waiting. The elevator can carry at most four people in one ride. We must keep the same arrival order when creating the ride groups. The goal is to return a list of rides. Each ride contains at most four destination floors. The solution takes the next four waiting people for each full ride. If fewer than four people remain at the end, they form the final ride. This directly satisfies the capacity and ordering rules and gives the required constrained grouping.

1. Should the returned rides preserve the exact arrival order of the input? In this problem, yes.
2. Can the final ride contain fewer than four people? In this problem, yes.
3. Should an empty input defensively return an empty ride list? The diagram shows that behavior.

The input is an integer array of destination floors. Each element represents one waiting person, and its position in the array represents that person's arrival order. The output is a list of rides. Each ride is another list containing at most four destination floors. For the example input [2, 9, 7, 4, 3, 1, 8, 6, 5], the output is [[2, 9, 7, 4], [3, 1, 8, 6], [5]].

We do not need sorting, searching, or a special lookup structure. We only need one result list and one small current-ride list. The central rule is simple: the current ride contains the next unassigned people in arrival order, and it never contains more than four people. When it reaches four, we dispatch it and start a new current ride.

Create an empty list called rides. This stores the completed ride groups. Create another empty list called current with capacity four. This stores the ride currently being built. At the start, no person has been assigned to a ride.

Start with input [2, 9, 7, 4, 3, 1, 8, 6, 5]. Add 2, so current becomes [2]. Add 9, so it becomes [2, 9]. Add 7, so it becomes [2, 9, 7]. Add 4, so current becomes [2, 9, 7, 4]. Its count is now four, so dispatch it. The rides list becomes [[2, 9, 7, 4]], and current becomes empty.

Next add 3, giving [3]. Add 1, giving [3, 1]. Add 8, giving [3, 1, 8]. Add 6, giving [3, 1, 8, 6]. The ride is full, so dispatch it. The rides list becomes [[2, 9, 7, 4], [3, 1, 8, 6]]. Start another empty current ride.

Finally add 5, so current is [5]. The input is finished. Because current is not empty, dispatch that final partial ride. The final result is [[2, 9, 7, 4], [3, 1, 8, 6], [5]].

At every point, current contains the next people who have not yet been assigned to a ride. We only append people, so their arrival order never changes. We dispatch immediately when current reaches four people, so no ride exceeds the capacity. Every input person is added exactly once to one ride. Therefore the final output contains every person in order and satisfies the capacity rule.

The method creates rides and current. It loops through floors from left to right. Each floor is appended to current. When current.Count becomes 4, that list is added to rides and a new empty current list is created. After the loop, a final non-empty current list is added. Then the method returns rides. The example in Main uses exactly [2, 9, 7, 4, 3, 1, 8, 6, 5] and prints the three rides shown in the diagram.

If n is the number of people, the loop processes each person once, so the time complexity is O(n). The in-progress ride holds at most four integers, so auxiliary space is O(1) beyond the returned output. The returned rides contain all n destination values, so the output itself uses O(n) space. A final partial group is valid. If the number of people is a multiple of four, every ride is full. The diagram also treats an empty input defensively by returning an empty ride list.

The key insight is that the illustrated constraints are arrival order and a maximum capacity of four people per ride. Because order cannot change, the correct grouping is to take the next four waiting people whenever possible. The invariant is: before each new input value is processed, every earlier person is already in exactly one completed ride or in the current ride, and the current ride has fewer than four people. Adding the next person preserves order. Dispatching when the count reaches four preserves capacity. Under these shown constraints, filling each ride to four whenever possible minimizes the number of rides.

Let n be the number of people. We read each destination floor once, so the time complexity is O(n). The current ride stores at most four integers, so it uses constant extra memory. Therefore the auxiliary space is O(1) beyond the returned rides. The returned result stores all n destination values across its ride lists, so the output space is O(n).

A common mistake is sorting the destination floors, which breaks the required arrival order. Another mistake is allowing more than four people into a ride before dispatching it. Candidates may also forget to add the final partial ride after the loop. Another error is adding the current list to the result and then mutating that same list instead of creating a new current list. Finally, do not claim O(1) total space without separating auxiliary space from the O(n) returned output.

State the invariant before coding: the current ride always contains the next unassigned people in arrival order and has at most four people. Then make the code follow that rule directly by dispatching exactly when the count reaches four.

I would keep each client memory-bounded instead of loading the full shared document. The client keeps only the visible 10,000-character viewport plus 5,000-character buffers on both sides. Edits go to an OT server with absolute revisions, an append-only operation log, and periodic durable snapshots. Reconnecting clients load a snapshot and replay later operations. Applying k operations is O(k) at the collaboration layer, while client memory stays bounded by the active window plus pending operation state.

The problem is that a shared document can become extremely large. If every browser keeps the whole document and all edit history in memory, memory use grows too much. The diagram solves this by keeping only the text near the user's screen in each client. Changes are sent to one collaboration server. The server orders and transforms concurrent edits. Durable snapshots and operation-log segments let clients rebuild state without keeping the full history forever.

1. Can each client keep only the visible document window plus a small buffer?
2. Should concurrent edits use server-ordered Operational Transformation?
3. Can persistent storage use durable snapshots plus append-only operation-log segments?
4. May old log segments be compacted only after a durable snapshot covers them?

The example document has 100,000,000 characters. The diagram treats that as about 100 MB of compact text storage. There are 50 active clients. Loading the complete document and all history into every client would waste memory.

The visible viewport is 10,000 characters. The client also keeps a 5,000-character buffer on each side. So it materializes 20,000 UTF-16 characters around the current editing area. That is about 40 KB of text. When the user scrolls, distant content can be evicted and a new nearby range can be loaded.

The user inserts "Hello" at global index 50,000. The client sends Insert(index=50,000, "Hello") with its BaseVersion. The server stores an absolute current revision and an absolute retained-log start revision. It transforms the incoming operation only against retained operations that happened after the client's base revision. Then it appends the transformed operation, advances the absolute server revision, and broadcasts the accepted operation.

The durable snapshot is snap_120 at revision 1,200,000. There are 25,000 operations after it. A client opens the document, loads snap_120, replays those 25,000 operations in server order, and then keeps only the viewport window and buffers in memory. The user edit is processed after that rebuilt revision.

The logical operation log is append-only. Periodically the system creates a durable snapshot. Only after the new snapshot is successfully persisted may operations covered by that snapshot be compacted. The retained-log boundary then advances to the snapshot revision. BaseVersion values remain absolute revisions even though the retained list is shorter.

The OT server gives accepted edits one ordered revision history. A client with a retained base revision can transform or replay the missing operations in that order. A snapshot plus the operations after it can reconstruct a later revision. Viewport eviction removes only materialized client text. It does not delete logical document data.

At the collaboration layer, replaying k operations requires O(k) operation applications. In the simplified insert-versus-insert OT rule, one transform against one retained operation is O(1), while one incoming operation may need to transform against c newer retained operations, so that receive step is O(c). Snapshot creation is O(document size) and is done infrequently. Client working memory is bounded by its materialized window plus pending operation state. Relevant edge cases are large pastes, reconnects older than the retained-log boundary, memory pressure, and binary objects stored out of line.

The key idea is to separate the complete logical document from the small working set that a browser needs. Each client materializes only the viewport and nearby buffers. Edits are represented as operations and sent to a server-ordered OT pipeline. The central invariant is that _logStartRevision is the absolute revision immediately before the first retained operation. Therefore an absolute BaseVersion is converted to a retained-list index by subtracting _logStartRevision. Durable snapshots are safe restart points. After snapshot revision R is persisted, operations covered by R may be compacted and the retained-log boundary can move to R.

Let k be the number of operations replayed after a snapshot and c be the number of retained operations newer than one incoming edit's BaseVersion. At the collaboration layer, replaying k operations is O(k) operation applications. The simplified insert-versus-insert transform itself is O(1), so transforming one incoming edit against c newer operations is O(c). Snapshot creation is O(document size) and is intentionally infrequent. The client keeps only the viewport, two buffers, and pending operation state. In the example, 20,000 UTF-16 characters are materialized, about 40 KB of text, and the diagram estimates about 3.5 MB total model-plus-operation memory per client. The runnable piece-table demo uses a simple list of pieces, so an arbitrary local insert can take O(p) to locate its piece, where p is the current number of pieces; a production balanced piece tree or rope can reduce that lookup to O(log p).

A common mistake is loading the complete document or full history into every browser. Another is mixing OT and CRDT rules without defining one consistent collaboration model. Candidates also sometimes use BaseVersion directly as a zero-based list index after compaction. It must remain an absolute revision, so the retained index is BaseVersion minus _logStartRevision. Another serious mistake is deleting old operations before the covering snapshot is durably stored. Also, viewport eviction must remove only materialized client content, not logical document data. Finally, a reconnecting client older than the retained boundary must reload from a newer snapshot instead of transforming against incomplete history.

State the invariant early: the browser holds only a bounded viewport window, while the server keeps absolute revisions. Then connect snapshots to safe log compaction. This gives the interviewer one clear story for memory, collaboration, recovery, and revision correctness.

At a high level, I would trace the failing request from the client to the API and identify where authentication or authorization breaks. The client sends GET /api/orders/123 over HTTPS with an Authorization: Bearer <JWT> header. The reverse proxy or API gateway forwards it to the ASP.NET Core Web API. I would verify token signature, issuer, audience, lifetime, scopes, roles, middleware order, and identity-provider key information. Then I would check whether the API returns 401, 403, or another error. The trade-off is stronger security with more configuration to debug.

This question asks me to find why a protected API request is failing. I need to follow one request from the client, through the gateway, into the application, and back again. I would check what the client sends and whether the gateway forwards it correctly. Then I would check whether the application can identify the caller and whether that caller has permission. I would also inspect the identity system and the data access shown in the diagram. The goal is to find the exact layer causing the failure instead of guessing.

• Is the problem happening for every caller or only some callers?
• Are we receiving 401 Unauthorized, 403 Forbidden, 500 Error, or another response?
• Did token settings, signing keys, roles, policies, or gateway rules change recently?

I would start with the exact request shown in the diagram. The client sends GET /api/orders/123 over HTTPS. It includes Authorization: Bearer <JWT> and Accept: application/json. I would check the URL, HTTP method, query parameters, headers, and token format. I would verify that the bearer token is present and does not contain extra spaces or use the wrong authentication scheme. I would also inspect token expiry, not-before time, issuer, audience, scopes, and roles. If client credentials are used elsewhere in the authentication setup, I would verify the configured client ID and secret without changing this request flow.

The request next reaches the reverse proxy or API gateway. The diagram shows this layer handling TLS termination, rate limiting, routing, and optional authentication. I would confirm that HTTPS works and that the gateway forwards the Authorization header to the ASP.NET Core Web API. I would also check routing, certificate problems, header limits, rate-limiting rules, and CORS behavior when the caller is a browser. A browser preflight problem or a gateway that strips the authorization header can look like an API authentication problem.

The gateway forwards the request over HTTPS to the ASP.NET Core Web API. The application flow is routing, authentication, authorization, endpoint processing, and then the action or controller. I would verify that UseAuthentication() executes before UseAuthorization(). Authentication answers, “Who is this caller?” For the bearer JWT shown here, I would validate the signature, trusted issuer, expected audience, token lifetime, not-before time, signing key, and accepted algorithm. A missing token, bad signature, expired token, untrusted issuer, or invalid audience should cause authentication to fail with 401 Unauthorized.

The diagram shows an Identity Provider such as Auth0, Azure AD, Google, or Okta. It can issue JWTs and provide JWKS signing-key information or token-introspection information. JWKS is a set of public keys that an API can use to verify JWT signatures. Depending on the configured authentication scheme, the Web API can obtain current key information or use an HTTPS introspection call and receive the corresponding token information. I would check for stale JWKS data after key rotation and confirm that the API trusts the correct issuer and keys.

After authentication succeeds, authorization answers, “May this caller perform this action?” I would inspect policies, roles, required scopes, endpoint attributes, and claims mapping. I would verify that [Authorize] and [AllowAnonymous] are applied as intended. I would also check whether role or identity claims are mapped to the names the application expects. If the token is valid but the caller lacks a required scope, role, or policy requirement, the correct result is 403 Forbidden. I would not weaken authorization merely to make the error disappear.

If authentication and authorization both succeed, the endpoint and action or controller can continue. The diagram then shows access to a data store, which may be a database or cache. The result comes back to the Web API. The Web API sends its response through the reverse proxy or API gateway and then back to the client over HTTPS. The diagram shows 200 OK, 401 Unauthorized, 403 Forbidden, and 500 Error, with Content-Type: application/json. I would reproduce the problem, capture the full request and response, review application, gateway, and identity-provider logs, change one suspected setting at a time, retest, and confirm the fix.

The benefit of this design is that each layer has a clear security job. The client supplies the bearer JWT. The gateway handles transport, routing, rate limiting, and optional authentication. ASP.NET Core performs authentication before authorization. The identity provider supplies trusted token or signing-key information. This makes problems easier to isolate. The downside is that many settings must agree. Issuer, audience, signing keys, token times, claims, roles, policies, gateway forwarding, and middleware order can all cause failures. JWKS reduces the need to hard-code public keys, but key rotation can cause temporary problems if cached information becomes stale. Token introspection can provide current token information, but it adds an HTTPS dependency on the identity provider.