2011-04-15

面试IT业界顶尖企业所应该知道的10道题(2)

Views: 26025 | 7 Comments

题目: 设计一个网站的后端系统, 网页带有一个输入框, 该输入框可进行输入提示, 如用户输入"a", 会提示一个下拉列表, 把以"a"开头的若干单词列出来, 词库总共有一千万个英文单词.

难度: 12K
作者: ideawu
领域: Web, 算法, 架构

*** 解析 ***

这道题不太涉及编码, 主要是考察面试者知识面广度, 架构设计能力. 面试者做的设计不能太理论化, 也不能具体到代码级别, 应该利用图, 表, 文字, 对话等方式来解.

首先考察面试者对 Web 应用前端的原理是否了解, 如使用 AJAX.

这道题不应该用数据库来解决.

如果面试者回复"用'树'的数据结构来保存所有单词", 则要求其设计这棵树的结构, 用图来画出来. 即使设计出了这样的树, 那么下一步, 将是如何实现的问题. 用什么语言? 主要的类和函数有哪些? 内存占用多少? 如何同 Web 结合?

如果面试者能把词典的存储和查询封装成一个网络服务, 那么这种思路可以加分. 下一步可以考察其对高性能网络编程的理解, 可不用具体到代码.

面试者提出其他方案也可, 关键是要看方案是否具有"可操作性".

Related posts:

  1. 面试IT业界顶尖企业所应该知道的10道题(1)
  2. Nginx 499 错误码以及 AJAX 调用失败
  3. 开发爬虫友好的Ajax网站
  4. Prado 中解决 Ajax 中文乱码问题
  5. Spring + Hibernate Web 开发者笔记
Posted by ideawu at 2011-04-15 20:55:42 Tags: ,

7 Responses to "面试IT业界顶尖企业所应该知道的10道题(2)"

  • 老大 后续题目呢 期待。。。 Reply
  • 当然用java也不错, 但是稍大的规模, java就会要消耗大得多的硬件. C/C++的程序员很好找, 稍作培训就可以开发PHP模块. 和伞哥用的lisp难度比还是低得多的. Reply
  • 这种应用最好用PHP的C模块实现. 类似于新浪的short url的查询机制. 新浪那个还需要用键表, 这个连键表都不用, 因为value本身就可以作为key, 而且还基本是固定表. 直接按升序排列后存入内存, 10mil的单词, 平均每个单词长度是7(非专业语库6足够了), 总共70mil的数据量, 算上结构冗余, 不会超过100M. 优化速度的目标只是数据中的定位速度. 以二分查找的形式, 最差情况下读取23.3个值就可以全匹配一个目标. 在这个案例里, 可以为第一位甚至第二, 第三位建立索引, 对像以s开头单词这样特别多的, 可以增加一位做索引. 输出可以通过PHP推出json, 而后就随便怎么处理了.
    另外, 这种应用如果拿SSD的话, 性能会非常棒 Reply
    to Milton Lai: 用PHP模块来处理确实性能可以满足要求, 但可扩展性和可维护性等方面来看还是有不少劣势. Reply
  • 我是个phper,就单纯从php角度来解问题。
    按照一般的情况来说,1K万单词的开头字母应该是平均分配的,所以可以考虑
    1.分表
    分成26个表,第1张表存储a开头的单词,第2张表存储b开头的单词;查询时,按照开头的字母,去对应的表里面取数据
    2.分库(就为了这个应用的话,成本太高了)
    分成N个数据库服务器来建表存数据,第n1个库存储a-c开头的表;查询时,先判断查哪个库,再判断查哪张表

    再加上建立上聚集索引,查询的速度应该不会很慢。

    最后再鄙视一下出题人,以a开头的单词不少于20万吧,如果用户输入“a”就开始出现提示的话----20万数据的下拉列表,何其壮观哪。。。 Reply
    to chenshao: 这个方法虽然有些丑陋, 但还是能很好工作. 另外, 提示肯定不是提示全部, 而是前n条. Reply
  • trie树, 只能用C/C++或者Java了 Reply

Leave a Comment