PPractick

The problem

An operating system has C page frames in memory. A program accesses pages in a given order. If the page is already in memory it's a hit; otherwise it's a page fault, and the page is loaded, evicting the least recently used page if all frames are full. Count the page faults. This is the LRU cache from system design, used as a simulation: a recency-ordered list plus a hash map from page to list position gives O(1) per access.

Example: pages [5, 0, 1, 3, 2, 4, 1, 0, 5], C = 4 → 8 faults.

Function signature

int pageFaults(const vector<int>& pages, int capacity);

Test cases

Input (pages, C)	Output	Explanation
([5, 0, 1, 3, 2, 4, 1, 0, 5], 4)	8	Only the second access to 1 is a hit
([1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5], 3)	10	The classic reference string
([7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2], 4)	6
([1, 2, 1, 2], 2)	2
([1, 1, 1], 1)	1

(Confirm: frames start empty; a hit refreshes the page's recency; capacity ≥ 1.)

How interviewers phrase it

• "Given a sequence of pages and a memory capacity, find the number of page faults using the LRU page replacement algorithm" (GeeksforGeeks "Page Faults in LRU").

Clarifying questions to ask

1. Do the frames start empty? (Yes, so the first accesses are compulsory faults.)
2. Does a hit update recency? (Yes, which is what makes it LRU.)
3. How large is the input? (A simple O(n · C) scan may be fine; O(n) is better.)

Follow-ups to expect

1. "How do you get O(1) per access?"
2. "Simpler version?"
3. "How does LRU compare to FIFO and OPT?"
4. "What do real systems do?"
5. "Complexity?"

Related questions

• LRU Cache Medium
• Task Scheduler Medium
• Hand of Straights Medium
• Design Twitter Medium
• LFU Cache Hard
• Longest subarray with sum K Medium

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in