2013年网易春季实习生招聘笔试题目

人生充满了各种杯具。昨晚网易2013年实习生招聘，来的有点仓促，me 后悔当初报的“Java服务器端开发”，而不是“C++开发” (当时 me 也么看到，O__O"…)。基础题目都是一样的，然后 C++ 和 Java 做不同的试卷，Java 试卷上又分为“Java开发/服务器开发/...”、“分布式/...”、“推荐算法/...”等。

me 做的是基础题目和服务器开发两大块内容，分布式的看了3道题，过后有个童鞋问了 me 3道 C++ 的题(听说是笔试题)。下面是大致的题目，以及一些分析或是 me 的一些结果，很多细节记不大清了。

基础题目(必做)

a,b,c,d 顺序入栈，可能的出栈情况有：(略)
分析：栈，后进先出 (LIFO)的数据结构；此题目简单，脑子中模拟一下过程基本就出来勒；
如果问，一共可能的出栈情况，应该是C4=14种，是catalan数；前5个Catalan数：1,2,5,14,42；(从1开始计数，实际上C0=C1=1；)
T=A+B*(C-D)/E 的后缀表达式：(TABCD-*E/+=)
分析：后缀表达式先写操作数后写操作符，比如 A+B 是中缀，后缀表示是：AB+；C-D/E 是中缀，后缀表示是：CDE/-；
优点：省去了使用括号来改变运算符的优先级；
排序算法中哪些是非稳定排序？(略)
分析：快速排序、堆排序和希尔排序是非稳定排序；
冒泡、简单选择排序和直接插入排序、归并排序是稳定排序；基数排序(me 不大了解)也是稳定排序；
关于时间复杂度：快速排序平均O(nlogn)，最坏O(n^2)；堆排序最坏O(nlogn)；归并排序最坏O(nlogn)，空间复杂度O(n)；
n个结点的四叉树，每个结点都有4个指向孩纸的指针，问空指针有多少个？
分析：每个结点 4 个指针，一共 4*n 个指针，然后有些指针指向实际的结点，一共有 (n-1) 条边，每一条边会“消灭”一个指针，所以空指针的数目：
4*n-(n-1) = 3*n+1；
一个C语言的按位运算题目，涉及到按位与 (&) 和移位(>>)。me 没有做，赶脚可能会繁琐。( 也许 me 错了，O__O"…)
分析：无；
进程线程的比较：(操作系统的有些东西是“公说公有理，婆说婆有理”。)
分析：线程是调度的基本单位，而进程是资源分配和管理的基本单位；
进程之间有 IPC(InterProcess Communication) 通信，同一个进程中的所有线程共享进程的空间；
线程之间是否可以IPC，me 不清楚 ! 进程是否也可以共享内存空间？应该可以，但是这种共享又不像线程之间的共享。
段页式存储管理：一个进程对应一张段表还是多张段表，一张段表对应多张页表还是一张页表？
分析：%>_<%，me 貌似答错了！一个进程多个段，但只需要一张段表，根据段号找到对应的页表；实际上一个进程有一张段表和多张页表。
传输层：TCP建立连接的状态变化
分析：me 表示不会，对，就是不会 !
数据库关于键、索引的问题：
分析：主键是否可以为NULL ？(No! 不过听说有些数据库的设计，比如 sql server/sqlite 主键可以为空) ；
一张表的外键是否必须是另外一张表的主键？(me 赶脚是no！) 索引会影响访问速度，会不会影响插入？(会！)
数据库：表示me题目都不懂，%>_<% ! (关于事务的，不能重复读 ? 肿之，搞不清楚 !)
分析：无；
写个求斐波那契数列的程序，估计算法复杂度，要求不超过O(n^2)。
1. int F ( int n )
2. {
3. if (n == 1 || n == 2 ) return 1 ;
5. int ans = 0, pretwo = 1, preone = 1 ;
7. for ( int i = 0 ; i <n - 2 ; i ++ ) { // 迭代 n-2 次
8. ans = pretwo + preone ;
9. pretwo = preone ;
10. preone = ans ;
11. }
12. return ans ;
13. }
时间复杂度为 O(n)，空间复杂度 O(1)；

Java题目(开发/服务器开发等)：

问一个 Java 程序的执行结果：主要涉及类中的变量的初始化顺序
分析：me丫梨大丫，Java 类中的变量的初始化顺序是怎么样的？有普通变量、有静态变量、有构造函数，还有个继承关系在里面，O__O"… 下面是 me 自己写了个类似的程序，有兴趣的可以猜一猜答案：
1. class Base {
2. private int a ;
3. private int b = echo ( ) ;
4. public Base ( ) {
5. System. out. println ( "Base.constructor." ) ;
6. System. out. println ( "Base.a == " +a + ", Base.b == " + b ) ;
7. }
8. public static int echo ( ) {
9. System. out. println ( "Base.echo." ) ;
10. return 2 ;
11. }
12. private static int s ;
13. static {
14. System. out. println ( "Base.static." ) ;
15. }
16. }
18. class Derive extends Base {
19. private int a = echo ( ) ;
20. public Derive ( ) {
21. System. out. println ( "Derive.constructor." ) ;
22. System. out. println ( "Derive.a == " +a + ", Derive.b == " + b ) ;
23. }
24. private static int b ;
25. public static int echo ( ) {
26. System. out. println ( "Derive.echo." ) ;
27. return 3 ;
28. }
29. static {
30. System. out. println ( "Derive.static." ) ;
31. }
32. }
34. public class Hello {
35. public static void main ( String [ ] args ) {
36. System. out. println ( "main.start." ) ;
37. Derive d = new Derive ( ) ;
38. }
39. }
执行结果：
```
main.start.
Base.static.
Derive.static.
Base.echo.
Base.constructor.
Base.a == 0, Base.b == 2
Derive.echo.
Derive.constructor.
Derive.a == 3, Derive.b == 0
```
根据情况选择适当的集合类(容器类)：
说有10个聊天室，每个聊天室1000人，问根据情况应该选择神马样的容器(集合)？
(1) 经常顺序地向群中的人发送通知信息；(me: ArrayList)
(2) 经常添加人，而且要保证名字的有序；(me: TreeMap，不过貌似不对 !)
(3) 经常加人，经常踢人，保证按添加的先后有序；(me: LinkedList)
(4) 经常查找某个人是否在聊天室中；(me: HashMap，不确定对不对 !)
根据给的几个函数，写出快速排序的基本思路，不需要符合Java的语法。me的答案：
1. qsort (list )
2. {
3. if (empty (list ) ) return ; // 空list，直接返回
5. a = get (list, 0 ) ;
6. left = extract (list, {it <a } ) ;
7. right = extract (list, {it >a } ) ;
9. qsort (left ) ; // 递归排序左侧
10. qsrot (right ) ; // 递归排序右侧
12. list = link (left, [a ] ) ; // shit! 当时忘记对 a 加 [] 勒
13. list = link (list, right ) ;
14. }
注：get/extract/link 都有提供，但是没有提供 empty 函数，me 表示有点诧异！(难道要自己写？O__O"…)
分析JVM对内存的管理以及和垃圾回收器之间的关系。
me：乱搭一通，主要说栈和堆；
写一个多线程程序：有三个线程，线程的 id 的分别是0、1、2，线程执行是打印 3 次自己的 id，程序输出结果是 012012012；
分析：创建三个线程简单，但是如何同步，让三个线程顺序执行才是问题的重点。me 想起来操作系统讲过“信号量”介个东西，用一个初始值为0的信号量可以同步两个进程(此处为线程)的执行，比如让A执行完释放信号量，B执行前获取信号量，便可以实现先A后B的执行。有了思路，网上搜了一下信号量 Semaphore 这个类，就写成了程序。(Java me 不熟，代码结构赶脚有些怪。)
1. package test ;
3. import java.util.concurrent.Semaphore ;
5. class TestRun implements Runnable {
6. Semaphore [ ] sems = null ; // 同步线程的信号量
7. public TestRun ( int id, Semaphore [ ] sems ) {
8. this. id = id ;
9. this. sems = sems ;
10. }
11. public void run ( ) { // 线程执行顺序：0 --> 1 --> 2 --> 0 --> 1 --> 2 --> 0 --> 1 --> 2
12. try {
13. for ( int i = 0 ; i < 3 ; i ++ ) {
14. if (id == 0 ) { // id == 0 的线程，先获取 sems[2]，执行一遍循环释放 sems[0]
15. sems [ 2 ]. acquire ( ) ;
16. System. out. print (id ) ;
17. sems [ 0 ]. release ( ) ;
18. } else if (id == 1 ) { // id == 1 的线程，先获取 sems[0]，执行一遍循环释放 sems[1]
19. sems [ 0 ]. acquire ( ) ;
20. System. out. print (id ) ;
21. sems [ 1 ]. release ( ) ;
22. } else { // id == 2 的线程，先获取 sems[1]，执行一遍循环释放 sems[0]
23. sems [ 1 ]. acquire ( ) ;
24. System. out. print (id ) ;
25. sems [ 2 ]. release ( ) ;
26. }
27. }
28. } catch ( Exception e ) {
29. e. printStackTrace ( ) ;
30. }
31. }
33. private int id ;
34. }
36. public class Hello {
37. public static void main ( String [ ] args ) {
38. Semaphore [ ] sems = new Semaphore [ 3 ] ;
40. sems [ 0 ] = new Semaphore ( 0 ) ; // 此处必须是 0，让 id == 1的线程不能首先执行
41. sems [ 1 ] = new Semaphore ( 0 ) ; // 此处必须是 0，让 id == 2的线程不能首先能执行
42. sems [ 2 ] = new Semaphore ( 1 ) ; // 此处必须是 1，让 id == 0的线程首先能执行
44. TestRun [ ] tests = new TestRun [ 3 ] ;
45. Thread [ ] threads = new Thread [ 3 ] ;
47. for ( int i = 0 ; i < 3 ; i ++ ) {
48. tests [i ] = new TestRun (i, sems ) ;
49. threads [i ] = new Thread (tests [i ] ) ;
50. threads [i ]. start ( ) ;
51. }
52. }
53. }
一个数据库连接代码的找错，主要涉及异常处理！
问题出现在连接conn 和流 out 的关闭竟然放在 try 块中，应该放在 finally 块中。第二问是说异常处理的一般原则。
me 的答案：try 块中放置正常逻辑代码，catch块捕捉各种异常并进行适当分析，finally块中放置必须处理的操作，比如清理代码；

Java题目(分布式/客户端)

TreeMap 和 HashMap 神马区别？还有一问忘记勒；
分析：无；
分析一个单例模式程序的错误
1. class Singleton {
2. private Singleton single = null ;
3. public static Singleton getInstance ( ) {
4. if (single == null )
5. single = new Singleton ( ) ;
6. return single ;
7. }
8. }
1. class Singleton {
2. private Singleton ( ) { } ;
3. private static Singleton single = null ;
4. public static Singleton getInstance ( ) {
5. if (single == null )
6. single = new Singleton ( ) ;
7. return single ;
8. }
9. }
Java异常处理关键字 throws, throw, try, catch, finally 的意思；
分析：throw 用来主动地抛出异常；try 放置正常逻辑的代码；catch 根据类型捕捉各种异常并进行处理；finally 是有无异常都要执行的代码，通常放置清理代码，比如数据库连接的关闭；throws 声明函数将某些异常抛出去，本函数可以不处理而让函数的调用者处理。

Java题目(推荐系统)

100 亿个 url ，去掉重复的；
搜索框中的拼音转换为汉字；
常见推荐算法及其优缺点、评价方法；
设计一个推荐算法；

还有一些 Java 题，不过 me 就不知道了。

C++题目(非原题)

引用和常引用分析：
分析：引用，比如 int& 只能引用左值，也就是能取到地址的对象，比如 a (int类型) 但是不能引用常量 2，或是临时量比如 a+2；常引用，比如 const int& 就可以引用左值，也可以引用右值，也就是 const int& r = 2; 是合法的，const int& r = a+2 也是合法的。右值引用，是c++11 新添加的东西，已经算做引用的一种了，顾名思义，右值引用可以引用到 a+2 这样的右值，比如：int&& rr = a+2;具体的一些细节可以参看引用和右值引用。
函数重载：除了返回值不一样，其他都一样的两个函数，编译和运行会怎么样？
分析：函数调用，只根据函数名和参数个数、类型以及顺序匹配，如果除了返回值其他都一样，这是不合法的重载，程序编译通不过。
函数 void str(const char* s="hello,world")：试分析"hello,world"：
分析："hello,world"是函数 str 的默认参数，也就是函数 str 的调用可以不传递参数；"hello,world" 是个字符串字面量，实际占的内存大小是12个字节，虽然只有11个字符，其中有个字符串结束符'\0'；字符串结束符可以输出，虽然可能什么都看不到，对它的访问也是合法的，不会造成编译和运行上的问题。
C++类中变量的初始化顺序：
分析：me 也有些不大清楚，不过可以确定的一些是：构造函数的初始化列表在函数体之前执行；变量的初始化按照在类中声明的顺序进行初始化，跟初始化列表写的顺序无关；

原文链接：http://ilovers.sinaapp.com/drupal/article/2013%E5%B9%B4%E7%BD%91%E6%98%93%E6%98%A5%E5%AD%A3%E5%AE%9E%E4%B9%A0%E7%94%9F%E6%8B%9B%E8%81%98%E7%AC%94%E8%AF%95%E9%A2%98%E7%9B%AE

秒客网