2012年10月30日，晴，宜搜【C/C++移动搜索开发实习生】面试
前面题目很简单，后面三道算法设计题不会做....
简答题一：
列出各种排序算法，其复杂度以及稳定性。
整理答案：
算法名称-时间复杂度-空间复杂度-稳定性
插入排序-O(n*n)-O(1)-是
冒泡排序-O(n*n)-O(1)-是
简单选择排序-O(n*n)-O(1)-否
希尔排序- -O(1)-否
快速排序-O(n*log2n)-O(log2n)-否
堆排序-O(n*long2n)-O(1)-否
二路归并排序-O(n*long2n)-O(1)-是
基数排序-O(d(n+r))-O(r)-是
算法题一：
在排列好的数组中查找某一个数可以采用二分查找算法，现在有一个数组，其中从某一个数开始循环有序，例如12,14,18,22,24,1,3,5,9，从1开始循环有序，设计算法实现在这种数组中查找某一个数，要求时间复杂度低于O(n)。
这里有解答：
http://blog.csdn.net/fanzy618/article/details/5274998
算法题二：
设计实现一个多线程安全的内存池pool，要求这个内存池提供两个功能，分配及释放内存：
void* pool::malloc(unsinged int size);
void pool::free(void *p);
说明算法，数据结构，必要的话可以画图说明。
4篇博客可以解决：
Linux多线程同步：
C++线程安全内存池：
系统设计题：
这个题要求设计一个数据库系统，实现同时更新读取插入删除等功能，题目不记得了，反正是一点也不会....
面试题一：
网络爬虫从网络上扒下来大量的URL，存储在一个文件中，文件大小为2G，可用内存只有60M，设计算法实现对这2G文件中的URL进行去重。
整理解答：
方案一（外存排序法）：
分多次读取原文件，每次将内存读满，然后进行排序，排好序后再将这些url按顺序存储到外寸成为一个小文件，然后再次读取url再排序再存储，直到将原来大文件中的url全部读取完后就得到了大量已经排序好的小文件，最后对这些小文件进行归并去重。
方案二（文件hasn散列法）：
依次读取原文件中的url，设计一个适当的hash散列函数和一系列的函数值区间，求出这些url的散列值，降落在同一个散列区间内的url保存到外存的同一个文件中，原文件读完后将得到一系列包含hash值处在统一区间的url的小文件，这样就保证了所有含有重复的url都在一个文件中。
这里有两种去重方法：
1，在对url进行hasn散列时去重，即求出url的hasn函数值后在hasn表中查找是否已经存在了，是的话表示重复就丢去，否则就存储。
2，当将原来大文件分割成小文件后，对每一个小文件分别进行去重处理，可以将小文件里的url读入内存排序去重，hash去重等等，最后存储回去。
去重后将这些小文件合起来即可。
面试题二：
MySQL数据库内部实现数据结构是什么？
面试题三：
操作系统内存分配算法是什么？
整理解答：
1，连续内存分配包括：
(1) 单一连续分配
(2) 个固定分区分配
(3) 动态分区分配，这里面又包括以下几个适应算法：
首次适应，最佳适应，最大适应（最差适应），邻近适应（循环适应）
2，非连续内存分配包括：
(1) 分页管理方式
(2) 分段管理方式
(3) 段页式个管理方式
具体内容看这里，或者看考研指导书操作系统第三章内存管理。
面试结果：失败被刷了，笔试题中内存池和数据库设计没做好，一面TopK算法和海量数据去重算法不熟悉，二面C/C++线程同步不熟悉，三面内存分配算法不熟悉，写代码内层循环中忘了加上结尾字符判断会导致死循环。
结论：数据结构算法，海量数据处理，计算机基础，多线程编程需要加强。