[Leetcode] Randomization

Posted on | In , |

Reservoir Sampling

Video: https://www.youtube.com/watch?v=8Xj0ODE9mW0&ab_channel=TryandCatchJeeves

Given a stream of size N which is too large to fit into memory, randomly select K elements such that each element has an equal probability of being chosen.

1
2
3
4
5
6
7
8
9
10
11
import random

def reservoir_sampling(stream: list, k: int):
    reservoir = []
    for i, value in stream:
        if i < k:
            reservoir.append(value)
        random_index = random.randint(0, i)
        if random_index < k:
            reservoir[random_index] = value
    return reservoir

382. Linked List Random Node

Leetcode: https://leetcode.com/problems/linked-list-random-node/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def __init__(self, head: Optional[ListNode]):
        self.head = head

    def getRandom(self) -> int:
        cur = self.head
        scope = 1
        chosen_val = 0
        while cur:
            if random.random() < 1 / scope:
                chosen_val = cur.val
            cur = cur.next
            scope += 1
        return chosen_val

random number

给一个袋子有1-75号球，给一个random函数能返回指定范围的整数。目的是要求写一个函数模拟随机从袋子里取N个小球。

1
2
3
4
5
6
7
8
9
10
11
12
import random

def getRandomBall(n):
    reservoir = []
    for i in range(75):
        value = i + 1
        if i < n:
            reservoir.append(i)
        random_index = random.randint(0, i)
        if random_index < n:
            reservoir[random_index] = value
    return reservoir

Fisher-shuffle

Video: https://www.youtube.com/watch?v=tLxBwSL3lPQ&ab_channel=AdamKhoury

Bingo card

https://leetcode.com/discuss/interview-question/343683/Google-or-Phone-screen-or-Bingo-Card

感觉reserivor sample 或者 fisher’s shuffle都行，后面一种应该稍微好一些（第一种要15+15的复杂度，第二种15+5，因为reserivor的主要优势在于对总数未知的取样）
follow up对每行hash一下（自己编码或者用tuple感觉都行），如果重复就重新生成。复杂度的话因为不知道要生成几张，可能要考虑random collision。想了一会儿，好像没想到啥直接生成的多张卡片 避免collision的方法

Given a 5x5 grid, create a bingo card with the folliwing condtions.
-the middle square in the middle column must have a free space
-it must generate random numbers per column as follows below:
-col1 1-15
-col2 16-30
-col3 31-45
-col4 46-60
-col5 61-75

so essentially

2 17 37 49 62
5 22 41 52 70
6 23 U 59 68
9 18 42 60 69
8 29 40 55 63

Followup: Generate n different Bingo Cards. Bingo Card 1 is different than Bingo Card 2 if every row in Bingo Card 1 is different than every row in Bingo Card 2.

Random assign board cells

题目 ： 88 的board，四个player，randomly and evenly assign cells to players。就每个人给16个格子。
Follow up： 8 8 的board， randomly and evenly assign cells to players。就每个人给16个格子， 但每个人的cells 必须连续。就是一副四色块的图.

1
2
def assignBoard():
    board = [[i % 4 for i in range(8)] for _ in range(8)]