Minimum Calls for Repeated API Lookups
Updated
Problem statement
For this exercise, assume a program must serve a sequence of read-only API lookups. Each entry in requestIds is the ID of one record to read.
- One API call fetches exactly one record ID.
- A record never changes during this sequence. Every lookup of the same ID needs the same result.
- The local cache starts empty, has no size limit, and never expires. A fetched result may serve later lookups of that ID without another API call.
- Every requested record must be fetched at least once before its result can be used. No lookup may be skipped, and one ID cannot stand in for another.
Return the minimum number of API calls needed to serve the entire sequence. Return 0 for an empty sequence. You only return the call count; you do not contact an API or return record data.
Function
minimumApiCalls(requestIds: int[]) → intExamples
Example 1
requestIds = [7,3,7,9,3]return = 3Fetch IDs 7, 3 and 9 once each. The later requests for 7 and 3 reuse their cached results, so three API calls are enough. Each of the three distinct IDs must be fetched, so fewer calls cannot work.
Example 2
requestIds = []return = 0There are no requested records, so no API call is needed.
Example 3
requestIds = [42,42,42]return = 1Fetch ID 42 for its first request. Both later requests reuse that result, so exactly one API call is needed.
Constraints
0 <= requestIds.length <= 20000.0 <= requestIds[i] <= 1000000000.
Interview reports that mention this question
Palantir interview experiences
- Palantir FDSE Experienced-Hire Interviews: 5 Experiences
- Palantir FDSE New Grad OA Questions: 6 Experiences (Part 2 of 2)
- Palantir FDSE New Grad Interviews: 5 Experiences (Part 1 of 2)
- Palantir FDSE Karat and Learning: 7 Experiences (Part 2 of 2)
- Palantir FDSE OA and Interviews: 16 Experiences (Part 1 of 2)