腾讯-后台开发-1面

2020/03/11 14:00-14:50

本来投的是平台型产品经理（技术背景），不知道为什么被后台开发捞走了。

其实我是想做开发的，现在技术不够，投个产品经理试试。

面试官打电话来问我面后台开发有没有兴趣，都打过来了，那肯定面啦。

面试开始：

首先面试官给我抛了两道题：（1）毒牛奶；（2）赛马。

后来才知道是很经典的面试题，但是面试过程中完全是新鲜玩意儿。

（1）毒牛奶：若干桶牛奶，其一有毒，老鼠试之，请快且少鼠地找出毒奶。

我给的回答是，直接当作二分查找做，每一天都把牛奶等分成两部分，让老鼠喝掉其中一部分。如果中毒了，第二天把这批牛奶等分，重复上述步骤；如果没有中毒，那就取另一批牛奶等分，重复上述步骤。

所以时间复杂度应该是O(log₂N)。

然后面试官问我，如果要求第二天就知道哪个是毒牛奶，用的老鼠不限，那怎样做才是使得用的老鼠最少呢？

这我就不知道了，直接回答了N只老鼠。。。。这肯定是不对的。

但其实还有更好的方法：把N变成二进制，二进制有几位就用几只老鼠。假设N=8，则变成二进制就是：

0001

0010

0011

0100

0101

0110

0111

1000

如此一来，让一号老鼠喝二进制第一位为1的牛奶，也就是1，3，5，7；N号老鼠喝二进制第N位为1的牛奶。这样子第二天把这些N号老鼠放到其第N位的二进制上，就知道哪个牛奶有毒了。

（2）赛马：有25匹马，5个赛道，不能计时，用最少的场次找到跑最快的前三名。

这题答得实在磕磕绊绊，面试官提示了好几次，慢慢引导，才回答准确并且比较接近答案，但仍然不是最好的。

我的回答是这样的：首先25匹马分成五组，五组跑下来，我就可以把每组的第一名组织在一起称为A组（A1，A2，···，A5），每组第二名组织在一起称为B组（B1，B2，···，B5），······，每组第五名组织在一起称为E组（E1，E2，···，E5）。这时候已经跑了5场了。

然后A组跑1场，找到第一名。然后让第一名所在那组的第二名与A组剩余的四匹马跑，找到第二名。然后按照同样的方法，再跑一场，找到第三名。所以一共需要5+1+1+1=8场。

实际上可以做得更好，关键是第六场开始如何处理：

第六场也是让A组跑，找出最快的第一名。然后，关键来了！这时候其实有部分马是不需要跑的，可以直接淘汰的.

A1 A2 A3

B1 B2 B3

C1 C2 C3

D1 D2 D3

E1 E2 E3

假设A1是最快的，那实际上就剩下加粗的那五个有机会进入2，3名。其余的马都可以扔掉了。加粗这5匹马正好组在一起赛一场。

所以，只需要5+1+1=7场比赛。

其实面试官问我还能不能更少场次的时候，我要是更冷静点应该还是能答上来的，被提示太多次了有点着急了。唉。

接下来就问项目相关了。

因为是后台开发，所以抓住校车小程序问我。但因为我不是做后台的，所以我直说，除了后台，其他都是我做的。对于面试官提问的Linux，数据库，C++开发，我都表示不是很懂。

实际上不应该这样回答的，应该说我做了什么，而不是“其他都是我做的”。

所以面试官就问了我linux里进城通信都有哪几种方式，答案是：

1. 管道(pipe)，
2. 命名管道(FIFO)，
3. 内存映射(mapped memeory)，
4. 消息队列(message queue)，
5. 共享内存(shared memory)，
6. 信号量(semaphore)，
7. 信号(signal)
8. 套接字(Socket）

详情戳这里复习吧：

最后面试官给了道编程题：求树的深度。

我用递归做的，但是忘了检查根节点是否位空。这个一定要记住啊！

struct TreeNode
{
    int val;
    struct TreeNode * left, * right;
};

int depth(const struct TreeNode *root){
    if(root == NULL){
        return 0;
    }
    else{
        int depth = 1;    
        depth = goDeep(root);
        return depth;
    }

}
int goDeep(TreeNode *p){
    if(p != NULL){
        int left_depth = 0;
        int right_depth = 0;
        left_depth = goDeep(p->left);
        right_depth = goDeep(p->right);
        if(left_depth >= right_depth){
            return left_depth+1;
        }
        else{
            return right_depth+1;
        }
    }
    return 0;
}

他还问我不用递归怎么写，这个不知道了，等过两天复习到树的时候这里补上：

结果：最终挂了。难受。但至少比18年暑假的面试有进步了，继续努力吧。

：(     

T_T