学步园

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

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

基础题目(必做)

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

1. 问一个 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. }
   17.  
   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. }
   33.  
   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
   

2. 根据情况选择适当的集合类(容器类)：
   说有10个聊天室，每个聊天室1000人，问根据情况应该选择神马样的容器(集合)？
   (1) 经常顺序地向群中的人发送通知信息；(me: ArrayList)
   (2) 经常添加人，而且要保证名字的有序；(me: TreeMap，不过貌似不对 !)
   (3) 经常加人，经常踢人，保证按添加的先后有序；(me: LinkedList)
   (4) 经常查找某个人是否在聊天室中；(me: HashMap，不确定对不对 !)
3. 根据给的几个函数，写出快速排序的基本思路，不需要符合Java的语法。me的答案：
   1. qsort(list)
   2. {
   3.     if(empty(list)) return; //
      空list，直接返回
   4.  
   5.     a = get(list, 0);
   6.     left = extract(list, {it<a});
   7.     right = extract(list, {it>a});
   8.  
   9.     qsort(left);  
       // 递归排序左侧
   10.     qsrot(right);   //
       递归排序右侧
   11.  
   12.     list = link(left, [a]); //
       shit! 当时忘记对 a 加 [] 勒
   13.     list = link(list, right);
   14. }

   注：get/extract/link 都有提供，但是没有提供 empty 函数，me 表示有点诧异！(难道要自己写？O__O"…)

4. 分析JVM对内存的管理以及和垃圾回收器之间的关系。
   me：乱搭一通，主要说栈和堆；
5. 写一个多线程程序：有三个线程，线程的 id 的分别是0、1、2，线程执行是打印 3 次自己的 id，程序输出结果是 012012012；
   分析：创建三个线程简单，但是如何同步，让三个线程顺序执行才是问题的重点。me 想起来操作系统讲过“信号量”介个东西，用一个初始值为0的信号量可以同步两个进程(此处为线程)的执行，比如让A执行完释放信号量，B执行前获取信号量，便可以实现先A后B的执行。有了思路，网上搜了一下信号量 Semaphore 这个类，就写成了程序。(Java me 不熟，代码结构赶脚有些怪。)
   1. package test;
   2.  
   3. import java.util.concurrent.Semaphore;
   4.  
   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.     }
   32.        
   33.     private int id;
   34. }
   35.  
   36. public class Hello {
   37.     public static void main(