字节跳动C++面经

作者:从0开始学c
链接:https://www.nowcoder.com/discuss/128236
来源:牛客网

然后问算法,问了反转链表,要求空间复杂度o1,我在循环内用了一个局部指针变量,虽然不优雅,但是局部变量每次循环完都会被析构,他硬说我的空间复杂度是on。

然后问了虚函数,这是唯一问的c++,我感觉他也就会个虚函数了。

然后问找前k大的数。

我: 如果内存放得下的话,用类似快排的思想,partition把大的放左边,小的放右边,调用partition之后,如果分界元素等于k,则返回最左边的k个值;否则对k所在的半边递归调用parition,平均时间复杂度是on。

面试官(惊讶): 时间复杂度是on?

我: 是啊

面试官: 真的是么?

我: 是啊,假如每次分界完,平均下次要处理的元素占总元素数的a/b,那么时间近似是(1+a/b+(a/b)^2+…)n= b/a*n

面试官: 那我的k要是很大,接近n,你这个不就是n平方了么

我: a/b是平均下次要处理的元素占本次处理的总元素的比值,跟k无关

面试官: 那最坏时间复杂度是多少

我: on^2 当数组已经有序,每次处理完规模减少1。 如果你觉得这个方法不好,在内存放得下的情况下,那我们用堆做,建一个最大堆,建堆的时间复杂度是on,调整k次,调整一次的时间复杂度是ologn,一共是o(n+klogn)

面试官: 建堆的时间复杂度是on?

我: 有什么疑问么

面试官: 你确定?

我: 确定!

面试官: 你再想想?

我: 建堆是从最后一个非叶结点开始调整,倒数第二层最多有n/2个需要调整的元素,最多需要调整1次,倒数第三层最多有n/4个需要调整的元素,每个最多需要调整2次,以此类推,最后累加起来接近线性时间复杂度。

面试官: 额…

我: 换一种方法,如果数据比较大,内存放不下,可以用优先队列,实现也是堆。优先队列是用一个最大堆,我们求前k大要用最小堆,所以要重载小于号运算符,优先队列重载时候要指定底层容器,我一般指定的是vector。执行时候如果队列里面的元素少于k个,则直接插入;否则将该元素与top()比较,如果大则删掉top把这个元素放到队列中。

面试官:额..

我: 如果重复元素算一个,就用set,set是默认从小到大排列的,所以不需要重载运算符。

然后面试官没有回话,思考了一会,用“你会数据库么”结束了对算法的问询。在得知我不会数据库之后,面试官开始了他的主导,一直问数据库。我说,我不会数据库,要不你问问别的吧。然后他问我会网络么,我说曾经会一些,很久没用了,于是就问我tcp连接的终止,在我答完四次握手之后,问我服务器单方面终止链接之后,客户端继续发送数据会怎么样; 双方都终止了之后,客户端继续向服务器发送数据会怎么样。
如何处理get和post
tcp接收窗口和拥塞窗口
什么时候会向对端传窗口大小
extern C的意义
假设rtt(数据从两端一来一回) 100ms,那么从输入一个http://url到得到网页要多少时间
https呢?
连续发送两次http请求,会得到两次结果吗?可能第二次比第一次快吗?
是否了解TCP包头阻塞?
服务器状态502 503 504什么问题,怎么排查
netstat具体查看什么问题
写题:多路归并(用了堆,在细节上有一些问题)
看代码中的问题:
class Foo
{
public:
Foo(){_p = new int();}
~Foo() {delete _p; _p = nullptr;}
private:
int* _p;
}
sql:三句查询,要求建立索引来优化查询
一些linux语句的作用:less more sed awk du df dd at tee crotab xargs
最近看了什么技术书籍

二面
linuxIO模型,区别在哪
线程独立拥有哪些资源
协程和线程有什么差别,优势呢?
get和post有什么差别
sendfile的优势在哪?
代码:随机播放100首歌(洗牌算法/这个我把自己绕进去了,洗一次直接输出就完了,我当时脑子短路了,洗一次播一首非要再洗一次来手动提升复杂度,最后没绕出去,然后换题了)
两个倒序数组找最第k大的(框架差不多,最后发现漏了一种情况,感觉还在想洗牌的事情)

因为二面代码花了很久,最后没写完,当时心态有点崩,但给了三面

三面
三面没有写代码,问了一个小时,面试官全程半启发半追问,感觉有点懵,我把上下文相关的问题空格分段了

C/C++内存问题有哪些,尽量说
free和delete在具体实现上的差异
free之后的指针使用有什么问题
缓冲区溢出如何避免,有哪些场景
如何检查/处理越界
野指针和悬空指针分别是什么
试图使用野指针有什么问题
内存上还有别的问题吗?

C++11用过什么特性

之前讲的内存问题有什么好的方法吗?
智能指针讲一下
shared_ptr讲一下,怎么实现的,unique_ptr呢?
是不是所有要用指针的地方都应该用智能指针,有什么问题和不足?(我答了两次寻址和额外空间)
这些缺陷,在不用shared_ptr的前提下有减少成本的策略吗?(跳过了)

include,头文件里面一般放了些什么
声明和实现要写在一起吗?是不是一定要分开写?
写在一起和分开对最后的代码有什么影响,怎么确认(这个我不会,面试官让我试着分析一下,结合include的行为来谈)
gdb怎么查看一个函数的地址?
你在Linux使用经常哪些指令
如何探查CPU负载情况
在什么时候CPU被认为是繁忙/空闲的?

看过哪些比较大的代码?(后面很多问题是从这来的)

服务器:
多线程服务器和nginx在工作方式有什么不一样的地方
nginx怎么处理请求
进程唤醒(惊群问题)的额外成本主要在哪?
nginx的负载均衡(我只答了那个worker的负载均衡)
为什么它要用多进程,优势在哪,劣势在哪
多线程怎么应付同样的问题,能够解决吗,讲一讲方案
你的方案有什么问题?

http了解多少?
http缓存机制了解吗?
长连接讲一下
如何实现长连接(保活)
带外数据如何使用?
你的这个方法有什么问题,可以直接兼容不同的浏览器吗?
了解nginx的解决方案吗?

redis
你对redis怎么理解的?
redis的总体结构
单线程的优势和缺点
redis的事件分发
讲一讲文件事件有哪些
client功能是怎么实现的
时间事件(serverCron函数)
serverCron做了什么
redis所有事情都只有一个单线程吗?
bgsave讲一下,为什么要fork一个进程来做

interrupt与signal有什么差别
interrupt的发起和接受者是谁
操作系统在interrupt中发挥了什么作用
signal呢,发起者又是谁,接收者呢?(这里答得有点混乱)

TCP
ack什么时候发送,丢失了会怎么样?
sack了解吗?
重传ack的时机只有ack超时吗?
重复报文被接收会发生什么?
拥塞窗口要不要把自己的大小发给接收方,意义何在?(这个问题一面也问了,没有答出来)
延迟ACK的意义在哪?
为什么不能每次都直接发大的窗口?

进程地址空间布局讲一下
BSS为什么要叫这个名字?(后来查了,block started by symbol)
static关键字有什么作用,如果用来修饰函数呢?
多个线程使用static数据会开启多个副本吗?

C++OO
多重继承怎么实现
虚拟继承怎么实现
对于函数寻址在时间成本上有什么差异?
对于继承体系很复杂的情况这个成本会被拉高吗?

 

算法:
1. 两个相交的单链表,找出交点
2. 给一棵树,找出路径和为n的路径
基础:
1. static关键字
2. 在一个函数内定义一个static对象,什么时候构造和析构。如果这个函数从没被调用,会怎么被析构
3. tcp连接和断开
4. 服务器大量close_wait状态,可能是什么原因,怎么解决
一面还有很多问题的,忘了。。。
一面感觉:那个两个相加的单链表的算法,我提出的算法他没见过,然后我证明,然后balabala说的不好,然后跳了。。。
这也是一面唯一一个感觉面的不好的地方
二面:
1. 设计LRU cache,查找复杂的O(1), 过期淘汰
数据库:
2. 联合索引, 最左匹配
3. 假如有联合索引<a,b>,查询where a=xx and c == yy,会用到联合索引么 为什么
4. 如果数据库主键是单调严格递增的,有一个图片,通过url带上id访问,然后查询数据库,会有什么影响
5. 上面那个问题,引出一个情景题,如何设计一个序列生成器,能够单调递增,但是不是严格递增的 ?保存在内存中,宕机怎么办?多个进程怎么办?
这个问题和面试官聊了很久,因为我在微信这边不久前看到过序列生成器
6. 解决并发情况下,使序列生成器生成的id唯一。还有就是在分布式系统,多机服务器怎么办?
7.
long multiply(int m,int n) {
long score;
score = m * n;
return score;
}
这段代码会有什么问题? 然后就说了一下m*n溢出
8.
请问下面的程序一共输出多少个 “-”?,执行一次下面的程序,总共生成了多少个进程?
#include <stdio.h>
#include <sys/types.h>
#include <unistd.h>
int main(void) {
int i;
for(i=0; i<2; i ) {
fork();
write(1, “-“, 1);
}
wait(NULL);
wait(NULL);
return 0;
}
我说了6次,然后解释了一遍
9. 然后说把write换成printf会多少个’-‘, 我算了一下,说8次,原因是printf是有缓存的
10. c语言程序的内存模型
11. 聊redis , 如果内存已经很多键了,会怎么样?然后说了一下cow 还有balabala
还有一些小问题完了
二面总结:最后的redis因为时间不够,然后面试官说结束了。感觉二面面的挺好的,和面试官聊的也很多
三面:
三面一看就是大佬,他一直在看我的简历,开始那7分钟,大家一句话都没说,很尴尬
1. 写sql
Sid:学号
Cid:课程编号
score:成绩
查询平均成绩大于 60 分的同学的学号和平均成绩
2.
void pass(){
}
int main( ) {
int x;
x = 123;
printf(“%d \n”,x);
pass();
printf(“%d \n”,x);
return 0;
}
// 123
// 456
他问在pass里面添加代码,使输出123和456
因为都在栈里面,有返回地址,占四个字节
void pass(){
int y;
int *addr = &y;
addr 加加  ;
addr加加   ;
*addr = 456;
}
大概思路是这样, 细节有待斟酌
算法题:
3.
随机数生成器:
float rand(); [0,1)
int rand5();
int rand7();
这个通过rand,然后写出rand5,最后写出rand7。面试官刚开始说rand返回[0,1),然后让我写代码验证,
我心里一凉,是不是写错了。果然跑的结果不对,然后现场debug,rand返回的是一个unsigned int,根本不是[0,1),
然后改好了
4. 写一个函数,N 个数字,找到其中第 K 大的数,要求平均时间复杂度尽量低。
我写出来后他让我算时间复杂度,时间复杂度一直没算对,还用了主定理。 作为一个理科生,最后时间复杂度要数列求和,没求出来,很惭愧
5.http状态码
tcp的连接,怎么用udp模拟tcp
数据库索引了解吗(b 树)
那为什么用b 树,有什么优点呢

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注