最近，我的兩位朋友參加了 Meta 倫敦辦事處的軟件工程師面試。他們都覺得自己準(zhǔn)備得很充分 -- 用 coding 技術(shù)武裝了自己...

最近，我的兩位朋友參加了 Meta 倫敦辦事處的軟件工程師面試。他們都覺得自己準(zhǔn)備充分 -- 掌握了編碼算法和系統(tǒng)設(shè)計(jì)知識。但出乎意料的是，他們都遇到了一個難題 -- 一個概率問題讓他們百思不得其解。我被他們的經(jīng)歷所吸引，于是進(jìn)入了與 Meta 相關(guān)的 LeetCode 討論，結(jié)果發(fā)現(xiàn)一個不可否認(rèn)的趨勢：許多應(yīng)聘者都遇到了類似的概率問題。事實(shí)上，一位用戶甚至表示："Meta 幾乎總是會拋出概率問題！"

那么，為什么概率問題會成為 Meta 面試過程中的主要問題？更重要的是，如何掌握這些問題才能脫穎而出？讓我們深入探討一些關(guān)鍵的概率問題，以及自信應(yīng)對這些問題的策略

輸入數(shù)組 = [1,2,3,4,5] 函數(shù)應(yīng)根據(jù)概率從輸入數(shù)組中返回一個數(shù)字，這意味著如果我調(diào)用函數(shù) 5-6 次，它應(yīng)至少返回每個元素一次。

方法 1：使用隨機(jī)函數(shù)

input_array = [1,2,3,4,5]
def get_random_item():
    return random.choice(input_array)

由于顯而易見的原因，這將是不可接受的，因?yàn)樗麄兿胗盟鼇韺?shí)現(xiàn)隨機(jī)邏輯

方法 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 范圍內(nèi)。然后我們在該索引處取值。雖然該函數(shù)不會返回隨機(jī)數(shù)，但會根據(jù)項(xiàng)目概率返回。每個項(xiàng)目被選中的概率為 1/n。

方法 3：使用時間戳

為了獲取隨機(jī)數(shù)，我們可以獲取毫秒級或納秒級的當(dāng)前時間戳，然后與 array_size 進(jìn)行模乘，以獲取數(shù)組索引。

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]

由于當(dāng)前時間戳每次都不同，我們無法在毫秒級別上對其進(jìn)行預(yù)測。我們可以將其視為一個隨機(jī)數(shù)。用 array_size 進(jìn)行調(diào)制，會得到一個介于 0-array_size 之間的數(shù)字，可以用來從數(shù)組中選取項(xiàng)目。

時間復(fù)雜性：所有 3 種方法的運(yùn)行時間均為 O(1)。

例如，輸入 {Math：2, History：1, Science：數(shù)學(xué)被選中的概率為 2/6，歷史被選中的概率為 1/6，科學(xué)被選中的概率為 3/6。

該函數(shù)應(yīng)返回學(xué)生人數(shù)越多的科目越有可能被選中。

方法 1

要解決這個問題，方法是準(zhǔn)備一個數(shù)組，其中每個科目的計(jì)數(shù)等于選擇該科目的學(xué)生人數(shù)。通過從數(shù)組中隨機(jī)抽取一個元素，計(jì)數(shù)越高的科目被選中的概率自然越大。

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]
"""

當(dāng)我們從這個數(shù)組中隨機(jī)抽取一個項(xiàng)目時，與重復(fù)次數(shù)較少的項(xiàng)目（如 "歷史"）相比，重復(fù)次數(shù)較多的項(xiàng)目（如 "科學(xué)"）被抽中的幾率更高。

時間復(fù)雜性空間復(fù)雜度：O(n)O(n)，其中 "n" 為數(shù)組（非輸入映射）的大小

由于我們準(zhǔn)備的是一個包含 N 個元素的列表，因此時間復(fù)雜度將變?yōu)?O(N)

方法 2

與其創(chuàng)建一個大型數(shù)組，我們可以采用累積求和的方法來優(yōu)化選擇過程。具體操作如下

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 和學(xué)生總數(shù)之間的隨機(jī)數(shù)。然后，我們檢查該隨機(jī)數(shù)在各學(xué)科學(xué)生人數(shù)累計(jì)總和中的位置。

例如，讓我們考慮一下

• 數(shù)學(xué)有 2 名學(xué)生
• 歷史有 1 名學(xué)生
• 理科有 3 名學(xué)生

總計(jì)數(shù)為 2 + 1 + 3 = 6。然后，我們生成一個介于 0 和 5 之間的隨機(jī)數(shù)（因?yàn)榭倲?shù)是 6）：

• 如果數(shù)字小于 2，我們就選數(shù)學(xué)。
• 如果數(shù)字是 2，我們就選擇歷史。
• 如果數(shù)字大于或等于 3，我們就選科學(xué)。

這樣，選中每個科目的概率與其學(xué)生人數(shù)成正比。例如，數(shù)字 4、5 和 6 的概率各為 1/6，由于所有數(shù)字都會導(dǎo)致選擇科學(xué)，因此科學(xué)被選中的概率為 3/6（或 50%）。

時間復(fù)雜性 O(n)，空間復(fù)雜性：O(n)，其中 "n" 為主題數(shù)

方法 3

在方法 2 中，我們可以不使用線性搜索，而是使用二進(jìn)制搜索來獲取 item_index 變量中較大元素的索引。

如 item_index 為 0 或 1，則較大元素為 2；如 item_index 為 4 或 5，則較大元素為 6。

這樣，時間復(fù)雜度將降低到 Log(n)

時間復(fù)雜性 O(Log n)，空間復(fù)雜性：O(n)，其中 "n" 為主題數(shù)