问一个老题，请帮忙解答多谢了 - JobHunting版

本页内容为未名空间相应帖子的节选和存档，一周内的贴子最多显示50字，超过一周显示500字访问原贴

JobHunting版 - 问一个老题，请帮忙解答多谢了

相关主题
● 一道字典题目	● 分享面试题目
● amazon ONSITE 面试，求BLESS	● 那个 google hint words 的老题
● list of words找两个没有相同字母的string S和T并且使得S.length()*T.length()最大	● 再问一道老题
● 一道二叉树的老题	● 给一个字典，找出字母顺序这题目有点意思
● 问一道老题	● Bloomberg on campus 非CS面经
● 弱问：两个数组的并集和交集	● FB online puzzle请教
● 问一道老题	● 一道很难的游戏题
● 一道老题	● 面试题：写一个猜单词策略

相关话题的讨论汇总
话题: 老题话题: list话题: 解答话题: 单词话题: 帮忙

进入JobHunting版参与讨论

(共1页)

a**x
发帖数: 154

怎么组织字典，使得在解cross puzzle时可以很快得到满足条件的所有单词(比如
所有第二个字母是o，第5个是H的单词）
多谢

g*******y
发帖数: 1930

每个位置的每个字母，对应一个word list。
这样一共有length * 26个list
总的空间消耗是总单词数*average of length
不过，word list里面可以存index of word,减少不少空间。
然后查询的时候就是直接找到若干个list，来做交集。
为了方便做交集，一个word list可以用hash set存。并且每次遍历最短的list开始。
可以想想，因为两个list交集的长度会大大减小，而两个list交集的时间又只决定与两
者中较短一个list的长度。所以性能应该还是不差的。

(共1页)

进入JobHunting版参与讨论

相关主题
● 面试题：写一个猜单词策略	● 问一道老题
● 一道amazon面试题	● 弱问：两个数组的并集和交集
● 讨论A家一道题	● 问一道老题
● 报offer from Amazon &MS，同时谢谢大家在板上学到好多东西	● 一道老题
● 一道字典题目	● 分享面试题目
● amazon ONSITE 面试，求BLESS	● 那个 google hint words 的老题
● list of words找两个没有相同字母的string S和T并且使得S.length()*T.length()最大	● 再问一道老题
● 一道二叉树的老题	● 给一个字典，找出字母顺序这题目有点意思

相关话题的讨论汇总
话题: 老题话题: list话题: 解答话题: 单词话题: 帮忙

#	版面	帖数(主题数)
-	全站	4871 (796)
1	Military	3777 (569)
2	Stock	341 (51)
3	Joke	117 (17)
4	History	116 (3)
5	Automobile	100 (9)
6	USANews	55 (9)
7	Midlife	45 (1)
8	Headline	41 (41)
9	Dreamer	33 (13)
10	FleaMarket	32 (20)
11	Living	30 (7)

boards

未名新帖统计// 7月16日

历史上的今天