双非大三狗
3月末面试的百度，面的C++研发，第一天一面+第二天（二面+三面），两天进行的比较快（get offer）
时间过去一个月了，所以有点题和回答记得不是特别清楚，因为也面试了一些小公司，回答可能记混，但是大致都差不多
百度C++研发一面
1:指针（各种指针，指针数组，数组指针，函数指针，n级指针）
2:char *a=new
char a[]
sizeof(a)大小
3:静态动态数组区别
4:new delete new[] delete [] malloc free底层实现
5:192.168.100.1 怎么存储
6:overlode override
7:unsigned long* p1=(unsigned long* )0x810000(地址)
unsigned char* p2=(unsigned char* )0x810000(地址)
p1+5=? p2+5=?
8:实现atoi（带无效字符）
9:快排思想
10:1000万个数，取出top100
可以堆实现和二分
11：两个杯子+50个红球+50个黑球，将100个球放入两个杯子，保证取出红球概率大的方法
12：tcp四次挥手过程
13:linux select poll epoll
14:怎么查看进程（ps aux）
15:time命令
16:vim一些操作
17:gdb操作
18:大端小端问题，intel主机是什么模式
19:32位平台上内存对齐的问题
C++研发二面
1：爬虫项目
2：守护进程，libevent
3：poll epoll select
4：为什么select有文件句柄限制，poll epoll没有
5：网络聊天项目
聊天用什么协议（UDP），问什么使用UDP
微信qq用什么协议
6：跟多个人聊天怎么实现的（多线程），多线程怎么判断和哪个人聊天，需要设置什么全局变量
7：这里用到什么IPC(文件映射)
8：进程线程区别联系，多线程多进程
9：多线程有什么危险（加锁）
多线程中如果一个线程崩掉会不会造成整个进程的死亡
10：如果多线程一个线程没有释放锁，会造成什么情况，
11：如果多线程一个线程没有释放锁，那么他和单线程相比是否就没有优势了
12:TIME_WAIT状态
13：长连接短连接
14：如果利用短连接，大量线程同事访问服务器会产生什么后果，如果短连接，一次发送了大量的数据会产生什么后果
15：Hadoop，redis，大数据，云计算了解不？（不了解）
16：线程里面有什么资源，都有什么用处
17：如果一个人在公路上半小时遇到车的概率是0.9，那么10分钟之内遇到汽车的概率的是多少
18：二分图问题，一个导游安排一堆旅客住宿，每一个旅客对每一个房间有自己的满意度，问怎么安排房间保证所有游客对导游的满意度最大（根据满意度建边，跑一边二分图匹配）
19：你有什么问题
c++研发三面
聊理想，谈感情，说故事
问我的博客记录些什么
最后问了点linux
（进程线程，僵尸，守护，孤儿）
,设计模式（单例模式懒汉饿汉，中介者模式）
，谈ACM经历
阿里巴巴 从3月底的一面断断续续到今天27号晚上已经进行了四面（我不知道为什么现在还在面试，正常应该结束了），不知道四面是否通过，
岗位也是c++研发
一面：
1:ACM经历，你刷过多少题？你们团队分工都是怎么样的?你最擅长哪些类算法?
2:topcoder,codeforge打了多少场，感觉怎么样
3:单源最短路你会哪些。说一下，时间复杂度都是多少？
dijska,spfa
4:dij能优化不？(堆优化和优先队列优化两种)
5:给你个图，已经源点和终点，问先从源点到终点，在从源点回到终点，最短路径怎么求?时间复杂度怎么样？
建立两个对称图搜索+标记+剪枝
还有什么方法?
跑一点最短路。另一遍进行搜索判断
6:vector内部元素内存不够了，内部怎么进行分配
7:mapset底层怎么实现的?插入删除复杂度怎么样
8:哈希表时间复杂度如何?冲突了如何解?
9:LRU模仿一下内部实现，实现insert函数（插入），get(获得头部元素，但是也相当于对头部进行查询)，?
最开始用O(N)静态数组复杂度模拟两个函数.
能优化不？用堆+map标记时间复杂度降低到log(n)
还能优化不？
get函数使用双向循环链表，只是更改指针，时间复杂度降为O<1>,insert没想法优化到1了。最低logn
阿里二面：
找不到了记录了，半个月前的了，但是我记得最后一个问题就是从一个栈中获得最大的元素（在线coding）借助辅助栈
阿里三面：105分钟
1:谈一下信号量吧？
ans:linux和windows的信号量都说了一下.
说一下具体怎么实现的？
说了一下怎么具体实现的，我把函数都说出来了
设计一个生产者消费者模型，通过queue，且有上限。
通过信号量设计了一下，顺便把条件变量也可以实现类似的功能说了一下
2：你对c++内存这里有什么见解，或者有什么好的设计理念
自己总结了几点，new，detele，new[],delete[],构造析购里面通常怎么设计，虚析购的概念
3：后来他又给我讲解了一下c++喜欢用namespace这种机制，类似于析购构造的原理，一段结束后自动释放的原理。
我接着也说了一下自己对namespace经常用到的地方（1）自动锁的原理经常用到namespace，起到自动调用析购的函数（2）还有喜欢把一个class也封装在一个namespace里面，
4：设计的类似TCP的协议
（1）让你设计一种协议，A,B两个机器，A从硬盘不断的读数据流，并不断的像B机器发送，并且是有序到达的，你怎么保证B机器可以有序的收到，并且可以按顺序的读取？
我模仿TCP的滑动窗口+重传机制设计了一下
（2）如果不是有序到达的，多个消息并发到达，乱序的，你怎么处理？
在B机器对于收到的部分，我们设定head和tail指针，并且放在确认报文里面的首部选项里，以便A端可以重传.
（3）如果假设，我们每一次发送的数据，没有序号的概念，也可以理解为序号不是连续的，可能1,3,5,12，111之类的，你怎么处理？
我回答，从硬盘读取的顺序一定是一定的，那么根据读取的时间，我们手动的设定一个序号。
（4）我不希望有类似于序号的这个概念，你又怎么处理？
我回答的指针，从硬盘读取的时候，我们保证构造一个双向链表的模型，我们每次固定连续发送n个数据，B端收到后，对着n个暴力进行排序，读取之后，在发送给A端一个确认的回复，之后在循环进行
（5）我忘了他又怎么问了，不知道自己回答的对不对，但是我都没太明白他具体要实现什么，他开始不让用序号，最后他说了一下他的思路，好像还是用到了序号的概念，跟我第三问好像差不多，总之比较乱
5：从n个数中取出k个怎么实现？
堆时间复杂度n*logp
（1）可不可以在优化？
我说如果数的大小上限的差如果小于p的话，可以通过二分去解决，每次二分，看有多少个比mid大的数，感觉这种想法肯定不是他想要的，但是还是说出来了
（2）如果说只去第k大的怎么解决？
开始没想到，他问了我一句，快排的原理你还懂不？我立刻知道他想怎么实现了，之后马上说出了思路，他说其实快排解决可以将时间复杂度降为0（n），其实我感觉不是O（n）,不知道他为什么这么说
（3）在线coding你的代码
下面是我在线10分钟左右敲完给他看的代码，其实事后我发现有几个地方出错了，当时coding没注意到，没法调试。除了下面3个错误，应该没有了，如果又发现的纠正意见
问题（1）l<r 这里面应该是l<=r，具体的原理自己模拟一下就知道了，虽然快排这么写不影响，但是这里影响
问题（2）,（3）:尼玛，忘加上return，（ps：编码一定不忘着急，犯这类低级错误）
return getNum(arr,head+1,r,k); //(2)
return getNum(arr,l,head-1,k-(r-head+1));//(3)
//coding
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
int getNum(int *arr,int l,int r,int k){
int ans;
if(l<r){ //(1)
int head=l,tail=r,tmp=arr[l];
while(head<tail){
while(head<tail&&arr[tail]>=tmp){
tail--;
}
if(head<tail){
arr[head++]=arr[tail];
}
while(head<tail && arr[head]<tmp){
head++;
}
if(head<tail){
arr[tail--]=arr[head];
}
}
arr[head]=tmp;
if((r-head+1)==k){
return arr[head];
}
else{
if((r-head)>=k){
getNum(arr,head+1,r,k); //(2)
}
else{
getNum(arr,l,head-1,k-(r-head+1));//(3)
}
}
}
return -1;
}
int main(){
int len;
int arr[10000];
int k;
cin>>len>>k;
for(int i=0;i<len;i++){
cin>>arr[i];
}
int ans=getNum(arr,0,len-1,k);
if(ans==-1){
cout<<"error"<<endl;
}
else{
cout<<ans<<endl;
}
return 0;
}
6：讨论了一下我的博客，告诉我一定要把这种习惯坚持下去。以后益处会很大。
7：你有什么问题？
8：最后说建议你在多看一些更加深层的书籍，对你提高更加有帮助（我不知道这句话是不是意味着我三面失败的意思，不懂），总之，很好
阿里云四面
1 :字典树的概念，插入和删除需要注意些什么
2：字典树你有什么优化的地方
3：同样很多的字符串，你怎么尽可能少的压缩空间去存储，设计一种数据结构实现，不能使用字典树
4：对于I/O你有什么积累的经验，对于read/write出错了你有哪些解决的办法？
5：异步+事务：对于一些异步事件，怎么保证当调用失败的时候保证整体的完整性？
6：你看过***源代码么（忘记了，自己没听过）
7：说一下你最近你感受最深的项目吧（由于正在***公司实习，参与了一个项目，，正好说了一下）
8：为什么想加入阿里？
9：你有什么问我的吗？
#阿里巴巴##百度##C++工程师#
投递华为等公司10个岗位 >