Implement a GPU credit manager
Company: OpenAI
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Quick Answer: This question evaluates understanding of concurrent resource management, advanced data structures for top-K and per-user queries, enforcement of caps and expirations, and algorithmic complexity guarantees while maintaining atomicity under concurrent operations.
Constraints
- 0 <= len(operations) <= 2 * 10^5
- Operation timestamps are in nondecreasing order
- 0 <= amount, cap <= 10^9
- User and organization names are non-empty strings
- If `expire_time` is not `None`, it is an integer timestamp; a lot with `expire_time <= t` is considered expired before time `t` operations run
Examples
Input: ({}, {}, {}, [])
Expected Output: []
Explanation: With no operations, there are no results to return.
Input: ({'alice': 10, 'bob': 7}, {'alice': 'org1', 'bob': 'org1', 'carol': 'org2'}, {'org1': 12, 'org2': 20}, [('grant', 1, 'alice', 8, 5), ('grant', 2, 'bob', 7, None), ('consume', 3, 'alice', 3), ('refund', 4, 'bob', 5), ('get', 4, 'bob'), ('topK', 4, 2), ('get', 5, 'alice'), ('topK', 6, 3)])
Expected Output: [8, 4, True, 3, 7, [['bob', 7], ['alice', 5]], 0, [['bob', 7]]]
Explanation: Bob's first grant is limited by the organization cap, Bob's refund is also capped, and Alice's remaining expiring credits disappear at time 5.
Hints
- You need two different orderings at once: earliest expiration for consuming/expiring lots, and largest current balance for `topK`. Heaps plus hash maps are a strong fit.
- For `topK`, avoid updating heap entries in place. Push new balance entries and skip stale ones later with lazy deletion.