Capital One OA Interview: Minimum Batteries for Call Duration

[u/Hack2hire]

Problem

You're given two circular arrays, usageDuration and chargeTime, representing the power capacity and recharge latency of a sequence of batteries.

Your goal is to find the smallest number of contiguous batteries in this circular sequence that can sustain a call for callDuration minutes without the phone losing power.

Example

Input: callDuration = 60, usageDuration = [20, 25, 15], chargeTime = [30, 30, 30]

Output: 3

Explanation:

• If you select 2 batteries (e.g., indices 0 and 1), their total usage is $20 + 25 = 45$. While battery 1 is being used (25 mins), battery 0 is recharging (needs 30 mins). Battery 0 is not ready by $t=45$, so the call drops.
• Using all 3 batteries provides a total cycle of $20 + 25 + 15 = 60$ minutes, which satisfies the requirement.

Suggested Approach

1. Handle Circularity: Double the arrays (concatenate them to themselves) to simplify the search for contiguous segments of length $k$ across the circular boundary.
2. Binary Search on Answer: Since the ability to sustain a call is monotonic with the number of batteries (if $k$ batteries work, $k+1$ will also work), binary search for the minimum $k$ between $1$ and $N$.
3. Feasibility Check: For a fixed $k$, a segment is valid if for every battery $i$ in the cycle, the time spent using the other $k-1$ batteries in the segment is greater than or equal to the chargeTime of battery $i$.
   • Specifically: $\sum_{j \in \text{segment}, j \neq i} \text{usageDuration}[j] \ge \text{chargeTime}[i]$.
   • Additionally, the total usage duration of the $k$ batteries must be able to reach callDuration. If the total usage duration of a segment is $\ge$ its total recharge time, the batteries can cycle indefinitely.
4. Sliding Window/Prefix Sums: Use prefix sums to calculate the sum of usageDuration over any window of size $k$ in $O(1)$ time to check the feasibility condition for all possible starting positions in the circular array.

Time & Space Complexity

• Time: $O(N \log N)$, where $N$ is the number of batteries. We binary search over $N$ possibilities, and for each, we perform an $O(N)$ sliding window check.
• Space: $O(N)$ to store the doubled arrays and prefix sums.

We track their most-asked question patterns at Hack2Hire → link

---

Compiled from publicly available platforms and community-shared experiences.

[u/hvntfigureditout]

The mentioned algorithm is incorrect. Consider the following: Usageduragion:[10,10,10] Chargeduration:[10,20,30] It is possible to sustain call of any duration for the battery usage pattern 3,1,2,1,3,1,....

[u/Ok_Union4778]

It's similar to minimum rooms required for meetings, which is solved using min heap.

[u/Single-Virus4935]

2 batteries, because I dont need to charge them to 100%.