Constant-Time Insert/Delete Data Structure | Dataford Interview Questions

Implement a list-based data structure that performs inserts and deletes in constant time.

Use an array and an auxiliary map from each value to its current index. The structure stores unique values. insert receives a value that is not present, and delete receives a value that is present. Deletion may change the order of remaining values.

Input and Output

Implement execute_operations(operations). Each operation is ["insert", value] or ["delete", value]. Return the final list in its current order after all operations.

Constraints

1 <= operations.length <= 100000
Each operation is a two-element list: ["insert", value] or ["delete", value]
Values are distinct among currently stored elements
Every inserted value is absent before insertion
Every deleted value is present before deletion
Values are hashable integers

Function Signature

def execute_operations(operations):

Your question is Constant-Time Insert/Delete 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