B-tree leaf insert and range
Maintain an ordered index under interleaved inserts and range queries (the operation log a B-tree leaf level would see). You are given a list of ops. Each op is either ['insert', key, value] (key is a unique int, inserting a key that already exists overwrites its value) or ['range', lo, hi] which returns the list of [key, value] pairs currently in the index with lo <= key <= hi, sorted ascending by key. Process ops in order and return the list of results, one list per 'range' op (inserts produce no output).
Implement
ordered_index_ops(ops: list[list]) → list[list]Examples
in
[[["insert",5,"e"],["insert",2,"b"],["insert",8,"h"],["range",2,5]]]out[[[2,"b"],[5,"e"]]]What a strong answer looks like
State your approach and its time/space complexity out loud before you optimize. Handle the edge cases (empty input, duplicates, overflow), and say why you chose this over the brute force. Green tests are the floor, not the grade.
0:00 of about 35 min
solution.py
InputExpectedGot
[[["insert",5,"e"],["insert",2,"b"],["insert",8,"h"],["range",2,5]]][[[2,"b"],[5,"e"]]]not run yetsample