Intersection of data structures, Big O complexities, and hardware performance (CPU caches, memory hierarchy, and SIMD)

What is the primary cause of the "Performance Gap" in modern computer architecture?

The widening disparity in growth rates between fast CPU processing speeds and slow main memory (RAM) access times.

What is spatial locality in the context of CPU caching?

The tendency of a processor to access memory addresses that are physically close to those it recently accessed.

What is temporal locality in the context of CPU caching?

The tendency of a processor to repeatedly access the exact same memory locations within a short time frame.

In system programming, what is the size of a typical CPU cache line on modern architectures (x86/ARM)?

64 bytes.

Scenario: You are sequentially iterating through millions of items. Why do contiguous Arrays consistently outperform Linked Lists on real hardware?

Arrays exploit spatial locality, allowing the CPU hardware prefetcher to load data into cache lines in bulk. Linked List nodes are scattered, causing frequent, expensive cache misses.

What is the time complexity of a Linked List traversal?

O(n) time, though hardware realities make it significantly slower than an O(n) array traversal due to cache misses.

Struct of Arrays (SoA) vs Array of Structs (AoS): Which memory layout is strictly better for SIMD (Single Instruction, Multiple Data) vectorization?

Struct of Arrays (SoA). It packs identical data fields contiguously, allowing vector instructions to load and process them in a single operation.

Array of Structs (AoS) vs Struct of Arrays (SoA): When should you choose Array of Structs?

When your program typically accesses and modifies all properties of a single entity at once (improving temporal locality within a single cache line).

What is the space complexity of a standard Hash Table?

O(n) space.

Scenario: Designing an embedded system with strict real-time constraints. Why might you choose a B-Tree over a Hash Table?

B-Trees provide predictable O(log n) worst-case latency. Hash Tables have unpredictable O(n) worst-case latency spikes during collisions or dynamic resizing.

Why are B-Trees preferred over standard Binary Search Trees for disk-based storage and databases?

B-Tree node sizes are deliberately tuned to match disk block sizes or memory pages, drastically minimizing costly I/O operations and cache misses during traversal.

What is the time complexity of searching a B-Tree?

O(log n) time complexity.

What is a Lock-Free Data Structure?

A concurrent data structure that guarantees at least one thread makes progress, typically implemented using atomic CPU instructions like Compare-And-Swap (CAS) instead of blocking mutex locks.

What is a common architectural drawback of implementing Lock-Free data structures?

They are highly prone to the ABA problem and can cause severe memory bus contention from threads spinning on atomic retries.

What specific problem do Probabilistic Data Structures (like Bloom Filters) solve?

They answer set-membership queries with extreme space efficiency, at the cost of a small, mathematically controllable false-positive rate.

Can a Bloom filter produce a false negative?

No. It can only tell you if an element is "possibly in the set" (false positive possible) or "definitely not in the set" (no false negatives).

What is memory fragmentation in the context of custom memory allocators?

The phenomenon where free memory is broken into small, non-contiguous blocks, making it impossible to allocate a large contiguous array even if the total free memory is sufficient.

Scenario: You need a data structure for IP routing table lookups and efficient string prefix matching in a firmware driver. What structure should you use?

A Trie (Prefix Tree).

What is the average time complexity of a Hash Table lookup?

O(1) time complexity.

How does modifying a Linked List (insertion/deletion) compare to a Dynamic Array in terms of hardware performance?

While Linked Lists are O(1) for insertion at a known node, Dynamic Arrays (O(n) worst-case) often still outperform them for small datasets because moving contiguous memory uses highly optimized hardware-level routines (like memmove).