46 Microsoft .NET Developer Interview Questions & Answers

I would use two pointers, one for each sorted array, and a third position for the result. I compare the current values and copy the smaller one into the result, then move that input pointer forward. When one array is exhausted, I copy the remaining values from the other array without more comparisons. This keeps the result sorted. The time complexity is O(m + n). The result array uses O(m + n) space, with O(1) auxiliary space beyond the output.

The two input arrays are already in ascending order. We need to combine all their values into one new array that is also in ascending order. We do not need to sort everything again. We start at the first value of each array. We compare those two values and copy the smaller one into the result. Then we move forward only in the array that supplied that value. When one input has no values left, we copy the rest of the other input directly.

1. Can I assume both input arrays are already sorted in ascending order?
2. Should I return a new array rather than modify either input array?
3. Should duplicate values be preserved in the merged result?

The diagram uses A = [1, 4, 7, 9] and B = [2, 3, 6, 8, 10]. Their lengths are m = 4 and n = 5. The result therefore has nine positions. The required result is [1, 2, 3, 4, 6, 7, 8, 9, 10]. Every input element is copied into the output.

Use pointer i for A and pointer j for B. Use k for the next free position in the result array. While both arrays still have values, compare A[i] with B[j]. Copy the smaller current value to result[k]. Then move the pointer for the array that supplied that value and move k forward. If the values are equal, the C# code uses A[i] <= B[j], so the value from A is copied first.

Create result with length m + n. Start with i = 0, j = 0, and k = 0. This means both input pointers begin at their first values and the result is empty. The main invariant is that result[0..k-1] is already sorted and contains exactly the values consumed so far from A and B in correct merged order.

At i = 0 and j = 0, compare 1 and 2. Take 1 from A and place it at result[0]. Now i = 1 and k = 1. The result prefix is [1].

Compare 4 and 2. Take 2 from B and place it at result[1]. Now j = 1 and k = 2. The result prefix is [1, 2].

Compare 4 and 3. Take 3 from B and place it at result[2]. Now j = 2 and k = 3. The result prefix is [1, 2, 3].

Compare 4 and 6. Take 4 from A and place it at result[3]. Now i = 2 and k = 4. The result prefix is [1, 2, 3, 4].

Compare 7 and 6. Take 6 from B and place it at result[4]. Now j = 3 and k = 5. The result prefix is [1, 2, 3, 4, 6].

Compare 7 and 8. Take 7 from A and place it at result[5]. Now i = 3 and k = 6. The result prefix is [1, 2, 3, 4, 6, 7].

Compare 9 and 8. Take 8 from B and place it at result[6]. Now j = 4 and k = 7. The result prefix is [1, 2, 3, 4, 6, 7, 8].

Compare 9 and 10. Take 9 from A and place it at result[7]. Now i = 4 and k = 8, so A is exhausted. The main comparison loop stops. The only remaining value is 10 from B, so it is copied directly to result[8]. The final result is [1, 2, 3, 4, 6, 7, 8, 9, 10].

Before each write, A[i] and B[j] are the smallest values not yet copied from their own sorted arrays. Choosing the smaller of those two values therefore gives the smallest value still available overall. This keeps the result sorted. When one array ends, the remaining part of the other array is already sorted and every remaining value belongs after the values already copied, so that suffix can be copied directly.

The C# method creates one result array of size m + n. The first while loop performs the comparisons and advances i or j. Two final while loops copy any values left in A or B. Each input element is copied exactly once, so the running time is O(m + n). The returned result occupies O(m + n) space. Apart from that required output array, the algorithm uses only the integer variables m, n, i, j, and k, so auxiliary space beyond the output is O(1).

The key insight is that both inputs are already sorted, so their smallest unmerged values are always at the two current pointer positions. Keep i on A and j on B. Compare A[i] and B[j], copy the smaller value to result[k], and move only the pointer that supplied that value. The invariant is that result[0..k-1] is sorted and contains exactly the values consumed so far from A and B in correct merged order. Once one input is exhausted, no more comparisons are needed because the remaining suffix of the other input is already sorted.

Let m be the length of A and n be the length of B. Every value from both arrays is copied to the result once, so the time complexity is O(m + n). The returned result array contains m + n values, so it uses O(m + n) space. If auxiliary space means extra working memory excluding the required returned array, the algorithm uses O(1), because it only keeps a few integer variables such as i, j, and k.

A common mistake is moving both input pointers after every comparison. Only the pointer for the value that was copied should move. Another mistake is forgetting to copy the remaining suffix after one array is exhausted. Candidates may also allocate a result array with the wrong length instead of m + n. Another error is sorting the combined values again, which throws away the advantage of already-sorted inputs. Finally, the complexity should be stated as O(m + n), not O(m * n).

While coding, say what i, j, and k mean before writing the loop. Then state the invariant: the part of result before k is already the correctly merged sorted prefix. This makes each comparison and pointer movement easy to justify.

I would use two pointers because the array is already sorted. I keep a write pointer at the next position for a unique value and scan from left to right with a read pointer. If nums[read] differs from nums[write - 1], I copy it to nums[write] and move write forward. Otherwise, I skip the duplicate. The returned write value is the new unique length. This takes O(n) time and O(1) auxiliary space.

The input is a sorted array, so repeated values appear next to each other. We need to keep one copy of each value, preserve the original order, and modify the same array instead of building another collection. After processing, the first k positions contain the unique values, and the function returns k. For the example [1, 1, 2, 2, 3, 3, 3, 4, 5, 5, 6], the valid prefix becomes [1, 2, 3, 4, 5, 6], so k is 6.

1. Can I modify the input array in place?
2. Should I return only the new length while storing the unique values in the first k positions?
3. Is the input guaranteed to be sorted?

The input is a sorted integer array. We remove repeated values in place while preserving the order of first appearance. We return an integer k. Indices 0 through k - 1 contain the unique values. Positions from k through the end of the physical array are not part of the returned result.

Because the array is sorted, duplicate values are consecutive. We use a read pointer to inspect each remaining element and a write pointer to mark the next place where a new unique value should go. The central invariant is that indices 0 through write - 1 always contain exactly the unique values found so far, in their original order.

If nums is null or empty, return 0. Otherwise, the first value is already unique, so set write = 1. Start read at index 1. At every step, compare nums[read] with nums[write - 1], which is the last unique value currently stored.

Start with nums = [1, 1, 2, 2, 3, 3, 3, 4, 5, 5, 6] and write = 1.

At read = 1, nums[1] is 1 and nums[write - 1] is nums[0] = 1. They are equal, so this is a duplicate. Skip it. write remains 1.

At read = 2, nums[2] is 2 and nums[0] is

1. They differ. Copy 2 to nums[1], then increment write to
2. The valid prefix is [1, 2].

At read = 3, nums[3] is 2 and nums[1] is 2. They are equal, so skip it. write remains 2.

At read = 4, nums[4] is 3 and nums[1] is

2. They differ. Copy 3 to nums[2], then increment write to
3. The valid prefix is [1, 2, 3].

At read = 5, nums[5] is 3 and nums[2] is 3. Skip this duplicate. write remains 3.

At read = 6, nums[6] is 3 and nums[2] is 3. Skip this consecutive duplicate too. write remains 3.

At read = 7, nums[7] is 4 and nums[2] is

3. They differ. Copy 4 to nums[3], then increment write to
4. The valid prefix is [1, 2, 3, 4].

At read = 8, nums[8] is 5 and nums[3] is

4. They differ. Copy 5 to nums[4], then increment write to
5. The valid prefix is [1, 2, 3, 4, 5].

At read = 9, nums[9] is 5 and nums[4] is 5. They are equal, so skip it. write remains 5.

At read = 10, nums[10] is 6 and nums[4] is

5. They differ. Copy 6 to nums[5], then increment write to
6. The valid prefix is now [1, 2, 3, 4, 5, 6]. The loop ends and the function returns 6.

Before each comparison, the first write positions contain all unique values seen so far in the correct order. If nums[read] equals nums[write - 1], the current value is another copy of the last unique value, so skipping it is safe. If they differ, nums[read] is the next new unique value, so writing it at nums[write] extends the valid prefix correctly. When the scan finishes, write equals the number of unique values.

The method first handles null or empty input. It starts write at 1 because the first element is already unique. A for loop moves read from index 1 to the last index. When nums[read] differs from nums[write - 1], the code stores nums[read] at nums[write] and increments write. Duplicates cause no write operation. The method finally returns write as k.

The read pointer moves through the array once, so the time complexity is O(n). The algorithm uses only pointer variables and modifies the original array, so auxiliary space is O(1). Null or empty input returns 0. A single element returns 1. If all values are equal, the result is 1. If all values are already unique, the result is the original array length.

Use two pointers on the sorted array. The read pointer scans from index 1 to the end. The write pointer marks the next position for a newly found unique value. At each step, compare nums[read] with nums[write - 1], the last unique value already stored. If they are equal, skip the duplicate. If they differ, copy nums[read] to nums[write] and increment write. The invariant is that indices 0 through write - 1 always contain exactly the unique values seen so far in their original order. This works because sorted input places equal values next to one another.

The time complexity is O(n), where n is the number of elements in the input array. The read pointer moves from index 1 to the end, so each remaining element is examined once. The auxiliary space complexity is O(1) because the algorithm changes the original array and uses only a constant number of integer variables. It does not create another array, set, or other collection that grows with n.

One mistake is incrementing write when the current value is a duplicate. That would put repeated values inside the valid prefix. Another mistake is comparing against the wrong value after earlier positions have been overwritten. The approved solution compares nums[read] with nums[write - 1], the last unique value stored. Candidates may also return the whole physical array instead of returning k and treating only indices 0 through k - 1 as valid. Another mistake is allocating a separate collection and then claiming O(1) auxiliary space. Finally, failing to handle an empty input can make the initial write = 1 state invalid.

Explain the invariant before writing the loop: indices 0 through write - 1 always contain the unique values found so far in the correct order. Then each comparison and write-pointer movement follows directly from that rule.

I would scan the string from left to right and use a HashSet<char> to remember characters I have already seen. I would also use a StringBuilder to build the result in order. If the current character is not in the set, I add it to the set and append it to the result. Otherwise, I skip it. This keeps only the first occurrence of each character. The solution takes O(n) expected time and O(n) auxiliary space in the worst case.

The problem asks us to remove repeated characters from a string while keeping the first time each character appears. The remaining characters must stay in the same left-to-right order. For example, the diagram uses "programming" and produces "progamin". I process one character at a time. I remember the characters that have already been accepted. If a character is new, I keep it. If it has already appeared, I skip it. This approach directly matches the required behavior and avoids repeatedly searching the result string.

1. Should character comparison be case-sensitive?
2. Should the first-occurrence order always be preserved?
3. How should an empty string be handled?

The input is a string. The output is a new string that keeps only the first occurrence of each character. The order of those first occurrences must stay unchanged. In the diagram, the input is "programming". The expected output is "progamin".

I use a HashSet<char> named seen. It stores the characters that have already been accepted. I also use a StringBuilder named result. It stores the output in the same order in which characters are accepted. The main rule is that a character is appended only when it is not already in seen.

At the beginning, seen is empty and result is empty. Processing starts with the first character and moves from left to right. The invariant is that seen contains the characters already kept, and result contains those same characters exactly once in their first-occurrence order.

The string is "programming" with indices 0 through 10.

At index 0, the character is 'p'. seen is empty, so 'p' is new. Add 'p' to seen and append it to result. result becomes "p".

At index 1, the character is 'r'. It is not in seen. Add it to seen and result becomes "pr".

At index 2, the character is 'o'. It is not in seen. Add it and result becomes "pro".

At index 3, the character is 'g'. It is not in seen. Add it and result becomes "prog".

At index 4, the character is 'r'. It is already in seen, so skip it. result stays "prog".

At index 5, the character is 'a'. It is new, so add it. result becomes "proga".

At index 6, the character is 'm'. It is new, so add it. result becomes "progam".

At index 7, the character is 'm'. It is already in seen, so skip it. result stays "progam".

At index 8, the character is 'i'. It is new, so add it. result becomes "progami".

At index 9, the character is 'n'. It is new, so add it. result becomes "progamin".

At index 10, the character is 'g'. It is already in seen, so skip it. result stays "progamin".

After the traversal finishes, the final returned string is "progamin".

A character is added to result only when it has not appeared before. As soon as the character is kept, it is also added to seen. Any later copy of that character is therefore skipped. Because the input is processed from left to right, the first occurrence is kept and the relative order of all kept characters is preserved.

The method first handles a null or empty string defensively. It then creates an empty HashSet<char> and an empty StringBuilder. The foreach loop reads characters from left to right. For each character, the code checks whether seen already contains it. If not, the code adds it to seen and appends it to result. If it is already present, no state change is made. After all characters are processed, result.ToString() returns the answer.

For n input characters, each character is processed once. HashSet<char> membership checks and insertions are O(1) on average, so the total expected time is O(n). The set can contain up to k distinct characters, where k is at most n, and the result can also grow with the input. Therefore, the auxiliary space is O(n) in the worst case. The diagram also shows important cases such as an empty string returning an empty string, "a" returning "a", "aaaa" returning "a", repeated characters mixed with numbers and symbols, and case-sensitive character handling.

The key idea is to remember which characters have already been accepted. HashSet<char> seen provides an average O(1) membership check. StringBuilder result stores the characters that survive duplicate removal. We traverse from left to right. For each character, we first check seen. If the character is new, we add it to seen and append it to result. If it is already present, we skip it. The central invariant is that seen contains exactly the characters already accepted, while result contains those characters once and in first-occurrence order.

Let n be the length of the input string. We process each character once. A HashSet<char> lookup or insertion is O(1) on average, so the overall expected time is O(n). This is expected time because hash-table operations are not guaranteed to be constant time in every theoretical worst case. The HashSet stores up to k distinct characters, where k is at most n. The StringBuilder also stores the output. Therefore, the auxiliary space is O(n) in the worst case.

One mistake is appending a character before checking whether it was already seen, which keeps duplicates. Another is sorting the input first, which destroys the required first-occurrence order. A candidate may also use frequency counting even though the problem only needs to know whether a character has appeared before. Repeated string concatenation can create unnecessary copies compared with StringBuilder. Another mistake is claiming guaranteed O(n) time instead of O(n) expected time when the solution depends on average O(1) HashSet operations.

Explain the invariant before writing the loop: seen contains every character already kept, and result contains those characters once in their original first-occurrence order. Then each loop decision becomes easy to justify.

I would use a running prefix sum and a Dictionary<int, int>. The dictionary stores an earlier prefix sum and the index where it appeared. For each number, I update the running sum and compute need = prefixSum - target. If need is already in the dictionary, the elements after that stored index through the current index form the answer. I process each item at most once and stop when the answer is found. This takes O(n) expected time and O(n) auxiliary space.

We have an unordered integer array and a target number. We need to find neighboring elements whose total equals that target. The elements must stay next to each other in the original array. In the shown implementation, we return the inclusive start and end positions of one matching group. We keep a running total while moving from left to right. We also remember earlier running totals so we can quickly tell when the part between two positions has exactly the required sum. This approach also works when the array contains negative numbers.

1. Should I return the start and end indices, the values, or the subarray itself?
2. If more than one valid subarray exists, is returning any one valid result acceptable?
3. What should I return when no matching subarray exists?

The input is an unordered integer array named nums and an integer target. We need one contiguous subarray whose values add up to target. Contiguous means the values must be next to each other in the original array. The implementation shown in the diagram returns two 0-based inclusive indices: the start index and the end index. If no matching subarray exists, it returns an empty integer array.

Use a prefix sum with a Dictionary<int, int>. A prefix sum is the total of all values processed so far. The dictionary maps a retained prefix sum to an earlier index where that sum occurred. If the current prefix sum is currentSum, then a subarray ending at the current index has sum target when an earlier prefix sum equals currentSum - target. That earlier prefix sum tells us where the matching subarray starts.

Set prefixSum to 0. Initialize the dictionary with 0 mapped to -1. The entry 0 -> -1 represents a prefix sum of zero before the array begins. This special entry lets the same logic find a valid subarray that starts at index 0. For example, if the running sum becomes 7, then need is 0 and the returned start index is -1 + 1, which is 0.

The array is [3, 4, -7, 1, 3, 3, 1, -4] and target is 7.

At index 0, the current value is 3. prefixSum becomes 3. We calculate need = 3 - 7 = -4. The dictionary currently contains {0: -1}. It does not contain -4, so no answer ends at index 0. We store prefix sum 3 at index 0. The dictionary becomes {0: -1, 3: 0}.

At index 1, the current value is 4. prefixSum becomes 7. We calculate need = 7 - 7 = 0. The dictionary contains 0 at index -1. Therefore the matching subarray starts at -1 + 1 = 0 and ends at index 1. We return [0, 1]. The values are [3, 4], and 3 + 4 = 7. Processing stops immediately, so indices 2 through 7 are not processed.

Suppose prefixSum[i] is the running total through index i, and an earlier prefix sum at index j equals prefixSum[i] - target. Then prefixSum[i] - prefixSum[j] equals target. That difference is exactly the sum of nums[j + 1] through nums[i]. The dictionary stores retained earlier prefix sums and their indices. When the needed prefix sum appears, the algorithm can recover the correct start index. In the example, prefix sum 0 is stored at index -1, so the valid range is indices 0 through 1.

The C# method creates a Dictionary<int, int> with 0 mapped to -1 and sets prefixSum to 0. It loops through nums from left to right. For each element, it updates prefixSum and calculates need = prefixSum - target. It calls TryGetValue before inserting the current prefix sum. If need exists, it immediately returns [storedIndex + 1, currentIndex]. Otherwise, it stores the current prefix sum only if it is not already present. If the loop finishes without finding an answer, it returns Array.Empty<int>().

The expected time is O(n) because we process the input at most once, and C# Dictionary<int, int> lookup and insertion are O(1) on average. The auxiliary space is O(n) because the dictionary can grow with the number of processed prefix sums. The method handles an empty array, no matching subarray, a valid subarray starting at index 0, and negative numbers. Negative values are important because a normal sliding-window approach that relies on the sum changing monotonically is not reliable here.

The key idea is to turn the subarray-sum problem into a prefix-sum lookup. Let prefixSum be the total from index 0 through the current index i. If an earlier prefix sum equals prefixSum - target, then the values after that earlier index through i sum to target. The invariant is that the dictionary contains retained prefix sums from earlier positions and the earlier index stored for each one. Lookup happens before insertion. This lets the algorithm return immediately when a valid range is found and works correctly even when the array contains negative numbers.

Let n be the number of elements in nums. We process the input at most once. Each Dictionary<int, int> lookup and insertion is O(1) on average, so the overall expected time is O(n). This is expected time because hash-table operations are not guaranteed to take constant time in every possible case. The dictionary may store prefix sums for many processed positions, so the auxiliary space is O(n). Auxiliary space means extra memory used by the algorithm.

A common mistake is using a simple sliding window even though negative values are allowed. With negative numbers, expanding or shrinking a window does not change the sum in a predictable direction. Another mistake is forgetting the initial dictionary entry 0 -> -1, which is needed to find a valid range starting at index 0. Candidates may also calculate the needed prefix sum incorrectly. It must be prefixSum - target. Another mistake is continuing to process later elements after this implementation has already returned a match. Finally, do not claim guaranteed O(n) time because Dictionary operations are O(1) on average.

Explain the equation before writing code: if currentPrefix - earlierPrefix = target, then earlierPrefix = currentPrefix - target. Once that relationship is clear, the dictionary lookup, returned indices, and 0 -> -1 initialization are easy to justify.

I would explain stack and heap as two different parts of the .NET memory model. Each thread has a call stack for active method frames and execution state. Most managed objects, such as class instances and arrays, live on the GC-managed heap. Value types are not automatically stored on the stack. Stack frames unwind when methods return, while heap objects remain alive while reachable from GC roots. Allocation and cleanup costs depend on the JIT, garbage collector, runtime configuration, and workload.

The question asks how the stack and heap differ in .NET and when each matters. The main distinction is lifetime. A thread's call stack represents active method calls and their execution state. The managed heap stores most managed objects. A value type is not automatically a stack value because its storage depends on where the containing value lives. A heap object can survive after its creating method returns if it is still reachable from a GC root. The JIT and garbage collector manage many physical details for us.

1. Do you want the conceptual .NET memory model, or should I also discuss JIT details such as registers and optimized-away locals?
2. Should I cover explicit stack-oriented features such as stackalloc, Span<T>, and ref-like types?
3. Should I explain GC reachability and why collection does not happen immediately when a method returns?

Each thread has its own call stack. It represents active method calls and execution state. A method call creates a logical stack frame. That frame may contain information such as eligible locals and return information. When the method returns, its frame is unwound.

The managed heap is runtime-managed memory controlled by the .NET garbage collector. Most class instances, arrays, strings, boxed values, collections, delegates, and other managed objects live there.

A common shortcut says value types live on the stack and reference types live on the heap. That is not generally correct.

A value type stores its data inline wherever its containing location lives. A value-type local may be held in a stack slot or register. A value-type field inside a class instance is part of that heap object. A boxed value is stored on the managed heap.

A reference-type object normally lives on the managed heap. A variable that holds its reference may be kept in a stack slot, register, heap object, or another location chosen by the JIT/runtime.

Method frames are managed automatically as calls execute and return. Frame setup and unwinding are typically very cheap.

Managed-object allocation is performed by the runtime. The new keyword commonly creates managed objects, but heap allocation is not defined only by that keyword.

A stack frame normally exists for the duration of its method invocation. A managed object follows a different rule. It remains live while reachable from GC roots. After it becomes unreachable, it becomes eligible for collection. A later GC may reclaim it. Collection timing is nondeterministic.

Program.Main calls Demo. Demo becomes the active method above Main on the call stack.

Demo creates int x = 10. x is a value-type local associated with Demo's execution. Its exact physical location is a JIT implementation detail.

Next, Person p = new Person() creates Person object A on the managed heap. p contains a reference to object A. The object initially has Name equal to null and Age equal to 0.

The code then sets Name to "Alice" and Age to 30. The program prints x = 10 and p.Name = Alice, p.Age = 30.

When Demo returns, its logical stack frame is unwound. x and p are no longer used by Demo. If Person object A is then unreachable from every GC root, it becomes eligible for collection. A later garbage collection may reclaim it.

C# parameters are passed by value by default. For a value type, the value is copied. For a reference type, the reference value is copied, so both variables can refer to the same object. The ref, out, and in keywords change parameter-passing behavior.

Normally, I choose the correct C# type and lifetime rather than manually choosing stack or heap memory. Stack-specific features such as stackalloc, Span<T>, and ref-like types are useful when their lifetime rules, size limits, and performance characteristics fit the scenario.

Stack-frame setup and unwinding are usually cheap. Managed allocation is also optimized, but a high allocation rate can increase GC pressure. Garbage collections can affect latency and throughput. Actual performance depends on the workload, memory locality, runtime configuration, and environment.

Every thread has finite stack capacity. Deep recursion or very large frames can cause StackOverflowException. Managed-heap capacity depends on runtime configuration, process limits, allocation patterns, object lifetimes, and the environment.

The garbage collector manages managed memory. It does not provide deterministic cleanup for unmanaged resources such as file handles. When deterministic cleanup is required, use IDisposable, using, or an appropriate SafeHandle pattern.

This is a memory-model explanation rather than a search algorithm. The key insight is to separate two lifetime models. The per-thread call stack tracks active method calls and their execution state. The GC-managed heap stores most managed objects. The central invariant is that stack-frame lifetime follows method invocation, while managed-object lifetime follows reachability from GC roots. Type category alone does not decide physical storage. Value-type data is stored inline wherever its containing location lives, and the JIT may keep eligible locals or reference values in stack slots, registers, or other runtime-selected locations.

There is no single Big-O time or auxiliary-space complexity for this conceptual example. The diagram compares runtime behavior instead. Stack-frame setup and unwinding are typically cheap. Managed-heap allocation is also optimized, but allocation rate and garbage collection can affect latency and throughput. Each thread has finite stack capacity. Managed-heap capacity and GC behavior depend on runtime configuration, process limits, allocation patterns, object lifetimes, and the environment. These costs are implementation-dependent and workload-dependent rather than one fixed algorithmic complexity.

A common mistake is saying all value types live on the stack and all reference variables live on the heap. Storage depends on context and JIT decisions. Another mistake is saying an object is collected immediately when its creating method returns. It is only eligible for collection after it becomes unreachable from GC roots. Candidates may also treat a managed reference as a permanent physical address even though the GC can move objects. Another mistake is saying the heap is always slow while the stack is always fast. Finally, GC-managed memory should not be confused with deterministic cleanup of unmanaged resources.

Start with the two lifetime rules: call-stack frames follow method calls, while managed-heap objects follow GC reachability. Then correct the common shortcut that says value types always live on the stack. That shows that you understand the .NET memory model beyond the beginner-level simplification.

I would use a sliding window with two frequency dictionaries. The right pointer expands the window until every required character has enough copies. Then the left pointer repeatedly shrinks the valid window, and I save a new answer whenever it becomes smaller. If removing a required character makes its count too low, shrinking stops and expansion continues. For the example, the result is "BANC" at indices [9,12]. The diagram reports O(n) time and O(n + m) auxiliary space.

We have a source string s and a target string t. We need the shortest continuous part of s that contains every character required by t, including the correct number of repeated characters. For the diagram example, s is "ADOBECODEBANC" and t is "ABC". The answer is "BANC", from index 9 through index 12. A sliding window works well because we can grow the current range until it is valid, then make it smaller while it stays valid.

1. Should character matching be case-sensitive?
2. What should I return if no valid substring exists?
3. Can t contain repeated characters whose full counts must appear in the window?

The input is two strings, s and t. We must return a substring of s. A substring is a continuous range of characters. It must contain every character required by t with the required frequency. If no valid window exists, the implementation returns an empty string. In the diagram, s = "ADOBECODEBANC" and t = "ABC". The final answer is "BANC" at [9,12].

I use two pointers called left and right. They mark the current window s[left..right]. The need dictionary stores how many copies of each target character are required. For t = "ABC", need is A:1, B:1, C:1. The window dictionary stores character counts inside the current window. required is the number of distinct required characters, which is 3. have tells us how many of those required characters currently meet their needed frequency.

At the start, left = 0 and have = 0. required = 3. The window dictionary is empty. bestLen starts at int.MaxValue, meaning that no valid answer has been found yet. bestLeft starts at -1. The right pointer then moves through s from index 0 to the end.

At right = 0, we add A. Its required count is met, so have becomes 1. D and O are added next, but they are not required characters. At right = 3, B reaches its required count, so have becomes 2. E does not change have. At right = 5, C reaches its required count, so have becomes 3. The window [0,5] is "ADOBEC". It is valid and becomes the first best window with length 6. We then remove A at left = 0. A falls below its required count, so have becomes 2. left becomes 1, and shrinking stops.

The right pointer continues. At right = 6 we add O, at 7 we add D, at 8 we add E, and at 9 we add B. A is still missing, so have remains 2 and the best answer remains "ADOBEC".

At right = 10, we add A. Now have becomes 3 again. We can shrink. Window [1,10] is "DOBECODEBA". Removing D keeps the window valid. Window [2,10] is "OBECODEBA". Removing O keeps it valid. Window [3,10] is "BECODEBA". Removing B keeps it valid because another B remains. Window [4,10] is "ECODEBA". Removing E keeps it valid. Window [5,10] is "CODEBA". Its length is 6, so it does not replace "ADOBEC" because the code updates only for a strictly smaller window. Removing C makes the C count fall below its need. have becomes 2, left becomes 6, and shrinking stops.

At right = 11, we add N. It is not required, so have remains

2. At right = 12, we add C. C reaches its required count again, so have becomes
3. Window [6,12] is "ODEBANC". Removing O keeps it valid. Window [7,12] is "DEBANC". Removing D keeps it valid. Window [8,12] is "EBANC". It is shorter than the best window, so the best becomes "EBANC" at [8,12]. Removing E keeps the window valid. Window [9,12] is "BANC". It is shorter again, so the best becomes "BANC" at [9,12]. Removing B then makes B fall below its required count. have becomes 2, left becomes 10, and shrinking stops. The final answer is "BANC".

The key invariant is that have == required only when every required character currently meets its needed frequency. While that condition is true, the current window is valid. We record it if it is smaller than the best window, then move left to test a smaller candidate. When removing a required character makes its count fall below need, have decreases and shrinking stops. This keeps every recorded best window valid.

The code first builds need from t. It then expands right through s and updates window. When a required character reaches exactly its needed count, have increases. While have == required, the code checks the current window before removing s[left]. If that window is smaller, it saves its length and starting index. It then decreases the outgoing character count. If a required count falls below need, have decreases. Finally, left moves forward. After the scan, the method returns the saved substring or string.Empty when no valid window was found.

The diagram reports O(n) time for the sliding-window processing because both pointers move only forward and each source character is added at most once and removed at most once. C# Dictionary lookup and update are O(1) on average. The diagram reports O(n + m) auxiliary space in the worst case for the frequency dictionaries. Important edge cases are an empty source, an empty target, no valid window, and repeated characters in t whose multiplicities must all be satisfied.

The key insight is to avoid checking every possible substring. The algorithm keeps one sliding window between left and right. The need dictionary stores required target frequencies, and the window dictionary stores frequencies inside the current window. The central invariant is that have == required means every required character currently has enough copies. The right pointer expands until this condition becomes true. Then left repeatedly moves forward while the window remains valid. The best answer is updated before removing the left character. Shrinking stops as soon as a required frequency falls below its needed value.

The diagram reports O(n) time for the sliding-window scan. The reason is that right only moves forward, and left also only moves forward. Each source character is added to the window at most once and removed at most once. Dictionary lookup and update in C# are O(1) on average. Auxiliary space means extra memory used by the algorithm. The need and window frequency dictionaries can use O(n + m) auxiliary space in the worst case, matching the final diagram.

1. Stopping the shrink step after moving left only once even though the window is still valid.
2. Updating the best answer after removing s[left] instead of before removing it.
3. Increasing have every time a required character appears instead of only when its required frequency is reached.
4. Ignoring repeated characters in t and checking only whether each character appears once.
5. Treating the answer as a subsequence instead of a continuous substring.
6. Claiming constant auxiliary space even though the frequency dictionaries can grow with the input.

State the invariant before writing the shrinking loop: have == required means every required character currently has enough copies. Then explain that you record the valid window before removing s[left]. This makes the pointer order and correctness easy to justify.

I would use multi-source BFS with a bitmask. Each state stores the current node and a mask showing which nodes have already been visited. I start BFS from every node at distance 0. From each state, I visit its neighbors and add the neighbor to the mask. BFS processes states in increasing distance, so the first state whose mask contains every node gives the shortest walk. The time complexity is O((n + m) * 2^n), and auxiliary space is O(n * 2^n).

We have a connected graph where every connection can be traveled in either direction. We need the smallest number of moves needed to visit every node at least once. We may begin at any node, and we are allowed to visit the same node or connection again. The important challenge is remembering both where we are now and which nodes we have already covered. The chosen method explores all useful possibilities in order from shorter walks to longer walks, so the first complete walk gives the minimum answer.

1. Is the graph guaranteed to be undirected and connected?
2. Can I start from any node and revisit nodes and edges?
3. Do you want only the minimum length, not the actual walk?

The input is an undirected connected graph with nodes numbered from 0 to n - 1. The output is one integer: the minimum number of edges in a walk that visits every node at least once. We may start at any node. We may also revisit nodes and edges.

I use multi-source BFS because every edge represents one move. Ordinary BFS that remembers only the current node is not enough. Reaching node 2 after visiting nodes {0, 2} is a different situation from reaching node 2 after visiting nodes {1, 2, 3}.

So each BFS state is (node, mask). The node is our current position. The mask is a bitmask that records which nodes have already been visited. The full mask is (1 << n) - 1. For the four-node example, the full mask is 1111 in binary, which is 15.

The walk may start at any node, so I place one starting state for every node into the queue. For node i, the starting mask is 1 << i and the starting distance is 0.

For the example, the initial states are (0, 0001), (1, 0010), (2, 0100), and (3, 1000). Each state is marked as discovered when it is added to the queue.

The example has nodes 0, 1, 2, and 3. Its undirected edges are (0-1), (0-2), (0-3), (1-2), (1-3), and (2-3).

At level 0, the queue contains the four starting states. Each mask has one bit set, so no state has visited all nodes.

At level 1, BFS reaches states with two visited nodes. For example, moving from node 0 to node 1 creates state (1, 0011).

At level 2, BFS can reach states with three visited nodes, such as (2, 0111). The full mask still has not been reached.

At level 3, BFS reaches a state such as (3, 1111). The mask 1111 means every node has been visited. BFS stops and returns 3. One valid shortest walk is 0 -> 1 -> 2 -> 3.

The main invariant is that BFS processes states in nondecreasing distance. A state is identified by both its current node and its visited mask. When a state is discovered for the first time, BFS has reached that state using the minimum possible number of edges. Therefore, the first dequeued state whose mask equals the full mask has the shortest possible walk length that visits every node.

The code uses dist[node, mask]. A value of -1 means that state has not been discovered. The queue stores pairs of current node and visited mask. For every neighbor, the next mask is currentMask | (1 << neighbor). This keeps every previously visited node and adds the neighbor.

If dist[neighbor, nextMask] is -1, the code stores currentDistance + 1 and adds the new state to the queue. When a dequeued state has the full mask, the code immediately returns its distance.

There are n * 2^n possible states. Processing their adjacency lists takes O((n + m) * 2^n) time, where m is the number of undirected edges. The distance table and queue use O(n * 2^n) auxiliary space. For n = 1, the answer is

1. For two connected nodes, the answer is
2. Dense graphs can have many valid shortest walks, but BFS still returns the minimum length.

The key insight is that the current node alone is not enough to describe progress. We must also know which nodes have already been visited. I represent that visited set with a bitmask, so every BFS state is (currentNode, visitedMask). Because the walk may begin anywhere, the queue starts with one state for every node. The central invariant is that BFS processes states in increasing distance. Therefore, the first state whose mask has every node bit set has the minimum possible walk length. Marking each (node, mask) state when it is enqueued prevents repeated work.

Let n be the number of nodes and m be the number of undirected edges. There are n choices for the current node and 2^n possible visited masks, so there are at most n * 2^n states. Across these states, processing adjacency lists takes O((n + m) * 2^n) time. The distance table stores information for up to n * 2^n states, and the BFS queue can also contain many states. Therefore, the auxiliary space complexity is O(n * 2^n).

A common mistake is marking only the graph node as visited. The same node can be reached after covering different sets of nodes, so the visited state must include both node and mask. Another mistake is starting BFS from only one node even though any node may be the start. Candidates may also mark states too late and enqueue the same state repeatedly. Another mistake is replacing the current mask instead of using OR to add the neighbor bit. Finally, the complexity must include adjacency traversal, not only the number of states.

Define the BFS state before writing code. Say clearly that (node, mask) means, "I am at this node, and this mask tells me every node I have already visited." Once that state is clear, the initialization, transition, stopping condition, and correctness proof become much easier to explain.

I would repeatedly scan the string from left to right and process one maximal run of equal adjacent characters at a time. If a run has length one, I copy that character to the next string. If the run has length two or more, I remove the whole run. After each complete pass, I compare the new string with the current one. If they are equal, I return it. Worst-case time is O(n²), with O(n) auxiliary space.

The input is a string L. We need to remove complete groups of identical characters when those characters are next to each other. We remove the whole group when its length is at least two. Removing one group can make other equal characters become neighbors, so we repeat the process. We stop when one complete pass does not change the string. In the diagram example, "abbaca" becomes "aaca", then "ca", and the next pass leaves "ca" unchanged.

1. Should an entire adjacent run of length two or more be removed at once?
2. Should removal continue until a complete pass makes no changes?
3. Should an empty string be returned when every character is removed?

The input is one string, L. The output is the stable reduced string. A stable string has no adjacent run of two or more equal characters. For the diagram example, the input "abbaca" must finally become "ca".

I process the current string from left to right. I identify one maximal run at a time. A maximal run is the complete group of equal adjacent characters. If the run length is one, I copy that character into a new string. If its length is two or more, I copy nothing from that run. This removes the entire run.

I start with current = L. For each pass, I create an empty StringBuilder named next. Index i points to the start of a run. Index j moves forward while current[j] equals current[i]. Then j - i is the run length. If the length is one, I append current[i]. Otherwise, I omit the whole run. I then set i = j and continue with the next run.

Start with current = "abbaca". In pass 1, the first "a" is a singleton, so it is copied. The maximal run "bb" has length two, so the whole run is removed. The following "a", "c", and "a" are singleton runs, so they are copied. The next string is "aaca".

In pass 2, current is "aaca". The maximal run "aa" has length two, so it is removed. The characters "c" and "a" are singleton runs, so they are copied. The next string is "ca".

In pass 3, current is "ca". Both characters are singleton runs, so the next string is also "ca". Because reduced == current, the algorithm stops and returns "ca".

During each pass, every maximal run of length two or more in the current string is removed, while singleton runs are kept in their original order. A removal can make previously separated equal characters become adjacent, so another pass may be needed. When a complete pass produces exactly the same string, no removable adjacent run remains. Therefore the returned string is fully reduced.

The C# code uses a StringBuilder to build the next string during each pass. The inner scan moves through the current string one maximal run at a time. After the pass, the code compares reduced with current. If they are equal, it returns current. Otherwise, it sets current = reduced and repeats. Each pass is linear in the current string length. Repeated passes give O(n²) worst-case time. The temporary result uses O(n) auxiliary space.

The key idea is to remove complete maximal runs rather than cancel equal characters in pairs. During one pass, the algorithm scans from left to right and identifies each maximal run of equal adjacent characters. A run of length one is copied to the next string. A run of length two or more is omitted completely. The invariant is that after a pass, the next string contains exactly the singleton runs from the current string, in their original order. Because removing a run can create new adjacent equal characters, complete passes repeat until the newly built string equals the current string. At that point, no removable run remains.

Let n be the original string length. One pass scans the current string from left to right, so that pass is O(n) in the largest case. Several passes may be needed because removing one run can create another removable run. Therefore the repeated full-pass implementation has O(n²) worst-case time. During a pass, the algorithm builds a new string that can contain up to n characters. That means the auxiliary space is O(n).

One common mistake is removing duplicate characters only in pairs. That is not the same as removing the entire maximal run. For example, the run "aaa" must be removed completely. Another mistake is performing only one pass, even though one removal can create a new adjacent run. Candidates can also forget the reduced == current stopping condition and create an infinite loop. Another error is copying part of a run whose length is at least two. Finally, claiming O(n) total time is incorrect for this repeated full-pass implementation.

Explain the rule before writing code: scan one maximal run at a time, keep it only when its length is one, remove the whole run otherwise, and repeat full passes until the string no longer changes.

I would first sort the intervals by their start value. Then I scan them from left to right and keep a list of merged intervals. I compare each interval with the last interval in the result. If its start is less than or equal to the last end, they overlap or touch, so I extend the end using the larger end value. Otherwise, I append a new interval. The total time is O(n log n), and the result uses O(n) space.

We are given several closed number ranges. Some ranges may overlap, touch at an endpoint, or sit completely inside another range. We need to combine ranges that belong together. The final result must be sorted by start and must contain non-overlapping, maximal ranges. The main idea is to sort the ranges by their starting value first. After sorting, possible overlaps appear next to each other. We can then move from left to right, extend the current merged range when needed, and start a new range only when there is a real gap.

1. Should intervals that only touch at an endpoint be merged?
2. May I sort the input array in place?
3. Can the input array be empty?

The input is an array of closed intervals. Each interval contains a start and an end. The output is a list of merged intervals sorted by start. The returned intervals must not overlap. Each returned interval must also be maximal, which means it cannot be extended by another interval that overlaps or touches it. In this solution, touching endpoints count as overlap because the intervals are treated as closed intervals.

First, sort all intervals by their start value. Then scan the sorted intervals from left to right. Keep a result list containing the merged intervals built so far. For each current interval, compare it only with the last interval in the result. If currentStart <= lastEnd, the intervals overlap or touch. Merge them by setting the last end to max(lastEnd, currentEnd). Otherwise, there is a gap, so append the current interval as a new result interval.

The diagram uses this input: [[5,7], [1,3], [2,6], [8,10], [15,18], [17,20]].

After sorting by start, it becomes [[1,3], [2,6], [5,7], [8,10], [15,18], [17,20]].

Start the result with the first sorted interval: [[1,3]].

The main invariant is that the result is always sorted and non-overlapping. Its last interval represents the complete merged span for the current group of overlapping or touching intervals processed so far.

Start with result [[1,3]].

Step 1: The current interval is [2,6], and the last result interval is [1,3]. Since 2 <= 3, they overlap. Update the end to max(3,6) = 6. The result becomes [[1,6]].

Step 2: The current interval is [5,7], and the last result interval is [1,6]. Since 5 <= 6, they overlap. Update the end to max(6,7) = 7. The result becomes [[1,7]].

Step 3: The current interval is [8,10], and the last result interval is [1,7]. Since 8 > 7, there is a gap. Append [8,10]. The result becomes [[1,7], [8,10]].

Step 4: The current interval is [15,18], and the last result interval is [8,10]. Since 15 > 10, there is a gap. Append [15,18]. The result becomes [[1,7], [8,10], [15,18]].

Step 5: The current interval is [17,20], and the last result interval is [15,18]. Since 17 <= 18, they overlap. Update the end to max(18,20) = 20. The final result is [[1,7], [8,10], [15,20]].

Sorting by start places intervals that can belong to the same merged span next to each other. While scanning, the last result interval contains the complete merged range for the current group. If the next interval starts at or before the last end, extending the end keeps all covered values and also handles nested intervals correctly. If the next start is greater than the last end, there is a real gap. Because all later starts are at least as large, the previous merged interval can safely be finished.

The method first returns an empty array when the input is null or empty. It sorts the input array by interval start. It copies the first sorted interval into a List<int[]>. For every remaining interval, it reads the last merged interval. If the current start is less than or equal to the last end, it updates that end with Math.Max. Otherwise, it appends a copy of the current interval. Finally, it converts the result list to an array.

Sorting takes O(n log n) time. The merge scan takes O(n) time, so total time is O(n log n). The result can contain up to n intervals, so the result storage is O(n). Relevant edge cases are empty input, one interval, all intervals overlapping into one range, touching endpoints, negative values, and intervals completely nested inside another interval.

The key insight is that sorting by start puts intervals that may need to merge next to each other. After sorting, one left-to-right scan is enough. The invariant is that the result is always sorted and non-overlapping, and its last interval is the maximal merged span for the current group. If currentStart <= lastEnd, merge by setting lastEnd = max(lastEnd, currentEnd). If currentStart > lastEnd, the previous span is complete, so append the current interval as a new span.

Let n be the number of intervals. Sorting the intervals by start takes O(n log n) time. After sorting, the merge loop processes each remaining interval once, which takes O(n) time. Sorting is the larger cost, so the total time is O(n log n). The result list may contain up to n intervals, so the space used for the result is O(n). The code sorts the input array in place, so it does not create another full interval array just for sorting.

1. Forgetting to sort the intervals by start before scanning them.
2. Using currentStart < lastEnd when touching closed endpoints are supposed to merge. The diagram uses currentStart <= lastEnd.
3. Replacing the last end directly with the current end instead of using Math.Max. That can break nested intervals.
4. Appending an interval even when it overlaps the last merged interval instead of updating the last interval.
5. Claiming O(n) total time and forgetting that sorting costs O(n log n).

State the merge rule before coding: after sorting by start, compare each interval only with the last merged interval. If currentStart <= lastEnd, extend the end with Math.Max. Otherwise, append a new interval. This makes the walkthrough and code easy to follow.