Interview question: randomly generate mines on a grid

  • 0

    You are given a mn grid. You are asked to generate k mines on this grid randomly. Each cell should have equal probability of k / mn of being chosen. Your algorithm should run in O(m) time.

  • 0

    The traditional resevoir sampling does not work due to the time complexity constraint
    def insert(h,w,m):
    position = [None]m
    lut = {}
    for i in range(m):
    pos = randint(0,h
    if pos in lut:
    position[i] = lut[pos]
    position[i] = pos
    lut[pos] = h*w-i-1

  • 0

    Assuming m=1, it can be solved by reservoir sampling with o(n) time but not o(1) time.
    Is the question legitimate?

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.