O(1) List Pop | Dataford Interview Questions

O(1) List Pop

EasyPython

Problem

Bloomberg Law may maintain in-memory work queues where processing order is unimportant. Implement a function that removes and returns the item at a specified index in O(1) time.

Because shifting elements would require linear time, preserve the complexity requirement by replacing the removed item with the final list element, then removing the final slot. This operation does not preserve the original order of the remaining items.

Formal Specification

Implement pop_constant_time(items, index):

items is a non-empty Python list of values.
index is a valid integer index from 0 through len(items) - 1.
Mutate items in place.
Return the value originally stored at items[index].
The order of the remaining values may change.
The operation must run in O(1) time and use O(1) additional space.

Constraints

1 <= len(items) <= 10^5
0 <= index < len(items)
Values may be any Python object
The order of remaining items may change

Function Signature

def pop_constant_time(items, index):

Bloomberg Law may maintain in-memory work queues where processing order is unimportant. Implement a function that removes and returns the item at a specified index in O(1) time.

Formal Specification

Implement pop_constant_time(items, index):

items is a non-empty Python list of values.
index is a valid integer index from 0 through len(items) - 1.
Mutate items in place.
Return the value originally stored at items[index].
The order of the remaining values may change.
The operation must run in O(1) time and use O(1) additional space.