Google 高频随机题

一道随机题: https://leetcode.com/discuss/interview-question/557982/Bingo-Card
非常高频
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

Follow up: create k different bingo cards. Bingo card 1 and bingo card 2 are different if each row of bingo card 1 is different than that of bingo card2.

Any algorihtm better than rejection sampling?
请教对于follow up有没有好的思路?


补充内容 (2021-08-11 16:47 +08:00):
我想问的是 follow up，谢谢了！

题目都看不懂。。。

1988deandean 发表于 2021-8-23 03:23
用 1到 15^5中的数字表示bingoBoard的row是好方法

我觉得用15^5代表row是个很好的办法, 如果和naive hashmap rejection对比,可以节约空间, 但这本质上还是一种rejection. 是否使用hashmap去reject这depends需要的board 数目多不多, 因为数量大了的话collision很多需要, 产生一个新的board很难, 总共有15*14*13*12*11个board, 那么如果你要用这个方法产生所有的board几乎是不可行的, 考虑到collision的情况.

同时我觉得那位层主忽略了一个点,也可能是我没看懂, 就是当你产生一个随机数‘0001 0001 0001 0001 0001’ 其实这个得判断这个数字是不能用的, 因为这会产生5个一样的数在一个row, 而这是不符合要求的.

我实现了那位层主的代码, 发现在数字小时, 这个代码很快, 但数字大了就很慢了因为有collision

1. def unique_number(num):
   
2.     b_num = bin(num)[2:]
   
3.     b_num = '0'*(20-len(b_num))+b_num
   
4.     num_set = set([b_num[i*4:i*4+4] for i in range(5)])
   
5.     if len(num_set) < 5 or '0000' in num_set:
   
6.         return False
   
7.     return True
   
8. def bitmask_to_row(num, start):
   
9.     b_num = bin(num)[2:]
   
10.     b_num = '0'*(20-len(b_num)) + b_num
    
11.    
    
12.     return [int(b_num[i*4:i*4+4],2) + start for i in range(5)]
    
13.         
    
14. def bingo_board_followup(N):
    
15.     # when it requires each row to be different
    
16.     # 16**5
    
17.     row_used = [set() for _ in range(5)]
    
18.     res = []
    
19.     for _ in range(N):
    
20.         for row_idx in range(5):
    
21.             while True:
    
22.                 rand_num = randint(2**16, 16**5)
    
23.                 if rand_num not in row_used[row_idx] and unique_number(rand_num):
    
24.                     row_used[row_idx].add(rand_num)
    
25.                     res.append(bitmask_to_row(rand_num, 15*row_idx))
    
26.                     break
    
27.     return res
    
28.                     
    
29.    
    
30. bingo_board_followup(100000)

复制代码

4xi 发表于 2021-8-11 19:17
当然可以这么做，generate这个list，然后shuffle，从前往后挨个取就是了，每个都是随机不一样的。这个值 ...

您好! 我之前想表达的是有一个情况我没理解, 就是当你产生一个随机数‘0001 0001 0001 0001 0001’ 其实这个得判断这个数字是不能用的, 因为这会产生5个一样的数在一个row, 而这是不符合要求的.
然后我代码实现在下面了, unique_number 这个函数就是判断上面这个情况, 可能能把我想说的解释得更清楚? 另外rejection的话还是会有collision的问题, 在N>100000时这不是一个好方法(在我看来), 我之前的解法在时间上会更好, 但是空间上会更差

1. def unique_number(num):
   
2.     b_num = bin(num)[2:]
   
3.     b_num = '0'*(20-len(b_num))+b_num
   
4.     num_set = set([b_num[i*4:i*4+4] for i in range(5)])
   
5.     if len(num_set) < 5 or '0000' in num_set:
   
6.         return False
   
7.     return True
   
8. def bitmask_to_row(num, start):
   
9.     b_num = bin(num)[2:]
   
10.     b_num = '0'*(20-len(b_num)) + b_num
    
11.    
    
12.     return [int(b_num[i*4:i*4+4],2) + start for i in range(5)]
    
13.         
    
14. def bingo_board_followup(N):
    
15.     # when it requires each row to be different
    
16.     # 16**5
    
17.     row_used = [set() for _ in range(5)]
    
18.     res = []
    
19.     for _ in range(N):
    
20.         for row_idx in range(5):
    
21.             while True:
    
22.                 rand_num = randint(2**16, 16**5)
    
23.                 if rand_num not in row_used[row_idx] and unique_number(rand_num):
    
24.                     row_used[row_idx].add(rand_num)
    
25.                     res.append(bitmask_to_row(rand_num, 15*row_idx))
    
26.                     break
    
27.     return res
    
28.                     
    
29.    
    
30. bingo_board_followup(100000)

复制代码

RuiJIN 发表于 2021-8-11 00:09
题目都看不懂。。。

这个其实是很高频的google 题. 可以参考这个的第三题如果没看懂: https://www.1point3acres.com/bbs/thread-773887-1-1.html

kikiisme0201 发表于 2021-8-11 00:19
这个其实是很高频的google 题. 可以参考这个的第三题如果没看懂: https://www.1point3acres.com/bbs/thre ...

非常感谢！超级有帮助

RuiJIN 发表于 2021-08-10 21:55:26
非常感谢！超级有帮助

不客气，请问对followup有什么想法吗

除开中间那个空数据，这就相当于生成5个5位15进制的随机数， 为了保证不一样，就把原来生成过的随机数用哈希表存起来就好了。如果是各自按行对比，那就用5个哈希表各比各的。

具体怎么用哈希表存呢就是假设值域是1到m（m是5位15进制数最大值） 第一次从1到m随机r， 表中加入key=r， v=m，逻辑上相当于把m，r换位。 第二次随机从1到m-1 ，得p，去表中找p是否存在，如果否，表中加入key=p v=m-1， 输出p， 如果存在，则输出表中对应的存储值，把值替换为m-1

4xi 发表于 2021-08-10 22:10:22
除开中间那个空数据，这就相当于生成5个5位15进制的随机数， 为了保证不一样，就把原来生成过的随机数用哈希表存起来就好了。如果是各自按行对比，那就用5个哈希表各比各的。

具体怎么用哈希表存呢就是假设

感谢回复，我不懂的是followup。在需要制造出来N个boards时，naive solution不够好

kikiisme0201 发表于 2021-08-11 01:47:03
感谢回复，我不懂的是followup。在需要制造出来N个boards时，naive solution不够好

我说的就是follow

kikiisme0201 发表于 2021-08-11 01:47:03
感谢回复，我不懂的是followup。在需要制造出来N个boards时，naive solution不够好

我说的就是follow up的思路，既然比的是行是否相同，那么问题简化为如何生成一行， 把生成一行抽象成为生成一个5位15进制的随机数， 等同于生成一个一个1到15的5次方之间的随机数。 并且这个随机数不能和之前生成过的重复。

4xi 发表于 2021-8-11 10:23
我说的就是follow up的思路，既然比的是行是否相同，那么问题简化为如何生成一行， 把生成一行抽象成为生 ...

这样子生成的数会存在两个位置上的数字相同? 比如 可能出现 1,1,1,1,1  = 31 的情况? 如果你说的这个思路可以的话, 那么第一问(非followup)其实也可以这么做, 但他就是要求不能有重复的?