第一题，基础题：

　　1. 数据库及线程产生死锁的原理和必要条件，如何避免死锁。
　　2. 列举面向对象程序设计的三个要素和五项基本原则。
　　3.Windows内存管理的方式有哪些？各自的优缺点。

第二题，算法与程序设计：

　　1.公司举行羽毛球比赛，采用淘汰赛，有1001个人参加，要决出“羽毛球最高选手”，应如何组织这次比赛？可以使用伪代码。

　　2.有100盏灯泡，第一轮点亮所有电灯，第二轮每两盏灯熄灭一盏，即熄灭第2盏，第4盏，以此类推，第三轮改变编号为3的倍数的电灯，第3盏，第6盏，如果原来那盏灯是亮的，就熄灭它，如果原来是灭的，就点亮它，以此类推，直到第100轮。问第100结束后，还有多少盏灯泡是亮的？

　　3.有20个有序数组，每个数组有500个uint变量，降序排序。要求从这10000个元素中选出最大的500个。

第三题，系统设计题：

　　手机数字键上有拼音字母，一个数字串对应着多个字母序列，如2--ABC，6--MNO，9--WXYZ，则926对应着WAN，YAN，是汉字“万”、“艳”的拼音等。要求设计一个系统，输入是联系人列表UserList<UserName, PhoneNo>，汉字字母映射Dict，数字串NumStr，输出满足下列条件的联系人列表ResultList<UserName, PhoneNo>：
（1）输入一个数字串，输出与其部分连续匹配的所有手机号，如，输入926，输出13926118288
（2）输入一个数字串，输出与其部分连续匹配的所有联系人姓名拼音，如输入926，输出“李万”，“李艳”等。

解答：

第一大题

　　1、操作系统中有若干进程并发执行， 它们不断申请、使用、释放系统资源，虽然系统的进程协调、通信机构会对它们进行控制，但也可能出现若干进程都相互等待对方释放资源才能继续运行，否则就阻塞的情况。此时，若不借助外界因素， 谁也不能释放资源， 谁也不能解除阻塞状态。根据这样的情况，操作系统中的死锁被定义为系统中两个或者多个进程无限期地等待永远不会发生的条件，系统处于停滞状态，这就是死锁。
产生死锁的原因主要是：

1. 因为系统资源不足。
2. 进程运行推进的顺序不合适。
3. 资源分配不当等。

如果系统资源充足， 进程的资源请求都能够得到满足，死锁出现的可能性就很低， 否则就会因争夺有限的资源而陷入死锁。其次，进程运行推进顺序与速度不同，也可能产生死锁。
产生死锁的四个必要条件：

1. 互斥条件：一个资源每次只能被一个进程使用。
2. 请求与保持条件：一个进程因请求资源而阻塞时，对已获得的资源保持不放。
3. 不剥夺条件:进程已获得的资源，在末使用完之前，不能强行剥夺。
4. 循环等待条件:若干进程之间形成一种头尾相接的循环等待资源关系。

这四个条件是死锁的必要条件， 只要系统发生死锁， 这些条件必然成立， 而只要上述条件之一不满足，就不会发生死锁。
死锁的避免：
　　死锁的预防是通过破坏产生条件来阻止死锁的产生，但这种方法破坏了系统的并行性和并发性。死锁产生的前三个条件是死锁产生的必要条件，也就是说要产生死锁必须具备的条件，而不是存在这3个条件就一定产生死锁，那么只要在逻辑上回避了第四个条件就可以避免死锁。避免死锁采用的是允许前三个条件存在，但通过合理的资源分配算法来确保永远不会形成环形等待的封闭进程链，从而避免死锁。该方法支持多个进程的并行执行，为了避免死锁，系统动态的确定是否分配一个资源给请求的进程。方法如下：

1. 如果一个进程的当前请求的资源会导致死锁，系统拒绝启动该进程
2. 如果一个资源的分配会导致下一步的死锁，系统就拒绝本次的分配

显然要避免死锁，必须事先知道系统拥有的资源数量及其属性。
　　2、面向对象三大基本特性,五大基本原则
透切理解面向对象三大基本特性是理解面向对象五大基本原则的基础.

三大特性是：封装,继承,多态
　　所谓封装，也就是把客观事物封装成抽象的类，并且类可以把自己的数据和方法只让可信的类或者对象操作，对不可信的进行信息隐藏。封装是面向对象的特征之一，是对象和类概念的主要特性。 简单的说，一个类就是一个封装了数据以及操作这些数据的代码的逻辑实体。在一个对象内部，某些代码或某些数据可以是私有的，不能被外界访问。通过这种方式，对象对内部数据提供了不同级别的保护，以防止程序中无关的部分意外的改变或错误的使用了对象的私有部分。

　　所谓继承是指可以让某个类型的对象获得另一个类型的对象的属性的方法。它支持按级分类的概念。继承是指这样一种能力：它可以使用现有类的所有功能，并在无需重新编写原来的类的情况下对这些功能进行扩展。 通过继承创建的新类称为“子类”或“派生类”，被继承的类称为“基类”、“父类”或“超类”。继承的过程，就是从一般到特殊的过程。要实现继承，可以通过“继承”（Inheritance）和“组合”（Composition）来实现。继承概念的实现方式有二类：实现继承与接口继承。实现继承是指直接使用基类的属性和方法而无需额外编码的能力；接口继承是指仅使用属性和方法的名称、但是子类必须提供实现的能力；

　　所谓多态就是指一个类实例的相同方法在不同情形有不同表现形式。多态机制使具有不同内部结构的对象可以共享相同的外部接口。这意味着，虽然针对不同对象的具体操作不同，但通过一个公共的类，它们（那些操作）可以通过相同的方式予以调用。

五大基本原则
单一职责原则SRP(Single Responsibility Principle)
是指一个类的功能要单一，不能包罗万象。如同一个人一样，分配的工作不能太多，否则一天到晚虽然忙忙碌碌的，但效率却高不起来。

开放封闭原则OCP(Open－Close Principle)
一个模块在扩展性方面应该是开放的而在更改性方面应该是封闭的。比如：一个网络模块，原来只服务端功能，而现在要加入客户端功能，
那么应当在不用修改服务端功能代码的前提下，就能够增加客户端功能的实现代码，这要求在设计之初，就应当将服务端和客户端分开，公共部分抽象出来。

替换原则(the Liskov Substitution Principle LSP)
子类应当可以替换父类并出现在父类能够出现的任何地方。比如：公司搞年度晚会，所有员工可以参加抽奖，那么不管是老员工还是新员工，
也不管是总部员工还是外派员工，都应当可以参加抽奖，否则这公司就不和谐了。

依赖原则(the Dependency Inversion Principle DIP) 具体依赖抽象，上层依赖下层。假设B是较A低的模块，但B需要使用到A的功能，这个时候，B不应当直接使用A中的具体类： 而应当由B定义一抽象接口，并由A来实现这个抽象接口，B只使用这个抽象接口：这样就达到了依赖倒置的目的，B也解除了对A的依赖，反过来是A依赖于B定义的抽象接口。通过上层模块难以避免依赖下层模块，假如B也直接依赖A的实现，那么就可能造成循环依赖。一个常见的问题就是编译A模块时需要直接包含到B模块的cpp文件，而编译B时同样要直接包含到A的cpp文件。

接口分离原则(the Interface Segregation Principle ISP)
模块间要通过抽象接口隔离开，而不是通过具体的类强耦合起来

　　3、win32 api的有：VirtualAlloc()，HeapAlloc()等，是从全局堆中申请的空间。
C run-time的有：malloc()等，也是在全局堆中申请的（没读过MSCRT的源码，有可能是用Win32 API中的函数批发一大块，再零售给应用程序玩的）。
new和delete是C++语言的，取决于编译器的实现，通常也是在全局堆申请的。

第二大题

　　1、这题其实可以用 胜利树 来实现，两个结点比较，赢了的人进入下一次比赛，经过几番较量就可以得到冠军，主要是要想想多余的那一个选手如何处理，必然要在第一次决出冠军后加入比赛组。

　　2、这道题让人一看觉着非常有趣，但又让人感觉很复杂，其实这道题，只要弄清三点，问题就迎刃而解了。

• 对于每盏灯，拉动的次数是奇数时，灯就是亮着的，拉动的次数是偶数时，灯就是关着的。
• 每盏灯拉动的次数与它的编号所含约数的个数有关，它的编号有几个约数，这盏灯就被拉动几次。
• 1——100这100个数中有哪几个数，约数的个数是奇数。我们知道一个数的约数都是成对出现的，只有完全平方数约数的个数才是奇数个。

所以这100盏灯中有10盏灯是亮着的。
它们的编号分别是： 1、4、9、16、25、36、49、64、81、100。
参考自：http://gzcsl.blog.163.com/blog/static/4103020088244441761/
实现

#include <stdio.h>
#define NUMBER 100

void run(){
	char bulb[NUMBER];
	int i = 0;
	int j = 0;

	for(i = 0; i < NUMBER; i++){
		bulb[i] = 1;
	}

	for(i = 1; i < NUMBER; i++){
		for(j = 0; j < NUMBER; j++){
			if((j + 1) % (i + 1) == 0){
				if(bulb[j]){
					bulb[j] = 0;
				}else{
					bulb[j] = 1;
				}
			}
		}
	}

	for(i = 0; i < NUMBER; i++){
		if(bulb[i]){
			printf("%d\t", (i + 1));
		}
	}

}

int main(){
	run();
	return 0;
}

　　3、这个其实也可以用胜利树来实现，如何解法详见本博客 数据结构：胜者树与败者树 里面的代码

第三大题

　　这道题其实和编程之美上面的一道题很类似，可以用字典树来解决。对每个姓名的连起来的汉语拼音求出其后缀的子字符串集和，遍历整个通讯录，建一个字典树，同时将满足parent的条件的所有的姓名保存至该tiretree的节点上，这样的话，如果匹配到了某个字符，我们就能根据其子节点保存的所有姓名即当前部分匹配的所有联系人，来得出结果。对电话号码可以采用同样的方法。

参考自：http://www.chingnotes.com/?p=57