Inno 3.3 Data Structures

Question 1

What is List<T> and how is it implemented internally?</T>

Answer 1

List<T> is a dynamic array internally backed by a contiguous memory block. It automatically resizes (usually doubling capacity) when more space is needed.</T>

Access by index is O(1), insert/remove at the end is amortized O(1), but insert/remove in the middle is O(n) due to shifting elements.

AUTOMATICLY RESIZES DOUBLING CAPACITY

Question 2

What is Dictionary<TKey, TValue> and how does it work under the hood?

Answer 2

Dictionary uses a hash table under the hood.

Keys are hashed, then mapped to a bucket index.

Reading and writing is fast (O(1) average), but depends on the quality of the hash function and number of collisions. Collisions are handled with chaining or probing.

If the load factor (75%) is overcomed, theres rehasing so creating the double the amount of buckets and copying there data

BUCKET, LOAD FACTOR, REHASING

Question 3

Why are read/write operations in Dictionary fast?

Answer 3

Because the key is first hashed, and then the hash determines the index in an internal array.

If the hash function distributes keys evenly, lookup is nearly constant time. Collisions degrade performance but are rare with good hashing.

Question 4

What’s the difference between Array, ArrayList, and List<T>?</T>

Answer 4

Array is fixed-size and type-safe.

List<T> is generic, type-safe, resizable and faster than ArrayList.</T>

ArrayList is non-generic and stores object, causing boxing/unboxing.

Question 5

What are the time complexities for common operations in List<T>?</T>

Answer 5

Index access: O(1)

Add (end): amortized O(1)

Insert (middle): O(n)

Remove (by index): O(n)

Question 6

Q: What is a Queue<T> and what are its time complexities?</T>

Answer 6

A: Queue<T> is a FIFO (First-In-First-Out) structure backed by a circular array. Enqueue and dequeue are both O(1) amortized. Good for producer-consumer scenarios.</T>

Question 7

Q: What is a Stack<T> and what are its time complexities?</T>

Answer 7

A: Stack<T> is LIFO (Last-In-First-Out). Push and Pop operations are O(1). Internally it uses a resizable array similar to List<T>.</T></T>

Question 8

Q: What is ConcurrentStack<T>?</T>

Answer 8

A: A thread-safe version of Stack<T>. It uses lock-free synchronization under the hood (compare-and-swap operations) to support concurrent access with high performance.</T>

Question 9

Q: What is LinkedList<T> and when is it better than List<T>?</T></T>

Answer 9

A: LinkedList<T> is a doubly-linked list. Insertion and deletion are O(1) if you have the node reference. However, lookup is O(n). It's better than List<T> when you often insert/delete in the middle or avoid reallocating memory.</T></T>

Question 10

Q: What is a Hashtable?

Answer 10

A: A non-generic dictionary that stores keys/values as object. Uses hashing internally. Slower than generic Dictionary<TKey,TValue> due to boxing/unboxing and lack of compile-time safety.

STORES AS AN OBJECT => USES BOXING/UNBOXING

Question 11

Q: What is SortedList<TKey, TValue> and how is it different from SortedDictionary<TKey, TValue>?

Answer 11

SortedList uses arrays internally and maintains keys in sorted order. Fast index access, but insertion is O(n) due to shifting.

SortedDictionary uses a binary search tree (Red-Black Tree), with O(log n) insertion/lookup and better scalability for large datasets.

Question 12

Q: What is ConcurrentDictionary<TKey, TValue> and how does it handle thread safety?

Answer 12

A: It partitions data internally (using segments) and applies fine-grained locking or lock-free techniques for concurrent operations. It avoids full locking for high performance in multithreaded environments.

Question 13

Q: What are the trade-offs between List<T> and LinkedList<T>?</T></T>

Answer 13

List<T> is better for indexed access and sequential data.</T>

LinkedList<T> is better for frequent inserts/removals when you already have a reference to the node.</T>

List<T> has better cache locality and lower memory overhead.</T>

Question 14

Q: How does resizing in List<T> work?</T>

Answer 14

A: When capacity is exceeded, **List<T> allocates a new array (usually double the size), copies all elements, and replaces the internal array**. This makes appending O(1) amortized, but resizing itself is O(n).</T>

Question 15

Q: What is cache locality and how does it affect performance in collections?

Answer 15

A: Cache locality means how well data fits and is accessed in CPU cache. Arrays and List<T> have good locality (contiguous memory), making them faster. Linked lists have poor locality, leading to cache misses and slower traversal.</T>

Cache locality describes how well a program uses the CPU cache, which is much faster than RAM.

When your code accesses memory, the CPU tries to load nearby data into its cache to speed things up. If your program accesses data that’s close together in memory, it benefits from better cache locality.

Arrays, List<T>: ✅ great locality – elements stored contiguously in memory.</T>

**LinkedList<T>, Dictionary<K,V>`: ❌ poor locality – nodes/entries are scattered in memory (heap allocated).</T>

HOW FAST IS FITS INTO THE CPU CACHE

Question 16

Q: When is it better to use a SortedList vs Dictionary?

Answer 16

Use SortedList when you need to maintain order and fast access by index.

Use Dictionary when order doesn’t matter but fast insertion and lookup are needed.

For large datasets, SortedDictionary scales better than SortedList.

Question 17

Q: Why is Dictionary not 100% O(1) lookup time?

Answer 17

A: Because hash collisions can occur. When multiple keys hash to the same bucket, collisions are handled via chaining or probing, which adds overhead. A poorly designed hash function or excessive load factor can degrade performance.

Question 18

Q: Why is List<T> generally faster than LinkedList<T> for most scenarios?</T></T>

Answer 18

A: List<T> is backed by a contiguous memory block (array), which gives it excellent cache locality. The CPU can load sequential data quickly into cache lines, making iterations and index-based access very fast. In contrast, LinkedList<T> stores elements as separate nodes with pointers, often scattered in memory. This leads to frequent cache misses and slower traversal, despite O(1) insertions and deletions when a node reference is known.</T></T>

Question 19

Q: Why is ArrayList slower and less safe than List<T>?</T>

Answer 19

A: ArrayList is a non-generic collection that stores elements as object, requiring boxing and unboxing for value types. This adds memory overhead and runtime performance penalties. List<T> is generic and avoids boxing, resulting in type safety, faster access, and better memory efficiency. Also, generic collections benefit from compile-time type checks and JIT optimizations.</T>

Question 20

Q: Why does Dictionary<TKey, TValue> provide fast key lookups on average?

Answer 20

A: Dictionary uses a hash table internally. The key is hashed (via GetHashCode), and the result is used to calculate an index in an internal array (bucket). If the hash function distributes keys uniformly and there are few collisions, lookup is close to O(1). Collisions are resolved using chaining or open addressing. Performance may degrade to O(n) in worst-case scenarios, but a good hash function and resizing strategy keep it fast on average.

Question 21

Q: What makes ConcurrentDictionary<TKey, TValue> thread-safe and performant?

Answer 21

A: ConcurrentDictionary avoids global locks by partitioning the data into internal segments. It applies fine-grained locking or uses lock-free techniques like Interlocked.CompareExchange. This design allows multiple threads to read/write concurrently with minimal contention, making it highly scalable for multi-threaded environments.

Question 22

Q: Why is SortedList<TKey, TValue> slower on inserts compared to SortedDictionary<TKey, TValue>?

Answer 22

A: SortedList uses two internal sorted arrays (for keys and values). When inserting a new item, it must perform a binary search to find the correct index (O(log n)), but then shift elements to maintain sorted order (O(n)). In contrast, SortedDictionary uses a self-balancing binary search tree (Red-Black Tree), which guarantees O(log n) insertion and avoids shifting, making it faster for large or dynamic datasets.

Question 23

Q: What is a Hashtable, and why is it slower than Dictionary<TKey, TValue>?

Answer 23

A: Hashtable is a non-generic key/value collection that internally uses hashing. It stores everything as object, which introduces boxing for value types and requires runtime type casting. This increases GC pressure and introduces potential for runtime errors. Dictionary<TKey, TValue> is generic, type-safe, and faster due to less boxing/unboxing, better memory alignment, and JIT optimizations.

Question 24

Q: Why does LinkedList<T> have worse read performance than List<T>?</T></T>

Answer 24

A: LinkedList<T> requires sequential traversal to access a specific element (O(n)), as it does not support index-based access. Each node is a separate object in memory with references to the next/previous node, which causes pointer chasing and poor cache locality. In contrast, List<T> stores elements in contiguous memory and supports O(1) indexing, making reads much faster.</T></T>

Question 25

Q: How does Queue achieve fast enqueue and dequeue operations?

Answer 25

A: Queue uses a circular array under the hood. Instead of shifting elements when dequeuing, it keeps track of head and tail indices and wraps around the array. This allows both enqueue and dequeue operations to be performed in O(1) time, with resizing occurring only when capacity is exceeded.

Question 26

Q: Why is Stack fast for push/pop operations?

Answer 26

A: Stack is implemented using a resizable array, with an index pointer to track the top element. Push and pop simply move this pointer up or down, resulting in O(1) operations. Since the data is stored contiguously, cache locality is good, making it efficient for CPU access.

Question 27

Q: What is boxing/unboxing, and why does it hurt performance in collections?

Answer 27

A: Boxing is the process of wrapping a value type (e.g., int) into an object, which allocates memory on the heap. Unboxing extracts the value type back. In collections like ArrayList or Hashtable, which store elements as object, value types are boxed, causing extra memory allocations, GC pressure, and CPU overhead. Generic collections avoid this, making them more efficient.

Question 28

Q: When does resizing occur in a List, and what happens internally?

Answer 28

A: Resizing occurs when the number of elements exceeds the current capacity. List then allocates a new larger array (typically double the size), copies existing elements to it, and discards the old array. This operation is O(n), but happens infrequently. This strategy enables amortized O(1) performance for Add().

Question 29

Q: What is the difference in collision handling between Dictionary and ConcurrentDictionary?

Answer 29

A: Both use hashing, but Dictionary handles collisions using chaining, typically with a linked list in each bucket. In newer versions of .NET, this changes to a small binary tree when collisions exceed a threshold. ConcurrentDictionary adds concurrency controls via locking or lock-free segments and avoids race conditions by synchronizing access during collisions.

Question 30

Q: Why should you not modify a collection during enumeration?

Answer 30

A: Modifying a collection while iterating through it (e.g., in a foreach loop) can cause an InvalidOperationException. This is because most enumerators are fail-fast: they detect structural changes and throw to prevent inconsistent states. Concurrent collections like ConcurrentDictionary or ConcurrentQueue support safe modifications during enumeration with special design.

Question 31

Q: What is the purpose of the IEnumerable and IEnumerator interfaces?

Answer 31

A: IEnumerable is the base interface for all non-indexed collections. It exposes a single method GetEnumerator(), which returns an IEnumerator. This interface allows foreach loops and deferred execution (e.g., with LINQ). IEnumerator provides **MoveNext(), Current, and Reset().** These interfaces allow iteration abstraction, decoupling traversal logic from the collection’s internal structure.

Question 32

Q: How does ICollection extend IEnumerable, and what additional functionality does it provide?

Answer 32

A: ICollection inherits from IEnumerable and adds counting, modification, and query features like **Count, Add, Remove, and Contains.** It represents a **mutable** collection of objects and is implemented by collections like List, Queue, and Stack. It also supports CopyTo, which helps for interop with arrays. ADD COUNTS, ADD, REMOVE, CONTAINS

Question 33

Q: What interface must a collection implement to support indexing?

Answer 33

A: To support indexing with square brackets ([]), a collection must implement **IList** (or **IReadOnlyList** for read-only access). IList provides access to elements by index (this[int index]), as well as insertion/removal at specific positions. It combines the capabilities of ICollection and indexed access.

Question 34

Q: What’s the difference between IList and IReadOnlyList?

Answer 34

A: IList supports read/write operations, including item setting and mutation methods. IReadOnlyList provides read-only indexed access and exposes the Count and indexer (T this[int index] { get; }) but no mutating methods. **Using IReadOnlyList in public APIs enforces immutability, making code safer and easier to reason about.**

Question 35

Q: What does the IDictionary interface define, and why is it useful?

Answer 35

A: IDictionary represents a key/value collection and defines methods like Add(key, value), Remove(key), ContainsKey(), and an indexer (this[key]). It abstracts the concept of map-like collections and is implemented by types like Dictionary and SortedDictionary. It allows algorithms to work with any dictionary-like collection polymorphically.

Question 36

Q: Why should developers program against interfaces like IEnumerable, ICollection, or IDictionary?

Answer 36

A: Programming to interfaces decouples code from specific implementations. This improves testability, allows swapping underlying collections (e.g., List vs LinkedList), and promotes better abstraction and reuse. For example, you can mock IEnumerable or ICollection in unit tests without relying on concrete classes.

Question 37

Q: What is ISet, and how does it differ from ICollection?

Answer 37

A: ISet represents a collection of **unique** elements and extends ICollection. It includes **set-specific** methods like UnionWith, IntersectWith, ExceptWith, and SetEquals. Unlike List, a set enforces uniqueness and offers mathematical set operations, which are useful for filtering, merging, and deduplication.

Question 38

Q: What is IReadOnlyCollection, and when should it be used?

Answer 38

A: IReadOnlyCollection is a read-only interface that exposes Count and allows enumeration (IEnumerable), but no modification. It's useful in APIs to signal intent that the caller should not change the collection. This helps enforce immutability and prevents bugs caused by unintended mutations.

Question 39

Q: What collection interfaces are implemented by Dictionary?

Answer 39

A: Dictionary implements IDictionary, IReadOnlyDictionary, ICollection>, and IEnumerable>. This allows it to be used flexibly in various scenarios requiring dictionary behavior, read-only access, or iteration over key/value pairs.

Question 40

Q: What role does the IComparer or IComparable interface play in sorted collections?

Answer 40

A: These interfaces define custom or natural ordering. SortedList, SortedDictionary, and SortedSet use **IComparer** (injected via constructor) or **IComparable** (on the type itself) to **maintain elements in sorted order**. Without these, the collection cannot determine how to arrange elements. This design enables flexible sorting logic without hardcoding comparisons.

Question 41

Q: What are the trade-offs between List and LinkedList in terms of performance and memory usage?

Answer 41

List is backed by an array, offering fast random access and low memory overhead due to contiguous memory allocation. However, its insertions/removals (especially at the beginning or middle) can be O(n) because it requires shifting elements. LIST IS BACKED BY ARRAY LinkedList, on the other hand, offers O(1) insertion/removal from both ends but has higher memory overhead due to the need for storing pointers (next/previous) alongside the data. It also suffers from poor cache locality because elements are scattered across memory.

Question 42

Q: Why does the Dictionary class outperform a List> for key lookups?

Answer 42

Dictionary is **backed by a hash table.** When a key is provided, the hash code is computed and used to index into an internal array, allowing for O(1) average-time lookup. On the other hand, List> requires linear search (O(n)) to find the corresponding KeyValuePair because it’s stored as a sequence without indexing. The performance gap grows as the dataset increases.

Question 43

Why would you use SortedDictionary instead of Dictionary when order matters?

Answer 43

SortedDictionary maintains elements in sorted order according to the natural order of the keys or a custom IComparer. It uses a red-black tree under the hood, ensuring O(log n) access, insertion, and deletion times while maintaining order. Dictionary, on the other hand, does not guarantee any particular order of elements, and you would need to sort it manually (e.g., via LINQ or OrderBy) after collection if order was needed.

Question 44

Why is ConcurrentDictionary optimized for multi-threading, and how does it differ from Dictionary?

Answer 44

ConcurrentDictionary is designed to allow multiple threads to safely read and write to the dictionary concurrently. It achieves this by partitioning the data into segments, with each segment independently locked when modified. This minimizes contention compared to a Dictionary, which would require a global lock to ensure thread safety, significantly reducing performance in multi-threaded scenarios.

Question 45

Q: What is the difference between Queue and Stack and in what scenarios would you use each one?

Answer 45

A: A Queue follows the **First-In-First**-Out (FIFO) principle, where elements are dequeued in the same order they were enqueued. It is ideal for scenarios like task scheduling, message queues, or breadth-first search (BFS). A Stack, on the other hand, follows **Last-In-First-Out (LIFO)** order, where the last added element is the first to be removed. It is useful for recursive algorithms, undo/redo operations, or depth-first search (DFS). The difference lies in the order of element processing — Queue is useful for processes that need to be executed in the order they were added, while Stack is used when you want to reverse the order of execution.

Question 46

Q: Why might you choose a ConcurrentQueue over a regular Queue in multi-threaded applications?

Answer 46

ConcurrentQueue is optimized for multi-threaded environments, where multiple threads can enqueue or dequeue items concurrently without the need for external synchronization (like locks). It uses a lock-free algorithm for adding and removing items, which helps to improve performance in a highly concurrent context. In contrast, Queue is not thread-safe, meaning that concurrent access can lead to race conditions and exceptions unless manually synchronized.

Question 47

Q: When would you use IReadOnlyList or IReadOnlyCollection instead of List?

Answer 47

IReadOnlyList and IReadOnlyCollection expose read-only access to a collection, which ensures that the collection cannot be modified from outside the class that owns it. These are ideal for cases where you want to encapsulate the collection and provide safe, immutable access. They are particularly useful in APIs where you want to prevent modification while allowing iteration or querying the length of the collection. List, being mutable, allows modifications, but might not be appropriate for scenarios requiring strong encapsulation of data.

Question 48

How do Hashtable and Dictionary differ in terms of performance, and when should you use one over the other?

Answer 48

Hashtable is a non-generic collection that stores both keys and values as object. This requires boxing for value types (e.g., integers), which can incur performance overhead and lead to memory inefficiencies. It also lacks compile-time type safety, making it more error-prone. Dictionary is a generic collection, which avoids boxing for value types and provides compile-time type safety. It also offers better performance due to optimizations specific to the types being used. Hashtable is generally slower and should be avoided in favor of Dictionary for modern development due to these issues.

Question 49

Why would you choose a SortedList over a Dictionary?

Answer 49

SortedList keeps its keys and values sorted by key, using an array internally. This allows it to have O(log n) lookup, insertion, and deletion times while maintaining order. It uses less memory compared to SortedDictionary (which uses a tree), but its insertions/removals are slower (due to the need to maintain order within the array). Choose SortedList if you need fast access to elements in sorted order with minimal memory overhead. However, if you don’t need the collection to be ordered or need more efficient insertion/removal, Dictionary is often a better choice.

Question 50

How does the IComparer interface affect sorting in collections like SortedSet or SortedDictionary?

Answer 50

The IComparer interface defines how two objects of type T are compared to each other. It provides a method Compare(T x, T y) that should return a value indicating whether x is less than, equal to, or greater than y. In collections like SortedSet and SortedDictionary, the IComparer is used to determine the ordering of elements. By default, SortedSet and SortedDictionary use the default comparer for T, but you can pass a custom IComparer to define a custom sorting logic, which is particularly useful for cases requiring specific ordering (e.g., case-insensitive string comparisons).