第一题，基础题：
1. 数据库及线程产生死锁的原理和必要条件，如何避免死锁。
2. 列举面向对象程序设计的三个要素和五项基本原则。
解答：
封装，继承，多态
面向对象的五大基本原则 单一职责原则（SRP） 开放封闭原则（OCP） 里氏替换原则（LSP） 依赖倒置原则（DIP） 接口隔离原则（ISP）单一职责原则（SRP）
3.Windows内存管理的方式有哪些？各自的优缺点。
第二题，算法与程序设计：
1.公司举行羽毛球比赛，采用淘汰赛，有1001个人参加，要决出“羽毛球最高选手”，应如何组织这次比赛？可以使用伪代码。
解答：
2. 有100盏灯泡，第一轮点亮所有电灯，第二轮每两盏灯熄灭一盏，即熄灭第2盏，第4盏，以此类推，第三轮改变编号为3的倍数的电灯，第3盏，第6盏，如果 原来那盏灯是亮的，就熄灭它，如果原来是灭的，就点亮它，以此类推，直到第100轮。问第100结束后，还有多少盏灯泡是亮的？
解答：
3.有20个有序数组，每个数组有500个uint变量，降序排序。要求从这10000个元素中选出最大的500个。
解答：
可能是多路归并排序思想，用到了堆，使用了优先队列数据结构
1 [cpp] view plaincopyprint? 2 3 #include <iostream> 4 #include <cstdlib> 5 #include <algorithm> 6 #include <queue> 7 using namespace std; 8 9 #define ROWS 20 10 #define COLS 500 11 12 int data[ROWS][COLS]; 13 14 void CreateData() 15 { 16 for(int i=0; i<ROWS; i++) 17 { 18 for(int j=0; j<COLS;j++) 19 { 20 data[i][j] = rand(); //生成随机元素 21 } 22 } 23 for( int i=0; i<ROWS; i++) 24 sort(data[i],data[i]+COLS, greater<int>()); //对每一行降序排列 25 } 26 27 struct Node 28 { 29 int *p; //指向某个列，因为要放入优先队列中，所以要比较大小，就用结构体封装了下 30 bool operator<(const struct Node &node) const 31 { 32 return *p < *node.p; 33 } 34 }; 35 36 void OutMinData( int k) 37 { 38 struct Node arr[ROWS]; 39 for(int i=0; i<ROWS;i++) 40 { 41 arr[i].p = data[i]; //初始化指针指向各行的首位 42 } 43 priority_queue<Node > queue( arr, arr+ROWS ); //使用优先队列，默认是大堆 44 45 for( int i=0; i<k&&i<COLS; i++) //算法核心就是这个循环 46 { 47 Node temp = queue.top(); //取出队列中最大的元素 48 cout << *temp.p << " " <<endl; 49 queue.pop(); //从队列里删除 50 temp.p++; //对应行的指针后移 51 queue.push( temp ); //这里面有log（ROWS）次操作，所以算法的总复杂度为O（klog（20）） 52 } 53 54 } 55 56 int main() 57 { 58 CreateData(); //生成数据 59 int k=500; 60 OutMinData( k ); //输出k个元素，这里k不要大于列数COL，可以改进，去掉这个限制，不过会让程序不好懂，就没加 61 }
4. 字符串左移，void *pszStringRotate(char *pszString, intnCharsRotate),比如ABCDEFG，移3位变DEFGABC，要求空间复杂度O（1），时间复杂度O（n）
1 [cpp] view plaincopyprint? 2 3 #include <iostream> 4 using namespace std; 5 6 void ReverseString( char* pBegin, char* pEnd ){ 7 8 while( pBegin < pEnd ){ 9 char ch = *pBegin; 10 *pBegin++ = *pEnd; 11 *pEnd-- = ch; 12 } 13 } 14 15 char *pszStringRotate(char *pszString, int nCharsRotate){ 16 char * end = pszString; 17 while( *end++ ); 18 end = end-2; 19 if( pszString + nCharsRotate -1 > end ) return NULL; 20 ReverseString( pszString, pszString+nCharsRotate-1); 21 ReverseString( pszString+nCharsRotate, end); 22 ReverseString( pszString, end); 23 return pszString; 24 } 25 26 int main(){ 27 char str[] = "ABCDEFG"; 28 char *s = pszStringRotate( str, 3 ); 29 if( s ) 30 cout << s <<endl; 31 return 0; 32 }
第三题，系统设计题：
手 机数字键上有拼音字母，一个数字串对应着多个字母序列，如2--ABC，6--MNO，9--WXYZ，则926对应着WAN，YAN，是汉字“万”、 “艳”的拼音等。要求设计一个系统，输入是联系人列表UserList<UserName, PhoneNo>，汉字字母映射Dict，数字串NumStr，输出满足下列条件的联系人列表ResultList<UserName, PhoneNo>：
（1）输入一个数字串，输出与其部分连续匹配的所有手机号，如，输入926，输出13926118288
（2）输入一个数字串，输出与其部分连续匹配的所有联系人姓名拼音，如输入926，输出“李万”，“李艳”等
解答：
1，字典树
2，哈希表
2.2的解答：
http://gzcsl.blog.163.com/blog/static/4103020088244441761/
这道题让人一看觉着非常有趣，但又让人感觉很复杂，其实这道题，只要弄清三点，问题就迎刃而解了。
1．对于每盏灯，拉动的次数是奇数时，灯就是亮着的，拉动的次数是偶数时，灯就是关着的。
2．每盏灯拉动的次数与它的编号所含约数的个数有关，它的编号有几个约数，这盏灯就被拉动几次。
3．1——100这100个数中有哪几个数，约数的个数是奇数。我们知道一个数的约数都是成对出现的，只有完全平方数约数的个数才是奇数个。
所以这100盏灯中有10盏灯是亮着的。
它们的编号分别是： 1、4、9、16、25、36、49、64、81、100。
转自：http://blog.csdn.net/huangxy10/article/details/8018879
本文转自夏雪冬日博客园博客，原文链接：http://www.cnblogs.com/heyonggang/archive/2012/12/13/2816874.html，如需转载请自行联系原作者
