📁 Sangam Dhakal - Portfolio v2.0 - Netscape Navigator 4.0
_
□
×

📚 Interview question

Code review: an OrderService keeps orders in a static List<Order>, finds them with FirstOrDefault, dedups with Any before Add, gets recent orders with OrderByDescending().ToList().Take(10), checks a blocklist with new List<string>{...}.Contains, drains a List with RemoveAt(0), and counts with ContainsKey plus the indexer. What is wrong, and how would you rewrite it?

A collection-focused code review: O(n) lookups and dedup, sorting everything for top-N, per-call allocations, List used as a queue, double dictionary lookups, thread safety and unbounded growth.

Senior CodeReview Intermediate big-o code-review collections data-structures performance thread-safety

🎯 Key points

  • Review correctness and operability first: a static List<Order> shared across requests is not thread-safe and grows without bound (unbounded retention, effectively a managed memory leak)
  • Question the design before tuning it: if the database can answer by-id and 'recent' queries with indexes, the in-process list may not need to exist; if a cache is needed, use IMemoryCache or HybridCache with size limits and expiry
  • Lookup and dedup by scanning are O(n) each, so adding n orders is O(n²); a dictionary keyed by Id with TryAdd makes both O(1)
  • Sorting everything for a top-10 is O(n log n) with O(n) memory and two copies; use an indexed database query or a size-K heap (O(n log K), O(K) memory)
  • Constant data allocated per call (new List<string>{...}.Contains) creates garbage and is case-sensitive; hoist it to a static readonly FrozenSet<string> with StringComparer.OrdinalIgnoreCase
  • List.RemoveAt(0) as a queue is O(n²) to drain; use Queue<T>, or Channel<T> when producers and consumers run concurrently
  • ContainsKey plus the indexer hashes twice; use CollectionsMarshal.GetValueRefOrAddDefault, TryGetValue or LINQ CountBy
  • Prioritise and prove: rank findings by impact, keep the rewrite simple and readable, and back each change with a test or benchmark

⏱ 30-second answer

Main problems:

  1. Static List<Order> shared across requests: not thread-safe and unbounded (memory leak).
  2. Find and Add scan the list: O(n) each, so adding n orders is O(n²). Use a Dictionary<int, Order> (or ConcurrentDictionary).
  3. Recent sorts everything and materialises twice for 10 items. Use a size-10 heap, keep orders indexed by time, or query the database with an index.
  4. IsBlocked allocates a list per call and is case-sensitive. Use a static readonly FrozenSet<string> with StringComparer.OrdinalIgnoreCase.
  5. ProcessPending uses RemoveAt(0) as a queue: O(n²). Use Queue<T> (or Channel<T> if fed concurrently).
  6. CountByStatus does two lookups per item. Use CollectionsMarshal.GetValueRefOrAddDefault, TryGetValue, or CountBy (.NET 9).

Also question whether an in-process cache belongs here at all (IMemoryCache/HybridCache with size limits and expiry).

🗣 Full answer (senior)

The code under review

public class OrderService
{
    private static List<Order> _cache = new();
    private List<Order> _pending = new();

    public Order? Find(int id) => _cache.FirstOrDefault(o => o.Id == id);

    public void Add(Order o)
    {
        if (!_cache.Any(x => x.Id == o.Id)) _cache.Add(o);
    }

    public List<Order> Recent() =>
        _cache.OrderByDescending(o => o.CreatedAt).ToList().Take(10).ToList();

    public bool IsBlocked(string country) =>
        new List<string> { "KP", "IR", "SY" }.Contains(country);

    public void ProcessPending()
    {
        while (_pending.Count > 0)
        {
            var next = _pending[0];
            _pending.RemoveAt(0);
            Handle(next);
        }
    }

    public Dictionary<string, int> CountByStatus()
    {
        var counts = new Dictionary<string, int>();
        foreach (var o in _cache)
        {
            if (counts.ContainsKey(o.Status)) counts[o.Status]++;
            else counts[o.Status] = 1;
        }
        return counts;
    }
}

Findings

# Code Problem Impact Fix
1 static List<Order> _cache Shared mutable state, not thread-safe, never evicted Corruption under concurrent requests; memory grows forever IMemoryCache/HybridCache with size limit and expiry, or ConcurrentDictionary + eviction
2 FirstOrDefault(o => o.Id == id) Linear scan O(n) per lookup Dictionary keyed by Id
3 Any(...) before Add Linear scan for dedup O(n²) to add n items TryAdd on a dictionary
4 OrderByDescending().ToList().Take(10).ToList() Sorts all, copies twice O(n log n) + O(n) memory per call Top-K heap, a time-ordered index, or the database
5 new List<string>{...}.Contains Allocates per call; case-sensitive; O(n) Garbage on hot path; "kp" not blocked static readonly FrozenSet<string> with ignore-case comparer
6 _pending[0] + RemoveAt(0) List used as a queue O(n²) to drain Queue<T> / Channel<T>
7 ContainsKey + indexer Double hashing ~2× lookups GetValueRefOrAddDefault or CountBy

Production example

A similar "cache" in an order API grew to 2 million orders over a week. Find took 15 ms on average, p99 rose steadily, and memory reached 6 GB before the pod was OOMKilled each Sunday. Moving to HybridCache with a size limit for by-id lookups and querying the database for "recent orders" (indexed on CreatedAt) cut p99 from 400 ms to 12 ms and kept memory flat at 600 MB.

🔍 What the interviewer is checking

Checks the ability to spot multiple data-structure problems in realistic code and prioritise them.

Green flags

  • Finds the thread-safety and unbounded-growth issues first.
  • Maps each operation to the right structure with complexity.
  • Spots per-call allocation, double lookups and List-as-queue.
  • Questions whether the cache should exist and proposes HybridCache/IMemoryCache or a DB query.

Red flags

  • Only suggests micro-optimisations.
  • Misses the static shared list.

📚 Learn in depth

1. Match the structure to the operation

Operation Wrong structure Right structure Cost change
Lookup by key List scan Dictionary / ConcurrentDictionary O(n) → O(1)
Dedup on insert List.Any HashSet / Dictionary.TryAdd O(n) → O(1)
Top K by a field Full sort Heap of size K / sorted index O(n log n) → O(n log K) or O(K)
Static membership New list per call Static FrozenSet O(n) + alloc → O(1), no alloc
FIFO processing List.RemoveAt(0) Queue / Channel O(n) → O(1) per item
Counting ContainsKey + indexer GetValueRefOrAddDefault / CountBy 2 lookups → 1

2. Thread safety of the original

ASP.NET Core services are often singletons or use static fields. With concurrent requests, List<T>.Add can lose items or throw, and enumeration during modification throws InvalidOperationException ("Collection was modified"). _pending is an instance field, so the risk depends on the service lifetime.

3. Is a cache the right tool?

  • If the database already has the data with good indexes, a cache may be unnecessary.
  • If a cache is needed: bounded size, expiry, stampede protection (HybridCache provides this), and a clear invalidation story.
  • "Recent orders" is a query, not a cache lookup: the database can answer ORDER BY CreatedAt DESC with an index in milliseconds.

4. LINQ pitfalls in the original

  • OrderByDescending(...).ToList() materialises the whole sorted list before Take. Removing the first ToList() helps, but it is still a sort over all items; a heap is O(n log K) with O(K) memory.
  • Redundant ToList() calls copy data unnecessarily.

5. How I would run this review

  1. Ask about lifetime (singleton? per request?) and data size.
  2. Rank findings by impact: correctness (thread safety, unbounded growth) before performance.
  3. Suggest the smallest change that fixes each, plus a test or benchmark proving it.

6. Try it yourself

  1. Benchmark the original Find, Add and Recent with 100,000 orders against the rewritten version.
  2. Run 16 parallel tasks calling Add on the original and observe exceptions or lost items.
  3. Add a test that IsBlocked("kp") returns true after the fix.

💻 Code

public sealed class OrderService(HybridCache cache, IOrderRepository repo)
{
    // static, allocation-free, case-insensitive membership
    private static readonly FrozenSet<string> BlockedCountries =
        new[] { "KP", "IR", "SY" }.ToFrozenSet(StringComparer.OrdinalIgnoreCase);

    // real queue; use Channel<Order> if producers and consumers run concurrently
    private readonly Queue<Order> _pending = new();

    // bounded, thread-safe cache keyed by id (HybridCache handles stampedes and expiry)
    public ValueTask<Order?> FindAsync(int id, CancellationToken ct) =>
        cache.GetOrCreateAsync($"order:{id}", async token => await repo.GetAsync(id, token),
            cancellationToken: ct);

    // let the database use its CreatedAt index
    public Task<List<Order>> RecentAsync(CancellationToken ct) => repo.GetRecentAsync(take: 10, ct);

    public bool IsBlocked(string country) => BlockedCountries.Contains(country);

    public void ProcessPending()
    {
        while (_pending.TryDequeue(out var next))   // O(1) per item
            Handle(next);
    }

    // one lookup per item
    public static Dictionary<string, int> CountByStatus(IEnumerable<Order> orders)
    {
        var counts = new Dictionary<string, int>(StringComparer.Ordinal);
        foreach (var o in orders)
            CollectionsMarshal.GetValueRefOrAddDefault(counts, o.Status, out _)++;
        return counts;
        // .NET 9+: orders.CountBy(o => o.Status).ToDictionary()
    }

    private void Handle(Order order) { /* ... */ }
}
// If you must keep top-N in memory: size-K heap instead of sorting everything
static List<Order> TopRecent(IEnumerable<Order> orders, int k)
{
    var heap = new PriorityQueue<Order, DateTimeOffset>(k);
    foreach (var o in orders)
    {
        if (heap.Count < k) heap.Enqueue(o, o.CreatedAt);
        else if (heap.TryPeek(out _, out var oldest) && o.CreatedAt > oldest) heap.EnqueueDequeue(o, o.CreatedAt);
    }
    return heap.UnorderedItems.OrderByDescending(x => x.Priority).Select(x => x.Element).ToList();
}

⚠ Common mistakes

  • Mistake: Focusing only on big-O and missing correctness. Why it is wrong: A static List<T> shared across requests is a thread-safety bug (lost items, "Collection was modified" exceptions) and grows until the pod is OOMKilled, which matters far more than lookup speed. Instead: Review lifetime, concurrency and bounds first, then performance.

  • Mistake: Replacing List with ConcurrentDictionary and stopping there. Why it is wrong: It fixes thread safety but the data is still unbounded, never expires and can serve stale orders forever. Instead: Use IMemoryCache or HybridCache with size limits and expiry, or remove the cache if indexed database queries are fast enough.

  • Mistake: Assuming every hot lookup needs an in-memory cache. Why it is wrong: Caches add invalidation, consistency and memory concerns; an indexed query that returns in a few milliseconds may already meet the latency goal. Instead: Measure the database path first and add caching only for a proven need, with a clear invalidation story.

  • Mistake: Fixing Recent with OrderByDescending().Take(10) on an ever-growing in-memory list. Why it is wrong: It is still a sort or partial sort over all data on every call. Instead: Query the database with an index on CreatedAt, or maintain a top-K structure.

  • Mistake: Leaving per-call allocations of constant data. Why it is wrong: new List<string>{...} on every call adds garbage on hot paths, and default string comparison lets "kp" through. Instead: Hoist constants to static readonly frozen collections with the right comparer.

  • Mistake: Giving a long list of nitpicks without priorities. Why it is wrong: Authors fix the easy cosmetic items and miss the outage-causing ones. Instead: Rank findings by impact and propose concrete fixes with tests or benchmarks.

🏛 Senior insight: trade-offs

Good collection choices come from asking what operations happen, how often, on how much data, and from how many threads. This code fails all four: by-id lookups on a list, dedup by scanning, full sorts for a top-10, a list used as a queue, and shared unbounded mutable state.

Priority Finding Why first
1 Static shared list: thread safety and unbounded growth Causes exceptions, data loss and OOM restarts
2 Should this cache exist? May remove most of the code
3 O(n) lookups, O(n²) dedup and drain, full sort for top-10 Latency grows with data size
4 Per-call allocation, case sensitivity Correctness bug ("kp") plus GC pressure
5 Double dictionary lookups Small win, easy fix

I balance performance with maintainability: the rewrite uses standard building blocks (HybridCache, an indexed query, FrozenSet, Queue<T>) rather than clever custom structures, so the next developer understands it immediately. The result is shorter, safer and faster, and each change is backed by a benchmark or test, which is the best kind of review outcome.

🔗 Follow-ups the interviewer may ask

  1. When: Candidate suggests a dictionary keyed by Id Why: Checks hash table depth
    How to answer

    A hash table turns a key into an integer hash, maps it to a bucket (hash % bucketCount), and stores the entry there. Lookups compute the same hash, go straight to the bucket, and compare keys with Equals. Average cost is O(1); worst case (everything in one bucket) is O(n).

    .NET's Dictionary<TKey,TValue> keeps an int[] buckets and an Entry[] entries array; colliding entries form a chain via a next index inside the entries array. When full, it resizes to roughly double (a prime size) and rehashes.

    Contract: if a.Equals(b) then a.GetHashCode() == b.GetHashCode(), and a key's hash must not change while it is in the dictionary. Good hashes spread keys evenly.

  2. When: Candidate suggests a heap for recent orders Why: Checks heap and top-K understanding
    How to answer

    A heap is a complete tree stored in an array that keeps the heap property: in a min-heap every parent ≤ its children, so the smallest item is always at the root.

    • Peek min: O(1). Insert (sift up) and remove min (sift down): O(log n). Build from n items: O(n).
    • Not sorted overall, and not searchable quickly (finding an arbitrary item is O(n)).

    .NET's PriorityQueue<TElement,TPriority> (.NET 6+) is an array-backed min-heap (4-ary internally). Enqueue, Dequeue, TryPeek, EnqueueDequeue; not stable for equal priorities; no decrease-key (Remove was added in .NET 9). For a max-heap, pass a reversed comparer.

    Top K from a stream: keep a min-heap of size K; for each item, if it beats the heap's minimum, replace it. That is O(n log K) time and O(K) memory.

    (Not to be confused with the managed heap, which is memory.)

  3. When: Candidate replaces RemoveAt(0) with a queue Why: Checks queues and Channels
    How to answer
    • A stack is LIFO (last in, first out): Push, Pop, Peek, all O(1). Used for the call stack, undo, expression parsing, DFS and backtracking.
    • A queue is FIFO (first in, first out): Enqueue, Dequeue, Peek, all O(1). Used for work queues, BFS, buffering and rate limiting.

    In .NET, Stack<T> is an array that grows at the end. Queue<T> is a circular buffer: head and tail indexes wrap around the array, so dequeuing does not shift elements.

    Neither is thread-safe. For concurrency use ConcurrentQueue<T>/ConcurrentStack<T>, or better for producer/consumer pipelines, a bounded Channel<T> which adds async waiting and back-pressure.

🛠 Real-world problems: how you handle them

In-process order list grows to 2 million items and OOMs weekly
Situation
[Order API] on .NET [10] in [AKS] with a static `List<Order>` used as a cache for lookups and "recent orders".
Signals
p99 rising during the week from [40 ms] to [400 ms]; memory growing to [6 GB]; pods OOMKilled each [Sunday]; occasional "Collection was modified" exceptions.
Investigation
Dump showed [2 million] orders in the list; profiler showed `FirstOrDefault` and `OrderByDescending` dominating CPU.
Resolution
Replaced with `HybridCache` for by-id lookups with size limit and expiry, moved "recent" to an indexed database query, and fixed the queue and counting code.
Prevention
Analyser rule against static mutable collections in services, memory growth alert, load test running for [24 hours].

How to tell it (STAR)

**S:** Our [order API] slowed down every day and was OOMKilled each [Sunday]. **T:** I was asked to stabilise it. **A:** A dump showed a static list holding [2 million] orders that every request scanned or sorted, with no thread safety. I replaced it with a bounded HybridCache keyed by order ID and moved "recent orders" to an indexed query. **R:** p99 dropped from [400 ms] to [12 ms], memory stayed flat at [600 MB], and the weekly restarts stopped.

↩ Usually asked after

More in Data Structures

Last updated 23 Oct 2026.

🌐 Sangam's Webring

⏪ Previous 🏠 Main Next ⏩
💬 Chat with me