Software Engineer · Phone Screen · Coding

OpenAI — Software Engineer ✅ Passed

Level: Senior-Level

Round: Phone Screen · Type: Coding · Difficulty: 5/10 · Duration: 45 min · Interviewer: Friendly

Topics: Heaps, Hash Maps

Location: San Francisco Bay Area

Interview date: 2026-01-22

Got offer: False

Summary

You are designing a system to manage GPU credits. Each credit grant has a unique ID and is valid during a specific time window. Credit grants may overlap in time.

Because of network delays, events such as adding or consuming credits may arrive and be processed out of order with respect to their timestamp. At any time, you may query the system for the total available credits at a particular timestamp or attempt to consume credits at a specified time.

Details

Implement the CreditSystem class:

• CreditSystem() Initializes the credit system.

• void grantCredit(String id, int amount, int startTime, int expirationTime) Adds a new credit grant identified by id, with amount units. The credit is active in the interval [startTime, expirationTime - 1] inclusively.

• void subtract(int amount, int timestamp) Deduct amount credits from all credits available at the specified timestamp.

  • Credits should be subtracted starting with grants that expire the soonest (i.e., those with the earliest expiration time).
  • If the total available credits at that time are less than the requested amount, use up all available credits. int getBalance(int timestamp) Returns the number of credits available at the given timestamp.

Constraints:

• No two operations (grantCredit or subtract) share the same timestamp.
• All grants, usage events, and queries may arrive in any order.
• All time windows are inclusive at both ends.
• All amount, startTime, and expirationTime are in the range [0, 1000].

Example:

` Input: ["CreditSystem", "grantCredit", "getBalance", "grantCredit", "subtract", "subtract", "getBalance", "getBalance", "getBalance", "getBalance", "getBalance", "getBalance"] [[], ["a", 3, 10, 60], [10], ["b", 2, 20, 40], [1, 30], [3, 50], [10], [20], [30], [35], [40], [50]]

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

Explanation:

CreditSystem cs = new CreditSystem(); cs.grantCredit("a", 3, 10, 60); // Grants 3 credits for time [10, 59]. cs.getBalance(10); // Returns 3. cs.grantCredit("b", 2, 20, 40); // Grants 2 credits for time [20, 39]. cs.subtract(1, 30); // Consumes 1 credit at t=30, deducted from the earliest-expiring grant ("b"). cs.subtract(3, 50); // Consumes 3 credits at t=50, only grant "a" is available. cs.getBalance(10); // Returns 3. Only grant "a" active at t = 10. cs.getBalance(20); // Returns 5. Both "a" and "b" are active at t = 20. cs.getBalance(30); // Returns 4. Only 1 credit has been consumed at t = 30. cs.getBalance(35); // Returns 4. cs.getBalance(40); // Returns 3. Only "a" is active at t = 40. cs.getBalance(50); // Returns 0. The remaining 3 credits are consumed. `

Solution

` from typing import List, Optional import heapq from collections import defaultdict

class Grant: def init(self, end, amount): self.end = end self.amount = amount

class ActiveGrant: def init(self, end, remaining): self.end = end self.remaining = remaining

def __lt__(self, other):
    return self.end < other.end

class CreditSystem: def init(self): self.grantsByStart = {} self.usesByTime = {}

def grantCredit(self, id: str, amount: int, startTime: int, expirationTime: int) -> None:
    if startTime not in self.grantsByStart:
        self.grantsByStart[startTime] = []
    self.grantsByStart[startTime].append(Grant(expirationTime, amount))

def subtract(self, amount: int, timestamp: int) -> None:
    current = self.usesByTime.get(timestamp, 0)
    self.usesByTime[timestamp] = current + amount

def getBalance(self, timestamp: int) -> int:
    # Min-heap ordered by expiration time
    pq = []

    # Merge-iterate both maps up to timestamp
    allTimes = set()
    for time in self.grantsByStart.keys():
        if time <= timestamp:
            allTimes.add(time)
    for time in self.usesByTime.keys():
        if time <= timestamp:
            allTimes.add(time)

    for time in sorted(allTimes):
        # Remove expired grants
        while pq and pq[0].end <= time:
            heapq.heappop(pq)

        # Add grants starting at this time
        startsNow = self.grantsByStart.get(time)
        if startsNow is not None:
            for g in startsNow:
                heapq.heappush(pq, ActiveGrant(g.end, g.amount))

        # Process subtract at this time
        subtractAmount = self.usesByTime.get(time)
        if subtractAmount is not None:
            need = subtractAmount
            temp = []

            while need > 0 and pq:
                ag = heapq.heappop(pq)
                take = min(need, ag.remaining)
                ag.remaining -= take
                need -= take

                if ag.remaining > 0:
                    temp.append(ag)

            # Put back grants with remaining credits
            for ag in temp:
                heapq.heappush(pq, ag)

    total = 0

    # Remove grants expired at timestamp
    while pq and pq[0].end <= timestamp:
        heapq.heappop(pq)
    
    while pq:
        total += heapq.heappop(pq).remaining

    return max(total, 0)

`