最近，我的两位朋友参加了 Meta 伦敦办事处的软件工程师面试。他们都觉得自己准备得很充分 -- 用 coding 技术武装了自己...
最近，我的两位朋友参加了 Meta 伦敦办事处的软件工程师面试。他们都觉得自己准备充分 -- 掌握了编码算法和系统设计知识。但出乎意料的是，他们都遇到了一个难题 -- 一个概率问题让他们百思不得其解。我被他们的经历所吸引，于是进入了与 Meta 相关的 LeetCode 讨论，结果发现一个不可否认的趋势：许多应聘者都遇到了类似的概率问题。事实上，一位用户甚至表示："Meta 几乎总是会抛出概率问题！"
那么，为什么概率问题会成为 Meta 面试过程中的主要问题？更重要的是，如何掌握这些问题才能脱颖而出？让我们深入探讨一些关键的概率问题，以及自信应对这些问题的策略
输入数组 = [1,2,3,4,5] 函数应根据概率从输入数组中返回一个数字，这意味着如果我调用函数 5-6 次，它应至少返回每个元素一次。
方法 1：使用随机函数
input_array = [1,2,3,4,5]
def get_random_item():
return random.choice(input_array)
由于显而易见的原因，这将是不可接受的，因为他们想用它来实现随机逻辑
方法 2：使用顺序选择
input_array = [1,2,3,4,5]
count = 0
def get_random_item():
count = count + 1
array_size = len(input_array)
return input_array[count % array_size]
在这里，我们每次都会选取下一个元素。我们使用 "mod"，这样得出的值总是在 0-array_size 范围内。然后我们在该索引处取值。虽然该函数不会返回随机数，但会根据项目概率返回。每个项目被选中的概率为 1/n。
方法 3：使用时间戳
为了获取随机数，我们可以获取毫秒级或纳秒级的当前时间戳，然后与 array_size 进行模乘，以获取数组索引。
import time
input_array = [1,2,3,4,5]
def get_random_item():
timestamp = time.time()
array_size = len(input_array)
return input_array[timestamp % array_size]
由于当前时间戳每次都不同，我们无法在毫秒级别上对其进行预测。我们可以将其视为一个随机数。用 array_size 进行调制，会得到一个介于 0-array_size 之间的数字，可以用来从数组中选取项目。
时间复杂性：所有 3 种方法的运行时间均为 O(1)。
例如，输入 {Math：2, History：1, Science：数学被选中的概率为 2/6，历史被选中的概率为 1/6，科学被选中的概率为 3/6。
该函数应返回学生人数越多的科目越有可能被选中。
方法 1
要解决这个问题，方法是准备一个数组，其中每个科目的计数等于选择该科目的学生人数。通过从数组中随机抽取一个元素，计数越高的科目被选中的概率自然越大。
def get_item(subject_count_map):
array = []
for subject, count in subject_count_map:
array.extend([subject]*count)
return get_random_item(array)
"""
Input = {Math: 2, History: 1, Science: 3}
array = [Math, Math, History, Science, Science, Science]
"""
当我们从这个数组中随机抽取一个项目时，与重复次数较少的项目（如 "历史"）相比，重复次数较多的项目（如 "科学"）被抽中的几率更高。
时间复杂性空间复杂度：O(n)O(n)，其中 "n" 为数组（非输入映射）的大小
由于我们准备的是一个包含 N 个元素的列表，因此时间复杂度将变为 O(N)
方法 2
与其创建一个大型数组，我们可以采用累积求和的方法来优化选择过程。具体操作如下
def get_item(subject_count_map):
cummulative_array = []
total_count = 0
for subject, count in subject_count_map:
cummulative_array.append([subject, total_count+count])
total_count = total_count + count
item_index = get_random_number(0, total_count)
for subject, total_count in cummulative_array:
if item_index < total_count:
return subject
return array[-1][0]
"""
Input = {Math: 2, History: 1, Science: 3}
cummulative_array = [[Math, 2], [History, 3], [Science, 6]]
"""
每次，我们都会生成一个介于 0 和学生总数之间的随机数。然后，我们检查该随机数在各学科学生人数累计总和中的位置。
例如，让我们考虑一下
- 数学有 2 名学生
- 历史有 1 名学生
- 理科有 3 名学生
总计数为 2 + 1 + 3 = 6。然后，我们生成一个介于 0 和 5 之间的随机数（因为总数是 6）：
- 如果数字小于 2，我们就选数学。
- 如果数字是 2，我们就选择历史。
- 如果数字大于或等于 3，我们就选科学。
这样，选中每个科目的概率与其学生人数成正比。例如，数字 4、5 和 6 的概率各为 1/6，由于所有数字都会导致选择科学，因此科学被选中的概率为 3/6（或 50%）。
时间复杂性 O(n)，空间复杂性：O(n)，其中 "n" 为主题数
方法 3
在方法 2 中，我们可以不使用线性搜索，而是使用二进制搜索来获取 item_index 变量中较大元素的索引。
如 item_index 为 0 或 1，则较大元素为 2；如 item_index 为 4 或 5，则较大元素为 6。
这样，时间复杂度将降低到 Log(n)
时间复杂性 O(Log n)，空间复杂性：O(n)，其中 "n" 为主题数
