Collections Interview Questions & Answers

.NET's collection library has types optimised for different access patterns. Picking the right one affects both performance and API clarity.

// List<T> — dynamic array; O(1) index, O(n) insert/remove in middle
var list = new List<int> { 1, 2, 3 };
list.Add(4);           // O(1) amortised
list.Insert(0, 0);     // O(n) — shifts elements

// Dictionary<K,V> — hash map; O(1) average lookup, insert, remove
var dict = new Dictionary<string, int> { ["a"] = 1, ["b"] = 2 };
dict["c"] = 3;
dict.TryGetValue("a", out int val); // val = 1

// HashSet<T> — unordered unique values; O(1) add, remove, Contains
var set = new HashSet<string> { "alpha", "beta" };
set.Add("alpha"); // no-op, already present

// Queue<T> — FIFO; Enqueue/Dequeue both O(1)
var queue = new Queue<int>();
queue.Enqueue(1); queue.Enqueue(2);
int first = queue.Dequeue(); // 1

// Stack<T> — LIFO; Push/Pop both O(1)
var stack = new Stack<int>();
stack.Push(1); stack.Push(2);
int top = stack.Pop(); // 2

// LinkedList<T> — O(1) insert/remove anywhere, O(n) lookup
var ll = new LinkedList<int>(new[] { 1, 2, 3 });
ll.AddFirst(0); // O(1)

Rule of thumb: Start with List<T> for ordered mutable sequences. Use Dictionary<K,V> for key-based lookup. Use HashSet<T> for membership tests. Only switch to specialised types (LinkedList, SortedDictionary) when profiling shows a concrete bottleneck.

Arrays are fixed-size and slightly faster for indexed access. List<T> wraps an array and automatically resizes when needed, at the cost of a small overhead.

// Array — fixed length set at creation:
int[] arr = new int[5];
arr[0] = 1; arr[4] = 5;
// arr.Add(6); — does not exist; arrays cannot grow

// List<T> — dynamic; backed by an internal array:
var list = new List<int>(capacity: 5); // hint initial capacity
list.Add(1); list.Add(2); // grows automatically when needed

// Span<T> interop — both support span (zero-copy slice):
ReadOnlySpan<int> span1 = arr;           // direct, no allocation
ReadOnlySpan<int> span2 = list.AsSpan(); // also zero allocation (since .NET 5)

// Performance:
// Array:  fastest indexed access, lowest memory overhead
// List<T>: ~same indexed speed; stores Count + Capacity + array ref

// API difference:
arr.Length;       // int, fixed
list.Count;       // int, current element count
list.Capacity;    // backing array size (>= Count)

// Returning from methods:
// Return T[] when size is fixed and caller should not modify it
// Return List<T> when caller needs to add/remove
// Return IReadOnlyList<T> to expose indexed access but prevent mutation

Rule of thumb: Use arrays (T[]) when the size is known at creation time and performance is critical. Use List<T> when the collection needs to grow. Return IReadOnlyList<T> or IReadOnlyCollection<T> from public APIs to prevent callers from modifying your internal state.

Dictionary<TKey, TValue> is a hash table. It calls key.GetHashCode() to find a bucket, then uses key.Equals() to resolve collisions within the bucket. Average time complexity is O(1) for Get, Add, ContainsKey; worst case O(n) with many hash collisions.

// Good key: string, int, Guid, record types (structural equality)
var d1 = new Dictionary<string, int> { ["a"] = 1 };
var d2 = new Dictionary<int, string> { [1] = "one" };

// BAD key: mutable reference type with default GetHashCode (pointer-based)
class MutableKey { public string Name { get; set; } = ""; }
var bad = new Dictionary<MutableKey, int>();
var key = new MutableKey { Name = "a" };
bad[key] = 1;
key.Name = "b"; // mutate after insertion — GetHashCode changes!
bad.ContainsKey(key); // may return false — key is in the wrong bucket!

// Custom equality:
var ci = new Dictionary<string, int>(StringComparer.OrdinalIgnoreCase);
ci["Hello"] = 1;
Console.WriteLine(ci["hello"]); // 1 — case-insensitive

// Capacity hint avoids rehashing:
var d3 = new Dictionary<string, int>(capacity: 1000); // pre-allocate buckets

// Safe access patterns:
if (d1.TryGetValue("a", out int val))   // preferred — single lookup
    Console.WriteLine(val);
// d1["missing"] — throws KeyNotFoundException!
int val2 = d1.GetValueOrDefault("missing", 0); // 0 — safe

Rule of thumb: Keys must have stable, consistent GetHashCode values. Never mutate an object while it is used as a dictionary key. For custom key types, implement GetHashCode and Equals correctly, or prefer record types which do this automatically.

HashSet<T> is ideal when you need fast membership tests or need to ensure uniqueness. Contains is O(1) for HashSet vs O(n) for List.

var list = new List<int> { 1, 2, 3, 4, 5 };
var set  = new HashSet<int> { 1, 2, 3, 4, 5 };

// Membership test performance:
list.Contains(5); // O(n) — scans every element
set.Contains(5);  // O(1) — hash lookup

// Uniqueness: HashSet silently ignores duplicates
set.Add(3); // returns false, set unchanged
list.Add(3); // always adds — now has two 3s

// Set operations (no equivalent in List<T>):
var a = new HashSet<int> { 1, 2, 3, 4 };
var b = new HashSet<int> { 3, 4, 5, 6 };
a.IntersectWith(b);  // a = { 3, 4 }
a.UnionWith(b);      // a = { 3, 4, 5, 6 }
a.ExceptWith(b);     // a = {} (b is a superset here)

// Remove duplicates from a list efficiently:
var withDupes = new List<int> { 1, 1, 2, 2, 3 };
var unique = new HashSet<int>(withDupes).ToList(); // [1, 2, 3]

// Sorted variant:
var sortedSet = new SortedSet<int> { 5, 1, 3, 2 };
Console.WriteLine(string.Join(", ", sortedSet)); // 1, 2, 3, 5 — always ordered

Rule of thumb: Use HashSet<T> for any "is X in the set?" question at scale. Use SortedSet<T> when you additionally need the elements in order. Use List<T> when order and duplicates both matter.

ConcurrentDictionary<K,V> is a thread-safe dictionary. Unlike Dictionary<K,V> (which is not thread-safe), it allows concurrent reads and writes without external locking for most operations.

var cache = new ConcurrentDictionary<string, int>();

// AddOrUpdate — atomic: adds if missing, or updates with a function
cache.AddOrUpdate("hits", 1, (key, old) => old + 1);
cache.AddOrUpdate("hits", 1, (key, old) => old + 1); // now 2

// GetOrAdd — atomic: returns existing value or adds new one
int val = cache.GetOrAdd("pageSize", 25); // adds 25 if not present

// WARNING: GetOrAdd with factory is NOT atomic — factory may run multiple times
// Use GetOrAdd(key, value) when value is cheap/idempotent
// Use Lazy<T> factory pattern for expensive initialisation:
var lazyCache = new ConcurrentDictionary<string, Lazy<ExpensiveObject>>();
var lazy = lazyCache.GetOrAdd("key", _ => new Lazy<ExpensiveObject>(() => new ExpensiveObject()));
ExpensiveObject obj = lazy.Value; // Lazy ensures only one instance created

// TryAdd, TryRemove, TryUpdate — safe, return bool:
cache.TryAdd("x", 42);
cache.TryRemove("x", out int removed);
cache.TryUpdate("hits", 99, currentValue: 2); // only updates if current == 2

// Avoid: foreach + mutation (enumerator takes a snapshot — safe but stale)
foreach (var (k, v) in cache)
    Console.WriteLine($"{k}={v}");

Rule of thumb: Use ConcurrentDictionary for shared caches, counters, or lookup tables accessed from multiple threads. Prefer the atomic methods (AddOrUpdate, GetOrAdd) over read-then-write patterns which reintroduce race conditions.

These three represent different levels of immutability guarantee.

// IReadOnlyCollection<T> — Count + enumeration, no index access
IReadOnlyCollection<int> roc = new List<int> { 1, 2, 3 };
Console.WriteLine(roc.Count); // 3
// roc[0] — no indexer

// IReadOnlyList<T> — adds indexer (IReadOnlyCollection + indexer)
IReadOnlyList<int> rol = new List<int> { 1, 2, 3 };
Console.WriteLine(rol[0]); // 1
// rol.Add(4); — no Add

// BUT: the underlying list is still mutable!
var mutable = new List<int> { 1, 2, 3 };
IReadOnlyList<int> view = mutable;
mutable.Add(4);
Console.WriteLine(view.Count); // 4 — view reflects change!

// ImmutableList<T> — truly immutable; returns a new list on each "mutation"
var immutable = ImmutableList.Create(1, 2, 3);
var updated   = immutable.Add(4); // new list; original unchanged
Console.WriteLine(immutable.Count); // 3
Console.WriteLine(updated.Count);   // 4

// ImmutableList is thread-safe (no locking needed) but slower than List<T>
// Use ImmutableArray<T> for value-type semantics + performance:
ImmutableArray<int> arr = ImmutableArray.Create(1, 2, 3);
ImmutableArray<int> arr2 = arr.Add(4); // arr still [1,2,3]

Rule of thumb: Return IReadOnlyList<T> from public APIs to prevent callers from adding/removing. Use ImmutableList<T> (from System.Collections.Immutable) when you need a truly immutable, shareable collection — e.g., in functional code, state management, or thread-safe contexts.

Span<T> is a stack-only struct that represents a contiguous region of memory — array, stack memory, or unmanaged memory — without copying it. Memory<T> is the heap-compatible version (can be stored in fields or used across await).

int[] array = { 1, 2, 3, 4, 5, 6, 7, 8 };

// Span — zero-copy slice of the array:
Span<int> slice = array.AsSpan(2, 4); // elements 2–5: [3,4,5,6]
slice[0] = 99; // modifies the ORIGINAL array!
Console.WriteLine(array[2]); // 99

// Stack allocation — no heap allocation at all:
Span<byte> stackBuffer = stackalloc byte[256];
stackBuffer.Fill(0);

// String slicing without allocation:
ReadOnlySpan<char> str = "Hello, World!".AsSpan();
ReadOnlySpan<char> greeting = str[..5];             // "Hello" — no allocation
Console.WriteLine(greeting.ToString());              // "Hello"

// Memory<T> — async-compatible (Span cannot cross await boundaries):
async Task ProcessAsync(Memory<byte> buffer)
{
    await stream.ReadAsync(buffer);        // Memory<T> works across await
    ReadOnlySpan<byte> span = buffer.Span; // access as Span inside sync code
    // do something with span
}

// High-performance parsing without allocating substrings:
ReadOnlySpan<char> csv = "Alice,30,London";
int comma1 = csv.IndexOf(',');
ReadOnlySpan<char> name = csv[..comma1]; // "Alice" — no allocation

Rule of thumb: Use Span<T> to slice and process buffers without allocation in synchronous hot paths. Use Memory<T> when you need to store the slice or cross an await. Prefer ReadOnlySpan<char> over string.Substring for zero-allocation parsing.

Queue<T> implements FIFO (first-in, first-out). Stack<T> implements LIFO (last-in, first-out). Both are O(1) for their primary operations.

// Queue<T> — FIFO:
var queue = new Queue<string>();
queue.Enqueue("first");
queue.Enqueue("second");
queue.Enqueue("third");

Console.WriteLine(queue.Peek());    // "first" — peek without removing
Console.WriteLine(queue.Dequeue()); // "first" — removes and returns
Console.WriteLine(queue.Count);     // 2

// Stack<T> — LIFO:
var stack = new Stack<string>();
stack.Push("bottom");
stack.Push("middle");
stack.Push("top");

Console.WriteLine(stack.Peek()); // "top" — peek without removing
Console.WriteLine(stack.Pop());  // "top" — removes and returns
Console.WriteLine(stack.Count);  // 2

// Real-world use cases:
// Queue: task queues, BFS graph traversal, request buffering
var bfsQueue = new Queue<TreeNode>();
bfsQueue.Enqueue(root);
while (bfsQueue.Count > 0)
{
    var node = bfsQueue.Dequeue();
    foreach (var child in node.Children)
        bfsQueue.Enqueue(child);
}

// Stack: undo history, DFS traversal, expression parsing, call-stack simulation
var history = new Stack<string>();
history.Push("open file");
history.Push("type text");
string undone = history.Pop(); // "type text" — last action undone first

Rule of thumb: Use Queue<T> for work-item processing where order must be preserved (FIFO). Use Stack<T> for undo, backtracking, or DFS. Use System.Threading.Channels or BlockingCollection<T> for producer-consumer queues across threads.

Both maintain keys in sorted order. The difference is their internal data structure: SortedDictionary uses a red-black tree; SortedList uses two parallel arrays.

// SortedDictionary<K,V> — red-black tree; O(log n) all operations
var sd = new SortedDictionary<string, int>();
sd["banana"] = 2;
sd["apple"]  = 1;
sd["cherry"] = 3;
foreach (var kv in sd)
    Console.Write(kv.Key + " "); // apple banana cherry — sorted!

// SortedList<K,V> — parallel arrays; O(log n) lookup, O(n) insert/delete
var sl = new SortedList<string, int>();
sl["banana"] = 2;
sl["apple"]  = 1;

// SortedList: supports index-based access to keys and values:
Console.WriteLine(sl.Keys[0]);   // "apple"
Console.WriteLine(sl.Values[0]); // 1

// When to choose which:
// SortedDictionary: frequent inserts/deletes on a large set
// SortedList: mostly reads after initial load; memory-efficient for dense data

// Custom comparer (e.g., case-insensitive keys):
var ci = new SortedDictionary<string, int>(StringComparer.OrdinalIgnoreCase);
ci["Zebra"] = 1;
ci["apple"] = 2;
foreach (var k in ci.Keys) Console.Write(k + " "); // apple Zebra (case-insensitive order)

Rule of thumb: Use SortedDictionary when you have frequent inserts and deletes with a need for sorted iteration. Use SortedList when the data is loaded once and read many times — it uses less memory and supports index-based access to keys/values.

The collection interfaces form a hierarchy, each adding more capabilities.

// IEnumerable<T> — only: iterate with foreach
IEnumerable<int> en = new[] { 1, 2, 3 };
foreach (var n in en) Console.Write(n);

// ICollection<T> — adds: Count, Add, Remove, Contains, Clear
ICollection<int> col = new List<int> { 1, 2, 3 };
Console.WriteLine(col.Count); // 3
col.Add(4);
col.Remove(1);
col.Contains(2); // true

// IList<T> — adds: indexer [], IndexOf, Insert, RemoveAt
IList<int> lst = new List<int> { 1, 2, 3 };
Console.WriteLine(lst[0]); // 1
lst.Insert(0, 0);          // insert at position
lst.RemoveAt(0);           // remove by index

// Read-only counterparts:
// IReadOnlyCollection<T> = IEnumerable<T> + Count
// IReadOnlyList<T>       = IReadOnlyCollection<T> + indexer
// IReadOnlyDictionary<K,V> = read-only key-value lookup

// Accept the most general interface:
void Print(IEnumerable<int> items) // accept anything iterable
{
    foreach (var i in items) Console.Write(i);
}
Print(new[] { 1, 2 });       // array — ok
Print(new List<int> { 1 });  // list — ok
Print(Enumerable.Range(1, 5)); // lazy sequence — ok

Rule of thumb: Accept the most general interface your method needs (IEnumerable<T> for read-only iteration). Return the most specific interface the caller needs (IReadOnlyList<T> for indexed access, IReadOnlyCollection<T> just for counting).

LinkedList<T> is a doubly-linked list. It is O(1) for insert and remove at any known node, but O(n) for index-based access (no indexer). List<T> is O(1) for indexed access but O(n) for insert/remove in the middle (shifts elements).

var linked = new LinkedList<int>(new[] { 1, 2, 3, 4, 5 });

// O(1) insert before/after a known node:
LinkedListNode<int>? node3 = linked.Find(3);
linked.AddBefore(node3!, 99); // [1,2,99,3,4,5]
linked.AddAfter(node3!, 88);  // [1,2,99,3,88,4,5]

// O(1) add at head/tail:
linked.AddFirst(0);  // [0,1,2,99,3,88,4,5]
linked.AddLast(999); // [0,1,2,99,3,88,4,5,999]

// O(1) remove any node if you have the reference:
linked.Remove(node3!); // remove '3' — O(1)

// No indexer — O(n) to reach element by position:
// linked[3] — doesn't exist
var val = linked.Skip(3).First(); // O(n)

// Real use cases:
// - Implement LRU cache (remove from middle + add to end = O(1))
// - Undo history where you insert/remove at specific positions
// - Queue/Deque where you add/remove both ends

LinkedList<T> vs List<T> summary:

Operation	List<T>	LinkedList<T>
Index by position	O(1)	O(n)
Insert at known node	O(n)	O(1)
Remove at known node	O(n)	O(1)
Memory	Contiguous (cache-friendly)	Scattered (pointer overhead)

Rule of thumb: Start with List<T>. Switch to LinkedList<T> only when you profile and confirm that frequent mid-list insertion/removal is the bottleneck and you can efficiently maintain LinkedListNode<T> references.

Several common mistakes make collection code slower than it needs to be.

// 1. Pre-size collections when count is known:
var list = new List<int>(capacity: 10_000); // avoids 13+ resize+copy cycles
var dict = new Dictionary<string, int>(capacity: 500);

// 2. Use TryGetValue instead of ContainsKey + indexer (two lookups vs one):
// double lookup:
if (dict.ContainsKey("key")) { var v = dict["key"]; }
// single lookup:
if (dict.TryGetValue("key", out int val)) { /* use val */ }

// 3. CollectionsMarshal for zero-copy dict value update (.NET 6+):
ref int count = ref CollectionsMarshal.GetValueRefOrAddDefault(dict, "hits", out _);
count++;  // in-place increment — no re-hash, no boxing

// 4. Prefer Span<T> over LINQ for hot-path slicing:
int[] data = Enumerable.Range(0, 100_000).ToArray();
// LINQ allocates enumerator + closure:
var sumLinq = data.Skip(100).Take(900).Sum();
// Span — stack-only, no allocation:
int sumSpan = 0;
foreach (var n in data.AsSpan(100, 900)) sumSpan += n;

// 5. For string-keyed dictionaries, use the right comparer:
// OrdinalIgnoreCase is faster than CurrentCultureIgnoreCase for most use cases
var ci = new Dictionary<string, int>(StringComparer.OrdinalIgnoreCase);

// 6. Avoid List<T> when a fixed array suffices:
static int[] ComputeSquares(int n)
{
    var result = new int[n]; // array — exact size, no overhead
    for (int i = 0; i < n; i++) result[i] = i * i;
    return result;
}

Rule of thumb: Pre-size collections, use TryGetValue over ContainsKey + indexer, prefer Span<T> for hot buffer operations, and profile before optimising — most code is not collection-bound.

PriorityQueue<TElement, TPriority> (.NET 6) is a min-heap where each element has an associated priority. Dequeue always returns the element with the lowest priority value. It replaces sorted-list workarounds for scheduling and graph algorithms.

// Elements are (value, priority) pairs; lowest priority is dequeued first
var pq = new PriorityQueue<string, int>();
pq.Enqueue("low task",    10);
pq.Enqueue("high task",    1);  // priority 1 = highest
pq.Enqueue("medium task",  5);

Console.WriteLine(pq.Dequeue()); // "high task"   (priority 1)
Console.WriteLine(pq.Dequeue()); // "medium task" (priority 5)
Console.WriteLine(pq.Dequeue()); // "low task"    (priority 10)

// Peek without removing:
pq.Enqueue("urgent", 0);
pq.TryPeek(out string? element, out int priority);
Console.WriteLine($"{element} at priority {priority}"); // urgent at priority 0

// Dijkstra shortest-path skeleton:
var distances = new Dictionary<string, int>();
var frontier  = new PriorityQueue<string, int>();
frontier.Enqueue(startNode, 0);

while (frontier.Count > 0)
{
    var (node, dist) = (frontier.Dequeue(), frontier.TryPeek(out _, out int p) ? p : 0);
    // Note: TryDequeue returns element and priority together:
    // frontier.TryDequeue(out string node, out int dist)
    foreach (var (neighbor, weight) in Graph[node])
    {
        int newDist = dist + weight;
        if (!distances.TryGetValue(neighbor, out int old) || newDist < old)
        {
            distances[neighbor] = newDist;
            frontier.Enqueue(neighbor, newDist);
        }
    }
}

Rule of thumb: Use PriorityQueue for Dijkstra, A*, task schedulers, and any scenario where you need the cheapest/most-urgent item repeatedly. Remember it is a min-heap — assign smaller numbers to higher-priority items, or negate the priority if you need max-heap behaviour.

FrozenDictionary<K,V> and FrozenSet<T> (.NET 8) are read-only, highly optimised collections built from existing data. They pay a higher one-time construction cost to produce a data structure tuned for the specific key set, then deliver faster lookups than Dictionary or HashSet for read-heavy workloads.

// Build once at startup — pay construction cost once:
var lookup = new Dictionary<string, int>
{
    ["apple"]  = 1,
    ["banana"] = 2,
    ["cherry"] = 3,
}.ToFrozenDictionary(); // FrozenDictionary<string, int>

// Lookups are typically faster than Dictionary<K,V> for the same data:
bool found = lookup.TryGetValue("banana", out int value); // true, value = 2
Console.WriteLine(lookup["cherry"]); // 3

// FrozenSet<T> for fast membership tests:
FrozenSet<string> allowedRoles =
    new HashSet<string> { "Admin", "Moderator", "Editor" }
    .ToFrozenSet(StringComparer.OrdinalIgnoreCase);

Console.WriteLine(allowedRoles.Contains("admin")); // true

// Typical use cases:
// - Permission sets loaded at startup and queried per request
// - Static lookup tables (HTTP status descriptions, currency codes, config keys)
// - Feature flag dictionaries

// Note: FrozenDictionary is immutable — no Add, Remove, or set-indexer.
// Rebuild the frozen collection if the source data changes.
var updated = sourceDict
    .Concat(new[] { KeyValuePair.Create("durian", 4) })
    .ToFrozenDictionary();

Rule of thumb: Use FrozenDictionary / FrozenSet for lookup tables that are populated once (startup, DI registration, config load) and read millions of times at runtime. They beat Dictionary on lookup speed at the cost of being immutable and slightly slower to construct.

System.Threading.Channels provides async-friendly producer-consumer pipelines. Unlike ConcurrentQueue<T> (which requires polling or blocking), channels let consumers await new items — no spin-loop, no blocking threads.

// Unbounded channel — producer never blocks:
Channel<int> channel = Channel.CreateUnbounded<int>();

ChannelWriter<int>  writer = channel.Writer;
ChannelReader<int>  reader = channel.Reader;

// Producer — runs on one task:
_ = Task.Run(async () =>
{
    for (int i = 0; i < 10; i++)
    {
        await writer.WriteAsync(i);
        await Task.Delay(50);
    }
    writer.Complete(); // signal no more items
});

// Consumer — awaits items as they arrive (no polling):
await foreach (int item in reader.ReadAllAsync())
    Console.WriteLine($"Received: {item}");

// Bounded channel — backpressure: producer is throttled when full
var bounded = Channel.CreateBounded<int>(new BoundedChannelOptions(capacity: 100)
{
    FullMode = BoundedChannelFullMode.Wait,        // await until space is available
    // Other modes: DropOldest, DropNewest, DropWrite
});

// Multiple producers / consumers are safe — channel is thread-safe:
var tasks = Enumerable.Range(0, 4)
    .Select(id => Task.Run(async () =>
    {
        while (await reader.WaitToReadAsync())
            if (reader.TryRead(out int item))
                Console.WriteLine($"Consumer {id}: {item}");
    }))
    .ToArray();
await Task.WhenAll(tasks);

Rule of thumb: Use Channel<T> for async producer-consumer pipelines where consumers should await work rather than poll or block. Use a bounded channel to apply backpressure and prevent producers from overwhelming consumers. Only use ConcurrentQueue<T> when you already have a polling/spinning loop or need the raw enqueue throughput without async overhead.