快手 C++ 后端研发一二三面面经

一面 1h

(1) 32 位机器，判断以下代码的输出：

int a = 0x1234;
char* p = (char*) &a;
*p == ?
*(p+1) == ?
*(p+2) == ?

int a = 0x00001234;
// 如果是大端序，地址从低到高存储为 00 00 12 34
// 如果是小端序，地址从低到高存储为 34 12 00 00
// 故输出为：
// 大端序：00 00 12
// 小端序：34 12 00

(2) 32 位机器，以下 a 是多少？

int a = (int)(((int *)0) + 4); // 16

(int *)0，相当于是一个 int 型指针，指向地址 0。
(int *)0) + 4 就是对一个 int 指针 + 4。指针每 + 1，相当于后移 n 字节，n 是这个指针指向的变量类型的字节数。这里是 int 指针，一个 int 4 字节，int* + 4 就是后移 16 字节。从地址 0 开始后移 16 字节，指向的地址变成 16。

等价于：

int* p = 0;
p = p + 4;
int a = (int)p; // 强制类型转换，读取 p 的值，即 p 指向的地址

(3) 请找出下面代码中的所有错误

• GetIntA 里参数应该是引用
• GetIntB 里应该返回 malloc 创建的变量的地址

void GetIntA(int *p) {
    p = malloc(sizeof(int));
    return;
}

int * GetIntB() {
    int kk;
    return &kk;
}

void main(void) {
    int *p;
    p = NULL; GetIntA(p); *p = 0x22;
    p = NULL; p = GetIntB(); *p = 0x33;
}

(4) 请找出下面代码中的所有错误。说明：以下代码是把一个字符串倒序，如“abcd”倒序后变为“dcba”

#include"string.h"
int main() { 
    char*src="hello,world"; 
    char* dest=NULL; 
    int len=strlen(src); 
    dest=(char*)malloc(len); 
    char* d=dest; 
    char* s=src[len]; 
    while(len--!=0) 
        d++=s--;  
    printf("%s",dest); 
    return 0;
}

改动后的代码（牛客网有原题）：

int main() {
    char* src="hello,world";
    char* dest=NULL;
    int len=strlen(src);
    dest=(char*)malloc(len+1); //
    char* d=dest;
    char* s=src+len-1; //;
    while(len--!=0) *(d++)=*(s--); //
    *d = '\0'; //
    printf("%s",dest);
    free(dest); // 
    return 0;
}

(5) 完全随机的抽取 50 人，求这 50 人发生生日冲突的可能性(2 个或更多的人生日相同)有多大？每年都按365天算。

• 思路：减去所有人都不是同一天生日的概率。上面的式子中，分母是所有人的可能的生日排列情况，分子是 50 个人不在同一天的排列情况
• 另一种思路：第二个人和第一个人生日不同的概率是 364/365，第三个人和前两个人生日不同的概率是 363/365，以此类推，和上面的公式一样。

(6) 用 C 语言写一个函数，把字符串里面的空格全部去掉，并返回删除的空格的个数，不允许新开辟空间，只能申请简单类型的自动变量。时间复杂度 O(n)：

int del_blanks(char* str) {
    int len = strlen(str);
    if (!len) return 0;
    int last = 0;
    for (int i = 0; i < len; i++) {
        if (str[i] == ' ') continue;
        str[last++] = str[i];
    }
    str[last] = '\0';
    return len-last;
}

其他问题：

• 哈希查找的原理
• 输入一个 url 到显示网页的过程（网络线程、dns、tcp 三次握手、https 四次握手、传输、解析渲染、对每个链接重复此过程、四次挥手；底层：tcp 拥塞控制流量控制、ip 路由、arp 解析）
• arp 表的更新方法

二面 40mins

• top k 问题，时间复杂度估计（快排 O(n)，堆 O(nlogk)，《剑指offer》原题）
• 生产者消费者问题，单线程与多线程的情况下分别怎么写？（不会，稀里糊涂做了 30 分钟后结束面试）

三面 1h

• 目前的 offer 情况，还面了哪些公司
• 这些公司如果都给你 offer，你会从几个维度进行选择？（地域，公司平台，未来发展，工作内容，薪资）
• Golang 为什么可以在函数里返回一个函数的地址，在函数外访问？（逃逸分析）
• 逃逸分析的原理（建议参考维基百科）
• 你用 Golang 的时候有没有遇到一些不好理解的地方（这里我说 err 只能一层层返回 / 没有泛型。然后面试官与我讨论为什么觉得这些特性是必须的）
• Golang 里返回一个 MyError 类型的 nil，可以用 err != nil 判断吗？（不可以，golang 中的 interface 是一个二元组 (type, value)）
• Golang 的 interface 的 type 和 value 是怎么保存的（不是很确定了）
• 动态 interface 和静态 interface 有没有听说过？（没有）
• Golang 的 slice append 扩容原理（slice 是一个指向数组的指针，对应的数组有一个容量 cap；如果 append 时 slice 的 cap 不足以容纳新元素，就会扩容）
• 扩容的时候是复制原数组的元素吗？（是）
• 这里会不会有一些问题？（不会，涉及到扩容细节和 golang 的内存分配，参考）

到这里一共 20 分钟。接下来是代码题。

(1) 判断以下代码的输出

char buf[4] = {0x12, 0x34, 0x56, 0x78};
*(short*) &buf[3] = ?

在内存中的存储：

地址：101 102 103 104 105
字节：12  34  56  78  ??

也就是 buf[3] 再往后就是其他变量的内存区域了。这时候用 *(short*) 读取从 buf[3] 开始的两字节，结果是 0x78??。

(2) 判断结果：

std::string str1 = "123";
std::string str2 = "3333333333";
sizeof(str1) ?= sizeof(str2)

相等，都是 8 个字节。这涉及到 std::string 的实现，内部存储的是指向实际字符串的指针。StackOverflow

(3) this 指针的问题，判断会不会 core：

class A {
 public:
  void print(int n) {
    std::cout << n << std::endl;
  }
};

int main(int argc, char **argv) {
  ((A*)0)->print(4);
}

main() 函数中将地址 0 强制类型转换为 A，然后调用它的 print() 方法。我理解是 print() 里没有用到 this，也就没有对地址 0 解引用，就不会触发异常。

可以了解下静态绑定和动态绑定，C++ 对于非虚成员函数是静态绑定，即不把它绑定到一个特定类型上。

(4) 以下代码会有什么后果？为什么？

char *TestFunc() {
   char buf[1024];
   buf[1026] = 3;
   ...
}

缓冲区溢出，可能会修改函数的参数 / 返回地址... 这里主要考察栈帧的内容：调用一个函数的时候会把哪些信息压倒栈里。推荐阅读《CSAPP》的第 3 章，对这部分内容描述的很清楚。

缓冲区溢出的检测方法（Canary、地址随机化等，同样在《CSAPP》中）。

(5) 海量数据找 topk（无法全部加到内存中）：用堆。

(6) 实现 Atoi，要求能处理溢出。这道题也被考了很多次，LeetCode 有原题，主要难点在于如果是 32 位机器该如何判断溢出。

总结

快手的面试体验和其他公司不一样，一二面问的几乎全是 C/C++ 的问题，很少问上层的网络协议等，我答得稀烂。感觉这个可能和部门的工作内容有关。三面的面试官很 nice，答错了会一步一步引导。