A: List<T>, pre-sized whenever the count is known, because contiguous storage gives the best iteration performance and the simplest semantics. I deviate when there is a specific reason I can state in a sentence: HashSet<T> or Dictionary<K,V> when membership or key lookup happens inside a loop, since that turns O(n·m) into O(n + m); a sorted structure when I need ordered iteration, ranges, or min and max; Queue or Stack when the processing order is the requirement and expressing it in the type documents the intent; and a concurrent collection when more than one thread touches it. The burden of proof is on deviating, not on the default.

A: Convert the inner collection to a HashSet<T> before the loop. List.Contains is a linear scan, so calling it once per element of an outer list is O(n·m); hashing the inner list once is O(m) and turns each membership test into O(1) average, making the whole thing O(n + m). This is the most common data-structure defect in business code, and it is dangerous precisely because it does not look wrong and performs fine on small test data — the quadratic term only bites at production scale, so it typically ships and then surfaces as a mysterious timeout months later.

A: When writes are rare relative to reads, because its per-operation overhead and striped locking cost more than a plain Dictionary, and a read-mostly workload can do better with an immutable dictionary replaced by an atomic reference swap or a plain dictionary behind a reader-writer lock. It is also wrong when you need atomicity across multiple keys, since each operation is individually atomic but a sequence of them is not, so "check one key then update another" still races. And its GetOrAdd factory can execute more than once under contention while only one result is kept, so it is wrong wherever that factory has side effects such as opening a connection or issuing a request.

A: By the read-to-write ratio and the memory budget. SortedDictionary is a red-black tree with O(log n) insert, delete, and lookup, so it suits collections that change frequently, at the cost of a node allocation per entry and pointer indirection that hurts locality. SortedList is a pair of sorted arrays: O(log n) binary-search lookup and O(1) access by index, but O(n) insert and delete because elements shift. So a lookup-heavy collection built once and then queried repeatedly favours SortedList, which also uses considerably less memory and iterates faster, while a write-heavy one favours SortedDictionary.

A: That it re-executes every time it is enumerated, which is invisible at the call site. Assigning orders.Where(...) to a variable runs nothing; calling Count(), then First(), then iterating it executes the whole pipeline three times — and if the source is IQueryable over a database, that is three round trips rather than one. The reverse mistake also exists: calling ToList() on a large source you only consume once materialises the whole thing in memory for no benefit. The rule is to materialise once when you will consume more than once, and stay lazy when you will consume once or may stop early.

A: When it is large, shared across processes or instances, must survive a restart, or needs to be queried by more than one key. Loading a large table into memory to filter it in application code is choosing the wrong layer: the database already has B-tree indexes, statistics, and a query planner, so it will do the filtering faster while using none of your process's heap and none of your GC budget. In-memory collections are right for per-request working sets, caches with an explicit eviction policy, and data small and stable enough that the whole thing fits comfortably — the failure mode is a cache that quietly grows until it becomes the process's memory problem.

A: A dictionary from key to node for O(1) lookup, plus a doubly-linked list holding the nodes in recency order, with the most recently used at the head. A get looks up the node in the dictionary and splices it to the front; a put inserts at the front and, if over capacity, evicts the tail and removes its key from the dictionary. Every operation is O(1) because the dictionary supplies the node reference directly, so the linked list never has to be searched — this is the canonical case where LinkedList<T> genuinely earns its place, since splicing a known node costs nothing and no bulk copy ever occurs. In production I would reach for MemoryCache or a maintained library first, since eviction, expiry, and thread-safety are where hand-rolled caches go wrong.

A: Naming the dominant operation and the access pattern rather than the complexity class. "Lookups by ID happen on every request and writes happen once at startup, so I used a Dictionary built once and never mutated — no ordering is required, so I do not pay for a tree" is a good answer. "Dictionary is O(1)" is not, because it recites a property without connecting it to this workload. The strongest version also names what you gave up and under what conditions you would revisit it — no ordering, no worst-case guarantee, and a rebuild if the keys ever become attacker-controlled.