Interview question: randomly generate mines on a grid


  • 0
    J

    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
    J

    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
    w-i-1)
    if pos in lut:
    position[i] = lut[pos]
    else:
    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.