凡人更得太慢了！# paladin - 谈古论金，黄梁一梦
m*n
1 楼
☆─────────────────────────────────────☆
PenguinLover (I love Penguin) 于 (Sun Oct 12 21:16:26 2008) 提到:
1）给你一个巨大的电话号码簿，每一个记录由名字和电话号码两部分组成，电话号码
簿按照名字的字母顺序排列。现在给你一个电话号码，问你如何设计算法使得在最快的
时间内找到电话号码的主人。
2）一个双精度浮点型数组，无序排列，有大概几百亿个元素（several tens of
billions of entries，我没理解错吧）。现在让你找出其中最大的一百个元素，要求
时间复杂度O(n)。我想到的是遍历一百次，但这肯定不是他想要的答案。
3）设计一个文本框，比如google search的那个框，你往里敲单词，比如computer。你
每敲一个字母，蹦出来的单词都会更新。比如，你敲c，会出来chicken, cat, concept
, combine,computer, 等等。你接着键入o，就只剩下concept和combine和computer了
。再键入m，就剩下comb
PenguinLover (I love Penguin) 于 (Sun Oct 12 21:16:26 2008) 提到:
1）给你一个巨大的电话号码簿，每一个记录由名字和电话号码两部分组成，电话号码
簿按照名字的字母顺序排列。现在给你一个电话号码，问你如何设计算法使得在最快的
时间内找到电话号码的主人。
2）一个双精度浮点型数组，无序排列，有大概几百亿个元素（several tens of
billions of entries，我没理解错吧）。现在让你找出其中最大的一百个元素，要求
时间复杂度O(n)。我想到的是遍历一百次，但这肯定不是他想要的答案。
3）设计一个文本框，比如google search的那个框，你往里敲单词，比如computer。你
每敲一个字母，蹦出来的单词都会更新。比如，你敲c，会出来chicken, cat, concept
, combine,computer, 等等。你接着键入o，就只剩下concept和combine和computer了
。再键入m，就剩下comb
