Company: Rippling
Difficulty: medium
Dual Cache Performance Analysis A team is doing an analysis of a dual cache performance. There are n requests in the queue to be processed by a service where the payload size of the i th request is denoted by payloadSize[i]. There are two caches A and B in the service which cache the response to requests made. If the i th request is cached by cache A, then cacheA[i] = 1, otherwise 0 for all 1 ≤ i ≤ n If the i th request is cached by cache B, then cacheB[i] = 1, otherwise 0 for all 1 ≤ i ≤ n Find the minimum sum of the payload sizes of a subset of requests in which each cache can serve at least minThreshold requests, or return -1 if they cannot. Constraints 1 ≤ n ≤ 2 * 10 5 1 ≤ payloadSize[i] ≤ 10 9 0 ≤ cacheA[i], cacheB[i] ≤ 1 1 ≤ minThreshold ≤ n Input Format For Custom Testing The first line contains an integer n, the number of requests. The next n lines contain an integer, payloadSize[i]. The following line contains an integer n, the number of requests. The next n lines contain cach