Given a dictionary of English words, preprocess it in a setup phase so future lookups can be very efficient.
Given 9 letters, where each occurrence can be used at most once and duplicate letters are allowed, find the longest dictionary word that can be formed from those letters.

简单来说，就是先给你一个英文词典，可以提前进行预处理。之后每次给 9 个字母，需要快速找到能够由这些字母组成的最长单词。每个字母只能使用一次，同时输入里允许出现重复字母。

这道题现场比较值得注意的其实是 “preprocess” 和 “future lookups can be very efficient” 这两个信息。

如果只是每次拿着 9 个字母去遍历整个 dictionary，当然也可以完成基本功能，但明显没有充分利用题目允许提前 preprocessing 这一条件。

比较自然的方向，是提前把 dictionary 按照字母组成建立索引。比如可以把单词转换成排序后的字符形式，或者使用 26 个字母的 frequency representation 作为 signature。

而查询端只有 9 个字母，这是另一个很关键的信息。

9 个位置对应的组合规模其实非常有限，最多也只有：

2^9 = 512

因此完全可以利用这个固定的小规模输入，把查询转化成少量 signature lookup，而不是每次重新扫描整个词典。

实际面试过程中，这类题真正容易拉开差距的地方，通常也不是“会不会写 HashMap”，而是能不能很快意识到：

Dictionary 很大，但 query 只有 9 个字符。

一旦抓住这个不对称性，后面的数据结构设计就会自然很多。

同时还有一个容易被忽略的小细节：题目明确说 duplicate letters are allowed。所以不能简单把字母理解成一个普通集合，例如两个 a 和一个 a 是不同的，需要保留字母出现次数。这也是现场 coding 和解释方案时比较容易被追问的地方。

这道题是我们近期在实际 Google 面试辅助场景中遇到的题型之一。相比单纯刷题，我们在实时辅助里更关注的是候选人现场会遇到的情况：面试官突然追问 preprocessing、complexity、edge case，或者在原题基础上继续改变 constraint。

csoahelp 目前提供 Google 等科技公司的实时文本面试辅助和 Mock Interview。

我们希望做的不是在面试前给候选人堆很多模板，而是在真实面试节奏里，帮助快速识别题目考点、整理方案，并应对面试官接下来的 follow-up。

如果近期有 Google Coding Interview，也可以联系我们了解相关的面试辅助服务。

我们也有代面试，面试辅助，OA代写等服务助您早日上岸~