2011-04-12

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

Views: 31110 | 7 Comments

题目: 现有一个包含一千万个单词的文本文件, 每个单词占一行, 每行小于1K字节. 要求找出出现次数最多的10个单词. 如果要从一千个这样的文件中找出出现次数最多的10个单词(所有单词加起来去重后不超过一千万个), 你会怎么设计?

难度: 10K
作者: ideawu
领域: 编码, 架构, 分布式

*** 解析 ***

这道题没有任何算法上的难度, 最简单的思路就是, 一次读取一行, 计数. 先从单个文件来考虑, 首先考察面试者最基本的用计算机解决简单问题的能力.

* Shell

如果面试者的简历提到 Linux Shell, 让其用一行 Shell 命令(sort, uniq)来解.

* 脚本语言

要求面试者用任何一种通用的脚本语言来解决, 例如 PHP, Python. 要求其手写出无语法错误的可执行的完全正确的代码, 考察其编码能力基本功.

* SQL

假设单词是保存在 MySQL 数据库表中, 要求面试者用一条 SQL 语句来解, 考察其是否掌握 SQL, 以及 count(), group by, order by 等关键字的使用.

* 多线程, 多机解决的思路

将条件设置为有一千个或者更多的文件的情况, 如果面试者能主动想到如上方法的局限性和性能问题, 可以加分. 要求面试者分析出影响性能的瓶颈在哪.

如果面试者能想到多线程, 多机分布式, 要求其设计一个大致的方案.

Related posts:

  1. 面试IT业界顶尖企业所应该知道的10道题(2)
  2. Web 开发程序员谈网游服务器开发
  3. Cpy是如何打败Python的
  4. 开始学习 Python
Posted by ideawu at 2011-04-12 20:49:54 Tags: ,

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

  • 每个文件生成一个索引表, 索引的值是命中数, 10mil*logM (M和索引键长有关, 哈希后M可以很小, logM最大不超过10)这是可以并发的, 然后得到总的索引表10mil*1, 这也是可以并发的, 最差情况系数乘10保证无互锁; 最后遍历总索引表, 10mil*3.3

    实际上在非稀疏并且分布白噪化的情况下, 可以根据经验值, 从第二步开始只对排在前Nmil的索引做总索引, N可以根据数据源数量和结果数量计算. Reply
  • 现有N 个数,找到其中最大的M个数,N>>M.
    使用大小为M的最小堆来实现。遍历N个数,前M个数用来构建这个堆,后面的数不停的插入到这个最小堆上。
    空间复杂度:O(M)
    时间复杂度:最坏时间复杂度O(N*logM)
    大多数人能找到堆排的方案,但是对于堆的长度和堆的大小性质,不少人会出错
    ———–
    其实如果量级不是很大(小于100w)且只执行一次的话,直接shell下sort uniq,TCO成本最低口牙 Reply
    回复suchasplus: 那就看面试官要考察是什么方面的内容了. 如果是快速解决实际问题, 当然是sort/uniq. 如果他要考察算法, 就只能用算法的方式来解. Reply
  • 多线程多机的答案是什么?我想要你的答案!~ Reply
  • 呵呵 那是
    不过好像很少直接出题库里面的原题 Reply
  • 回复suchasplus: 这个真不行^_^. Reply
  • 博主把ecom的题库直接发出来好了… Reply

Leave a Comment