Choosing Collections and Understanding Their Complexity

Learning outcomes

Choose a collection by the operations you need, explain average and amortized costs, preserve a deliberate output order, and implement a small sliding-window limiter. The examples use synthetic data and run independently as .NET 10 console programs.

The examples were verified with .NET SDK 10.0.401 and runtime 10.0.12 on Windows x64.

Start with the question you need to answer

“Give me item 20,” “Have I seen this product?”, and “Which request arrived first?” are different questions. Write down the required operations, ordering, duplicate policy, and owner of mutable state before choosing a type.

• List<T>: an ordered, indexable sequence with duplicates. Index access is constant time; an unsorted membership scan is linear. Inserting or deleting near the front shifts following elements. Add usually has space available, but an expansion copies existing elements. Across many appends, its cost is amortized O(1), not a promise that every append is O(1).
• Dictionary<TKey,TValue>: one value per distinct key. Use TryGetValue when absence is expected. Setting an existing key replaces its value; Add rejects a duplicate. Lookup is expected O(1) with suitable hashing; collisions can make a lookup O(n). Neither dictionary nor set enumeration is an ordering contract to build a report around.
• HashSet<T>: membership and uniqueness according to its comparer. Add returns false for an existing equal item. Hash-based lookup assumes cheap, well-distributed hashing; the cost of hashing or equality itself also matters.
• Queue<T> / Stack<T>: first-in-first-out / last-in-first-out. A queue fits arrivals; a stack fits undo history. Removal from the relevant end is constant time. Array growth makes some enqueue/push operations linear; many such additions have amortized constant cost.
• Immutable collections: an update produces another collection value while the old one stays usable. That is useful for retaining versions. It does not freeze referenced objects, and update cost depends on the collection and operation. Read-only access alone does not prove that another owner cannot mutate the underlying collection.

Here n means collection size, not a measured duration. Average-case reasoning depends on the inputs and hashing; amortized reasoning spreads occasional expensive operations over a sequence. A small list can still be the right choice: an index costs memory, construction, and maintenance. Choose using the actual workload rather than Big-O alone.

References: List, Dictionary, HashSet, Queue, Stack, ImmutableList.

Equality is part of the design

Equal keys must have equal hash codes, but equal hash codes do not prove equality. Do not change a key in a way that changes its equality or hash while it is stored. Use the same equality policy wherever you compare related identifiers. For machine identifiers, choose deliberately between ordinal case-sensitive and ordinal case-insensitive matching; do not let the current culture choose silently.

Worked example: latest order and unique products

The input is a finite sequence of non-null orders with non-null product arrays. The dictionary holds the latest order encountered for each customer. A strictly newer timestamp replaces the current value. Equal timestamps keep the first encountered order: this is an explicit tie rule relative to input order, not a rule that the smallest order ID wins. If input order is not controlled, use a business tie-breaker instead.

Paste this entire listing into Program.cs in a fresh .NET 10 console project. Each later listing is a separate program, not an addition to this one.

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

public static class Program
{
    public static void Main()
    {
        var t = new DateTimeOffset(2030, 1, 1, 0, 0, 0, TimeSpan.Zero);
        Order[] orders =
        {
            new(101, 2, t, new[] { 8, 8, 3 }),
            new(102, 1, t.AddMinutes(5), new[] { 3, 5 }),
            new(103, 2, t.AddMinutes(2), new[] { 9 }),
            new(104, 1, t.AddMinutes(5), new[] { 5 }),
            new(105, 2, t.AddMinutes(1), Array.Empty<int>())
        };
        var latestByCustomer = Latest(orders);
        foreach (var pair in latestByCustomer.OrderBy(x => x.Key))
            Console.WriteLine($"Customer {pair.Key}: order {pair.Value.Id}");

        var distinctProducts = orders.SelectMany(o => o.ProductIds).ToHashSet();
        Console.WriteLine($"Products: {string.Join(", ", distinctProducts.OrderBy(x => x))}");
        Console.WriteLine($"Contains 8: {distinctProducts.Contains(8)}");
    }

    public static Dictionary<int, Order> Latest(IEnumerable<Order> orders)
    {
        ArgumentNullException.ThrowIfNull(orders);
        var latestByCustomer = new Dictionary<int, Order>();
        foreach (var order in orders)
        {
            if (!latestByCustomer.TryGetValue(order.CustomerId, out var current) ||
                order.CreatedAt > current.CreatedAt)
                latestByCustomer[order.CustomerId] = order;
        }
        return latestByCustomer;
    }
}

public sealed record Order(
    int Id, int CustomerId, DateTimeOffset CreatedAt, int[] ProductIds);

Verified output

Customer 1: order 102
Customer 2: order 103
Products: 3, 5, 8, 9
Contains 8: True

Trace the decision

1. 101 initializes customer 2. 102 initializes customer 1.
2. 103 is newer than 101, so customer 2 changes to 103.
3. 104 ties 102 and is ignored. 105 is older than 103 and is ignored.
4. The product set removes repeated 8, 3, and 5. Sorting the keys and product IDs before printing makes display order explicit.

For n orders, c customers, and p product occurrences, building these indexes takes expected O(n + p) work under ordinary integer hashing, with O(c + u) entries for u unique products. Printing sorted results adds O(c log c + u log u). An empty input yields empty collections. The result contains the original Order references; it is not a deep copy.

Worked example: processing order and snapshot boundaries

using System;
using System.Collections.Generic;
using System.Collections.Immutable;

public static class Program
{
    public static void Main()
    {
        var pending = new Queue<string>();
        pending.Enqueue("first");
        pending.Enqueue("second");
        Console.WriteLine($"Queue: {pending.Dequeue()}");
        var undo = new Stack<string>();
        undo.Push("first");
        undo.Push("second");
        Console.WriteLine($"Stack: {undo.Pop()}");

        var item = new Item("Draft");
        var original = ImmutableList.Create(item);
        var expanded = original.Add(new Item("Ready"));
        item.Name = "Edited";
        Console.WriteLine($"Counts: {original.Count}, {expanded.Count}");
        Console.WriteLine($"Shared item: {original[0].Name}, {expanded[0].Name}");
    }
}

public sealed class Item
{
    public Item(string name) { Name = name; }
    public string Name { get; set; }
}

Verified output

Queue: first
Stack: second
Counts: 1, 2
Shared item: Edited, Edited

The first request leaves the queue first; the most recent operation leaves the stack first. Adding to original returns expanded without changing original's count. Both versions still refer to the same mutable Item, so both observe its new name. Use immutable element types or deliberate copying if the element state must also be isolated. Do not assume “immutable collection” means “deeply immutable object graph.”

Solved practice: a small in-memory rate limiter

Problem: allow at most two accepted requests per client within the last ten milliseconds. Decide the data structures and their costs before reading the solution.

Policy: calls are single-threaded. The caller supplies elapsed milliseconds from one shared monotonic timeline, nonnegative and nondecreasing across all clients and sweeps. The active window is (now − window, now], so a timestamp exactly at the lower boundary has expired. Client IDs are nonblank and ordinal case-sensitive. Denied requests are not recorded. No real clock, network, sleeping, or external account is involved.

Structures: a dictionary locates one queue per client. Each queue holds only accepted timestamps in arrival order. Remove expired timestamps from its front; deny if it still contains the limit; otherwise append now. A sweep is an explicit maintenance operation that prunes every queue and removes empty entries.

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

public static class Program
{
    public static void Main()
    {
        var limiter = new SlidingWindowLimiter(2, 10);
        (string Client, long Time)[] requests =
        {
            ("A", 0), ("A", 1), ("A", 2), ("a", 2),
            ("A", 10), ("A", 10), ("A", 11)
        };
        foreach (var request in requests)
        {
            bool allowed = limiter.Allow(request.Client, request.Time);
            Console.WriteLine($"{request.Client}@{request.Time}: {allowed}");
        }
        limiter.Sweep(21);
        Console.WriteLine($"Tracked clients: {limiter.TrackedClients}");
    }
}

public sealed class SlidingWindowLimiter
{
    private readonly int limit;
    private readonly long window;
    private readonly Dictionary<string, Queue<long>> accepted =
        new(StringComparer.Ordinal);
    private long lastTime;
    public int TrackedClients => accepted.Count;

    public SlidingWindowLimiter(int limit, long windowMilliseconds)
    {
        if (limit <= 0) throw new ArgumentOutOfRangeException(nameof(limit));
        if (windowMilliseconds <= 0)
            throw new ArgumentOutOfRangeException(nameof(windowMilliseconds));
        this.limit = limit;
        window = windowMilliseconds;
    }

    public bool Allow(string client, long now)
    {
        if (string.IsNullOrWhiteSpace(client))
            throw new ArgumentException("Client is required.", nameof(client));
        CheckTime(now);
        if (!accepted.TryGetValue(client, out var times))
        {
            times = new Queue<long>();
            accepted.Add(client, times);
        }
        Expire(times, now);
        if (times.Count >= limit) return false;
        times.Enqueue(now);
        return true;
    }

    public void Sweep(long now)
    {
        CheckTime(now);
        foreach (string client in accepted.Keys.ToArray())
        {
            var times = accepted[client];
            Expire(times, now);
            if (times.Count == 0) accepted.Remove(client);
        }
    }

    private void Expire(Queue<long> times, long now)
    {
        long cutoff = now - window;
        while (times.Count > 0 && times.Peek() <= cutoff)
            times.Dequeue();
    }

    private void CheckTime(long now)
    {
        if (now < 0 || now < lastTime)
            throw new ArgumentOutOfRangeException(nameof(now));
        lastTime = now;
    }
}

Verified output

A@0: True
A@1: True
A@2: False
a@2: True
A@10: True
A@10: False
A@11: True
Tracked clients: 0

Why each result occurs

• At A@2 the queue is [0, 1], so the request is denied and the queue is unchanged.
• a is a different client from A. It has its own allowance.
• At A@10, timestamp 0 expires. The queue becomes [1, 10]. A second request at 10 is denied.
• At A@11, timestamp 1 expires, producing [10, 11]. The rejection at 2 never consumes later capacity.
• Sweep(21) removes timestamps at or before 11. Both client entries disappear. Sweep is not automatic; without it, idle clients can remain tracked.

Cost and limits of this solution

Assuming bounded client-ID length and constant-cost hashing/equality, if k timestamps expire in one call, Allow does expected O(1 + k) work, apart from occasional dictionary/queue growth. Each accepted timestamp is enqueued once and removed at most once, so expiration work amortizes across accepted traffic. A single cleanup can still be expensive. Sweep visits c tracked clients plus e expired timestamps: expected O(c + e), and its key snapshot uses O(c) extra space. At most limit timestamps remain per tracked client, but the number of distinct clients is unbounded without admission rules or cleanup.

This is a data-structure exercise, not a distributed or production limiter. Concurrent calls need coordination around the whole decision, not just a concurrent dictionary. Restarting loses history; multiple processes would each grant their own quota. Clock choice, storage bounds, fairness, and failure behavior need separate production decisions.

Failure modes and interview check

1. “Dictionary always means O(1).” No: hash distribution, equality cost, collisions, and growth matter. Mutable hash-relevant keys can make later lookup fail even though an entry still exists.
2. “I saw sorted output once.” That is insufficient. Preserve sequence order with a sequence type, or explicitly sort at the output boundary.
3. “Use an immutable list for every update.” First decide who owns the data, which versions must survive, and which element objects can change.
4. “A queue makes the limiter constant time.” Trace a call that expires many timestamps. Then explain the difference between that call's cost and amortized cleanup.

Check your understanding

Question: change only the timestamp comparison from > to >=. What changes? Answer: equal timestamps now choose the last encountered order. Customer 1 would print 104 for the fixture. Uniqueness and sorting are unaffected.

Question: should rejected limiter calls be enqueued? Answer: not under this policy. Doing so changes the rule to count attempted requests and can prolong denial. A different policy can be valid, but must be specified and tested separately.

Test checklist: empty orders; both tie permutations; newer then older; independent clients; repeated same-time requests; one tick before and exactly on expiration; invalid client/time/limit; denied requests absent from history; cleanup and reuse. The supplied verification harnesses exercise these boundaries separately from the learner listings.

Sources

• List

• Dictionary

• HashSet

• Queue

• Stack

• ImmutableList