Coding - GPU Credit Tracker

Full Interview Question: "Coding - GPU Credit Tracker" asked at OpenAI

Problem Overview

Design a GPU credit ledger that supports:

• adding credits with start and expiration windows
• subtracting usage at a timestamp
• querying balance at any timestamp This is intentionally close to resource management problems.

Problem Statement

You are given a GPU credit ledger system that needs to support the following operations:

1. Add credits with a start time and an expiration time.
2. Subtract usage at a specific timestamp.
3. Query the balance at any given timestamp.

Implement a class GPUCreditTracker with the following methods:

• addCredits(int credits, int start, int end): Add credits to the ledger with a start time start and an expiration time end.
• subtractUsage(int timestamp, int usage): Subtract usage from the ledger at the given timestamp.
• queryBalance(int timestamp): Return the balance at the given timestamp.

Constraints

• 0 <= credits, usage <= 10^9
• 0 <= start < end <= 10^9
• 0 <= timestamp <= 10^9

Examples

1. GPUCreditTracker tracker = new GPUCreditTracker();

   • tracker.addCredits(10, 1, 5);
   • tracker.queryBalance(3); returns 10
   • tracker.subtractUsage(4, 5);
   • tracker.queryBalance(4); returns 5
   • tracker.queryBalance(6); returns 0 (credits expired)

2. GPUCreditTracker tracker = new GPUCreditTracker();

   • tracker.addCredits(20, 2, 8);
   • tracker.addCredits(30, 5, 10);
   • tracker.subtractUsage(7, 15);
   • tracker.queryBalance(7); returns 35
   • tracker.queryBalance(9); returns 20

Hints

1. Use a data structure to efficiently store and query the credits with their respective start and end times.
2. Consider using a balanced binary search tree or a segment tree to manage the credits.

Solution

`java import java.util.TreeMap;

class GPUCreditTracker { private TreeMap<Integer, Integer> credits;

public GPUCreditTracker() {
    credits = new TreeMap<>();
}

public void addCredits(int credits, int start, int end) {
    this.credits.put(start, this.credits.getOrDefault(start, 0) + credits);
    this.credits.put(end, this.credits.getOrDefault(end, 0) - credits);
}

public void subtractUsage(int timestamp, int usage) {
    if (credits.containsKey(timestamp)) {
        int balance = credits.get(timestamp) - usage;
        if (balance < 0) {
            credits.put(timestamp, 0);
        } else {
            credits.put(timestamp, balance);
        }
    }
}

public int queryBalance(int timestamp) {
    int balance = 0;
    for (Map.Entry<Integer, Integer> entry : credits.entrySet()) {
        if (entry.getKey() <= timestamp) {
            balance += entry.getValue();
        }
    }
    return balance;
}

} `

This solution uses a TreeMap to efficiently store and query the credits with their respective start and end times. The addCredits method adds credits to the start time and subtracts them from the end time. The subtractUsage method updates the balance at the given timestamp. The queryBalance method calculates the balance at the given timestamp by iterating through the TreeMap and summing up the credits.