Data Structures

Arrays, linked lists, stacks, queues, hash tables, trees, binary trees, heaps, graphs, tries, sets and maps, and the .NET collections that implement them.

1. What is an array, and how does List<T> build on it in .NET? Explain memory layout, indexing cost, how List<T> grows, and when you would use an array, List<T> or Span<T>.

   Arrays as contiguous memory, O(1) indexing, List<T> as a growable array with capacity doubling, amortised O(1) Add, and when to use arrays, lists, spans and pooled buffers.

   Junior Theory Data Structures · 🔗 3 follow-ups
2. What is a linked list? Compare LinkedList<T> with List<T> in .NET, including big-O and real-world performance, and give a case where a linked list is the right choice.

   Singly and doubly linked lists, O(1) node insert/remove vs O(n) search, poor cache locality, LinkedList<T> in .NET, and the LRU cache as a classic use.

   Intermediate Theory Data Structures · 🔗 2 follow-ups
3. Explain stacks and queues. How are Stack<T> and Queue<T> implemented in .NET, where do you see them in real systems, and which thread-safe alternatives would you use?

   LIFO and FIFO structures, their array-based implementations in .NET, the call stack, undo, BFS and work queues, plus ConcurrentStack, ConcurrentQueue and Channels.

   Junior Theory Data Structures · 🔗 3 follow-ups
4. How does a hash table work? Explain how Dictionary<TKey,TValue> in .NET stores and finds entries, handles collisions and resizes, and what GetHashCode and Equals must guarantee.

   Hash table fundamentals and .NET Dictionary internals: buckets and entries, chaining, load and resizing, the GetHashCode/Equals contract, average vs worst-case cost, and hash flooding protection.

   Mid-Level Theory Data Structures · 🔗 3 follow-ups · 🛠 1 real-world
5. A Dictionary-based cache in a .NET service gets slower and slower and sometimes "loses" entries that were definitely added. What could be wrong with the key type, and how would you debug and fix it?

   Debugging hash-based collection failures: constant or poor GetHashCode, mutable keys, inconsistent Equals, culture-sensitive comparisons, and thread-unsafe access to Dictionary.

   Senior Debugging Data Structures · 🔗 2 follow-ups · 🛠 1 real-world
6. What is a set? When would you use HashSet<T>, SortedSet<T>, FrozenSet<T> or ImmutableHashSet<T> in .NET, and what set operations do they support?

   Sets as collections of unique items, hash vs tree-based sets, set algebra (union, intersection, difference), frozen and immutable variants, and common performance wins over List.Contains.

   Intermediate Theory Data Structures · 🔗 3 follow-ups
7. A map (dictionary) associates keys with values. Compare the map types in .NET: Dictionary, SortedDictionary, SortedList, OrderedDictionary, ConcurrentDictionary, FrozenDictionary, ImmutableDictionary and ILookup. How do you choose?

   The map abstraction and .NET's map implementations: hash vs tree vs sorted array, ordering, concurrency, frozen and immutable variants, multi-maps, and how to choose by access pattern.

   Mid-Level Theory Data Structures · 🔗 3 follow-ups · 🛠 1 real-world
8. What are trees, binary trees and binary search trees? Explain traversals, why balance matters, and where trees appear in real .NET systems and databases.

   Tree terminology, binary trees and BSTs, in/pre/post/level-order traversals, balanced trees (red-black, AVL), B-trees in database indexes, and real-world trees in .NET.

   Mid-Level Theory Data Structures · 🔗 3 follow-ups · 🛠 1 real-world
9. What is a heap data structure, and how does PriorityQueue<TElement,TPriority> work in .NET? Show how you would find the top K items from a large stream efficiently.

   Binary and d-ary heaps stored in arrays, heap operations and costs, PriorityQueue in .NET (min-heap, no stability, Remove in .NET 9), and classic uses: top-K, scheduling, merging sorted streams and Dijkstra.

   Mid-Level Coding Data Structures · 🔗 2 follow-ups · 🛠 1 real-world
10. What is a graph data structure? How do you represent one in C#, and where do graphs show up in real backend systems (dependencies, workflows, permissions)? How would you detect a cycle or find a valid execution order?

    Graph terminology, adjacency list vs matrix vs edge list, directed acyclic graphs, topological sort and cycle detection, and real-world graphs such as DI containers, build systems and job schedulers.

    Senior Theory Data Structures · 🔗 4 follow-ups · 🛠 1 real-world
11. What is a trie (prefix tree)? Implement insert, exact search and prefix search in C#, and discuss when a trie is the right choice for something like autocomplete versus alternatives.

    Trie structure and operations, O(L) insert and search, prefix queries, memory trade-offs and compressed (radix) tries, and alternatives such as sorted arrays, database prefix queries and search engines.

    Mid-Level Coding Data Structures · 🔗 3 follow-ups · 🛠 1 real-world
12. 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 Data Structures · 🔗 3 follow-ups · 🛠 1 real-world