FastPrepLRU Page Faults
Problems/LRU Page Faults

LRU Page Faults

Expedia logoExpedia● MediumFULLTIMENEW GRADOA

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: The reported LRU page-fault example has a total of 5, which is correct. Its intermediate cache steps do not agree with each other, so we replaced them with plain least-recently-used behavior. We chose the limits and what happens with zero capacity. Our version is about 98% the same as the reported question.

A cache starts empty and can hold at most capacity distinct pages. Process pages in order. Accessing a cached page is a hit and makes it the most recently used page.

Accessing an absent page causes one page fault. Insert it, first evicting the least recently accessed cached page if the cache is full. Return the total faults. A cache with capacity 0 stores nothing, so every access faults.

Function

lruFaults(pages: int[], capacity: int) → int

Examples

Example 1

pages = [1,2,1,4,2,3,5]capacity = 4return = 5

The first accesses to 1,2,4,3 and 5 fault. Before 5, recency order from least to most recent is [1,4,2,3], so 1 is evicted.

Example 2

pages = [7,7,7]capacity = 1return = 1

Only the first access is absent.

Constraints

  • 0 <= pages.length <= 10000.
  • 0 <= pages[i] <= 1000000000.
  • 0 <= capacity <= 1000.

More Expedia Online Assessment questions

  • Balanced NumbersOA · Seen Aug 2026
  • REST API: Discounted PriceOA · Seen Aug 2026
  • Maximum Team SizeOA · Seen Mar 2026
  • Per-Domain Request LimiterOA · Seen Oct 2025
  • Count Equal-Frequency SubsequencesOA · Seen Mar 2025
  • Count Increasing Stock PeriodsOA · Seen Mar 2025
  • Get Minimum StepsOA · Seen Oct 2024
  • Rank Songs by PopularityOA · Seen Oct 2024
  • Calculate the SumOA · Seen Oct 2024
  • Get Maximum EfficiencyOA · Seen Oct 2024

Similar questions at other companies

  • Least Recently Used CacheMicrosoft · OA · PHONE SCREEN · ONSITE INTERVIEWMicrosoft interview questions
  • LFU CacheSnowflake · OA · ONSITE INTERVIEWSnowflake interview questions
  • LFU CacheArista Networks · OAArista Networks interview questions
  • LRU Cache for Query ResultsAmazon · PHONE SCREEN · ONSITE INTERVIEW
  • LRU Key-Value Cache OperationsCohesity · PHONE SCREEN
  • First-Fit Memory AllocatorGoogle · ONSITE INTERVIEWGoogle interview questions
  • LRU CacheAMD · ONSITE INTERVIEWAMD interview questions
  • LRU CacheApple · PHONE SCREEN · ONSITE INTERVIEWApple interview questions
  • Callback Signal RegistryCandid Health · PHONE SCREEN
  • Least Recently Used CacheByteDance · PHONE SCREEN · ONSITE INTERVIEWByteDance interview questions

Interview reports that mention this question

  • Expedia New Grad SDE Oldest Loops: 4 Experiences (Part 3 of 3)

Expedia interview experiences

  • Expedia Intern Final Round in 2021: 28 Experiences (Part 4 of 6)
  • Expedia Intern Finals Before 2020: 14 Experiences (Part 6 of 6)
  • Expedia Intern Final Round in 2020: 24 Experiences (Part 5 of 6)
  • Expedia Intern Final Round in 2022: 15 Experiences (Part 3 of 6)
  • Expedia Intern Final Round in 2023: 17 Experiences (Part 2 of 6)
All Expedia interview questionsSee Expedia hiring insights
Saved
class Solution {
    public int lruFaults(int[] pages, int capacity) {
        // Write your code here.
    }

}
Checking account…