Chinaunix

标题: 来看看真正有技术含量的面试题！ [打印本页]

作者: 侧面bt 时间: 2010-04-04 21:03
标题: 来看看真正有技术含量的面试题！
1、
考虑一个在线好友系统。系统为每个用户维护一个好友列表，列表限制最多可以有500个好友，好友必须是这个系统中的其它用户。好友关系是单向的，用户B是用户A的好友，但A不一定是B的好友。

用户以ID形式表示，现给出好友列表数据的文本形式如下：
1 3,5,7,67,78,3332
2 567,890
31 1,66
14 567
78 10000
…
每行数据有两列，第一列为用户ID，第二列为其好友ID，不同ID间用”,”分隔，ID升序排列。列之间用”t”分隔。

要求：
请设计合适的索引数据结构，来完成以下查询：
给定用户A和B，查询A和B之间是否有这样的关系：B是A的二维好友（好友的好友）。
如上例中，10000为1的二维好友，因为78为1的好友，10000为78的好友。

详细说明自己的解题思路，说明自己实现的一些关键点。并给出实现的伪代码实现建立索引过程和查询过程，并说明空间和时间复杂度。

限制：
用户数量不超过1000万，平均50个好友。

2、
请设计一个网页存储系统，能存储千万量级的网页。

要求：
1.支持按照URL为键值的随机添加，删除和修改网页
2.支持多个线程同时添加，修改和删除
3.支持多线程按照入库时间批量的获取网页，并尽可能的快
提示:设计应包括如下几方面:
1.网页的存储方式设计,即硬盘数据的组织形式
2.如何支持随机查找
3.如何优化批量检索
4.增删改查之间的同步和互斥,如何达到最大的并发.
  系统限制和一些参考参数:
硬盘400G, 内存4G
硬盘的I/O比内存的I/O速度慢1000倍
硬盘的连续I/O比随机I/O快10倍
网页的平均长度为25K
附加：
请说明你的系统在亿到十亿规模的扩展方法．

3、
为某图书馆开发在线浏览系统，使用户可以通过自定义的图书别名浏览相关联的图书
内容。假设该图书馆有1000万注册用户，馆藏图书1000万部。在线浏览系统允许用户自
定义分类名称，每个分类可以包含若干部书籍。用户可以添加、删除分类，修改分类的
名称（同一用户不允许有名称相同的分类），可以在分类下添加、删除书籍，修改书籍
的别名（同一分类下不允许有名称相同的别名）。现在设定每个用户最多可以自定义10
0个分类，每个分类最多可以包含100部书籍。

A、假定用数据库解决存储问题，请设计相关的数据表结构，并给出设计考虑。

B、请给出下列操作的SQL语句

  展示用户A的所有分类

  展示用户A所设置的分类F下的所有书籍信息

C、请根据题目A的结果，尝试分析一下当用户数目增长到1亿，馆藏图书达到10亿册，每
天访问用户达到500万，平均每人有10次操作时，系统应当做哪些改进或优化。

4、假设一个mp3搜索引擎收录了2^24首歌曲，并记录了可收听这些歌曲的2^30条URL，但每
首歌的URL不超过2^10个。系统会定期检查这些URL，如果一个URL不可用则不出现在搜索结
果中。现在歌曲名和URL分别通过整型的SONG_ID和URL_ID唯一确定。对该系统有如下需求
：
1) 通过SONG_ID搜索一首歌的URL_ID，给出URL_ID计数和列表
2) 给定一个SONG_ID，为其添加一个新的URL_ID
3) 添加一个新的SONG_ID
4) 给定一个URL_ID，将其置为不可用

限制条件：内存占用不超过1G，单个文件大小不超过2G，一个目录下的文件数不超过128个
。

为获得最佳性能，请说明设计的数据结构、搜索算法，以及资源消耗。如果系统数据量扩
大，该如何多机分布处理

作者: prolj 时间: 2010-04-04 21:11
恩，有技术含量，这个职位你们肯出35W+的薪水么？

作者: starzhestarzhe 时间: 2010-04-04 21:39
{:3_183:}，看到题目头就大了，果然有技术含量。

作者: A.com 时间: 2010-04-04 21:43
麻花藤招事业部经理么？

作者: prolj 时间: 2010-04-04 21:46
行了，不就是腾讯么？

作者: peidright 时间: 2010-04-04 21:51
{:3_185:},怀疑是某个公司的sb总监，设计架构有几个地方设计不出来，在这上面问答案了吧。
大部分内容，可以在 mg那本书中找到答案。

作者: dozec 时间: 2010-04-04 22:16
百度

作者: shang2010 时间: 2010-04-04 22:33
二维好友
这个名词好难听,不看注释还真不懂

作者: iamybj 时间: 2010-04-04 23:24
提示: 作者被禁止或删除内容自动屏蔽

作者: ironside_zy 时间: 2010-04-05 09:11
回复 6# peidright

mg那本书是哪本？呵呵

作者: linuxlixk 时间: 2010-04-05 10:22
好友在线~~~~
presence 飘过~~~

作者: wohenry84 时间: 2010-04-05 19:18
第一题用十字链表法？
然后遍历两重循环不就知道是不是他的好友了吗？
哈哈：麻花藤？

作者: byjxy 时间: 2010-04-05 19:21
这个软件面试题也太长了，短时间内很难进入状态的

作者: benjiam 时间: 2010-04-06 09:28
第一道很有难度啊！如果将情况考虑成qq 的服务器，而不是1000w 人， 50个好友这个数量。

关键是实时的实现用户上线，下线的系统维护。

这个好像可以说是一个六度分隔理论。

想法是双向链表加指示标记来实现。

作者: asdmonster 时间: 2010-04-06 10:10
1，才百万的数据量，用现有的关系型数据库都能满足需求。没有必要自己去设计什么数据结构算法——数据库满足不了并发可以集群，个人费那劲干嘛。

2，怎么看怎么看都是bigtable的模子，甚至不用去抄别人的实现，提到的几个问题人家文档里面都说出详细的解决方法了。
单机硬盘400G, 内存4G 想要上亿数据的crud，脑子秀逗了。

3，对数据库开发人员来说，这道题是入门级别的。

用户数目增长到1亿，馆藏图书达到10亿册，每天访问用户达到500万，平均每人有10次操作时

后端数据毫无特点，即使做了rac,也不会很快，修改业务吧。

4，

一个目录下的文件数不超过128个。

无非考官的潜意识是用文件系统解决问题呗。一个目录容量不够可以多个，一级不够可以多级嘛。

数据量大了，就是考虑分布式或者用现成的db解决问题。
除非，如果这个面试题是Oracle，Google招聘核心开发人员，需要自造轮子，就别论了————可能么？

作者: 梅川内依酷 时间: 2010-04-06 10:51
回复 1# 侧面bt

这些题目是数据库的吧发这个版不合适

作者: gdmadbug 时间: 2010-04-06 11:15

,怀疑是某个公司的sb总监，设计架构有几个地方设计不出来，在这上面问答案了吧。
大部分内容，可 ...
peidright 发表于 2010-04-04 21:51

显然是的，哪个公司会出这么啰嗦的题目

不过总监倒应该不是最多就是个不够格的sb系统工程师

作者: ZSMDEV 时间: 2010-04-06 11:37
很有技术含量啊，仔细瞧瞧~

作者: hansion3406 时间: 2010-04-06 12:24
看来很多人对数据库的应用不是那么懂啊....

很多事情数据库可以解决的，为啥一定要自已再搞个轮子...

作者: benjiam 时间: 2010-04-06 13:13

看来很多人对数据库的应用不是那么懂啊....

很多事情数据库可以解决的，为啥一定要自已再搞个轮子...
hansion3406 发表于 2010-04-06 12:24

google 是不是所有的网页存在一个表里面用select * from xx where like 语句来实现的啊？

作者: hansion3406 时间: 2010-04-06 15:55
你看LZ提的这些题目，在那种压力的情况下面，有必要这么搞吗？

这不是一种操蛋行为吗？
不同的压力，到算法难道都是一成不变？

作者: hansion3406 时间: 2010-04-06 16:01
不过， benjiam 同志，你估计没有做过内存数据库的应用..
速度比你想象中的快得多，而且又有数据库的特性...
如果业务刚好适合，为啥不用？

作者: wenlujon 时间: 2010-04-06 16:49
对于问题1，一个笨拙的设计思路：

1）为所有的用户建立一张非常大的HASH表（大小为所有用户数），HASH函数直接选择userID，第一个元素存储的是其用户本身，后面的结点存储的是其好友；
2）如果把C添加为A的好友，就以A为index，将C添加到A的桶中；
3）如果要判断B是否是A的二维好友，则依次遍历A的所有好友，对于每一个A的好友buddy[i]，用它的userID做HASH，得到buddy[i]的HASH桶，然后遍历此HASH桶，看能否找到B，如果找到则返回B是A的二维好友，否则不是。

由于需要遍历两个HASH桶，所以需要的时间是O(n^2)；

空间是1000万乘以50.

作者: benjiam 时间: 2010-04-06 17:48

不过， benjiam 同志，你估计没有做过内存数据库的应用..
速度比你想象中的快得多，而且又有数据库的特性. ...
hansion3406 发表于 2010-04-06 16:01

我讨论的是一个比较实用的例子。不是简单的面试题。这种依靠db的方案，在扩展性上问题很大。所以不是很好的方案

作者: cx6445 时间: 2010-04-06 21:12
这几个问题都是国内最大的那几个互联网公司正在解决的问题，没几年相关工作经验还真答不好。基本属于传统数据库目前解决不了的成本和线性扩展的问题。

作者: wwdwwd 时间: 2010-04-06 23:59
简单想了一下思路，抛砖引玉一下：
1：可以自己设计数据结构也可以使用数据库，自己设计数据结构的话，我会先设计一个hash表，用户id的哈希值为表索引，每个槽后面跟一个平衡二叉树，二叉树节点为好友id。简单估算之后发现总存储量为1000w*(4+50*12)=5.6G，大于4G，或者采用64位操作系统，或者采用多个32位服务器(选3个，按大小hash一下就行)。只说64位单台服务器的(多台服务器仅多一层hash)，查找二维好友需要先找到用户的槽，对平衡树中的每个用户再找他的好友。由于找到槽需要O(1)的时间，平衡树中平均有50个节点，从平衡树中查找好友需要lg(50)的时间，故而查找时间为1+50*lg(50)=283；插入/删除的话比较简单了,都是O(1+lg(50))。
如果采用数据库设计的话，一种表，两个字段，用户id和好友id，根据我们的数据量1000w*50=5亿应该分表。假设用mysql的话，根据之前的经验，每个db下数据表保持在300以下，每个表数据量保持在100w以下速度比较平稳，分成103个表，每个表大概49w数据量。查询二维好友的话，也是先查出所有一维好友，然后对每个一维好友再查一遍好友，时间跟上面的类似。
2：方式为数据库+文件。数据库中存url，创建时间，网页文件目录名，而文件中存真实网页内容。考虑到会按时间批量获取网页，则将网页按(年/月/日)的日期目录存放，每个目录下文件量也不会太大。
3：两个关系表，用户和分类关系表，分类和文章关系表，两个关系表都做分表。
4：还是用数据库吧，三种表，歌曲表，url表，歌曲与url关系表，这三个表都可以hash。歌曲表按歌曲id哈希，url表按url的id哈希，歌曲与url关系表按歌曲id哈希，将URL_ID置为不可用时仅在url表中设置状态，而下次查询歌曲对应的url时检查一下url的可用状态，不可用则删除此条url记录和歌曲与url关系表中的对应记录。

怎么感觉这些题目都是考数据库设计呢？至于存储量大了，访问量大了怎么办，只能是分而治之了。^_^

作者: wwdwwd 时间: 2010-04-07 00:04

第一道很有难度啊！如果将情况考虑成qq 的服务器，而不是1000w 人， 50个好友这个数量。

关键是实时的实 ...
benjiam 发表于 2010-04-06 09:28

qq的上下线一般不用自己维护吧，他只需要把上线消息推送给用户的好友就可以了，自己想统计的话几个日志就可以了

欢迎光临 Chinaunix (http://bbs.chinaunix.net/)