FastPrepLFU Cache Operations
Problems/LFU Cache Operations

LFU Cache Operations

Morgan Stanley logoMorgan Stanley● HardFULLTIMEONSITE INTERVIEW

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: Reported in a Morgan Stanley onsite interview for a full-time role. The question looks like LFU. The author links LFU Cache but says the interview task was similar, and the twist is not reported. Here we use that problem's frequency counters, LRU tie-break, get and put behavior, and the goal of average constant time. We chose the limited commands and the function that reports what happened.

Our version is about 80% the same as the reported question.

Process commands for a least-frequently-used cache with capacity capacity. For this exercise, [0,key] means get and [1,key,value] means put. Start with an empty cache and return the result of each get, in command order. Put commands contribute no output entries.

A get returns the stored value and increments that key’s use frequency when present; otherwise it returns -1 and does not change the cache. A put on an existing key updates its value, increments its frequency and makes it most recently used at its new frequency. A newly inserted key starts at frequency 1.

Before inserting a new key into a full cache, evict a key with the smallest frequency. If several keys tie, evict the least recently used among them. A successful get, an existing-key put and a new insertion each count as a use for recency. An evicted key that is later reinserted starts fresh at frequency 1.

Implement average O(1) work per get or put, apart from appending the required results. Leave the command array unchanged. The function adapter simulates one fresh cache instance; it does not change the named cache rules.

Function

processLFUCache(capacity: int, commands: int[][]) → int[]

Examples

Example 1

capacity = 2commands = [[1,4,40],[1,6,60],[0,4],[1,8,80],[0,6],[0,8],[1,10,100],[0,4],[0,8],[0,10]]return = [40,-1,80,-1,80,100]

The first hit on key 4 makes key 6 less frequent, so inserting 8 evicts 6. Later keys 4 and 8 each have frequency 2, but 4 is older, so inserting 10 evicts 4. The get results are [40,-1,80,-1,80,100].

Example 2

capacity = 2commands = [[1,1,10],[1,2,20],[1,1,11],[1,3,30],[0,1],[0,2],[0,3]]return = [11,-1,30]

Updating key 1 to value 11 also raises its frequency to 2. Key 2 still has frequency 1, so inserting key 3 evicts key 2. The gets return [11,-1,30].

Constraints

  • For this exercise, assume 1 <= capacity <= 100.
  • For this exercise, assume 0 <= commands.length <= 500.
  • Every command row has between 2 and 3 integers.
  • Every command integer is between 0 and 1000000.
  • A command is exactly [0,key] or [1,key,value]; keys and values use the stated integer bounds.

More Morgan Stanley Onsite Interview questions

  • Generate Strings of Length at Least ThreeONSITE INTERVIEW · Seen Sep 2026
  • Maximum Concurrent ProcessesOA · ONSITE INTERVIEW · Seen Sep 2026
  • Kth Largest Array ElementONSITE INTERVIEW · Seen Jul 2026
  • Run-Length Encode Consecutive Letter RunsONSITE INTERVIEW · Seen Jul 2026
  • Maximum Edge Removals for Two TravelersONSITE INTERVIEW · Seen Oct 2025
  • Remove K DigitsONSITE INTERVIEW · Seen Oct 2025
  • Count Ideal ArraysONSITE INTERVIEW · Seen Aug 2023
  • Distinct Palindrome PartitionsONSITE INTERVIEW · Seen Aug 2023
  • All-Pairs Shortest PathsOA · ONSITE INTERVIEW · Seen Feb 2022
  • Fibonacci with Input ValidationONSITE INTERVIEW · Seen Feb 2022

Similar questions at other companies

  • LFU CacheAmazon · ONSITE INTERVIEW
  • LFU CacheJP Morgan Chase · ONSITE INTERVIEW
  • LFU CacheSnowflake · OA · ONSITE INTERVIEW
  • LRU Cache with TTLAutodesk · ONSITE INTERVIEW
  • Recover a Function-Call LRU Cache with a Write-Ahead LogAnthropic · ONSITE INTERVIEW
  • LFU CacheSalesforce · ONSITE INTERVIEW
  • LFU CacheBlinkit · ONSITE INTERVIEW
  • Thread-Safe LRU Cache with TTLLinkedIn · ONSITE INTERVIEW
  • Fair Multi-Tenant CacheOkta · ONSITE INTERVIEW
  • LFU CacheZomato / Eternal · ONSITE INTERVIEW

Interview reports that mention this question

  • Morgan Stanley Apprenticeship and Tech Interviews: 6 Experiences

Morgan Stanley interview experiences

  • Morgan Stanley New Grad Technology Analyst: 2 Experiences
  • Morgan Stanley Intern Oldest Loops: 5 Experiences (Part 5 of 5)
  • Morgan Stanley Intern OOP Loops: 5 Experiences (Part 4 of 5)
  • Morgan Stanley Intern Earlier Loops: 5 Experiences (Part 3 of 5)
  • Morgan Stanley Intern Tech Rounds: 5 Experiences (Part 2 of 5)
See Morgan Stanley hiring insights
Saved
class Solution {
    public int[] processLFUCache(int capacity, int[][] commands) {
        // Write your code here.
    }

}
Checking account…