Skip List Expected Pointers

Problem

In a skip list each node is promoted to the next level with probability p, so the number of levels (pointers) per node is geometric with mean 1 / (1 - p). Return [expected_levels_per_node, expected_total_pointers] for n nodes as floats. Assume 0 < p < 1.

Hint

The expected value of a geometric distribution with success probability 1 - p is 1 / (1 - p).

Test cases

case 1

in: [100,0.5]

expected: [2,200]

case 2

in: [10,0.25]

expected: [1.3333333333333333,13.333333333333332]

case 3

in: [0,0.5]

expected: [2,0]

case 4

in: [1000,0.1]

expected: [1.1111111111111112,1111.111111111111]

Starter codePython

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

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