网易有道面经（2013校园招聘杭州站）

上机考试：

网易有道的筛选模式是先上机考试，然后根据上机考试选择大概1/3参加面试。上机的平台和ACM有点类似，提交代码然后有手动阅卷。

上机考试时隔比较久远，不过还能想起两个题目：

1. 给定一个点分IP地址表示，写个程序把它转换成相应的32位的无符号整数并输出，如果输入不是合法数据，就返回0.

这个题目如何利用好标准输入输出，其实可以很容易判断出不合法的输入用例，不过当时没有想好，导致这个题目没有AC。

后来回去写的代码如下：

1. #include <stdio.h>  
2. #include <string.h>  
3. bool checkpoint(char *str){ 
4.  
5.     int npoint = 0; 
6.     while(*str){ 
7.         (*str) == ‘.’ ? npoint++ : npoint; 
8.         if(*(str) != ‘.’ && !((*str) <= ‘9’ && (*str) >= ‘0’)) return false; 
9.         str++; 
10.     } 
11.     return npoint == 3; 
12. } 
13.  
14. bool checkinrange(int addr[4]){ 
15.     for(int i = 0; i < 4; i++){ 
16.         if(addr[i] > 255){ 
17.             return false; 
18.         } 
19.     } 
20.     return true; 
21. } 
22. bool convertIP(char s[], int addr[4]){ 
23.     char tmp[128]; 
24.     if(checkpoint(s)){ 
25.         sscanf(s, “%d.%d.%d.%d”,addr, addr + 1, addr + 2, addr + 3); 
26.         sprintf_s(tmp, sizeof(tmp), “%d.%d.%d.%d”, addr[0], addr[1], addr[2], addr[3]); 
27.         if(strcmp(s, tmp) == 0 && checkinrange(addr)){ 
28.             return true; 
29.         } 
30.  
31.         //sprintf_s()  
32.     } 
33.     return false; 
34. } 
35. int main() 
36. { 
37.     char s[128] = {0}; 
38.     int addr[4]; 
39.      
40.     while(scanf(“%s”, s) != EOF){ 
41.         memset(addr, -1, sizeof(addr)); 
42.         if(convertIP(s, addr)) 
43.         { 
44.             unsigned int result = 0; 
45.             result = addr[0] * (0x1 << 24); 
46.             result += addr[1] * (0x1 << 16); 
47.             result += addr[2] * (0x1 << 8); 
48.             result += addr[3]; 
49.             printf(“%u\n”, result); 
50.         } 
51.         else{ 
52.             printf(“-1\n”); 
53.         } 
54.  
55.     } 
56.  
57.     return 0; 
58. } 

2. 给出大小为N的数组，用最快的办法找出前M个大的数字

这个题目可以用一个大小是M的最小堆来实现，初始建堆用数组前M个建好后，如果后面的元素a[i] 大于堆顶元素，那么就删除堆顶，插入新的元素。

1. #include <queue>  
2. #include <vector>  
3. using namespace std; 
4.  
5. int main(){ 
6.  
7.     priority_queue<int,std::vector<int>, std::greater<int>> q; 
8.  
9.     int n,m; 
10.     int num; 
11.     scanf(“%d%d”, &n, &m); 
12.  
13.     int i; 
14.     for(i = 0; i < m; i++){ 
15.         scanf(“%d”, &num); 
16.         q.push(num); 
17.     } 
18.  
19.     for( ; i < n; i++){ 
20.         scanf(“%d”, &num); 
21.  
22.         if(num > q.top()){ 
23.             q.pop(); 
24.             q.push(num); 
25.         } 
26.     } 
27. } 

一面：

面试官是一个看起来比较技术的MM，MM上来什么也没有问，直接来算法。

题目1. 一个人在网上做项目，加入每天都有很多项目可以选，每个项目都有一个开始时间和截止时间，假设每个项目的钱是一样的，那么在n天内，如何安排自己的接活才能保证赚钱最多。

问题简化后就是贪心的活动安排问题， 传送门： http://www.linuxidc.com/Linux/2012-10/72404.htm

然后证明（想半天，没有想出来）

问题2. 假如这个时候，每个活的钱数是不同的，可以获得最大的钱数是多少？

（我给的答案是枚举任务，然后做dp）

写代码….

1. #define MAX_TAST 100  
2. struct Task{ 
3.     int s, e; 
4.     int val; 
5. }; 
6.  
7. bool TaskInRange(const Task &t, int s, int e){ 
8.     return t.s >= s && t.e <= e; 
9. } 
10.  
11. int dp[MAX_TAST][MAX_TAST]; 
12. int nTask; 
13. Task aTask[MAX_TAST]; 
14. int GetMaxValue(int s, int e){ 
15.  
16.     if(dp[s][e] != -1){ 
17.         return dp[s][e]; 
18.     } 
19.     if( s == e){ 
20.         return dp[s][e] = 0; 
21.     } 
22.     int maxvalue = 0; 
23.     for(int i = 0; i < nTask; i++){ 
24.         if(TaskInRange(aTask[i], s, e)) 
25.         { 
26.             int value = GetMaxValue(s, aTask[i].s) +   
27.                         GetMaxValue(aTask[i].e, e) + 
28.                         aTask[i].val; 
29.             if(value > maxvalue){ 
30.                 maxvalue = value; 
31.             } 
32.         } 
33.     } 
34.     return dp[s][e] = maxvalue; 
35. } 

然后她问我如何优化，我说可以先把任务排序，然后搜索到合适的任务岂止点，将枚举从O(n)降低到O(logn).

二面：

二面先聊自我介绍，简要介绍之前做的项目

问题1. 写代码：判断一个数字序列是BST后序遍历的结果，下面是我现场写的代码，没有测试过

1. bool IsPostOrderOfBST(int array[], int low, int high) 
2. { 
3.     if(low >= high){ 
4.         return true; 
5.     } 
6.     int split = -1, i; 
7.  
8.     for( i = low; i < high; i++){ 
9.         if(split != -1 && array[i] < array[high]){ 
10.             return false; 
11.         } 
12.         if(split == -1 && array[i] > array[high]){ 
13.             split = i; 
14.         } 
15.     } 
16.     if(split == -1){ 
17.         return IsPostOrderOfBST(array, low, high-1); 
18.     } 
19.     return IsPostOrderOfBST(array, low, split-1) && IsPostOrderOfBST(array, split, high-1); 
20. } 

问题2. 写一个单件模式，然后顺便被我引导到扯扯 线程安全 异常安全等话题，我不断完善最初代码使得满足线程安全和异常安全。

下面的代码大概是最初版本：

1. #include <stdio.h>  
2.  
3.  
4. class Singleton{ 
5.  
6.  
7. private: 
8.  
9.     Singleton(){} 
10.     Singleton(const Singleton &); 
11.     Singleton& operator=(const Singleton&); 
12.  
13. public: 
14.  
15.     static Singleton *Instantialize(); 
16.     static Singleton *pInstance; 
17. }; 
18.  
19. Singleton* Singleton::pInstance = 0; 
20. Singleton* Singleton::Instantialize(){ 
21.  
22.     if(pInstance == NULL){ 
23.         pInstance = new Singleton(); 
24.     } 
25.     return pInstance; 
26. } 

然后大概扩展到如下形式：

1. class Lock{ 
2. private:         
3.     CRITICAL_SECTION &m_cs; 
4. public: 
5.     Lock(CRITICAL_SECTION cs):m_cs(cs) 
6.     { 
7.         m_cs.lock(); 
8.     } 
9.     ~Lock() 
10.     { 
11.         m_cs.unlock(); 
12.     } 
13. }; 
14.  
15. class Singleton{ 
16. private: 
17.     Singleton(); 
18.     Singleton(const Singleton ); 
19.     Singleton operator = (const Singleton &); 
20.  
21. public: 
22.     static Singleton *Instantialize(); 
23.     static Singleton *pInstance; 
24.     static CRITICAL_SECTION cs; 
25. }; 
26. Singleton* Singleton::pInstance = 0; 
27. Singleton* Singleton::Instantialize() 
28. {       if(pInstance == NULL){//double check  
29.     Lock lock(cs);//用lock实现线程安全，用资源管理类，实现异常安全  
30.     if(pInstance == NULL) 
31.     { 
32.         pInstance = new Singleton(); 
33.     }} 
34.     return pInstance; 
35. } 

问题3 对C++ virtual的理解 . 我从实现角度给他说了  虚函数和虚继承

问题4 如果有一个websever，例如12306，用户量特别大，网站面临效能问题，如何解决。

我先胡扯了线程池，然后又扯到多个机器搞这个问题等等

最后问一下我对什么感兴趣，他给我介绍了有道云笔记。

总结：

和很多人分享了一些面试题目，感觉我面试的题目难度是比较水的，感觉其他同学面的都很难。有道说十一以后还会安排三面，是技术总监面试，估计也是终面了吧~