SSTable Index Lookup

Problem

Find the data offset for a key using an SSTable sparse index.

index_keys is the sorted list of index keys and index_offsets holds the matching data offsets. Return the offset of the largest index key less than or equal to the target, because that block may contain the key.

Return the offset, or -1 when the key sorts before the first index key.

Hint

Scanning stops at the first index key greater than the target.

Test cases

case 1

in: [[10,20,30],[100,200,300],25]

expected: 200

case 2

in: [[10,20],[5,6],5]

expected: -1

case 3

in: [[],[0],7]

expected: -1

case 4

in: [[5],[7],9]

expected: 7

Starter codePython

def sstable_lookup(index_keys, index_offsets, key):
    # Your code here
    pass

4 test cases · run your code against them in the editor