Skip List Insert Levels

Problem

Generate skip-list node levels: seed the random module with seed, then for each of n nodes start at level 1 and increment while random.random() < p. Return [levels, max_level] where levels is the generated list and max_level is 0 for no nodes. Assume 0 < p < 1.

Hint

random.seed at the start makes the promotion coin flips reproducible for a given seed.

Test cases

case 1

in: [5,0.5,1]

expected: [[2,1,4,1,3],4]

case 2

in: [8,0.25,42]

expected: [[1,2,2,1,1,2,3,3],3]

case 3

in: [0,0.5,7]

expected: [[],0]

case 4

in: [10,0.9,3]

expected: [[11,21,4,5,9,2,2,4,1,9],21]

Starter codePython

def skip_list_levels(n, p, seed):
    # Your code here
    pass

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