Define and Prove Data Structure | Dataford Interview Questions

Explain a data structure you designed and how you proved its correctness, including what each function should do.

Implement a dynamic half-open interval structure through process_operations(operations). Each operation is ['add', start, end], ['remove', start, end], ['max_overlap'], or ['covered_length']. Return query results in order. Intervals use [start, end), and removals are guaranteed to match an existing interval. Explain the invariants that establish correctness for every public operation.

Constraints

1 <= len(operations) <= 5000
Each interval satisfies start < end
Coordinates are integers in [-10^9, 10^9]
Remove operations are guaranteed to match an active interval
At least one add or remove operation is present
Query results must be returned in their original order

Function Signature

def process_operations(operations):

Your question is Define and Prove Data Structure. 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

Explain a data structure you designed and how you proved its correctness, including what each function should do.

Constraints

1 <= len(operations) <= 5000
Each interval satisfies start < end
Coordinates are integers in [-10^9, 10^9]
Remove operations are guaranteed to match an active interval
At least one add or remove operation is present
Query results must be returned in their original order

Function Signature

def process_operations(operations):

Your question is Define and Prove Data Structure. 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.