「面试」美团肝了我30+问题
叮。。。。。美团来电。这次不是外卖而是电话面试。所报岗位为后端/服务端开发,但是从我的复盘来看,这和 Java 后端开发的内容差不多,除了部分的语言特性外,还是四大件基础知识为重,下面我们来看看都问了啥,小心下次面你的时候就有这些问题哦
如果你问我,看了这些题就完事了?非也,这只是开始,你需要学习的还有很多,知道路子是怎么走才是重要的勒。
开始之前,我们先看提纲,大家默默的想一想,如果是你,你将怎么去回答这个问题,然后再看我的回答也许更佳哈。
1 一面(40分钟)
自我介绍
老规矩,我叫啥,啥专业,技术栈是啥,能做啥
怎么理解分布式
其实如果没有去实习,可能很少接触分布式的内容。对于面试官而言,也没多期望你们对分布式的理解到多深的地步,只是希望你们能对其有个初步的了解即可。
不管是高登摩尔提出的摩尔定律还是Gordon Moore坚持的2版本是啥,总之如果你的系统需承载的计算量的增长速度大于摩尔定律的预测,那么在未来的某一个时间点,集中式系统将无法承载你所需的计算 量。
在整个计算机系统发展的过程中,最实际的还是经济的元素。人们发现使用更加廉价的机器,组合在一起的分布式系统,除了可以获得超过CPU发展速度的性能以外,还可以有更好的性价比,所以得出如下结论:
无论是要以低价格获得普通的性能,还是要以较高的价格获 得极高的性能,分布式系统都能够满足。并且受规模效应的影响,系统越大,性价比带来 的收益越高。
随着计算机的飞速发展,科学家们发现分布式系统相比于集中式系统的另一个很明显的优势就是:具有更高的可用性。假设使用10个能够承载10000流量相同的节点,其中的两个节点挂了,只要实际的流量不超过8000,那么系统仍然正常运转。
说这么多,分布式系统还是建立在「分治」和「冗余」的基础上,这也就是分布式系统的本质
那么分治是什么?
这和我们大脑解决问题类似,大问题分解为小问题,然后治理最后归并。
为什么要这样做?
小问题容易解决,解决了众多的子问题,大问题也就更容易解决啦
如果拆分的父子问题有依赖关系怎么办?
大问题拆分的过程中,非常重要的即不同分支的子问题不能相互依赖,需要各自独立,因为如果存在依赖关系,父子问题就失去了「归并」的意义,那么在开发中,这就是「聚合度」和「内聚度」的问题。
什么是聚合度和内聚度?
所谓聚合度即软件系统中各个模块的相互依赖程度。比如在调用A方法的时候都需要同步调用方法B,显然这样的耦合度就高
所谓内聚度即模块之间具有共同点的相似程度,所以在拆分的时候要尤其注意这两点。
什么是冗余?
这里的冗余不是代码的冗余,而是容许系统在一定范围内出现故障,但对系统的影响很小
如上图将冗余的节点部署在单独的服务器,完全是为了备用而做的冗余,如果不出现故障,那么资源是不是就浪费了,所以大多数情况会使用诸如双主多活、读写分离之类的概念提高资源利用率
其实在生活中冗余也很常见,比如大部分的汽车系统中的底层控制系统也是有冗余机制,飞机发动机为什么是偶数,也是同样的道理。还有更多的关于后端的基础总结要点则参考另一篇文章42图揭秘,「后端技术学些啥」
写个代码热热身----栈实现队列
class MyQueue {
public:
stack<int> stIn;
stack<int> stOut;
/** Initialize your data structure here. */
MyQueue() {
}
/** Push element x to the back of queue. */
void push(int x) {
stIn.push(x);
}
/** Removes the element from in front of queue and returns that element. */
int pop() {
// 只有当stOut为空的时候,再从stIn里导入数据(导入stIn全部数据)
if (stOut.empty()) {
// 从stIn导入数据直到stIn为空
while(!stIn.empty()) {
stOut.push(stIn.top());
stIn.pop();
}
}
int result = stOut.top();
stOut.pop();
return result;
}
/** Get the front element. */
int peek() {
int res = this->pop(); // 直接使用已有的pop函数
stOut.push(res); // 因为pop函数弹出了元素res,所以再添加回去
return res;
}
/** Returns whether the queue is empty. */
bool empty() {
return stIn.empty() && stOut.empty();
}
};
介绍下第一个项目
注意:校招的的面试在我看来写两个项目差不多了,印象更深刻且自己的理解程度更好的放在上面。面试之前一定要搞懂这三个问题,且在练习的时候想想怎么能引面试官上钩
项目的描述
自己在项目中担任的角色,做了什么
在项目中遇到什么难点,怎么处理,有没有测试过
说说快排思想?
如果我们的每一次分区操作都能正好将数组分成大小接近相等的两个小区间,那么快排的时间复杂度和归并是差不多的,所以其时间复杂度为O(nlogn)
这里特别注意所谓的每次分区操作有个前提条件,即选择的pivot很合适,能挣好的将大区间对等的一分为二,如果原来的数据是一件排好序的,我们选择最后一个元素为pivot,这样每次分区得到的两个区间是不均等,我们需要进行大约n次分区操作,每次分区平均扫描n/2个元素,此时的复杂度将退化为0(n ^ 2)
注:一定要能手撕快排啊,这真是无数次会被考!!!
public class QuickSort {
public static void main(String[] args) {
int[] arr = { 49, 38, 65, 97, 23, 22, 76, 1, 5, 8, 2, 0, -1, 22 };
quickSort(arr, 0, arr.length - 1);
System.out.println("排序后:");
for (int i : arr) {
System.out.println(i);
}
}
private static void quickSort(int[] arr, int low, int high) {
if (low < high) {
// 找寻基准数据的正确索引
int index = getIndex(arr, low, high);
// 进行迭代对index之前和之后的数组进行相同的操作使整个数组变成有序
//quickSort(arr, 0, index - 1); 之前的版本,这种姿势有很大的性能问题,谢谢大家的建议
quickSort(arr, low, index - 1);
quickSort(arr, index + 1, high);
}
}
private static int getIndex(int[] arr, int low, int high) {
// 基准数据
int tmp = arr[low];
while (low < high) {
// 当队尾的元素大于等于基准数据时,向前挪动high指针
while (low < high && arr[high] >= tmp) {
high--;
}
// 如果队尾元素小于tmp了,需要将其赋值给low
arr[low] = arr[high];
// 当队首元素小于等于tmp时,向前挪动low指针
while (low < high && arr[low] <= tmp) {
low++;
}
// 当队首元素大于tmp时,需要将其赋值给high
arr[high] = arr[low];
}
// 跳出循环时low和high相等,此时的low或high就是tmp的正确索引位置
// 由原理部分可以很清楚的知道low位置的值并不是tmp,所以需要将tmp赋值给arr[low]
arr[low] = tmp;
return low; // 返回tmp的正确位置
}
}
半连接了解吧,如果SYN半连接队列满了怎么处理,只能丢弃连接?
如果你看过我之前写的文章,这个问题应该就非常容易解决了。SYN半连接队列已满,通过开启cookies功能就可以在不使用SYN队列的情况下成功建立连接
syncookies是怎么操作的?
服务端返回 ACK 的时候会计算一个值放在发出的SYN+ACK报文中,当客户端返回ACK的时候取出该值进行验证,如果合法即连接成功
Linux如何开启syncookies呢?
通过将参数tcp_cookies设置1即可。如果参数值为2,表示无条件开启这个功能。如果为1表示仅当SYN半连接队列放不下的时候,再开启。
那可不可以绕过三次握手?
还有这种操作?
三次握手中,一个较大的问题是HTTP请求必须在一次的RTT后才能发送。从而谷歌提出了TFO。想要绕过三次握手过程,如果是客户端发起连接,想要在SYN的请求报文中放入数据,需要得到服务端的认可,所以事先需要有个约定。
首次建立连接走正常的三次握手,客户端会在SYN报文中明确告诉服务器要使用TFO功能,服务端答应后就会将客户端的IP地址用自己的密钥加密(cookie)携带在返回的SYN+ACK中,客户端收到后将cookie缓存到本地
下次客户端再建立连接,就可以在SYN中携带请求的数据+缓存的cookie
刚才你说的密钥是不会变的?
当然变化,不然就很容易产生SYN泛洪攻击了。
Linux中如何打开TFO?
这里要注意了,需要客户端和服务端都支持,TFO才会生效,当tcp_fastopen设置为3的时候才生效
net.ipv4.tcp_fastopen=3
举几个使用缓存的例子
这里涉及面就非常广了,什么数据库缓存,如何选择缓存的读写策略,如何做到缓存高可用,缓存穿透的怎么处理以及CDN相关,我们先举几个缓存的例子
我们知道虚拟地址到物理地址转换的时候需要通过一个叫做MMU的硬件,每次这样的转换无疑会造成性能的转换,所以接住了TLB来缓存最近转换过的,下一次转换的时候,如果缓存存在就直接转换即可
在路由寻址的时候,会有个映射表让我们知道该访问哪个目的地址,同样存在于缓存中
HTTP缓存机制。通过缓存协商方式减少网络传输的数据大小从而提升页面展示的性能
缓存怎么个分类?
缓存分类分为三种,分别为静态缓存、分布式缓存与本地缓存。
静态缓存
通常使用静态HTML实现静态缓存。通过在Nginx上部署静态缓存减少对于后台应用服务器的压力。当然你也可以存放数据库,然后前端穿透查询,但是对于后端的服务器压力是非常大的。比如内容系统,通常在录入文章的时候先渲染成静态页面,然后放在前端Ngix服务器上,这样用户会直接访问前端静态页面,但是如果是动态请求,这样就需要分布式缓存了
分布式缓存
面试中高频的Redis和Memchache,就是通过集群的方式突破单机瓶颈
热点本地缓存
热点嘛,微博每天都有热点,尤其是什么XX明星出轨,这样的查询通常会命中某一个缓存节点,短时间内极高的缓存热点查询。这个时候就会在代码中使用一些本地本地缓存方案。如hashmap
缓存的不足
从上面基本上知道,缓存的主要作用是提升访问的速度,提升并发的能力。
缓存最好适用于读多写少且带有一定的热点属性
因为既然是缓存受限于存储介质,不可能缓存所有数据,只有当数据有一定的热点属性才能有更高的缓存命中率
缓存让系统更加复杂,容易出现数据不一致的现象
比如更新数据库成功了,但是更新缓存失败了。这个时候可以考虑固定时间清理或者手动清理。
给运维带来一定的成本
运维小哥需要了解一些缓存组件的使用
一面小结
一面面试涉及到了项目,计算机网络,数据结构和后端的基本知识,也基本覆盖了校招的各科且有一定的是实践性考察,不同公司面试当然不一样,看多了你会发现重点就是这些了,继续复盘二面
2 二面
慢慢的到了10月,面试的越多不知道的越多,感觉需要学习的越多,当然越战越勇,面完一面是一面,积累一面是一面。团团既然给脸,那就面呗
写个代码-----数组中数字出现的次数
我擦,上来就是写代码,不过大家习惯就好,每个面试官套路不同,资本社会接受即可,写呗,准备这么久的你还怕啥。管他三七二十一,能上位运算就上位运算,盘它完事,小伙伴说能不能写个python版本,那就py呗。如果这个题目还要犹豫,赶紧再去练练《剑指offer》和leetcode100题呀
class Solution(object):
def singleNumbers(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
temp = 0
for i in nums:#得到用于区分的数字
temp ^= i
num = 1
while not (num & temp):#找到用于区分的数字中从右到左的第一位为1的值
num = num << 1
result1 = 0
result2 = 0
for i in nums:
if num & i:# 划分两个数组
result1 ^= i#两个数组分别取异或
else:
result2 ^= i
return[result1,result2]
说说TCP的收发包可通过哪些配置?
这个题就有点大了,我可以扯很久,而且只要问到TCP发送或者接受的类似问题,真是可以大干好几百个回合。在这里就稍微详细的说说,在以后的面试过程中,遇到此题讲不在多说哈,还答不上来就打自己几耳巴可好,别别,还是不能这么对自己,好了,不多BB了,上干货
收包是数据到达网卡后交给应用程序处理的过程,发包则调用相应的发包函数将数据包从网卡发出的场景。
我们再看看类似的几个问题
我明明是用了write和send进行发包,但是总是发不出去
通过抓包发现数据包已经到网卡了,但是应用程序为什么就是收不到
调整了缓冲区大小,不失效的原因
和前面一样,都是需要了解相应的系统参数才能较好的回答这些问题且能体现你对网络的了解深度
TCP数据包在发送的过程中会受到哪些影响?
这个图画了一个小时,一定要好好看看,顺便记得给我一个赞,么么哒,下面我们详细看看这个图
当我们通过write等发包函数进行发包的时候,这些系统调用都是将数据包先从用户缓冲区拷贝到TCP发送缓冲区中,可是这个TCP缓冲区是有大小限制的,正是这个限制就会产生各种问题。
TCP发送缓冲区的默认受到 net.ipv4.tcp_wmen 控制
这三个参数分别的叫做是min,default,max。TCP发送缓冲区会在min和max中浮动,初始的大小为default。
为什么需要自动调整,是不是越大越好?
首先这个动态调整是由内核来完成,不需要应用程序的干预,而且每次发包的大小不一样,数据太小,缓冲区却很大自然就浪费了内存,所以通过动态调整的方式满足发包的需要。
TCP缓冲区设置太小或者太大有什么标志?
TCP的发送缓冲区设置太小,最明显的特征即导致业务延迟。如何发现呢,可以通systemtap等工具在内核打点完成观察,如果发现了有sk_stream_wait_memory就认为这发送缓冲区太小了,需要调大tcp_wemem:max
可不可以开发的时候指定需要发送的大小?
当然可以呀,通过setsockopt中的SO_SNDBUF设置固定的缓冲区大小。但是设置了这个参数,tcp_wmem就会失效,也就没有了动态调整,设置的值不能超过net.core.wmem_max,如果超过了,内核会强制设置为wmem_max。所以通常情况下,我们不会通过SO_SNDBUF设置TCP缓冲区的大小,设置太大浪费内存,设置太小引起缓冲区不足的问题。
上面所说的tcp_wmem和wmem_max都是针对单个tcp连接,其单位是字节。系统中通常有非常多的tcp连接,连接太多可能导致内存耗尽
我们能不能设置tcp消耗内存的大小?所谓上限
当所消耗的内存达到max就不会再发包
可以通过什么方式观测到这种情况?
Linux内核给我们早就埋了点,sock_exceed_buf_limit。观察的时候只需要打开tracepoint即可
然后在日志中查看是否发生了事件
伴随tcp层数据包的处理完毕来到ip层,在IP层需要考虑端口范围的问题,太小可能导致无法创建连接。
net.ipv4.ip_local_port_range = 1024
为了实现tcp/ip数据流进行流控,Linux内核在ip层实现了qdisc(排队规则)。我们平时见的比较多的TC即是基于qdisc的流控工具,实际上我们通过ipconfig看到的txqueuelen即qdisc的队列长度。它太小就会导致数据包被丢失
我们如何观察到这个现象?
如果发现dropped不为0,则很可能是txqueuelen太小导致,此时就需要调大这个值
经过ip层后就进入网卡了,此时需要发送的数据包走完TCP/IP协议栈
那么对于接受放而言,是怎么接受的?
同样,先看看图
从上图可以发现其接受流程和发送流程基本相反。当数据包到达接受方的网卡,就会触发中断,高速CPU读取数据包,但是在高速网络中,大量的数据包,如果每来一个数据包就触发一次中断势必让CPU的处理效率大大折扣,所以提出了NAPI技术,让CPU一次性轮询多个数据包,通过批量的方式来提升效率,降低中断带来的性能开销
在poll的时候,一次轮询多少个?
这个poll通过sysctl选项控制
此值默认大小为300,通常会增加此值到600使得一次性能处理更多的的数据包
可以无限增大此值?
当然不行,系统存在太多进程,CPU需要权衡自己的时间照顾其他的进程,如果CPU在poll的时间太多,其他任务的调度就会延迟。
当poll了数据包就会到IP层处理,随后到达tcp层,从而遇到我们之前所说的TCP接受缓冲区
默认通过tcp_rmem控制缓冲区的大小,通过适当的调整该值来获取更好的网络性能
TCP的默认缓冲区大小会在min和max之间动态的调整,不过和发送缓冲区不同的是,这个动态调整时通过选项tcp_moderade_rcvbuf。通常我们都会打开它
为什么接受缓冲区时通过选项来自动调节,而发送缓冲区不是
因为tcp接受缓冲区会直接影响tcp拥塞控制,从而影响对端的发包,所以通过选项控制的方式更加灵活的控制对端的发包行为
还有其他方式控制tcp的接受缓冲区?
当然有,可以通过setsockopt()的配置选项SO_RECVBUF控制,如果设置了此值,那么tcp缓冲区的自动调整将关闭,总之只有当tcp_moderate_rcvbuf 为 1,并且应用程序没有通过 SO_RCVBUF 来配置缓冲区大小的情况下,TCP 接收缓冲区才会动态调节
总结:
TCP/IP协议栈复杂无比,此文介绍了很多配置选析,后续给大家总结一个常用的参数表
好了,这个题目也许啰嗦,但是你会发现确实有点东西哈,盘它呀,接着面试
小伙子对这个问题的理解比较深刻,差不多都答在了点上,你说说一致性哈希是什么?
说一致性哈希是什么,那我们肯定需要告诉面试官为啥要用一致性哈希,直接使用哈希不香?有什么问题嘛?
我先用个简单的例子让大伙看一波为啥使用一致性哈希
现在我们有一个分布式缓存,需要存放6w张美女照片,别问我干啥,就是存着
方案1:直接采用哈希算法,对每个图片进行分片
余数正好对应每个机器节点
这样子会出现什么问题?
通过哈希算法,每个key可以寻址对应服务器,假设发过来的请求为key01,计算公式为hash(key01)%3
经过计算后寻址编号为1的服务器节点,如下图所示
此时加入新的服务器节点,就会出现路由失败的情况。此时从三个节点变化为4个节点,之前的hash(kley01)%3=1就变化为 hash(key-01) % 4 = X,因为取模运算发生了变化,所以这个 X 大概率不是 1,这时你再查询,就会找不到数据了,因为 key-01 对应的数据,存储在节点 A 上,而不是节点 B。同样的道理,如果我们需要下线 1 个服务器节点(也就是缩容),也会存在类似的可能查询不到数据的问题
对于这个问题怎么解决呢
我们就需要迁移数据,基于新的计算公式 hash(key-01) % 4 ,来重新对数据和节点做映射。需要注意的是,数据的迁移成本是非常高的。
如何解决这个问题---一致性哈希
一致性哈希也是使用了取模运算,但是和传统的取摸运算不同,一致性哈希算法是对2^32 - 1进行取模运算
即使这些数据均匀,但是数据的活跃度不同,存放热点数据多的节点访问量非常大,就很容易的达到CPU瓶颈。一致性哈希算法即将整个哈希值空间组织成一个虚拟的圆环---哈希环
通过哈希算法,将节点映射到哈希环上,通常是节点主机名,ip地址等如下图
在寻址的过程就只需要两步
将key作为参数执行c-hash计算出哈希值,确定key在环的位置
从这个位置沿着哈希环顺时针走,遇到的第一个节点即key对应的节点
如下图所示
从上图可以发现,key01对应节点A,key03对应节点C,如果此时C宕机了,只需要将key03定位到节点A即可,key01和key02并不需要改变。所以一致性哈希算法在增加和减少节点的时候,只需要重新定位一小部分数据而不需要重新定位所有数据,这样就实现了"增加/减少节点需要大规模迁移"这个问题
如果节点比较少,是不是很容易就将请求数据打到一个节点呢?
这个问题即"数据倾斜问题",由于节点的不均匀是的大量你的请求访问到节点A上,造成负载不均衡。
鉴于这个问题引入了虚拟节点,简单的来说通过增加节点的个数来缓解节点的不均匀现象
所谓虚拟节点即对每个服务器节点计算多个哈希值,假设一个真实的节点有2个虚拟节点,此时我的三个节点就共有6个虚拟节点,如下图所示
此时如果在环上顺时针寻找虚拟节点,假设key01选择虚拟节点nodeB02,那么此时将请求映射到真是节点B即可
所以通过虚拟节点扩充节点数量的方式解决节点较少情况下数据倾斜的问题,代价非常小,只需要增加一个字典map维护真实节点和虚拟节点的映射关系即可
说说HTTP1.0 1.1 2 3的演进
之前有一篇文章单独说了这个问题,现在粗略总结下,希望读者们再去查查相关资料
http/1.1
相对于http/1.0
性能上的改进:
http/1.0 采用的是短连接,会有较大的三次握手和四次挥手的开销
支持管道传输,
http/1.0
只有第一个响应回来才能发这个请求,但是http/1.1
可以连续发送,并不需要等待其回来,减少了整体响应时间
http/1.1
性能瓶颈:
请求/响应的头部没有经改压缩就发送,只能压缩body部分
发送冗长的首部,每次互相发送相同的首部造成的浪费较多
服务器是按顺序响应的,会出现队头拥塞的情况
没有请求优先级控制
请求只能从客户端开始,服务器只能被动响应
http/2
采用了
HPACK
算法避免传送相同的头部,并且对头部数据进行了压缩对传输的数据采用二进制的方式传输,分为头部帧和数据帧
对连接进行了复用,只要访问同一个域名下的资源,不必进行TCP连接的重新建立
支持服务端push
对于服务端的响应也不会不会出现队头拥塞的情况,可以根据优先级进行响应
http/3 QUIC
采用了基于
UDP
的传输层协议,希望取代TCP
仍然也有队头阻塞的情况,例如当TCP出现丢包重传时
支持应用层级别的重传,而且在只丢失一个数据包的情况下不需要重传,使用纠错机制恢复丢失的包
说说数据库事务的四大特性
事务时一个可执行的逻辑单元,该逻辑单元的操作要么都执行,要么都不执行,事务具有ACID四个性质
原子性:指事务包含的所有操作,要么都被执行成功,如果中间有一条语句失败,则进行回滚。
一致性:指事务执行前和执行后都必须处于一致性状态
隔离性:事务之间是相互独立的,中间状态对外是不可见的
持久性:数据的修改是永久的
多加索引一定很好吗
索引主要用于加速查询速度,但并发越多越好,因为索引需要占用物理空间的,且索引的维护需要时间的,所以如果建索引,一般来说,应该查询的次数大于插入的次数,同时我们一般只对例如where或者having子句中涉及的字段进行设置索引,因为其它的地方就算建立了索引,一般也用不到,只是浪费。
请问TCP哪些保证了数据传输的可靠性
序列号、确认重传、超时重传、拥塞控制(ps 看过我之前文章的小伙伴,问这个问题如果不能扯上一小时,自罚三杯)
三个线程顺序打印A-Z
#include
#include
#include
using namespace std;
char ch = 'A' - 1;
pthread_cond_t cond = PTHREAD_COND_INITIALIZER;
pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
void* print_fun(void * args){
int i = *((int*)args);
char next_ch = 'A' + i;
while(next_ch <= 'Z'){
pthread_mutex_lock(&mutex);
while(ch + 1 != next_ch)pthread_cond_wait(&cond, &mutex);
ch++;
cout<< pthread_self() << ":"<< ch << endl;
next_ch = ch + 3;
pthread_mutex_unlock(&mutex);
pthread_cond_broadcast(&cond);
}
return nullptr;
}
int main(){
pthread_t tids[3];
int pos = 0;
for(int i = 0; i < 3; ++i){
pthread_create(tids + i, nullptr, print_fun, &pos);
sleep(1);
pos++;
}
for(int i = 0; i < 3; ++i){
pthread_join(tids[i], nullptr);
}
return 0;
}
5 总结
请记下以下几点:
公司招你去是干活了,不会因为你怎么怎么的而降低对你的要求标准。
工具上面写代码和手撕代码完全不一样。
珍惜每一次面试机会并学会复盘。
对于应届生主要考察的还是计算机基础知识的掌握,项目要求没有那么高,是自己做的就使劲抠细节,做测试,只有这样,才知道会遇到什么问题,遇到什么难点,如何解决的。从而可以侃侃而谈了。
非科班也不要怕,怕了你就输了!一定要多尝试。
— 【 THE END 】— 本公众号全部博文已整理成一个目录,请在公众号里回复「m」获取! 3T技术资源大放送!包括但不限于:Java、C/C++,Linux,Python,大数据,人工智能等等。在公众号内回复「1024」,即可免费获取!!