Cache Memory and Computer Organization Interview Questions with Numericals
Last updated 2026-11-19
Cache memory is where computer organization questions become numerical: split a 32-bit address into tag, index and offset, trace a short access sequence through a small cache and count hits, or compute the average memory access time with two cache levels. This page covers those calculations with the working shown, plus the conceptual questions on write policies, replacement, locality, memory interleaving and DMA.
Virtual memory and TLBs are the software side of the same hierarchy, covered in paging and virtual memory interview questions. For the processor side see computer architecture interview questions. For test preparation, how to crack a technical MCQ test explains how to pace numerical questions.
| Address split | Address = tag | index | block offset |
|---|---|
| Key formula | AMAT = hit time + miss rate x miss penalty |
| Numericals | Tag bits, AMAT one and two level, direct vs 2-way vs full trace, block mapping |
Address breakdown recipe
- Offset bits = log2(block size in bytes).
- Number of lines = cache size / block size. Number of sets = lines / associativity. Index bits = log2(sets).
- Tag bits = address bits - index bits - offset bits. Direct mapped is associativity 1, fully associative has one set and no index.
Cache Memory and Computer Organization Interview Questions with Numericals: questions with worked answers
1 What is a cache and why does it work?
easyA cache is a small, fast memory between the CPU and main memory that holds copies of recently used data. It works because of locality of reference: temporal locality (recently used data is likely to be used again soon) and spatial locality (data near recently used addresses is likely to be used next, which is why a whole block is fetched on a miss). With a high hit rate the average access time is close to the cache speed while the capacity is that of main memory.
2 Describe the memory hierarchy and the trade-offs between levels.
easyFrom top to bottom: registers, L1, L2 and L3 caches (SRAM), main memory (DRAM), SSD and disk. Moving down, capacity and latency increase and cost per byte falls: registers take under a nanosecond, L1 about 1 ns, DRAM about 50 to 100 ns, SSD tens of microseconds and disks milliseconds. The hierarchy delivers nearly the speed of the top with the size and price of the bottom, relying on locality.
3 Compare direct-mapped, fully associative and set-associative cache mapping.
mediumIn direct mapping a memory block can go to exactly one line (block number mod number of lines): simple and fast, but blocks that map to the same line keep evicting each other (conflict misses). In fully associative mapping any block can go in any line: fewest conflict misses, but every tag must be compared in parallel, so it is expensive and slow, and used only for small caches such as TLBs. A k-way set-associative cache maps a block to one set and any of k lines in it, a compromise used in real caches (typically 4 to 16 ways).
4 Numerical: A 16 KB direct-mapped cache has 64-byte blocks and a 32-bit address. Find the offset, index and tag bits. Repeat for 4-way set associative and for fully associative.
mediumOffset = log2(64) = 6 bits. Lines = 16 KB / 64 B = 256, so a direct-mapped cache has 256 sets, index = 8 bits, tag = 32 - 8 - 6 = 18 bits. 4-way: sets = 256 / 4 = 64, index = 6 bits, tag = 32 - 6 - 6 = 20 bits. Fully associative: 1 set, no index, tag = 32 - 6 = 26 bits. Higher associativity means a longer tag and more comparators per access.
5 Numerical: Memory block 29 is accessed in a direct-mapped cache with 8 lines. Which line holds it? What about a 2-way set-associative cache with 8 lines?
mediumDirect mapped: line = block number mod number of lines = 29 mod 8 = 5. With 2-way associativity there are 8 / 2 = 4 sets, so the set is 29 mod 4 = 1, and the block can go in either of the two lines of set 1.
6 Numerical: Hit time 1 ns, miss rate 5 percent, miss penalty 100 ns. Find the average memory access time. Then add an L2 cache with a 10 ns hit time and a 20 percent local miss rate.
mediumSingle level: AMAT = 1 + 0.05 x 100 = 6 ns. For the two-level version take an L1 hit time of 1 ns and an L1 miss rate of 10 percent, then an L2 hit time of 10 ns, L2 local miss rate 20 percent and memory 100 ns: AMAT = 1 + 0.10 x (10 + 0.20 x 100) = 1 + 0.10 x 30 = 4 ns. The L2 turns the 100 ns miss penalty into an effective 30 ns. The local miss rate of L2 is its misses divided by accesses reaching it, so the global miss rate is 0.10 x 0.20 = 2 percent.
7 Numerical: A cache has 4 lines. The block address sequence is 0, 4, 8, 0, 4, 8. Count hits and misses for direct-mapped, 2-way LRU and fully associative LRU.
mediumDirect mapped: every block address mod 4 is 0, so all map to line 0 and each access evicts the previous one: 6 misses, 0 hits. 2-way (2 sets): all addresses are even so all map to set 0, which holds 2 blocks. Accesses: 0 miss, 4 miss, 8 miss (evict 0), 0 miss (evict 4), 4 miss (evict 8), 8 miss (evict 0): 6 misses. Fully associative with 4 lines: 0, 4, 8 miss (3 compulsory misses), then 0, 4, 8 hit: 3 misses, 3 hits. The example shows conflict misses vanishing as associativity grows.
8 What are the three types of cache miss?
mediumCompulsory (cold) misses happen on the first reference to a block and are unavoidable except by prefetching. Capacity misses occur because the cache is too small to hold the working set, even if fully associative. Conflict misses occur only in direct-mapped or set-associative caches when multiple blocks compete for the same set, and larger associativity reduces them. A fourth, coherence misses, appear in multiprocessors when another core invalidates a copy.
9 Compare write-through and write-back, and write-allocate and no-write-allocate.
mediumWrite-through updates both the cache and main memory on every write: simple and memory stays consistent, but each write is slow unless a write buffer hides it. Write-back updates only the cache and marks the line dirty, writing it to memory when the line is evicted, which saves bandwidth on repeated writes but complicates coherence. On a write miss, write-allocate loads the block into the cache first (usually paired with write-back), while no-write-allocate writes straight to memory (usually paired with write-through).
10 Describe cache replacement policies.
mediumLRU evicts the least recently used line in the set: good use of temporal locality, with hardware cost growing with associativity, so true LRU is used for 2 to 4 ways and approximations (pseudo-LRU) beyond. FIFO evicts the oldest line and is simpler but can evict hot data. Random replacement is cheap and performs surprisingly close to LRU for high associativity. LFU counts uses and is rare in hardware.
11 Why do loops over a 2D array in row order run faster than in column order?
mediumC and Java store arrays in row-major order, so consecutive elements of a row are adjacent in memory and each cache line fetch brings several of them: spatial locality gives about one miss per line instead of one per element. Walking down a column jumps by a whole row each step, so with large rows every access touches a different cache line and may evict useful ones. The code is identical in operations, but the access pattern can make it several times slower.
c// fast: stride-1 access for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) sum += a[i][j]; // slow for large N: stride-N access for (int j = 0; j < N; j++) for (int i = 0; i < N; i++) sum += a[i][j];12 What is cache coherence and how does the MESI protocol address it?
mediumWith a private cache per core, several cores can hold copies of the same line, and a write by one makes the others stale. MESI tags each line Modified (only this cache has it, and it is dirty), Exclusive (only this cache, clean), Shared (several caches, clean) or Invalid. Caches snoop the bus or use a directory: a write to a Shared line first invalidates other copies, so afterwards only one valid writable copy exists. False sharing, where unrelated variables on one line make cores invalidate each other, is a known performance trap.
13 Differentiate SRAM and DRAM.
mediumSRAM stores a bit in a six-transistor flip-flop: fast, no refresh needed, but large and costly, used for caches and registers. DRAM stores a bit as charge on a capacitor with one transistor: dense and cheap, but the charge leaks so each row must be refreshed every few milliseconds, and reads are destructive and slower, used for main memory. Cost per bit and size are why caches are SRAM and main memory is DRAM.
14 What is memory interleaving?
mediumInterleaving splits memory into several independent banks so consecutive addresses are in different banks and can be accessed in an overlapping manner. With low-order interleaving across 4 banks, address mod 4 selects the bank, so sequential accesses rotate through banks, and 4 words can be delivered in about the time of one access plus small gaps. It raises bandwidth for sequential patterns but gives no gain when the stride equals the number of banks.
15 Explain the three I/O transfer modes and where DMA helps.
hardIn programmed I/O the CPU polls the device status and moves each word itself, which wastes CPU time. In interrupt-driven I/O the device interrupts the CPU when ready, so the CPU can do other work, but it still moves every word. With DMA a controller transfers a whole block between the device and memory on its own, and interrupts the CPU only when finished; it takes bus cycles by cycle stealing or burst mode. DMA is best for large, fast transfers such as disk and network, as the CPU is free apart from setup and completion.
16 How does a virtually indexed cache interact with the TLB?
hardPhysically indexed, physically tagged caches wait for the TLB translation before the lookup, adding latency. A virtually indexed, physically tagged (VIPT) cache uses the page offset bits, which do not change in translation, to start indexing while the TLB translates in parallel, then compares physical tags. This works when index and offset bits together fit within the page offset, which limits cache size per way to the page size (4 KB x associativity), one reason L1 caches are often 32 KB with 8 ways.
Frequently asked questions
What is the hit ratio and how does it relate to the miss ratio?
Hit ratio is the fraction of accesses found in the cache, and miss ratio is one minus it. A hit ratio of 95 percent means a miss ratio of 5 percent.
Why are cache blocks larger than one word?
Spatial locality: fetching neighbouring words costs little extra once the access latency is paid and often saves later misses. Very large blocks waste bandwidth and raise the miss penalty, and mean fewer lines for the same capacity.
What is the difference between L1, L2 and L3 caches?
L1 is smallest and fastest, private to a core and split into instruction and data caches. L2 is larger and slower, usually per core, and L3 is larger still and shared by cores on the chip.
What is a write buffer?
A small queue that holds data waiting to be written to memory so the CPU can continue without waiting for the slower write to finish, commonly used with write-through caches.
Related guides
- Computer Architecture Interview Questions with Numericals
- Paging and Virtual Memory Interview Questions with Numericals
- Memory Management Interview Questions with Numericals
- Operating Systems Interview Questions with Worked Answers
- Process and Thread Interview Questions with fork() Output Problems
- File System Interview Questions: Inodes, Allocation and Disk Scheduling
More in CS Fundamentals Interview Questions
- Caching Interview Questions and Answers
- Cloud Computing Basics Interview Questions with Answers
- Computer Architecture Interview Questions with Numericals
- Computer Networks Interview Questions with Worked Answers and Numericals
- CPU Scheduling Interview Questions with Gantt Chart Numericals
- Database Indexing Interview Questions
- DBMS Concurrency Control Interview Questions
- DBMS Interview Questions and Answers
- DBMS Keys Interview Questions
- Deadlock Interview Questions with Banker's Algorithm Worked Example
- Design Patterns Interview Questions with Code
- Distributed Systems Interview Questions