Meta VO 面试真题解析：随机返回最大元素索引 / 最频繁的 3 页面序列

Given an array of integers, return the index of one of the largest elements, chosen uniformly at random.

Example:

index:  0 1 2 3 4 5 6
array: [5, 3, 6, 6, 0, 2, 6]
should return 2, 3, or 6, each with probability 1/3

You are given a list of web pages, with each edge indicating a transition from the prior page to the next page. We want the most frequent sequence of 3 pages.

Example:

input: [A, B, A, B, A, C, B, A]
seqs: ABA, BAB, ABA, BAC, ACB, CBA
A => youtube.com
B => google.com
C => facebook.com

We would want ABA since that sequence occurs twice.

这道题考察的是对“最大值下标随机等概率返回”和“网页访问中最频繁的 3 页面序列”两类经典面试题的理解。前者通常用一次遍历完成：先找出最大值，再统计所有最大值出现的位置，最后从这些位置中均匀随机选一个返回；关键是保证每个最大元素被选中的概率相同。后者本质上是长度为 3 的滑动窗口统计问题：把页面访问序列中连续 3 个页面组成一个 pattern，用哈希表记录每个序列出现次数，最后返回出现次数最多的序列。若题目要求从图或有向边中恢复页面访问顺序，则通常需要先按输入顺序构造访问流，再对连续三元组做计数。