Meta 电话面试经验总结

刚刚结束了 Meta 的电话面试，想趁热把过程和心得记录下来。面试中我遇到了两道算法题，一道是有关 加权随机选择城市 的问题，另一道是 字符串缩写匹配 的问题。下面分别介绍这两题的题目要求、我的解题思路和代码实现，最后也分享一些个人的面试准备建议。

第一题：按人口比例随机选择城市

🥉 题目描述

给定一个字典（HashMap），其中 key 是城市名称，value 是该城市的人口数。实现一个函数 pickCity()，能够根据各城市人口的比例随机返回一个城市名称。

示例：

{"A市": 10000, "B市": 30000, "C市": 60000}

总人口 10 万，函数应该保证：

• A市 概率约10%
• B市 概率约30%
• C市 概率约60%

解题思路

本质上是 加权随机选择 问题：

1. 前缀和数组：

   • 先算出总人口 total_population，
   • 再构造前缀和数组 prefix_sums，其中每个元素是“前缀人口累计值”

2. 随机数取样：

   • 随机生成 [1, total_population] 之间的整数 r

3. 二分查找：

   • 用二分查找在 prefix_sums 中查找 r 所属的区间，返回对应的城市

处理效率：

• 初始化时间复杂度 O(n)
• 随机选择时间复杂度 O(log n)

代码实现

import random

city_populations = {"A市": 10000, "B市": 30000, "C市": 60000}

# 构造前缀和数组
total_population = sum(city_populations.values())
prefix_sums = []
running_sum = 0
for city, pop in city_populations.items():
    running_sum += pop
    prefix_sums.append((running_sum, city))

def pickCity():
    r = random.randint(1, total_population)
    lo, hi = 0, len(prefix_sums) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if prefix_sums[mid][0] < r:
            lo = mid + 1
        else:
            hi = mid
    return prefix_sums[lo][1]

# 測试
print(pickCity())

第二题：字符串缩写匹配

题目描述

给定一完整单词 word，和其一个缩写形式 abbr（包含字母和数字），判断是否匹配。

示例：

• "internationalization" vs "i12iz4n" → True
• "apple" vs "a3e" → True
• "apple" vs "a2e" → False

解题思路

用双指针模型：

1. 开始 i = j = 0

2. 遍历 abbr：

   • 如果是字母，判断 word[i] == abbr[j]
   • 如果是数字，积累解析整数 num，然后 i += num
   • 前缀 0 是非法格式，要判 False

3. 遍历完后，如果 i == len(word) 并且 j == len(abbr)，则匹配成功

代码实现

def valid_word_abbr(word, abbr):
    i = j = 0
    while i < len(word) and j < len(abbr):
        if abbr[j].isdigit():
            if abbr[j] == '0':
                return False
            num = 0
            while j < len(abbr) and abbr[j].isdigit():
                num = num * 10 + int(abbr[j])
                j += 1
            i += num
        else:
            if i >= len(word) or word[i] != abbr[j]:
                return False
            i += 1
            j += 1
    return i == len(word) and j == len(abbr)

# 測试
print(valid_word_abbr("internationalization", "i12iz4n"))  # True
print(valid_word_abbr("apple", "a3e"))  # True
print(valid_word_abbr("apple", "a2e"))  # False

面试准备建议

• 熟悉算法模板：如前缀和 + 二分查找，是解决加权随机选择的标准方案
• 字符串解析技巧：解析数字、处理前缀零、字母匹配，该练的需要进一步精细
• 边界值无法进位：如查看 i 是否超级 word 长度
• 同步说明复杂度：如 O(n)，O(log n)，澄清表述背后的实现界限和效率
• 保持准备心态：遇到不会时先分析类型，大拟类似题，然后加以解释

希望我的经验对你有所帮助，预祝 offer 🌟！