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

Log in to reply

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