How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at PayPal.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at PayPal during technical interviews.

Compare write-back vs write-through caches

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.

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.

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

Expected Output: {'write_through': {'latency': 38, 'memory_writes': 2}, 'write_back': {'latency': 28, 'memory_writes': 1, 'dirty_lines': 1}}

Explanation: Under write-back, writing block 3 forces eviction of dirty block 1, causing a single write-back to memory. Block 3 remains dirty at the end.

Input: (2, [('R', 1), ('W', 2), ('R', 1), ('W', 3), ('R', 2)], 4, 7)

Expected Output: {'write_through': {'latency': 35, 'memory_writes': 2}, 'write_back': {'latency': 28, 'memory_writes': 1, 'dirty_lines': 1}}

Explanation: The read of block 1 makes block 2 the LRU, so when block 3 is written, block 2 is evicted. In write-back, only that dirty eviction reaches memory.

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

Expected Output: {'write_through': {'latency': 18, 'memory_writes': 3}, 'write_back': {'latency': 15, 'memory_writes': 2, 'dirty_lines': 1}}

Explanation: With capacity 1, every new block evicts the previous one. Write-back reduces immediate writes, but each dirty eviction still writes to memory.

Hints

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.
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.

Quick Overview