Batch Commit Function Implementation | Dataford Interview Questions

Figma multiplayer edits may depend on earlier edits, such as creating a frame before adding a child layer. Implement commit_batch to divide edits into ordered commit batches while ensuring every edit is committed strictly after all of its dependencies.

Each batch may contain at most max_batch_size edits. Among edits that are currently eligible, preserve their original input order. Edits that become eligible while constructing a batch must wait until the next batch. Assume the dependency graph is valid and acyclic.

Formal Specification

Given a list operations, where each operation is a dictionary with:

id: a unique string identifying the edit
depends_on: a list of operation IDs that must be committed earlier

Return a list of batches. Each batch is a list of operation IDs. Every dependency must appear in an earlier batch, and no batch may exceed max_batch_size.

Constraints

1 <= len(operations) <= 10^5
1 <= max_batch_size <= 10^4
Operation IDs are unique strings.
Every dependency refers to an operation in operations.
The dependency graph is acyclic.

Function Signature

def commit_batch(operations, max_batch_size):

Your question is Batch Commit Function Implementation. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem