美團 2014 校招筆試真題深度解析（長沙站+哈爾濱站）

前言

整理自網絡流傳的美團 2014 校招筆試題，涵蓋概率、鏈表、智力邏輯、組合數學、Catalan 數、測試理論、棧隊列轉換、動態規劃、數論等經典考點。答案經驗證，歡迎指正補充。

題目一：硬幣翻轉概率（哈爾濱站）

一堆硬幣，機器人無限次操作：反面→翻正面；正面→拋擲一次。求穩態下正反面比例。

解析

設穩態正面朝上概率為 x，反面 1-x。一次操作後：

• 原反面（1-x）全變正面；
• 原正面（x）拋擲，一半正面（0.5x），一半反面（0.5x）。

新正面概率 = (1-x) + 0.5x = 1 - 0.5x。穩態要求不變：

x = 1 - 0.5x → 1.5x = 1 → x = 2/3

答案：正反面比例 = 2:1

題目二：K 個一組翻轉鏈表

給定鏈表 1→2→3→4→5→6，k=2 翻轉為 2→1→4→3→6→5；k=3 為 3→2→1→6→5→4；k=4 為 4→3→2→1→5→6。實現算法。

核心思路

1. 先翻轉前 k 個節點；
2. 遞歸/迭代處理剩餘部分，每 k 組翻轉一次；
3. 不足 k 組保持原序。

關鍵代碼（C++）

// 翻轉 [head, end] 閉區間 
void ReverseLinkList(Node* head, Node* end) { 
    Node *pre = nullptr, *cur = head, *stop = end->next; 
    while (cur != stop) { 
        Node* nxt = cur->next; 
        cur->next = pre; 
        pre = cur; 
        cur = nxt; 
    } 
} 

Node* ReverseKLinkList(Node* head, int k) { 
    if (!head || k <= 0) return nullptr; 
    Node* cur = head; 
    for (int i = 0; i < k-1; ++i) { 
        if (!(cur = cur->next)) return head; // 不足 k 個直接返回 
    } 
    Node* newHead = cur; 
    Node* nextGroup = cur->next; 
    ReverseLinkList(head, cur); 
    head->next = ReverseKLinkList(nextGroup, k); 
    return newHead; 
}

題目三：夜間過橋問題（長沙站）

A(1分)、B(2分)、C(5分)、D(10分) 過橋，一盞燈，最多兩人同行，速度按慢者算。最短總耗時？

最優策略

1. A、B 過橋（2），A 回（1） → 3
2. C、D 過橋（10），B 回（2） → 12
3. A、B 過橋（2） → 2

總耗時 17 分鐘。關鍵：讓最慢的兩人（C、D）一起過，避免他們各自拖慢節奏。

題目四：25 匹馬找最快前三（長沙站）

5 條跑道，每場 5 匹馬，無計時器。最少幾場定出前三？

7 場方案

1. 分 5 組賽（A1~A5 ... E1~E5） → 5 場
2. 各組第一名決賽（A1 B1 C1 D1 E1） → 第 6 場，假設 A1 > B1 > C1 > D1 > E1
3. 淘汰邏輯：D1、E1 組全軍覆沒；C1 組除 C1 外淘汰；B1 組除 B1、B2 外淘汰；A1 組除 A1 外，A2、A3 仍有爭奪資格。
4. 候選馬：A2, A3, B1, B2, C1 → 第 7 場決出前二，與 A1 組成前三。

題目五：找零概率與 Catalan 數（長沙站）

2N 人買 5 元票，N 人持 5 元，N 人持 10 元，售票處無零錢。求無人等待找零的概率。

模型轉化

持 5 元記為 1，持 10 元記為 0。合法序列條件：任意前綴中 1 的個數 ≥ 0 的個數。

組合計數

• 總排列數：C(2N, N)
• 非法排列數：存在首個位置 k 使 0 比 1 多 1。將 k 後 0/1 互換，得到 n+1 個 0、n-1 個 1 的序列，數量 C(2N, N+1)。

合法概率 = (C(2N,N) - C(2N,N+1)) / C(2N,N) = 1/(N+1)（即第 N 個 Catalan 數 / 總排列）。

題目六：黑盒測試 int f(int n) 恒返回 0？

無額外信息下，僅能：

• 全域遍歷 INT_MIN ~ INT_MAX（不可行）；
• 隨機抽樣 + 邊界值（0, ±1, INT_MIN, INT_MAX）；
• 若知函數性質（如純函數、單調），可構造等價類測試。

開放題，考察測試思維。

題目七：雙棧實現隊列（長沙站）

經典結構

• s1 專職入隊（push）
• s2 專職出隊（pop）

操作邏輯

• add(x)：s1.push(x)
• remove()：若 s2 空，將 s1 全部彈出壓入 s2（順序反轉），再 s2.pop()；否則直接 s2.pop()。

C++ 實現

template <class T> 
struct MyQueue { 
    void add(const T& t) { s1.push(t); } 
    T front() { 
        if (s2.empty()) { 
            if (s1.empty()) throw; 
            while (!s1.empty()) { s2.push(s1.top()); s1.pop(); } 
        } 
        return s2.top(); 
    } 
    void remove() { 
        if (s2.empty()) { 
            while (!s1.empty()) { s2.push(s1.top()); s1.pop(); } 
        } 
        if (!s2.empty()) s2.pop(); 
    } 
    stack<T> s1, s2; 
};

題目八：最長公共子串長度（長沙站）

S1=GCCCTAGCCAGDE, S2=GCGCCAGTGDE，最長公共子串 GCCAG，長度 5。

動態規劃

dp[i][j] 表示以 S1[i]、S2[j] 結尾的公共子串長度：

if (S1[i] == S2[j]) 
    dp[i][j] = (i&&j) ? dp[i-1][j-1] + 1 : 1; 
else 
    dp[i][j] = 0; 
maxLen = max(maxLen, dp[i][j]);

時間/空間 O(n*m)，空間可優化至 O(min(n,m))。

題目九：100 盞燈開關問題（哈爾濱站）

100 盞燈初始關閉。第 i 輪翻轉 i 的倍數編號燈。最終亮著的燈？

數學本質

燈 k 被翻轉次數 = k 的約數個數。只有完全平方數約數個數為奇數（因平方根單獨出現）。

1~100 間完全平方數：1, 4, 9, 16, 25, 36, 49, 64, 81, 100。

結語

這套題目覆蓋了校招高頻考點：概率建模、鏈表指針操作、貪心策略、組合數學、Catalan 數、測試理論、數據結構轉換、動態規劃、數論規律。建議逐題複盤，舉一反三。本文出自「驿落黃昏」博客：原文鏈接