题目: 设计一个网站的后端系统, 网页带有一个输入框, 该输入框可进行输入提示, 如用户输入"a", 会提示一个下拉列表, 把以"a"开头的若干单词列出来, 词库总共有一千万个英文单词.
难度: 12K
作者: ideawu
领域: Web, 算法, 架构
*** 解析 ***
这道题不太涉及编码, 主要是考察面试者知识面广度, 架构设计能力. 面试者做的设计不能太理论化, 也不能具体到代码级别, 应该利用图, 表, 文字, 对话等方式来解.
首先考察面试者对 Web 应用前端的原理是否了解, 如使用 AJAX.
这道题不应该用数据库来解决.
如果面试者回复"用'树'的数据结构来保存所有单词", 则要求其设计这棵树的结构, 用图来画出来. 即使设计出了这样的树, 那么下一步, 将是如何实现的问题. 用什么语言? 主要的类和函数有哪些? 内存占用多少? 如何同 Web 结合?
如果面试者能把词典的存储和查询封装成一个网络服务, 那么这种思路可以加分. 下一步可以考察其对高性能网络编程的理解, 可不用具体到代码.
面试者提出其他方案也可, 关键是要看方案是否具有"可操作性".
另外, 这种应用如果拿SSD的话, 性能会非常棒 Reply
按照一般的情况来说,1K万单词的开头字母应该是平均分配的,所以可以考虑
1.分表
分成26个表,第1张表存储a开头的单词,第2张表存储b开头的单词;查询时,按照开头的字母,去对应的表里面取数据
2.分库(就为了这个应用的话,成本太高了)
分成N个数据库服务器来建表存数据,第n1个库存储a-c开头的表;查询时,先判断查哪个库,再判断查哪张表
再加上建立上聚集索引,查询的速度应该不会很慢。
最后再鄙视一下出题人,以a开头的单词不少于20万吧,如果用户输入“a”就开始出现提示的话----20万数据的下拉列表,何其壮观哪。。。 Reply