Free lesson · DSA Mastery - Interview Prep, End to End

C# for DSA

Easy7 min readdsaprogramming-fundamentals

C# for DSA

C# is the choice for engineers in the Microsoft ecosystem and a perfectly reasonable language for technical interviews. It has a rich standard library, modern syntax, and a type system similar to Java. If you write C# daily and your target company uses .NET extensively, C# is a natural choice.

This topic covers the C# APIs that matter for DSA problems. The focus is on the collections in System.Collections.Generic and the patterns that show up in interview code.

Why C# for Interviews

C# has practical advantages similar to Java:

• Strong type system. Type errors fail at compile time. Catches a lot of bugs.
• Excellent collections library. List<T>, Dictionary<K, V>, HashSet<T>, and friends are all production-quality.
• Familiar to Microsoft-stack interviewers. Microsoft, LinkedIn (post-acquisition), and many enterprise companies use C#.
• Cleaner syntax than Java. Properties, LINQ, lambdas, and pattern matching make code more concise.

The trade-offs are minor for interview purposes. C# is slightly less common than Java or Python at FAANG companies outside Microsoft, but any interviewer should be able to read it.

The Core Data Structures

C#'s System.Collections.Generic namespace provides the standard collections.

The big one to know: C# has a built-in PriorityQueue since .NET 6 (2021). If your interview environment is on an older runtime, you may need to implement your own. Always check the available version before relying on it.

Arrays and Lists

C# arrays are fixed-size and primitive-friendly.

int[] arr = new int[10];
int[] arr2 = { 5, 2, 8, 1, 9, 3 };
arr2.Length;      // 6
arr2[0];          // 5

For dynamic arrays, use List<T>:

using System.Collections.Generic;

List<int> list = new List<int>();
list.Add(1);
list.Add(2);
list.Add(3);
list[0];                    // 1
list.Count;                 // size
list.Remove(2);             // remove first occurrence
list.RemoveAt(0);           // remove by index
list.Contains(3);           // O(n)
list.Reverse();             // in-place

For 2D arrays:

int[,] grid = new int[3, 4];   // rectangular, fixed
grid[1, 2] = 5;

int[][] jagged = new int[3][];  // jagged, each row variable
for (int i = 0; i < 3; i++) {
    jagged[i] = new int[4];
}

Rectangular arrays (int[,]) are slightly faster but less flexible. Jagged arrays (int[][]) are more like Java's int[][] - each row is independent.

Dictionary

Dictionary<K, V> is C#'s hash map.

Dictionary<string, int> counts = new Dictionary<string, int>();
counts["a"] = 1;
counts["a"] = counts.GetValueOrDefault("a", 0) + 1;
counts["b"] = 5;

if (counts.ContainsKey("a")) {
    int value = counts["a"];
}

// TryGetValue is also idiomatic:
if (counts.TryGetValue("a", out int v)) {
    // v is set
}

GetValueOrDefault is the C# equivalent of Java's getOrDefault. The TryGetValue pattern is more idiomatic for cases where you want to do something only if the key exists.

To iterate:

foreach (var kvp in counts) {
    string key = kvp.Key;
    int value = kvp.Value;
}

// Or with deconstruction:
foreach (var (key, value) in counts) {
    // C# 7.0+
}

HashSet and SortedSet

HashSet<T> is hash-based, unordered, O(1) average.

HashSet<int> seen = new HashSet<int>();
seen.Add(5);
if (seen.Contains(5)) { }
seen.Remove(5);

SortedSet<T> is tree-based, ordered, O(log n).

SortedSet<int> sorted = new SortedSet<int>();
sorted.Add(3);
sorted.Add(1);
sorted.Add(2);
// Iterates in order: 1, 2, 3

int min = sorted.Min;
int max = sorted.Max;

Stack and Queue

Stack<T> is LIFO.

Stack<int> stack = new Stack<int>();
stack.Push(1);
stack.Push(2);
stack.Push(3);
int top = stack.Pop();      // 3 (removes and returns)
int peek = stack.Peek();    // 2 (does not remove)
stack.Count;

Queue<T> is FIFO.

Queue<int> queue = new Queue<int>();
queue.Enqueue(1);
queue.Enqueue(2);
queue.Enqueue(3);
int front = queue.Dequeue();    // 1
int peek = queue.Peek();        // 2
queue.Count;

Unlike C++, Pop and Dequeue return the element. This matches Java's conventions.

For a deque, C# does not have a dedicated type. LinkedList<T> works but is slower than a true array-backed deque. For interviews requiring deque operations (sliding window maximum, monotonic queue), use LinkedList<T>:

LinkedList<int> deque = new LinkedList<int>();
deque.AddFirst(1);
deque.AddLast(2);
deque.RemoveFirst();
deque.RemoveLast();
deque.First.Value;
deque.Last.Value;

PriorityQueue

.NET 6 (2021) introduced a built-in PriorityQueue<TElement, TPriority>. It is a min-heap by default.

PriorityQueue<string, int> pq = new PriorityQueue<string, int>();
pq.Enqueue("low priority", 5);
pq.Enqueue("urgent", 1);
pq.Enqueue("medium", 3);

string next = pq.Dequeue();    // "urgent" (lowest priority value)

For a max-heap, you pass an inverted comparer:

PriorityQueue<int, int> maxHeap = new PriorityQueue<int, int>(
    Comparer<int>.Create((a, b) => b - a)
);

The separate-element-and-priority design is unusual. Other languages typically use the element itself as the priority. To use the same value for both:

PriorityQueue<int, int> heap = new PriorityQueue<int, int>();
heap.Enqueue(5, 5);
heap.Enqueue(2, 2);
heap.Enqueue(8, 8);
int min = heap.Dequeue();    // 2

If you are on an older .NET version that lacks PriorityQueue, you have to implement your own heap. For interviews, ask the interviewer about the runtime first.

Strings

C# strings are immutable, like Java.

string s = "hello";
s.Length;                   // 5
s[0];                       // 'h'
s.ToUpper();                // "HELLO"
s.Substring(1, 3);          // "ell" (start, length)
s.IndexOf("ll");            // 2
s.Replace("l", "L");        // "heLLo"
s.Split(',');               // returns string[]
string.Join(",", parts);    // join
s.StartsWith("he");
s.EndsWith("lo");
s.Trim();

For mutable string building:

using System.Text;

StringBuilder sb = new StringBuilder();
sb.Append("hello");
sb.Append(" ");
sb.Append("world");
string result = sb.ToString();

As in Java, repeated string concatenation in a loop is O(n²). Use StringBuilder for any meaningful number of appends.

Sorting

Array.Sort and List<T>.Sort are in-place. They use Introsort.

int[] arr = { 3, 1, 4, 1, 5 };
Array.Sort(arr);                                  // ascending
Array.Sort(arr, (a, b) => b - a);                 // descending lambda

List<int> list = new List<int> { 3, 1, 4 };
list.Sort();
list.Sort((a, b) => b - a);

For 2D arrays (intervals):

int[][] intervals = { new[] {1, 3}, new[] {2, 6}, new[] {8, 10} };
Array.Sort(intervals, (a, b) => a[0] - b[0]);

C# also has LINQ for more declarative sorting:

using System.Linq;

var sorted = list.OrderBy(x => x).ToList();
var sortedDesc = list.OrderByDescending(x => x).ToList();
var sortedByMultiple = list.OrderBy(x => x.Length).ThenBy(x => x).ToList();

LINQ creates new collections rather than mutating in place. For interview code, in-place sorting is usually preferable.

Common Idioms

A few C# patterns that show up frequently.

Counting with Dictionary

Dictionary<char, int> counts = new Dictionary<char, int>();
foreach (char c in s) {
    if (counts.ContainsKey(c)) {
        counts[c]++;
    } else {
        counts[c] = 1;
    }
}

A cleaner version with TryGetValue:

foreach (char c in s) {
    counts.TryGetValue(c, out int count);
    counts[c] = count + 1;
}

TryGetValue returns 0 (the default for int) when the key is missing, so this works without explicit checks.

Tuple Returns

public (int min, int max) MinMax(int[] arr) {
    int min = arr.Min();
    int max = arr.Max();
    return (min, max);
}

var (min, max) = MinMax(arr);

Named tuples make multi-return functions clean.

Pattern Matching

switch (node) {
    case null:
        return 0;
    case TreeNode { Left: null, Right: null }:
        return node.Value;
    default:
        return Solve(node.Left) + Solve(node.Right);
}

Pattern matching (C# 7.0+) makes some recursive solutions more elegant. It is a stylistic choice, not a necessity.

Tree Node and List Node Classes

Standard interview classes:

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class ListNode {
    public int val;
    public ListNode next;
    public ListNode(int val = 0, ListNode next = null) {
        this.val = val;
        this.next = next;
    }
}

Performance Notes

A few C# specific points worth knowing:

Reference types vs value types. int, bool, double, structs are value types - copied by value. Classes (including List<T>, Dictionary<K, V>, custom classes) are reference types - passed by reference. This matters for performance and for understanding when a function modifies its arguments.

List<T>.Contains is O(n). For fast membership testing, use HashSet<T>.

LINQ has overhead. It is expressive but slower than raw loops. For tight loops in interview code, prefer the imperative style.

Dictionary<K, V> does not preserve insertion order. If order matters, use OrderedDictionary from System.Collections.Specialized (which is non-generic and clunkier), or maintain a separate list of keys.

Common Mistakes to Avoid

Modifying a collection while iterating. Adding or removing items from a collection during a foreach loop throws InvalidOperationException. Iterate over a copy (ToList()) or use a regular for loop with index management.

Null reference exceptions. Classes can be null. Always check before accessing members on a reference type, especially when traversing trees or linked lists. C# 8.0's nullable reference types help with this.

Integer overflow. int is 32-bit. Like in Java, you may need long for computations involving large products.

Implicit copying of value types. Passing a struct to a function copies it. If you modify the parameter, the original is unchanged. This sometimes surprises developers coming from reference-type-heavy languages.

Boilerplate to Remember

A minimal C# interview template:

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution {
    public int Solve(int[] nums) {
        Dictionary<int, int> counts = new Dictionary<int, int>();
        foreach (int x in nums) {
            counts.TryGetValue(x, out int count);
            counts[x] = count + 1;
        }
        return 0;
    }
}

That covers most of what you need. The rest of this course uses Java for code examples - the API differences are minimal, and most patterns transfer directly to C# by changing capitalization and a few keywords (HashMap becomes Dictionary, getOrDefault becomes GetValueOrDefault, and so on).

Back to DSA Mastery - Interview Prep, End to End