大四了，出国的出国了，保研的无忧无虑了，考研的天天自习，找工作的到处奔波。时间越久，越来越发现心仪的工作不是那么好找。不是你觉得工资少不想做，就是工资高的自己又拿不下来。

最近先后去了应聘了腾讯和百度，先说结果，腾讯没戏了，百度还没消息（不过估计也悬）。之前我一直在忙 Activity 的项目，虽然敲代码速度见长，但是根本没有看书复习准备笔试面试，果然腾讯笔试之后就觉得惨不忍睹，腾讯也是，全考C/C++，几乎不见Java，无奈我最近接触的全是Java，C/C++好久都没接触过了，笔试回来当晚就恶补了C++，这里推荐一本不错的书，《高质量C++编程》是林锐博士写的，里面全是C++的易错点，个人觉得十分不错，林锐在前言里写到，“书的最后有一道测试题，建议你在看书之前先独自做一做这些题，如果你能得满分，请允许我叫你师傅。。” 瞧这口气，可见是多么容易出错。

后来百度笔试，虽然全是大题（腾讯除了附加题全是选择题。。），但不限制你用 C/C++、Java，你哪个熟悉用哪个。有个一部分还是二选一，主要方向是 Android 和 Web，我选的Android的题， 都是些基础概念题，什么四大组件啊，AndroidManifest.xml啊，Activity的生命周期啊、启动模式啊，之类的。考完下来，就觉得笔试应该没问题。果然一天过后，收到面试通知。

面试在昨天，下午3点。去的时候还不紧张，等到了那里，坐了一会儿忽然叫到我的名字，意识到我马上要面试了，就有点紧张起来了。不过面试的时候又放松了下来，一是面试官人还不错，挺年轻的，叫我不要紧张，二是面试起来根本没有时间去想紧张这回事儿好么！刚开始聊得挺愉快的，跟我讲什么Android刷机啦，Android和IOS的差异啦，做过的项目啦，都没什么问题。最后面试官开始出题了，求二叉树的深度，其实用递归实现挺简单的，例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

int GetDepth(TreeNode *pTreeNode)
{
      // if it is empty
      if( !pTreeNode )
            return 0;

      // get the depth of left sub tree
      int left = GetDepth(pTreeNode->m_pLeft);
      // get the depth of right sub tree
      int right = GetDepth(pTreeNode->m_pRight);

      // return the larger
      return (left > right) ? (left + 1) : (right + 1);
}

看看我当时脑抽写的…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

int left = right = 0;

int GetDepth(TreeNode *pTreeNode)
{
    if (pTreeNode->hasLeft() )	
	{
		left++;
		GetDepth(pTreeNode->m_pLeft); 
	}

    if (pTreeNode->hasRight() )	
	{
		right++;
		GetDepth(pTreeNode->m_pRight); 
	}

    // return the larger
    return (left > right) ? (left) : (right);
}

最后一个问题，1T数据，无序，求中位数。第一反应是不该用排序，但我实在想不出来了。。研究中。。

update:
海量数据，无序，求中位数的问题。我在后来发现腾讯笔试以前出过类似的题目：

“只有2G内存的 PC 机，在一个存有10G个整数的文件，从中找到中位数，写一个算法。”

网上比较靠谱的解答是，“假设整数是int 2^32, 然后把整数分成 2^16 个块，每块包含2^16 个数， 也就是 0~65535、65535~* 这些块。
然后把数据从头到尾走一遍，就可以知道中位数在哪一个块中了；
然后再把数据从头到尾走一遍，就可以知道中位数是哪个数。”

update2:
//求二叉树深度的非递归算法。PS：对深度的定义貌似不统一，一般定义为，根节点的深度为1。来自：kiwi’s garden

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  };
 
struct denode  
{  
    TreeNode* node;  
    int degree;  
}; 

class Solution {
public:
    int maxDepth(TreeNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
     
    if (root == NULL)
    	return 0; 
        
    queue<denode> que;  
      
    denode dnode;  
    dnode.degree = 1;  
    dnode.node = root;  
  
    que.push(dnode);  
  
    int degree = 1;  
    while ( !que.empty() )  
    {  
        denode ptr = que.front();  
        que.pop();  
  
        degree = ptr.degree;  
  
        if (ptr.node->left != NULL)  
        {  
            denode p;  
            p.node = ptr.node->left;  
            p.degree = ptr.degree+1;  
            que.push(p);  
        }  
  
        if (ptr.node->right != NULL)  
        {  
            denode p;  
            p.node = ptr.node->right;  
            p.degree = ptr.degree+1;  
            que.push(p);  
        }  
    }  
    return degree;   
        
    }
};