FastPrepLRU Cache with Expiring Entries
Problems/LRU Cache with Expiring Entries

LRU Cache with Expiring Entries

Paytm logoPaytm● HardFULLTIMEPHONE SCREEN

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: The report asks for an LRU cache with TTL and also mentions multithreading and concurrency. The judge checks a sequential, explicit-time version; it does not verify thread safety. API and expiry rules are practice assumptions, with about 80% core-task similarity.

Process a sequence of operations on an initially empty least-recently-used cache with at most capacity live entries. Each entry has the same time-to-live duration ttl. Return the results of all get operations, in input order.

Each operation is a row [type, time, key, value], in nondecreasing time order. Process rows with equal times in their input order.

  • type = 0: put the key and value. An inserted or updated entry expires at time + ttl and becomes most recently used.
  • type = 1: get the key. Its value field is 0 and is ignored. Return the stored value if live and make it most recently used; otherwise return -1. A get does not extend expiry.

Before each operation at time t, remove every entry with expiry time less than or equal to t. If putting a new key would exceed capacity, evict the least recently used live entry. A failed get changes no recency. Expired entries never consume capacity.

The operations run one after another, and each row carries its own time. Handling many users at once is a discussion topic. It does not change the results you return.

Function

cacheResults(capacity: int, ttl: int, operations: int[][]) → int[]

Examples

Example 1

capacity = 2ttl = 5operations = [[0,0,1,10],[0,1,2,20],[1,2,1,0],[0,3,3,30],[1,3,2,0],[1,5,1,0]]return = [10,-1,-1]

Getting key 1 makes key 2 least recent, so inserting key 3 evicts key 2. Key 1 still expires at time 5 because get does not refresh TTL.

Example 2

capacity = 1ttl = 3operations = [[0,0,7,4],[0,2,7,9],[1,3,7,0],[1,5,7,0]]return = [9,-1]

Updating key 7 resets expiry to time 5. Its older expiry at time 3 must not remove the refreshed entry.

Constraints

  • 1 <= capacity <= 10^4.
  • 1 <= ttl <= 10^9.
  • 0 <= operations.length <= 10^5; every row has four integers.
  • There are at most 10^4 get operations, so the returned array remains bounded.
  • type is 0 or 1.
  • 0 <= time <= 10^9, with nondecreasing times.
  • 1 <= key <= 10^9 and 0 <= value <= 10^9. Get rows have value zero.

More Paytm interview questions

  • Nth Highest SalaryPHONE SCREEN · Seen Nov 2026
  • Second Highest SalaryPHONE SCREEN · Seen Nov 2026
  • Jump GamePHONE SCREEN · Seen Nov 2026
  • Detect a Linked-List CycleONSITE INTERVIEW · Seen Sep 2026
  • Find First and Last Position in Sorted ArrayONSITE INTERVIEW · Seen Sep 2026
  • Minimum Coins for a TargetONSITE INTERVIEW · Seen Sep 2026

Similar questions at other companies

  • LRU Cache with TTLAutodesk · ONSITE INTERVIEWAutodesk interview questions
  • Split Tender Part 4 - RefundsStripe · OA · PHONE SCREENStripe interview questions
  • 15-Minute Chat Session TrackerOpenAI · PHONE SCREEN · ONSITE INTERVIEWOpenAI interview questions
  • Capacity-Limited Timed CacheNetflix · PHONE SCREENNetflix interview questions
  • Tiered Expiring Item StoreHudson River Trading · PHONE SCREEN · ONSITE INTERVIEWHudson River Trading interview questions
  • LFU CacheFreshworks · PHONE SCREENFreshworks interview questions
  • Tiered Expiring Item StoreAkuna Capital · PHONE SCREENAkuna Capital interview questions
  • Multi-Level Inventory Storage SystemOptiver · OA · PHONE SCREENOptiver interview questions
  • Limit Order Book Matching EngineCitadel · PHONE SCREENCitadel interview questions
  • Document Enrichment Stream AggregatorBloomberg LP · PHONE SCREENBloomberg LP interview questions
All Paytm interview questionsSee Paytm hiring insights
Saved
class Solution {
    public int[] cacheResults(int capacity, int ttl, int[][] operations) {
        // Write your code here.
    }
}
Checking account…