Count-Min Dimension Guarantee

Problem

Choose Count-Min sketch dimensions that guarantee additive error at most epsilon with probability at least 1 - delta.

Width = ceil(e / epsilon) and depth = ceil(ln(1 / delta)) satisfy the standard bound, where e is Euler's number. Return [width, depth], or [0, 0] when epsilon is non-positive or delta lies outside the open interval (0, 1).

Hint

Invert the two Chernoff-style requirements: width controls error size, depth controls failure odds.

Test cases

case 1

in: [0.01,0.01]

expected: [272,5]

case 2

in: [0.1,0.05]

expected: [28,3]

case 3

in: [1,0.5]

expected: [3,1]

case 4

in: [0,0.5]

expected: [0,0]

case 5

in: [0.5,1]

expected: [0,0]

Starter codePython

import math


def cms_dimensions(epsilon, delta):
    # Your code here
    pass

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