（讨论）百度2010校园招聘网络笔试题

scu_guzo

题目

百度2010校园招聘全国笔试题RD-3


温馨提示：
1． 本次考试为闭卷考试，请保证独立完成试卷；
2． 请深入思考每一个问题，方法不会只有一种，请尽情发挥，充分展示你的才华；
3． 解决问题是一门权衡的艺术，如果有可能，请说明你的考虑；
4． 若写不出具体代码，也请写明解题思路；
5． 题目或许有难有益，请通览试卷后进行答题，尽可能多的完成你所擅长的题目；

准备好！笔试马上开始。
“框”广天地，大有所为！祝同学们都能够取得好成绩！

本试卷共分为两个部分，共4道题。


第一部分、算法与程序设计

1．在一棵一般的二叉树中找到指定的元素，如果有重复出现的元素，要求元素为深度最深的任何一个。指定元素找不到时返回EMPTY_NODE，请用C语言实现，相关数据结构与函数声明如下：
struct Node
{
    int iValue;　　
    int id;
    Node *pLeft;
    Node *pRight;
};

const Node EMPTY_NODE = {0, 0, NULL, NULL};
Node findDeepest(Node *pRoot, int iWanted); //pRoot为根节点，wanted为指定元素的iValue


2．一个单词字典库，单词个数约为10万，每个单词长度不超过16，单词都是由小写字母组成，同时给出16个小写字母，请设计一种高效算法来找到用这些给出字母拼出一个字典中最大长度的单词。给出的16个字母每个字母最多使用一次，也可以不使用。存在多解的时候给出任意一个最优答案就行。
例如：给出adeenrstuvxyzuki可以拼出adventures
请详细描述你的算法思路（如需要，可给出代码\伪代码来辅助描述），并分析其时间复杂度。最后请分析下你的算法以及数据结构的优缺点，存在哪些可改进的地方。


第二部分、系统设计题

1.       有200亿条数据，每条数据的大小在1K~1M不等，每条数据有一个唯一的u_int64的id。
请设计一个读取数据系统，能根据id获取数据。要求：
A.        内存有限制，16G
B.        尽可能利用内存资源
C.        尽可能高效的获取数据
D.        可以利用磁盘，磁盘容量不受限制


2.       C2C网站的商品子系统，包括的关系数据有 分类、属性、商品。
一个商品只能属于一个分类，不同的分类有不同的属性（多个），每个属性有多个候选属性值，其中分类、属性、属性值的更新频率较低。
一个商品的属性，是所属分类的属性，属性值是候选属性值中的一个或多个。
例如：
分类：衣服
属性：尺寸、颜色
尺寸的候选属性值：S/M/L/XL/XXL/XXXL
颜色的候选属性值：黑/白/红/黄/蓝
商品：衣服A，尺寸S，颜色黑
另外，商品还有卖家、价格等其它信息

请设计商品子系统的存储结构或数据库结构。要求：
A.        能够正确维护分类、属性、商品之间的关系数据
B.        尽量减少冗余
C.        考虑数据的增、删、改、查操作，效率尽可能高
D.        能够按照卖家查询出其发布的所有商品

scu_guzo

我的解答：

第一部分
1.
static Node *res==NULL;
static int resdeep=-1;

static void find(Node *root,int iWanted,int deep)
{
    if(root!=NULL)
    {
        if(root->iValue==iWanted && deep>resdeep)
        {
            res=root;
            resdeep=deep;
        }
        find(root->pLeft,iWanted,deep+1);
        find(root->pRight,iWanted,deep+1);
    }
}

Node findDeepest(Node *pRoot, int iWanted)
{
    find(pRoot,iWanted,0);
    if(res) return *res;
    return EMPTY_NODE;
}

2.不会


第二部分
1./*谢谢fromheaven 提醒，这种解法是错的*/   假设这200亿条数据存储在文件里。 用数组u_int64 ref[20000000000] 存储每条数据在文件中的索引位置。每条记录的id作为ref的下标。如此内存使用接近但小于16G.   X

还可以采用分布式处理。如第一台电脑存储前100亿条数据以及数据在磁盘上的索引，第2台电脑存储后100亿条数据以及数据在磁盘上的索引。则可以根据所查询的id的范围在第一台电脑或第2台电脑上读取数据


2.在数据库中建一张表，有 卖家、商品、分类、价格等信息。这些字段都是易变的，且存在一张表中便于维护它们之间的关系。
对于分类的属性名称则可以用XML来管理。属性的候选值也可以用XML来管理。这部分的信息是不容易改变的，而且由于分类所拥有的属性个数不同，也可以减小冗余。属性的候选值也一样。而且在XML中也便于修改。这两个XML文件不会很大，对于XML的处理会很快。

[ 本帖最后由 scu_guzo 于 2009-11-9 19:27 编辑 ]

peidright

第二题目。我感觉除非专门为这种需求，设计特别的字典的存储结构，才可能有好办法。
如果按一般的字母顺序存储的话，需要对整个表扫描一次，每次把字符串转化为向量，计算向量距离。距离最小的为所得结果。
扫描的时候，如果当前字母数少于已得结果，或者所得结果=16，终止.

向量距离的计算方法如下：

标准向量： 我们已经给出的字母序列， 比如 aabcdef   则向量为[2 ,1 1,1,1,1 ,0,0,0......]26个。
向量： 扫描每一个字母的时候，                    向量为[*,*,*,..........................]
距离的算法： 只有当前word的向量小于对应的标准向量的时候，才作计算，否则，距离为无穷大。
遍历一遍后，所得最大结果就是

ccaaatt

否则
如果字典没有什么特别地方，那么

反正10万个单词总要查过
那就一个100K的循环

然后单词每个字母总要查过
while一下喽

单词长度小于已知Max的，跳过
有不认识字母的，skip
已经16了，return

如果要优化，长度小于5的，skip。
如果要再优化，能不能从长度为16的单词开始check？

ecjtubaowp

有点难度啊！！

cugb_cat

第一部分2，将10w个单词排序，将10w个单词中每个单词的字母排序，将给的16个字母排序，这样再循环就可以剪掉很多枝了。

scu_guzo

貌似第一部分第2题没有好的算法啊！

我提交的答案是用26叉树，也算是一种剪枝。跟peidright 的距离向量差不多


ccaaatt 的解法就算是枚举了，

ccaaatt

关键是字典怎么设计
否则这么反复排序
最后一轮可能快
可前面要枚举好几轮呢

shmild

第二题，没有人想起有一种数据结构叫trie树吗

peidright

:wink: ...搜搜这个树。。
楼上能说说用tire树怎么做么。。。？
看了一下tire树。不知道怎么做。 感觉还是我的方法好。

[ 本帖最后由 peidright 于 2009-11-9 12:38 编辑 ]