Quick Overview

This question evaluates understanding of caching policies and memory/storage hierarchy trade-offs, focusing on how write-back and write-through handle writes, coherence, durability, latency, bandwidth, dirty bits, write amplification, and power-loss risks.

Compare write-back vs write-through caches

Company: PayPal

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Compare write-back and write-through caching policies. Explain how each handles writes, coherence, durability, latency, and bandwidth; discuss typical use in CPU caches vs storage systems and the trade-offs (e.g., dirty bits, write amplification, and risk on power loss).

Quick Answer: This question evaluates understanding of caching policies and memory/storage hierarchy trade-offs, focusing on how write-back and write-through handle writes, coherence, durability, latency, bandwidth, dirty bits, write amplification, and power-loss risks.

You are given a fully associative cache with LRU replacement and write-allocate on write misses. Each operation is a tuple like ('R', address) or ('W', address), where each address represents one whole cache block. Simulate both write-through and write-back policies and compare their trade-offs. Rules: - Every cache access costs 1 unit of latency. - A miss must fetch the block from memory, adding read_cost latency. - A write sent to memory adds write_cost latency and counts as one memory write. - Write-through: every write updates memory immediately. Cache lines are always clean. - Write-back: writes only mark the cached block dirty. Memory is updated only when a dirty block is evicted. - On eviction, remove the least recently used block. - Do not flush the write-back cache at the end. Instead, report how many dirty lines remain; these represent data still vulnerable to power loss. Return a dictionary with metrics for both policies. The memory_writes value acts as a proxy for bandwidth and coherence-visible traffic.

Constraints

  • 1 <= capacity <= 10^5
  • 0 <= len(operations) <= 2 * 10^5
  • Each operation is ('R', address) or ('W', address)
  • 1 <= read_cost, write_cost <= 10^9
  • Expected solution should run in O(n) time with O(capacity) extra space

Examples

Input: (2, [], 5, 10)

Expected Output: {'write_through': {'latency': 0, 'memory_writes': 0}, 'write_back': {'latency': 0, 'memory_writes': 0, 'dirty_lines': 0}}

Explanation: No operations means no latency, no memory writes, and no dirty lines.

Input: (2, [('W', 1), ('W', 1)], 5, 10)

Expected Output: {'write_through': {'latency': 27, 'memory_writes': 2}, 'write_back': {'latency': 7, 'memory_writes': 0, 'dirty_lines': 1}}

Explanation: Write-through writes to memory on both writes. Write-back loads block 1 once, then keeps it dirty in cache with no memory write yet.

Hints

  1. Use a hash map plus an order-aware structure so you can test membership, update recency, and evict the LRU block in O(1) average time.
  2. Both simulators share most of their logic. The key differences are what happens on a write hit and whether a dirty block generates a memory write when evicted.

Loading coding console...