Category: 技术

上上周百度又让我参加了一轮在线笔试。今天忽然在桌面上看到于是就贴出来。
第一部分、算法与程序设计
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.        能够按照卖家查询出其发布的所有商品
==============问题和解答的分割线======================
1111111111111111111111111111111111111111111111111111111111111111111111111111
Node findDeepest(Node *pRoot, int iWanted); //pRoot为根节点，wanted为指定元素的iValue
{
return findDeepestWithDepth(pRoot, iWanted, 1);
}
Node findDeepestWithDepth(Node *pRoot, int iWanted, int depth)
{
static int maxDepth = 1;
static Node deepestNode = EMPTY_NODE;
if(pRoot != null)
{
Node l = findDeepestWithDepth(pRoot->pLeft, iWanted, depth+1);
Node r = findDeepestWithDepth(pRoot->pRight, iWanted, depth+1);
if(isEmpty(l) && isEmpty(r))
{
if(maxDepth < depth)
{
maxDepth = depth;
node = *pRoot;
return *pRoot;
}
else
{
return deepestNode;
}
}
else
{
return deepestNode;
}
}
else
{
return EMPTY_NODE;
}
}
bool isEmpty(Node node)
{
return node.iValue == 0 && node.id == 0 && node.pLeft == NULL && node.pRight == NULL;
}
2222222222222222222222222222222222222222222222222222222222222222222222222
1. 对字典中每一个单词进行遍历，计算出每个单词每个字母的个数和单词的长度
2. 针对每个单词里每个字母(a-z)的个数和单词的长度建立索引，类似数据库的一张表，表一共有28个列（加上一个隐含的rowid），包括单词内容（1列），26个字母每个字母的个数（26列）和单词的长度
3. 搜索时，对给定的字符串进行相同的统计，计算出每个字母的个数。根据统计结果去搜索个数小于给定字符串字母的单词的rowid，最多16次搜索，搜索后对结果进行交集（思想类似： select word from words where a <= 1 and b <= 1 and d <= 2 and …)
4. 对最后的交集根据长度，得出最长的单词的rowid，最终得出单词
时间复杂度: 16次搜索，每次为O(log n)，最多15次的交集运算，复杂度为O(logn * logn)，最后寻找最大值可以忽略，所以时间复杂度为O(logn*logn)
改进：提高索引效率，如联合索引
33333333333333333333333333333333333333333333333333333333333333333333333333
1. 内存中使用二叉搜索树进行索引，每个节点占用16字节（2个指针+1个id），可放10亿个节点，则底层节点有5亿个。底层节点左右为空，8个字节用来表示记录在磁盘的存储位置
2. 磁盘存储分为5亿块，每个块里有40条记录
3. 块分为块头索引和块内容。块头索引按id顺序排列，包括了该块的id，起始位置和长度。块头大小为40*(8+8+4)=800字节
4. 每次通过id访问数据，首先查找二叉搜索树，经过29次内存比较得到索引块，再载入索引块头，使用二分搜索得到内容的起始位置和长度，最终得到内容。一共35次左右内存访问和2次磁盘访问
44444444444444444444444444444444444444444444444444444444444444444444444444444
商品表 product: id, name, seller, price, category
分类表 category: id, name
属性表 attribute: id, name, category_id, type
属性候选值表 attribute_value: id, attribute_id, value
商品属性表 product_value: product_id, attribute_value_id

10号晚上的宣讲+笔试，笔试笔得一般，程序题做错了，没想到用递归，还有记得做错的是一道网络题，问会话层(Session)是OSI里的第几层，我忘了展示层(Presentation)，于是选了第六层光荣的错了。
11号一早通知9点面试，我起床洗漱吃早饭，然后又接到一个电话说是12号早上9点，于是只好上床继续睡觉。
面试前打印了几份简历，进去咖啡馆之后填了表格就开始面了。中间省略过程数百字。。。直接开始总结几个答的不好的问题，因为一面就挂了。
Spring的事务有几种方式？
题目到现在也不是很明白，我觉得大概的解答应该是声明式事务处理的几种方式（1.0时代的parentTemplate、2.0时代的AOP代理和@Transational），另外加上编程式事务处理，直接上TransactionTemplate和PlatformTransactionManager。
Spring Bean加载有几种方式？
我回答了启动时加载，现在看来有点答非所问。加载bean默认为即时加载，另外也可以设置延迟加载。加载可以为单例、每次一个实例、request、session、global-session。
Spring Bean有几个设置属性？
我只想起来scope，应该想起来auto-wire, init-method, destroy-method一时都忘了。另外还有lazy-init,  factory-bean, factory-method。
Collections.sort()对参数的要求？
这个是最不应该答错的题目。我只想起来sort的集合必须实现List接口，却忘了最重要的sort的对象必须实现Comparable接口。
描述一个LRU的HashMap。
这题一开始楞没听明白，老想着HashMap不是链式连接冲突的entry的么，怎么会size不够。磨叽了半天，搞了一个堆出来计数，面试官也不满意。
后来想想其实用个链表把Entry链接起来就可以了，正好在网上搜到了使用LinkedHashMap实现LRU Cache的做法，在这里描述一下内部实现：

1. 扩展HashMap.Entry，使Entry间使用双链表连起来；
2. get的时候，把该Entry移到链表的尾部；
3. put的时候，把Entry放到链表的头部；
4. 如果规模超标，则把链表头部的Entry抛弃；

项目里使用的设计模式。
我拿了资源安排里，封装两种安排算法到两个实现同一个接口的类的例子，说这是策略模式，面试官有些不认同。后来回头想想，项目里还有其他的模式：

• Singleton，Facade自不必说；
• Strategy有一个更好的例子，使用PROBE的A、B、C、D四种方法进行时间和规模的估算。另外还有两个Factory来负责生成相应的计算方法实例。
• Decorator模式，封装了MultiTenantSessionFactory，持有一个SessionFactory对象，也实现了SessionFactory接口。

大概就想起来这些问题。一开始的自我介绍忘记介绍做过的项目了，这可能是悲剧的来源吧。