Memoized Async Lookups with Shared Pending Calls
Updated
Problem statement
A slow lookup runs in the background: it starts when it is called and hands back its answer some time later. It either returns a value or fails. You wrap it in a memoized version, which remembers answers so the same arguments do not start the real lookup again.
Call i happens at time times[i] with the argument list args[i]. If the real lookup starts for this call, it takes durations[i] time units and then gives results[i]. A result of -1 means it fails. If the real lookup does not start for this call, durations[i] and results[i] are not used.
Two calls have the same key when their argument lists are exactly equal: the same length and the same numbers in the same order. For a call at time t:
- If a lookup for this key has already finished with a value, the call gets that value at once, at time
t. The real lookup does not start. - Otherwise, if a lookup for this key is still running (it finishes after
t), the call waits for it and gets the same result at the same finish time. Every call that waits on a lookup that fails gets the failure. - Otherwise, the real lookup starts for this call and finishes at
t + durations[i]withresults[i].
A failure is never remembered: after a failed lookup finishes, the next call with the same key starts a new lookup. A value is remembered for good. A lookup that finishes at time T is done before any call at time T. Calls at the same time are handled in the order they are given.
Return one row per call, in input order: [finish time, value, started]. The finish time is when this call gets its answer, the value is the result (-1 for a failure), and started is 1 if the real lookup started for this call and 0 otherwise.
Function
memoizedLookups(times: int[], args: int[][], durations: int[], results: int[]) → int[][]Examples
Example 1
times = [0,1,2,6,6,7]args = [[3,1],[3,1],[1,3],[3,1],[1,3],[2]]durations = [5,9,4,9,9,3]results = [40,99,13,77,77,-1]return = [[5,40,1],[5,40,0],[6,13,1],[6,40,0],[6,13,0],[10,-1,1]]Call 0 starts the lookup for [3,1]; it finishes at 0 + 5 = 5 with 40. Call 1 has the same arguments while that lookup is still running, so it waits for it and also gets 40 at time 5. Call 2 uses [1,3], a different key because the order differs, so it starts its own lookup: 13 at time 6. At time 6 both keys have finished successfully, so calls 3 and 4 get 40 and 13 at once. Call 5 starts a lookup for [2], which fails at time 10.
Example 2
times = [0,2,4,4,5]args = [[7],[7],[7],[7],[7]]durations = [4,1,3,8,1]results = [-1,50,60,70,80]return = [[4,-1,1],[4,-1,0],[7,60,1],[7,60,0],[7,60,0]]Call 0 starts a lookup that fails at time 4, and call 1 waits for it, so both get -1 at time 4. A failure is not kept, and the lookup is done before the calls at time 4. So call 2 starts a new lookup, which finishes at 4 + 3 = 7 with 60. Calls 3 and 4 come while it is running and share it.
Example 3
times = [0,0,1,3]args = [[],[12,3],[1,23],[]]durations = [2,1,1,5]results = [5,6,7,8]return = [[2,5,1],[1,6,1],[2,7,1],[3,5,0]]An empty argument list is a key too. [12,3] and [1,23] are different lists, so each starts its own lookup. Call 3 repeats the empty list after its lookup finished at time 2, so it gets 5 at once, at time 3.
Constraints
1 <= times.length <= 1000, andargs,durationsandresultshave the same length astimes0 <= times[i] <= 10^6, andtimesis sorted in non-decreasing order0 <= args[i].length <= 4and-10^4 <= args[i][j] <= 10^41 <= durations[i] <= 10^6-1 <= results[i] <= 10^9, where-1means the lookup fails
More Rippling Phone Screen questions
- Filter, Sort, and Deduplicate Scheduled TasksPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Stateful Log Transform and SearchPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Dependency-Aware Task SchedulerPHONE SCREEN · Seen Nov 2026
- Delivery Cost Tracker with Effective-Dated RatesPHONE SCREEN · Seen Nov 2026
- Camel CardsPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Best and Worst Camel Card CompletionsPHONE SCREEN · Seen Nov 2026
- Corporate Card Expense RulesOA · PHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2026
- In-Memory Priority Task SchedulerPHONE SCREEN · Seen Oct 2026
- Limit an Organization Tree's HeightPHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2026
- Median Across N Sorted ArraysPHONE SCREEN · Seen Oct 2026
Similar questions at other companies
- LRU Cache for Query ResultsAmazon · PHONE SCREEN · ONSITE INTERVIEW
- In-Memory Filesystem CommandsPerplexity AI · PHONE SCREEN · ONSITE INTERVIEWPerplexity AI interview questions
- Rectangle Point Coverage CountsOpenAI · PHONE SCREEN · ONSITE INTERVIEWOpenAI interview questions
- File Storage ServiceCresta · PHONE SCREENCresta interview questions
- Return Every Matching DecryptionDuolingo · PHONE SCREENDuolingo interview questions
- Corporation Reporting LinesMicrosoft · PHONE SCREENMicrosoft interview questions
- Key-Value Store on a Block DeviceLambda · PHONE SCREEN
- LRU Key-Value Cache OperationsCohesity · PHONE SCREEN
- Fixed-Window Rate LimiterProofpoint · PHONE SCREEN
- LRU CacheApple · PHONE SCREEN · ONSITE INTERVIEWApple interview questions