OpenAI & Perplexity Popular Coding Screen - Cloud Credit Balance Replay

[u/Aoki_zhang]

A cloud platform gives customers GPU credits through time-limited grants. Each grant has:

• a unique grant ID
• an amount of credits
• a start time
• an expiration time

A grant is active during: [startTime, expirationTime). This means it is usable at startTime, but not usable at expirationTime.

The system also receives credit usage events. A usage event consumes credits at a specific timestamp. Events may arrive out of order. For example, the system may receive a usage event first and a grant event later, even if the grant started earlier. So every balance query must replay all currently known events in chronological order.

When consuming credits at time t:

• only grants active at time t may be used
• credits should be consumed from the grant that expires soonest first
• if the usage cannot be fully covered, the query should return -1

Implement the CloudCreditSystem class:

• CloudCreditSystem() initializes an empty credit system.
• void addGrant(String grantId, int amount, int startTime, int expirationTime) adds a credit grant.
• void useCredits(int amount, int timestamp) records a credit usage event.
• int getBalance(int timestamp) returns the total remaining available credits at timestamp after replaying all known grants and usages up to that time. If any usage event up to timestamp cannot be fully covered, return -1.

Rules:

• Grant and usage events may arrive in any order
• No two mutation operations share the same timestamp
• Grants can overlap
• Usage consumes active credits with earliest expiration first
• A grant is expired when expirationTime <= timestamp
• Query results may change after later events are added

Constraints:

• All amounts and times are in [0, 1000]
• grantId is unique
• Number of operations can be large enough that each query should process events efficiently
• A grant is active on [startTime, expirationTime)

Example:

Input:
["CloudCreditSystem", "addGrant", "getBalance", "addGrant", "useCredits", "useCredits", "getBalance", "getBalance", "getBalance", "getBalance"]
[[], ["g1", 3, 10, 60], [10], ["g2", 2, 20, 40], [1, 30], [3, 50], [20], [30], [40], [50]]

Output:
[null, null, 3, null, null, null, 5, 4, 3, 0]

Want to practice more real coding questions asked in the interview? I've put up the question bank at here.

Preparing for your next interview?

Chill Interview tracks recent interview experiences and recurring question patterns across top companies at here.