54 Google .NET Developer Interview Questions & Answers

I would use BFS, but I would include both the position and the unlock condition in each state. So a state is (row, column, hasKey). BFS processes these states in increasing distance order. When I enter K, hasKey becomes true. I can enter D only after that. I mark each full state visited before enqueueing it. The first time I dequeue the goal, its distance is shortest. Time is O(rows × cols), and auxiliary space is O(rows × cols).

The map is a grid with a start S, goal G, walls #, key K, and door D. The door cannot be crossed until the key has been reached. We need the smallest number of up, right, down, or left moves from the start to the goal. The important idea is that reaching the same place before and after getting the key can lead to different future moves. BFS fits because every valid move costs 1.

1. Are movements limited to the four directions: right, down, left, and up?
2. Does every valid move have the same cost of 1?
3. Should I return -1 when the goal cannot be reached even after all possible unlocks?
4. Can the starting cell already satisfy the unlock condition?

The input is a grid together with start and goal coordinates. In the diagram's example, the grid has 3 rows and 4 columns. S is at (0,0). K is at (0,2). D is at (1,3). G is at (2,3). The grid rows are S . K #, # # . D, and # # # G. Walls cannot be crossed. The door can be crossed only when hasKey is true. The required output is the minimum number of moves. The result for this example is 5.

I use a queue for BFS. BFS is correct for this problem because every move costs 1. Each queue item stores (row, column, hasKey, distance). The visited structure is visited[row, column, state], where state is 0 without the key and 1 with the key. This keeps (row, column, false) separate from (row, column, true). That distinction is necessary because the second state may be able to cross D even when the first state could not.

The initial queue contains (0,0,F,0). The matching visited entry is marked before the state is enqueued. Here F means hasKey is false and T means it is true. The central invariant is that the first time a complete state (row, column, hasKey) leaves the BFS queue, its stored distance is the shortest distance to that exact state.

The neighbor order is right, down, left, up.

Step 0: Dequeue (0,0,F,0). The only open new neighbor is (0,1). Enqueue (0,1,F,1).

Step 1: Dequeue (0,1,F,1). Moving right reaches K at (0,2). Collecting the key changes the state from false to true. Enqueue (0,2,T,2).

Step 2: Dequeue (0,2,T,2). Moving down reaches the open cell (1,2). Enqueue (1,2,T,3).

Step 3: Dequeue (1,2,T,3). The cell to the right is D. Because the key is already held, the door is traversable. Enqueue (1,3,T,4).

Step 4: Dequeue (1,3,T,4). Moving down reaches G at (2,3). Enqueue (2,3,T,5).

Step 5: Dequeue (2,3,T,5). This state is the goal, so processing stops and the method returns 5.

One valid shortest route is S -> (0,1) -> K -> (1,2) -> D -> G.

Every move costs 1, so BFS processes reachable states in nondecreasing distance order. The state includes the unlock information, so a coordinate reached without the key is different from the same coordinate reached with the key. The visited array therefore removes cycles without throwing away a later state that has more capability. The first time the goal is dequeued, its distance is the shortest valid distance in this expanded state space.

The queue stores row, column, key state, and distance. The code marks a complete state visited before enqueueing it, which avoids duplicate queue entries for that same state. Entering K changes nextHasKey to true. Entering D is rejected unless nextHasKey is true. The four direction arrays implement right, down, left, and up. When the goal is dequeued, the code returns its distance. If the queue becomes empty first, it returns -1.

There are at most rows × cols × 2 states because every cell can be represented without the key or with the key. Each state checks four neighbors. The time complexity is therefore O(rows × cols), and the auxiliary space is O(rows × cols). Relevant edge cases are starting with the key condition already true, encountering D before K, the goal being unreachable even after unlocking, and reaching the same coordinate again with a different unlock state.

The key insight is that the grid position alone is not enough to describe the search. Reaching K changes which future moves are legal, so the search state must be (row, column, hasKey). BFS is the right algorithm because every movement edge has equal cost. The central invariant is that the first time a complete state leaves the BFS queue, the stored distance is the shortest distance to that exact state. A three-dimensional visited array prevents repeated work while still allowing the same coordinate to be revisited when its unlock state is different.

Let rows be the number of rows and cols be the number of columns. Each cell has at most two relevant states: key not held and key held. So the search has at most rows × cols × 2 states. Each state checks four directions, which is constant work. Therefore the time complexity is O(rows × cols). The queue and visited array can also grow with the number of states, so auxiliary space is O(rows × cols). With k independent binary unlock conditions, the number of state combinations can grow to 2^k, giving O(rows × cols × 2^k) states.

A common mistake is using only visited[row, col]. That can incorrectly remove a later visit to the same cell after the key has been collected. Another mistake is allowing D before the unlock state becomes true. Candidates may also mark a state visited only after dequeuing it, which can add duplicate states to the queue. Using DFS and assuming it automatically returns the shortest route is another error. Finally, the complexity analysis must account for both unlock states of each cell.

Define the state before writing any BFS code. Say clearly that (row, col, false) and (row, col, true) are two different search states because they allow different future moves. That explanation makes the visited structure, the door rule, and the shortest-path proof much easier to justify.

I would use a sliding window with a Dictionary<char, int> that stores each character and its frequency in the current window. I move the right pointer to expand the window. If the number of distinct characters becomes greater than k, I move the left pointer and reduce frequencies until the window is valid again. Then I update the longest valid window. This gives O(n) expected time and uses O(min(n, number of distinct characters in s)) auxiliary space.

The input is a string s and an integer k. We need the longest continuous part of the string that contains no more than k different characters. A repeated character does not create another distinct character. We only count the different characters inside the current continuous window. A sliding window fits this problem because we can grow the window from the right and shrink it from the left only when it has too many distinct characters.

1. Should character comparisons be case-sensitive?
2. If several longest valid substrings have the same length, is returning any one of them acceptable?
3. Should an empty string or k <= 0 return an empty string?

The input is string s and integer k. The output is the longest contiguous substring containing at most k distinct characters. Contiguous means the characters must stay next to each other in the original string. For the diagram example, s = "eceba" and k = 2. The returned substring is "ece".

Use two boundaries called left and right. They describe the current substring s[left..right]. Use Dictionary<char, int> called counts. Each key is one distinct character currently in the window. Its value is that character's frequency. Repeated copies increase the frequency but do not increase counts.Count. The central invariant is: after shrinking finishes, the current window contains at most k distinct characters.

Start with left = 0, bestStart = 0, and bestLength = 0. The counts dictionary is empty. The right pointer has not started processing the string yet. As right moves forward, the character at s[right] is added to the frequency map.

For s = "eceba" and k = 2:

At right = 0, the character is 'e'. counts changes from {} to {e:1}. The current window is "e". It is valid, so bestStart stays 0 and bestLength becomes 1.

At right = 1, the character is 'c'. counts changes from {e:1} to {e:1,c:1}. The current window is "ec". It has two distinct characters, so it is valid. bestStart stays 0 and bestLength becomes 2.

At right = 2, the character is 'e'. counts changes from {e:1,c:1} to {e:2,c:1}. The current window is "ece". It still has only two distinct characters. bestStart stays 0 and bestLength becomes 3.

At right = 3, the character is 'b'. counts first becomes {e:2,c:1,b:1}. That has three distinct characters, so the window is invalid. We shrink repeatedly from the left. We remove one 'e' at left index 0, giving {e:1,c:1,b:1}, and left becomes 1. There are still three distinct characters, so we continue shrinking. We remove 'c' at left index 1. Its frequency becomes 0, so we remove the 'c' key. counts becomes {e:1,b:1}, and left becomes 2. The current window is now "eb". Its length is 2, so the best result remains "ece" with length 3.

At right = 4, the character is 'a'. counts first becomes {e:1,b:1,a:1}. There are three distinct characters, so we shrink again. We remove 'e' at left index

2. Its frequency becomes 0, so the key is removed. counts becomes {b:1,a:1}, and left becomes
3. The current window is "ba". Its length is 2, so the best result still remains "ece" with length 3.

The frequency map always represents the current window. Whenever counts.Count becomes greater than k, the left pointer moves until the window contains at most k distinct characters again. We update the best answer only after the window is valid. For each right position, the algorithm therefore considers a valid window ending at that position, and the longest valid window seen during the traversal is recorded.

The method first returns string.Empty when s is empty or k <= 0. It then creates the Dictionary<char, int> frequency map and initializes left, bestStart, and bestLength. The for loop moves right through the string. Each new character increases its frequency. While counts.Count > k, the code decreases the frequency of s[left], removes that dictionary key if the frequency becomes 0, and increments left. After the window becomes valid, it computes right - left + 1 and updates the best window when the new length is larger. At the end, it returns s.Substring(bestStart, bestLength).

The expected running time is O(n). The right pointer visits each character once, and the left pointer only moves forward, so each character can leave the window at most once. Dictionary operations are O(1) on average, with normal hashing and collision caveats. The auxiliary space shown in the diagram is O(min(n, number of distinct characters in s)). Relevant edge cases are an empty string, k <= 0, a string containing only one repeated character when k >= 1, and k being at least the number of distinct characters in the whole string.

The key insight is that we do not need to restart from every possible substring. We maintain one sliding window. The right pointer expands it, and Dictionary<char, int> stores character -> frequency for that current window. counts.Count is therefore the number of distinct characters currently present. If counts.Count becomes greater than k, we repeatedly move left and reduce frequencies until the window is valid again. A key must be removed when its frequency reaches 0. The invariant is: after shrinking, s[left..right] contains at most k distinct characters. Only then do we compare the current window with the best result.

The expected time is O(n). The right pointer moves from the start of the string to the end. The left pointer also moves only forward, and each character can leave the window at most once. Dictionary<char, int> lookup, insertion, update, and removal are O(1) on average, so the total expected work is linear. The auxiliary space shown in the diagram is O(min(n, number of distinct characters in s)) because the dictionary stores frequencies for distinct characters from the current window.

A common mistake is shrinking only once when counts.Count > k. The code must keep shrinking until counts.Count <= k. Another mistake is decreasing a frequency to 0 but leaving that key in the dictionary, which makes the distinct-character count wrong. Candidates may also update the best answer before restoring a valid window. Another error is treating the required result as a subsequence instead of a contiguous substring. Finally, it is inaccurate to describe Dictionary operations as guaranteed O(1); they are O(1) on average.

State the invariant before coding: after the shrinking loop finishes, the current window contains at most k distinct characters. Then make the implementation follow that sentence directly: expand right, shrink left while invalid, and update the best answer only after the window is valid.

I would use post-order DFS. Each recursive call returns the longest downward same-value path that can continue through its parent, measured in edges. After I process both children, I extend only the sides whose child value matches the current node. I combine the two matching sides to update a global maximum, then return only the longer side upward. Each node is visited once, so the time is O(n), with O(h) auxiliary space for the recursion stack.

We have a binary tree, and we want the longest connected path whose nodes all have the same value. The path may begin and end anywhere, so it does not need to contain the root. In this solution, path length means the number of edges. We process children before their parent. Each node learns how far a matching path can continue downward on its left and right sides. It combines those two sides for the best path through that node and keeps the largest result seen anywhere.

1. Should the path length be counted in edges? In this solution, yes.
2. Can the path start and end anywhere in the tree? Yes.
3. Can a valid path use both a matching left branch and a matching right branch through the same node? Yes.

The input is the root of a binary tree. Each node contains an integer value. We return one integer: the maximum number of edges in a connected path where every node has the same value. The path may be completely inside a subtree or may pass through the root.

The diagram's example has root value 1. Its left child is 1 and its right child is 2. The left child has a left child 1 and a right child 3. That lower 1 has two leaf children with value 1. On the right side, the top 2 has a matching child 2, which has a matching leaf 2. The final answer is 3 edges.

I use depth-first search in post-order. This means I process the left subtree and right subtree before finishing the current node. Each recursive call returns the longest one-sided same-value path, measured in edges, that starts at that node and goes downward.

The base case is a null node. It returns 0.

After both recursive calls return, I extend a side only when that child exists and has the same value as the current node. If the values do not match, that side becomes 0 because the same-value path stops there.

For a matching left child, leftLen becomes the child's returned length plus 1 for the edge from the current node to that child. Otherwise leftLen becomes 0. The same rule is used for rightLen.

A complete path through the current node may use both matching sides. Its length is leftLen + rightLen. I compare this value with the global maxLen.

Only one side can be returned to the parent because a downward path cannot branch. Therefore the recursive call returns Math.Max(leftLen, rightLen).

The two deepest leaf nodes with value 1 each return 0 because they have no downward edges.

Their parent has value 1. Both children also have value 1, so leftLen = 1 and rightLen = 1. The path through this node is 1 + 1 = 2. maxLen becomes 2. The node returns 1 to its parent.

The node with value 3 is a leaf, so it returns 0. Its parent has value 1. The matching left child returned 1, so adding the connecting edge gives leftLen = 2. The right child has value 3, so rightLen = 0. The path through this node is 2. maxLen stays 2, and the node returns 2.

On the right side, the bottom leaf with value 2 returns

1. Its parent extends that matching child to length 1 and returns
2. The next 2 extends it again to length 2 and returns
3. The largest path on that side is 2 edges, so maxLen remains 2.

Finally, the root has value 1. Its left child also has value 1, so the returned 2 becomes leftLen = 3 after adding the connecting edge. Its right child has value 2, so rightLen = 0. The path through the root is 3 + 0 = 3. maxLen becomes 3. The final answer is 3.

At each node, leftLen and rightLen contain only paths that can connect directly to the current node and still have the same value. A different child value makes that side 0. Therefore leftLen + rightLen is exactly the longest same-value path that passes through the current node.

The DFS performs this calculation for every node. The global maximum stores the largest complete same-value path among all nodes processed so far. This covers paths inside either subtree and paths that pass through any node.

The Solution class stores maxLen as global state. LongestSameValuePath resets it to 0, calls Dfs on the root, and returns the final maximum.

Dfs first handles the null base case. It recursively processes both children. A matching child contributes its returned length plus 1 edge. A nonmatching child contributes 0. The method updates maxLen with leftLen + rightLen and returns Math.Max(leftLen, rightLen), because the parent can extend only one downward branch.

The time complexity is O(n) because each of the n nodes is visited once. The auxiliary space is O(h), where h is the height of the tree, because recursive calls use the call stack. For a skewed tree, h can be n.

An empty tree returns 0. A single node returns 0 because it contains no edges. If all adjacent node values are different, the result is 0. If every node has the same value, the result depends on the tree shape. A chain of n nodes has a longest path of n - 1 edges.

The key insight is that a parent does not need the complete best path from a child. It only needs the longest same-value path that starts at that child and continues downward, because that is the only path the parent can extend. Post-order DFS gives this information naturally because both children are solved before their parent. The invariant is: each Dfs return value is the longest downward same-value path in edges starting at that node, and maxLen is the largest complete same-value path among all nodes processed so far. A node may combine matching left and right paths for the global answer, but it returns only the longer one-sided path upward.

Time is O(n), where n is the number of nodes. Each node is visited once, and the work done at each node is constant. Auxiliary space is O(h), where h is the tree height. This extra memory comes from the recursion stack. In a balanced tree, h is O(log n). In a completely skewed tree, h can be O(n). The algorithm does not use an extra map, set, queue, or other collection.

1. Counting nodes instead of edges. A single node has length 0, and the diagram's final result is 3 edges. 2. Adding an extra 1 when updating the global maximum. The correct formula is leftLen + rightLen because both values already count connecting edges. 3. Extending through a child whose value does not match the current node. That side must become 0. 4. Returning leftLen + rightLen to the parent. The parent can continue through only one branch, so Dfs returns Math.Max(leftLen, rightLen). 5. Forgetting that the best path may be completely inside a subtree. A global maximum is needed because the answer does not have to pass through the root. 6. Claiming O(1) auxiliary space and forgetting the O(h) recursion stack.

State the recursive contract before writing code: "Dfs returns the longest downward same-value path from this node in edges." Then separate the two jobs clearly: use leftLen + rightLen to update the global answer, but return only Math.Max(leftLen, rightLen) to the parent.

I would first state my interpretation: '.' is an empty cell, 'W' is blocked, and a neighborhood is a maximal group of empty cells connected up, down, left, or right. I scan the grid in row-major order. When I find an unvisited empty cell, I increment the count and run DFS to mark that entire component visited. This counts every neighborhood exactly once. The time complexity is O(m × n), and the auxiliary space is O(m × n).

The reported prompt does not fully define what a neighborhood means, so I would first make the model explicit. In the approved diagram, '.' means an empty location and 'W' means a blocked location. Empty cells belong to the same neighborhood only when they connect through a shared side. The goal is to count the separate empty regions. I scan every cell. When I reach an empty cell that has not been visited, I start DFS, mark the whole connected region, and add one to the count.

1. Should neighborhoods use only up, down, left, and right connections, or should diagonal cells also connect?
2. Which value represents an empty location and which value represents a blocked location?
3. What should be returned for an empty grid?

I use the interpretation shown in the diagram. The input is a rectangular character grid. A '.' cell is empty. A 'W' cell is blocked. Two empty cells belong to the same neighborhood when a path of empty cells connects them using only up, down, left, and right moves. The output is one integer: the number of separate empty neighborhoods.

The verified example has 5 rows and 6 columns: Row 0: W W . . W . Row 1: W . W . W . Row 2: . . . W . W Row 3: W . W W . . Row 4: . . . . W W

The expected output is 4.

I use depth-first search, or DFS. DFS starts from one empty cell and visits every empty cell connected to it through the four allowed directions.

I also use a boolean visited matrix with the same dimensions as the grid. visited[r, c] tells me whether that cell has already been assigned to a neighborhood.

The main invariant is: every visited empty cell already belongs to a neighborhood that has been counted. Therefore, when the outer scan reaches an empty cell that is still unvisited, that cell must start a new neighborhood.

The grid has m rows and n columns. I create visited[m, n], with every value initially false. I set count to 0.

I scan the grid in row-major order. That means I process row 0 from left to right, then row 1, and continue until the last row.

For each cell, I check whether it contains '.' and whether visited[r, c] is false. If either condition is false, I continue. If both are true, I increment count and run DFS from that cell.

The first unvisited empty cell is at (0,2). This starts component 1. DFS marks exactly (0,2), (0,3), and (1,3). Component 1 has 3 cells.

The next unvisited empty cell in row-major order is (0,5). This starts component 2. DFS marks (0,5) and (1,5). Component 2 has 2 cells.

The next unvisited empty cell is (1,1). This starts component 3. DFS marks (1,1), (2,0), (2,1), (2,2), (3,1), (4,0), (4,1), (4,2), and (4,3). Component 3 has 9 cells.

The next unvisited empty cell is (2,4). This starts component 4. DFS marks (2,4), (3,4), and (3,5). Component 4 has 3 cells.

After that, all remaining empty cells have already been visited. The component sizes are {1:3, 2:2, 3:9, 4:3}. The final count is 4, so the algorithm returns 4.

Under the interpretation above, each DFS starts from an empty cell that has not been assigned to an earlier component. DFS follows every valid four-directional empty connection, so it marks exactly one maximal connected neighborhood.

When that DFS finishes, every cell in that neighborhood is marked visited. The outer scan cannot count the same neighborhood again. Every separate neighborhood starts exactly one DFS, so the final count equals the number of neighborhoods.

The code creates a visited matrix and two direction arrays. dr stores row changes and dc stores column changes for up, down, left, and right.

The nested loops scan every cell in row-major order. If the cell is blocked or already visited, the code skips it. Otherwise, it increments count and calls Dfs.

Dfs marks the current cell visited immediately. It then checks the four neighboring coordinates. A neighbor is visited recursively only if it is inside the grid, contains '.', and has not already been visited.

After every cell has been processed, the function returns count. For the diagram's example, Main prints 4.

There are m × n cells. The outer loops inspect the grid, and each empty cell is visited by DFS at most once. Therefore, the time complexity is O(m × n).

The visited matrix needs O(m × n) extra memory. Recursive DFS can also use O(m × n) call-stack space in the worst case when one neighborhood contains most of the grid.

If there are no empty cells, the result is

1. If a non-empty grid contains only empty cells, the result is
2. Multiple isolated empty cells each count as separate neighborhoods. A single row or a single column works the same way. For a very large grid, iterative DFS or BFS can avoid recursion-stack overflow.

Treat the empty cells as connected components. Scan the grid in row-major order. When the scan finds a '.' cell that has not been visited, increment the neighborhood count once and run DFS from that cell. DFS marks every four-directionally connected empty cell in the same component before the outer scan continues. The central invariant is that every visited empty cell already belongs to a neighborhood that has been counted. Because the entire component is marked before scanning continues, the same neighborhood cannot be counted twice.

Let m be the number of rows and n be the number of columns. The algorithm takes O(m × n) time. The outer loops inspect the cells, and each empty cell is visited by DFS at most once. The visited boolean matrix uses O(m × n) extra memory. Recursive DFS can also use O(m × n) call-stack space in the worst case if one connected empty region contains most of the grid.

1. Counting every empty cell instead of counting connected components.
2. Treating diagonal cells as connected even though this interpretation allows only up, down, left, and right.
3. Forgetting the visited matrix, which can cause repeated visits or recursive cycles.
4. Marking a cell visited too late instead of marking it when DFS enters that cell.
5. Claiming O(1) extra space and forgetting both the O(m × n) visited matrix and the possible O(m × n) recursion stack.

State the neighborhood interpretation before writing code because the reported prompt is ambiguous. Then explain the invariant in one sentence: every unvisited empty cell found by the outer scan starts exactly one new component, and DFS marks that whole component so it cannot be counted again.

I would combine all shift operations into one net rotation instead of changing the string after every operation. I treat a left shift as negative movement and a right shift as positive movement. After processing all operations, I normalize the total with modulo by the string length. Then I rotate the string once by splitting it and joining the suffix before the prefix. This takes O(m + n) time and O(n) auxiliary space for the returned string.

The input is a string and a list of shift operations. Each operation has a direction and an amount. Direction 0 moves characters left. Direction 1 moves them right. Characters that pass one end wrap around to the other end. Large shifts can wrap around many times. Instead of changing the string after every operation, I combine all movements into one total shift. I then reduce that total using the string length and rotate the string only once.

1. Can the string be empty or null?
2. Can a shift amount be larger than the string length?
3. Are shift directions always represented by 0 for left and 1 for right?

The input string in the diagram is "abcdef". The shift operations are [[0, 8], [1, 2], [0, 1]]. A direction of 0 means shift left. A direction of 1 means shift right. When a character moves past one end, it wraps around to the other end. The required final string for this example is "bcdefa".

A large shift can contain complete wraps. The string length is 6, so shifting left by 8 has the same final effect as shifting left by 2 because shifting by 6 returns every character to its starting position.

The key idea is to combine all rotations first and rotate the string once. I use one integer named netRight. Positive values represent movement to the right. Negative values represent movement to the left.

For each operation, a left shift subtracts its amount from netRight. A right shift adds its amount. After all operations are processed, modulo by the string length removes complete wraps.

The invariant is: after processing the first i operations, netRight equals the effective signed right rotation of those processed operations.

The string length is n = 6, and netRight starts at 0.

For [0, 8], the direction is left, so I subtract 8. The state changes from netRight = 0 to netRight = -8.

For [1, 2], the direction is right, so I add 2. The state changes from netRight = -8 to netRight = -6.

For [0, 1], the direction is left, so I subtract 1. The state changes from netRight = -6 to netRight = -7.

All three shift operations have now been processed.

The raw total is netRight = -7. I convert it to a non-negative right shift with k = ((netRight % n) + n) % n.

For this example, k = ((-7 % 6) + 6) % 6 = 5. A right shift of 5 on a string of length 6 is equivalent to a left shift of 1.

I calculate split = n - k = 1. The prefix is "a" and the suffix is "bcdef". Returning suffix + prefix gives "bcdefa".

This matches the direct sequence in the diagram: "abcdef" shifted left by 8 becomes "cdefab", shifted right by 2 becomes "abcdef", and shifted left by 1 becomes "bcdefa".

Rotations on a circular string combine by addition. Left movement is represented by a negative amount and right movement by a positive amount. Adding these signed movements preserves the final position of every character. Taking modulo n removes complete rotations without changing the final circular arrangement. Therefore, one final rotation produces the same result as applying all original operations in order.

The C# method first handles a null or empty string defensively. It then accumulates every shift into netRight. The expression ((netRight % n) + n) % n safely converts a negative total into a valid right-shift amount from 0 through n - 1. If k is 0, the original string is already the answer. Otherwise, the code splits at n - k and returns the suffix followed by the prefix.

If m is the number of shift operations and n is the string length, the time complexity is O(m + n). Processing the operations costs O(m), and building the final rotated string costs O(n). Auxiliary space is O(n) for the strings created to produce the returned result.

The key insight is that every operation is a rotation of the same circular string, so all shifts can be combined before rebuilding the string. Store one signed total called netRight. Subtract left-shift amounts and add right-shift amounts. After all operations, normalize the total with ((netRight % n) + n) % n. This removes complete wraps and produces one right-shift amount from 0 through n - 1. The central invariant is that after processing the first i operations, netRight represents the effective signed right rotation of those processed operations. Finally, split at n - k and return suffix + prefix. This performs only one final rotation instead of rebuilding the string after every operation.

Let m be the number of shift operations and n be the string length. Processing the m shift operations takes O(m) time. Building the final rotated string takes O(n) time. The total time is O(m + n). The code also creates string data whose total size grows with n while building the answer, so auxiliary space is O(n). The integer variables such as n, netRight, k, and split use only constant-size extra memory.

A common mistake is rotating the whole string after every operation, which can repeat O(n) work for each shift. Another mistake is reversing the direction signs. In this solution, left subtracts and right adds. Candidates may also use netRight % n directly and forget that C# can produce a negative remainder, so the correct normalization is ((netRight % n) + n) % n. Another mistake is splitting at k instead of n - k for the final right rotation. Large shift amounts must also wrap around instead of being treated as invalid.

State the signed-rotation rule before coding: left subtracts, right adds, then normalize once with modulo n. Walk through netRight as 0, -8, -6, -7, and then k = 5. This makes the final split at index 1 and the result "bcdefa" easy to justify.

I would process the events and keep one running total for each user in a dictionary. After aggregation, I would sort users by total score descending and then by UserId ascending so ties are deterministic. I would take the first three users, or all users if fewer than three exist. For large input, I keep only the per-user totals instead of the raw events. The expected time is O(n + u log u), and the auxiliary space is O(u).

The input is a sequence of events. Each event has a UserId and a Score. The same user can appear more than once. We add all scores for each user, then rank users by their final total. A larger total comes first. If two totals are equal, the smaller UserId comes first. We return up to three users. For large input, we can read events one at a time and keep only each user's running total.

1. If two users have the same total score, should UserId ascending be the tie-breaker?
2. If fewer than three unique users exist, should I return every available user?
3. Can the input be processed as a stream so I do not need to keep every event in memory?

Each input item contains a UserId and a Score. A user can have several events. We need the three users with the highest total scores. The output contains UserId and TotalScore. Higher totals rank first. For equal totals, UserId ascending decides the order. If fewer than three unique users exist, we return all of them.

I create a dictionary named totals. Its key is UserId. Its value is that user's running total score. I process the events in input order. When a user appears again, I add the new score to the existing total. This means I do not need to keep the complete event history.

The events are (u1,10), (u2,15), (u1,7), (u3,20), (u2,5), (u4,20), and (u3,8). After the first event, totals is {u1:10}. After u2 scores 15, it is {u1:10, u2:15}. The next u1 event changes u1 to 17. Then u3 becomes 20. The next u2 event changes u2 to 20. Then u4 becomes 20. Finally, u3 receives 8 more points and becomes 28. The final totals are u1=17, u2=20, u3=28, and u4=20.

I sort the aggregated users by TotalScore descending. For equal scores, I sort by UserId ascending. The complete order is (u3,28), (u2,20), (u4,20), (u1,17). Taking the first three gives (u3,28), (u2,20), and (u4,20). The tie between u2 and u4 is resolved by UserId ascending.

The dictionary always contains the exact sum of all processed scores for each user. After all events are processed, it contains the final score for every unique user. Sorting these totals by the required ranking rules puts the users in the correct order. Taking the first three therefore returns the correct top three users.

The code uses Dictionary<string, long> for the running totals. It processes each event once and updates that user's value. Then LINQ orders the dictionary by total descending and UserId ascending. Take(3) returns up to three entries. Because Take does not require three items to exist, fewer than three users are handled naturally. The example prints u3 28, u2 20, and u4 20.

Let n be the number of input events and u be the number of unique users. Aggregating takes O(n) expected time because dictionary lookup and update are O(1) on average. Sorting u users costs O(u log u). Total expected time is O(n + u log u). The dictionary and ordered result require O(u) auxiliary space. Empty input returns an empty result. Fewer than three users returns all available users. Negative scores still work because ranking uses the final totals.

The key idea is to separate aggregation from ranking. First, use a dictionary that maps UserId to that user's running TotalScore. The invariant is: after processing any prefix of the input, totals[userId] equals the sum of all scores seen so far for that user. After every event has been processed, the dictionary contains each user's exact final total. We then sort those totals by score descending and UserId ascending. Taking the first three entries gives the required result. This also fits large input because the raw event history does not need to stay in memory. Only O(u) aggregated user totals are retained.

Let n be the number of events and u be the number of unique users. We process every event once. Dictionary lookup and update are O(1) on average, so aggregation takes O(n) expected time. We then sort u aggregated users, which takes O(u log u) time. The total expected time is O(n + u log u). The dictionary stores one total for each unique user, and the ordered result may hold up to u users during sorting, so the auxiliary space is O(u).

A common mistake is ranking individual events instead of first adding all scores for the same user. Another mistake is sorting equal scores without the UserId tie-breaker, which can make the order nondeterministic or incorrect for the stated rule. Candidates may also sort scores ascending instead of descending. For large input, keeping every raw event wastes memory when only the running total for each user is needed. Finally, claiming O(n) total time is incorrect for this implementation because sorting the u unique users costs O(u log u).

State the ranking rule before writing the sort: total score descending, then UserId ascending. Then explain that the dictionary removes the need to keep the raw event history and that the final sort is why the total complexity includes O(u log u).

I would use a Dictionary<char, int> to count how many times each character appears. First, I scan the string from left to right and build the frequency map. Then I scan the string again in the original order. The first character whose count is exactly 1 is the answer, so I return it immediately. For "swiss", the first unique character is 'w'. This takes O(n) expected time and O(n) auxiliary space in the worst case.

The input is a string. We need to return the first character that appears exactly once. The word "first" means the earliest such character when we read from left to right. If no character appears exactly once, this solution returns '\0'. The diagram uses two passes. The first pass counts every character. The second pass keeps the original order and finds the first count of 1. For the example "swiss", the answer is 'w'.

1. Should uppercase and lowercase letters be treated as different characters?
2. What should I return when there is no unique character? In this solution, I will return '\0'.

The input is one string. We return a character, not an index. We need the first character whose total frequency is exactly 1. If no such character exists, we return '\0'. The diagram treats character comparison as case-sensitive.

I use a Dictionary<char, int>. Each key is a character. Its value is the number of times that character appears in the string. The important idea is to count first and then check characters in their original order. Counting tells us which characters are unique. The second pass tells us which unique character comes first.

Start with an empty dictionary. Process "swiss" from left to right. At index 0, read 's', so the map becomes { s: 1 }. At index 1, read 'w', so it becomes { s: 1, w: 1 }. At index 2, read 'i', so it becomes { s: 1, w: 1, i: 1 }. At index 3, read 's', so s becomes

2. At index 4, read 's' again, so s becomes
3. The completed map is { s: 3, w: 1, i: 1 }.

Now scan "swiss" again from left to right. At index 0, 's' has frequency 3, so it is not unique. Continue. At index 1, 'w' has frequency 1. That satisfies the condition, so return 'w' immediately. No later character needs to be checked.

After the first pass, the dictionary contains the exact frequency of every character in the string. During the second pass, we visit characters in their original left-to-right order. Therefore, the first character we see with frequency 1 must be the first non-repeating character. For "swiss", that character is 'w'.

The method first handles a null or empty string by returning '\0'. It then creates a Dictionary<char, int>. The first foreach loop counts characters. The second foreach loop checks those counts in original order. As soon as a count equals 1, the method returns that character. If the second loop finishes without finding one, the method returns '\0'.

There are at most two passes over the string. Dictionary lookup and insertion are O(1) on average, so the overall expected time is O(n). The dictionary stores one entry for each distinct character, so it uses O(k) extra memory where k is the number of distinct characters. In the worst case, k can equal n, so the auxiliary space is O(n). Important cases are an empty string, all characters repeating, one unique character, and uppercase versus lowercase characters.

The key insight is to separate two jobs: count every character, then preserve the original order while finding the answer. A Dictionary<char, int> stores character -> frequency. After the first pass, the central invariant is that the dictionary contains the exact frequency of every character in the full string. The second pass reads the original string from left to right. Therefore, the first character whose stored frequency is 1 is exactly the first non-repeating character. This avoids repeatedly rescanning the string to count each candidate character.

Let n be the length of the string and k be the number of distinct characters. The code makes at most two passes through the input. Dictionary lookup and insertion are O(1) on average, so the total expected time is O(n). The dictionary stores one entry for each distinct character, which is O(k) extra memory. Because k can grow to n, the worst-case auxiliary space is O(n), matching the diagram.

A common mistake is returning any character with frequency 1 instead of the first one in the original string. Another mistake is deciding that a character is unique during the first pass before all frequencies are known. Candidates may also forget the no-result case and fail to return '\0'. Another error is claiming guaranteed O(n) time without noting that Dictionary operations are O(1) on average. Finally, do not accidentally treat uppercase and lowercase characters as the same when using char keys as shown here.

Explain why there are two passes: the first pass learns the final frequency of every character, and the second pass preserves original order so the first character with count 1 can be returned immediately.

I would lowercase the text, extract word tokens with the regex [A-Za-z0-9']+, and then process every adjacent pair from left to right. I store each bigram in a Dictionary<string, int>, where the value is its frequency. If the pair is new, I store 1. If it already exists, I increment the count. This correctly counts repeated pairs, and the dictionary keys also give the unique bigrams. The solution takes O(n) expected time and O(u) auxiliary space, which is O(n) in the worst case.

The input is one text string. We need to find every pair of neighboring words while keeping their original order. We first make the text lowercase and extract words while ignoring punctuation. Then we join each word with the next word to form a bigram. We count how many times each bigram appears. For the example "The cat sat on the cat sat.", the repeated pairs "the cat" and "cat sat" each appear twice. A dictionary fits well because it stores one count for each unique pair.

1. Should matching ignore letter case?
2. Should punctuation be ignored while preserving the original word order?
3. Should repeated bigrams be returned with their counts, or should the result contain only unique bigrams?

The input is a text string. The diagram uses "The cat sat on the cat sat." After lowercase tokenization, the tokens are ["the", "cat", "sat", "on", "the", "cat", "sat"]. We must form every adjacent two-word pair in order and count its frequency. The final frequency map is {"the cat":2, "cat sat":2, "sat on":1, "on the":1}. If a deduplicated result is needed, the dictionary keys give the unique bigrams: ["the cat", "cat sat", "sat on", "on the"].

I use a Dictionary<string, int>. Each key is one bigram. Each value is the number of times that bigram has appeared. I process the token list from left to right. At position i, I combine tokens[i] and tokens[i + 1]. The central invariant is: before processing position i, the dictionary stores the exact frequencies for all bigrams from positions 0 through i - 1.

The text is converted to lowercase. Regex [A-Za-z0-9']+ extracts the word tokens while ignoring punctuation and preserving token order. The dictionary starts empty. Traversal starts at i = 0. If there are fewer than two tokens, there is no adjacent pair, so the loop runs zero times and the returned dictionary is empty.

There are 7 tokens, so there are 6 adjacent bigram positions.

Step 1, i = 0: tokens[0] is "the" and tokens[1] is "cat". They form "the cat". The state before is {}. The pair is new, so it is added with count 1. The state becomes {"the cat":1}.

Step 2, i = 1: "cat" and "sat" form "cat sat". The state before is {"the cat":1}. The pair is new, so the state becomes {"the cat":1, "cat sat":1}.

Step 3, i = 2: "sat" and "on" form "sat on". The pair is new. The state becomes {"the cat":1, "cat sat":1, "sat on":1}.

Step 4, i = 3: "on" and "the" form "on the". The pair is new. The state becomes {"the cat":1, "cat sat":1, "sat on":1, "on the":1}.

Step 5, i = 4: "the" and "cat" form "the cat" again. The dictionary already contains this key, so its count changes from 1 to 2. The state becomes {"the cat":2, "cat sat":1, "sat on":1, "on the":1}.

Step 6, i = 5: "cat" and "sat" form "cat sat" again. Its count changes from 1 to 2. The final state is {"the cat":2, "cat sat":2, "sat on":1, "on the":1}.

After step 6, all adjacent positions have been processed. The loop stops because there is no later token available to form another pair.

Every adjacent pair has exactly one starting position. The loop processes every valid starting position exactly once. A new pair is inserted with count 1. A repeated pair updates the same dictionary key by increasing its count. Therefore, after all six positions are processed, each stored value equals the true frequency of that bigram. Dictionary keys are unique, so the same structure also provides the deduplicated bigram set.

GetBigramCounts first converts the text to lowercase and uses Regex.Matches with [A-Za-z0-9']+ to build the token list. It creates an empty Dictionary<string, int>. The loop runs while i < tokens.Count - 1. At every position it builds tokens[i] + " " + tokens[i + 1]. ContainsKey checks whether the bigram already exists. Existing counts are incremented. New bigrams are inserted with count 1. The method returns the frequency map. GetUniqueBigrams reuses GetBigramCounts and returns its keys as a list.

Let n be the number of tokens and u be the number of unique bigrams. The loop processes n - 1 adjacent positions. Dictionary lookup and insertion are O(1) on average, so the overall expected time is O(n). The dictionary stores u entries, so its auxiliary space is O(u), which is O(n) in the worst case. Relevant edge cases are fewer than two tokens, repeated pairs, punctuation, and differences in letter case.

The key idea is to count each adjacent pair as it is encountered. After tokenization, position i forms exactly one bigram from tokens[i] and tokens[i + 1]. A Dictionary<string, int> stores bigram -> frequency. If the bigram is new, its count starts at 1. If it is already present, its existing count is incremented.

The invariant is: before processing position i, the dictionary contains the exact frequencies of all bigrams from positions 0 through i - 1. Processing position i updates exactly the bigram that starts there. After the last valid position is processed, the dictionary contains the correct frequency for every bigram. Its unique keys also provide the deduplicated result.

Let n be the number of tokens and u be the number of unique bigrams. There are n - 1 adjacent pairs to process. A C# Dictionary lookup or insertion is O(1) on average, so the total expected time is O(n).

The dictionary stores one entry for each unique bigram. That needs O(u) auxiliary space. In the worst case, nearly every adjacent pair is different, so u grows with n and the auxiliary space is O(n).

1. Splitting only on spaces. This can leave punctuation attached to a word, so "sat." and "sat" become different tokens.
2. Forgetting to normalize case. Then "The" and "the" can create different bigrams even though the diagram treats them as the same token.
3. Resetting a repeated bigram to 1 instead of incrementing its existing count.
4. Building pairs from non-adjacent tokens. A bigram here must use tokens[i] and tokens[i + 1] in the original order.
5. Claiming guaranteed O(n) time. Dictionary lookup and insertion are O(1) on average, so the correct overall wording is O(n) expected time.

Before coding, state exactly what the dictionary stores: each key is one adjacent bigram and each value is its frequency. Then use the repeated pairs "the cat" and "cat sat" to show why an existing key must be incremented instead of inserted again.

I would sort the strings with two comparison keys. The first key is the string length, so shorter strings come first. If two strings have the same length, I would compare the full strings with StringComparer.Ordinal as the tie-break. In C#, OrderBy handles the length and ThenBy handles the ordinal text comparison. For the example, the result is ["an", "fig", "kiwi", "pear", "plum", "apple"]. The worst-case time is O(n log n * k), with O(n) auxiliary space.

The input is an array of strings. We need to return the same strings in sorted order. Shorter strings must come before longer strings. When two strings have the same length, their text decides which one comes first. The diagram uses case-sensitive ordinal comparison for that tie. The main idea is to use two comparison keys for every string: its length first and the full string second. C# LINQ supports this directly with OrderBy followed by ThenBy, so the implementation is short and matches the required order.

1. Should equal-length strings use case-sensitive ordinal comparison?
2. Should the method return a new sorted array instead of changing the input array?
3. Can the input contain duplicate strings or be empty?

The input is a string array. The output is also a string array. We return the strings themselves, not their indices. The first rule is shorter length first. If two strings have the same length, we compare their full text with StringComparer.Ordinal. This comparison is case-sensitive and culture-independent.

For the diagram example, the input is ["pear", "fig", "apple", "kiwi", "plum", "an"]. The output is ["an", "fig", "kiwi", "pear", "plum", "apple"].

For every word, I use a two-part comparison key. The first part is the string length. The second part is the string itself, compared with StringComparer.Ordinal.

The example keys are:

• pear -> (4, "pear")
• fig -> (3, "fig")
• apple -> (5, "apple")
• kiwi -> (4, "kiwi")
• plum -> (4, "plum")
• an -> (2, "an")

The central invariant is that length always decides first. Text is compared only when the lengths are equal.

Start with ["pear", "fig", "apple", "kiwi", "plum", "an"]. Their lengths are 4, 3, 5, 4, 4, and 2.

"an" has length 2, so it comes first. "fig" has length 3, so it comes next. "pear", "kiwi", and "plum" all have length 4. Their lengths are tied, so StringComparer.Ordinal compares their text. That gives the order "kiwi", "pear", "plum". Finally, "apple" has length 5, so it comes last.

The ordered keys are (2, "an"), (3, "fig"), (4, "kiwi"), (4, "pear"), (4, "plum"), and (5, "apple"). The final returned array is ["an", "fig", "kiwi", "pear", "plum", "apple"].

OrderBy(word => word.Length) creates the primary ordering by length. ThenBy(word => word, StringComparer.Ordinal) resolves equal-length ties with ordinal text comparison. ToArray() materializes the ordered sequence into the final string array.

There is no hash map, stack, queue, or custom data structure. The solution uses the built-in LINQ sorting pipeline with two comparison keys.

Every comparison follows the same composite rule: (Length, String). A string with a smaller length must come before a string with a larger length. If the lengths match, ordinal text comparison gives a consistent order inside that equal-length group. Because both required ordering rules are applied in this exact sequence, the returned array satisfies the sorting rule.

The SortStrings method receives the input string array. OrderBy reads word.Length as the primary key. ThenBy uses each word itself as the secondary key with StringComparer.Ordinal. ToArray creates the final returned array. Main runs the exact example from the diagram and prints ["an", "fig", "kiwi", "pear", "plum", "apple"].

Let n be the number of strings. Let k represent the cost of comparing string characters when equal-length strings need the tie-break. The worst-case time shown by the diagram is O(n log n * k). The auxiliary space is O(n) for the ordered result and sorting buffers.

An empty array returns an empty array. Duplicate strings remain together naturally. Equal-length strings rely on the ordinal tie-break. Uppercase and lowercase follow case-sensitive ordinal ordering.

Use a two-key sort. The primary key is word.Length. The secondary key is the complete string compared with StringComparer.Ordinal. The central invariant is that every comparison decides by length first, and only equal-length strings use ordinal text order. This exactly matches the required rule. In C#, OrderBy expresses the primary key and ThenBy expresses the tie-break key. For the example's length-4 group, "pear", "kiwi", and "plum" are tied on length, so ordinal comparison orders them as "kiwi", "pear", "plum".

Let n be the number of strings. Let k be the cost of comparing string characters when equal-length strings need the secondary comparison. The worst-case time is O(n log n * k). The n log n part comes from sorting. The k part accounts for text comparisons that may inspect several characters. The auxiliary space is O(n) because LINQ's ordering operation uses storage for the ordered data and the final result is materialized into an array. This complexity includes the sorting work shown in the diagram.

A common mistake is sorting only by length and forgetting the required tie-break for equal-length strings. Another mistake is using a culture-sensitive string comparison instead of StringComparer.Ordinal. A candidate may also reverse the keys and sort by text before length, which produces a different order. Another mistake is returning indices even though this problem asks for the sorted strings themselves. It is also incorrect to ignore the cost of string comparison when explaining the diagram's O(n log n * k) worst-case time.

Before writing code, state the comparison rule clearly: "I will sort by the pair (Length, String), using StringComparer.Ordinal for the second key." That makes the OrderBy and ThenBy implementation easy to explain and verify.