Coding Round Practice (DSA in C#)

Convert to a char[], swap from both ends towards the middle with two pointers, then build a new string. O(n) time, O(n) space for the array (strings are immutable, so you can't do it in place).

static string Reverse(string s)
{
    var c = s.ToCharArray();
    for (int i = 0, j = c.Length - 1; i < j; i++, j--) (c[i], c[j]) = (c[j], c[i]);
    return new string(c);
}

Mention: for user-visible text with emoji or combining characters, use StringInfo text elements.

Two pointers from both ends, skip non-alphanumerics, compare case-insensitively. O(n) time, O(1) space. Simple version: s == new string(s.Reverse().ToArray()), which is O(n) extra space.

static bool IsPal(string s)
{
    for (int i = 0, j = s.Length - 1; i < j; i++, j--)
        if (char.ToLower(s[i]) != char.ToLower(s[j])) return false;
    return true;
}

long a = 0, b = 1;
for (int i = 0; i < n; i++) { Console.Write($"{a} "); (a, b) = (b, a + b); }

Iterative is O(n) time and O(1) space. Naive recursion F(n-1)+F(n-2) is O(2ⁿ) — mention memoisation if asked for recursion.

Use a HashSet<int>: Add returns false when the item already exists. O(n) time, O(n) space. LINQ alternative: arr.GroupBy(x => x).Where(g => g.Count() > 1).Select(g => g.Key). If O(1) space is required and the array can be modified: sort first (O(n log n)) and compare neighbours.

var seen = new HashSet<int>();
var dups = arr.Where(x => !seen.Add(x)).Distinct().ToList();

var counts = new Dictionary<char, int>();
foreach (var c in s) counts[c] = counts.GetValueOrDefault(c) + 1;
// LINQ: s.GroupBy(c => c).ToDictionary(g => g.Key, g => g.Count());
// .NET 9: s.CountBy(c => c)

O(n) time, O(k) space where k = distinct characters.

In short: Single pass tracking first and second (skip values equal to first if distinct values are needed).

• O(n), O(1).
• Sorting is simpler but O(n log n): arr.Distinct().OrderByDescending(x => x).Skip(1).First().
• Clarify: what if all elements are the same or there's only one?

Brute force: two loops, O(n²). Optimal: one pass with a Dictionary<value, index>. For each number, check whether target - number was seen. O(n) time, O(n) space. If the array is sorted, use two pointers in O(1) space.

var seen = new Dictionary<int, int>();
for (int i = 0; i < nums.Length; i++)
{
    if (seen.TryGetValue(target - nums[i], out var j)) return [j, i];
    seen[nums[i]] = i;
}

In short: Sliding window: keep the last index of each character.

• When a repeat appears inside the window, move start past its previous position, and track the max window length.
• O(n) time, O(k) space.
• Example: "abcabcbb" → 3 ("abc").

In short: At each element, either extend the current subarray or start fresh: cur = max(a[i], cur + a[i]), and best = max(best, cur).

• O(n) time, O(1) space.
• Works with all-negative arrays if you initialise with a[0].
• Example: [-2,1,-3,4,-1,2,1,-5,4] → 6 ([4,-1,2,1]).

In short: Push opening brackets on a Stack<char>.

• For each closing bracket, the stack must be non-empty and the top must match.
• At the end the stack must be empty.
• O(n) time and space.

In short: Iterate with three pointers: prev, current, next.

• Save next, point current.Next to prev, advance both.
• Return prev.
• O(n) time, O(1) space.
• Recursive version: O(n) stack space.

In short: Floyd's cycle detection: slow pointer moves one step, fast moves two.

• If they meet, there is a cycle; if fast reaches null, there isn't.
• O(n) time, O(1) space.
• To find the cycle start, reset one pointer to head and move both one step at a time until they meet.
• Alternative: a HashSet of visited nodes (O(n) space).

In short: On a sorted array, compare with the middle element and discard half each time: O(log n) time, O(1) space iteratively.

• Compute mid = lo + (hi - lo) / 2 to avoid overflow.
• Variants: first/last occurrence, search in a rotated array, lower bound.

In short: Combine a Dictionary<key, LinkedListNode> for O(1) lookup with a doubly LinkedList ordered by recency.

• On get: move the node to the front.
• On put: update and move to the front, or insert at the front.
• If over capacity, remove the last node and its dictionary entry.
• Thread safety: wrap in a lock or use per-key strategies.
• In production use MemoryCache with a size limit.

In short: If the distinct IPs fit in memory: stream the file line by line (File.ReadLines), count in a Dictionary<string,int>, then keep a min-heap of size 10, O(n log 10).

• If not: partition by hash of the IP into N temp files so each file's distinct IPs fit in memory, count each file, and merge the per-file top-10s.
• For a stream with bounded error, use a Count-Min Sketch or the Space-Saving algorithm.
• In practice you'd load the data into SQL/Kusto and `GROUP BY ...
• ORDER BY COUNT(*) DESC`.

In short: Find the repeated work in the inner loop.

• Usual upgrades: (1) a hash map/set to replace an inner search, O(n²) → O(n);
• (2) sort + two pointers, O(n log n);
• (3) a sliding window for contiguous subarray/substring problems;
• (4) prefix sums for range sums;
• (5) a heap for top-K;
• (6) binary search on a sorted structure or on the answer;
• (7) memoisation/DP for overlapping subproblems.
• Say the trade-off (more memory for less time).