20210108腾讯PCG二面+三面and网易二面

二面

1.一个二维网格图，每个节点代价均大于0，每个节点的上下左右方向都可以走(如果有)，请找出左上角点到右下角点的最小代价路径？

解决思路：本题就是一道无向图的最短路径问题，可以使用 弗洛伊德算法 or 迪杰斯特拉算法 解决。

两者的主要区别----Floyd算法是计算所有起点到所有终点的最短距离，Dijkstra是计算指定起点到所有终点的最短距离。

(1)弗洛伊德算法
需要两个数据结构：dist[i][j]表示i到j的最短距离，path[i][k]表示i到j下一步要去的节点
三层for：

//使用弗洛伊德核心算法，三层循环求解for (k = 0; k < G.numVertexes;k++){ //中间节点for (i = 0; i < G.numVertexes;i++){ //起点for (j = 0; j < G.numVertexes;j++){ //终点//i!=j使不更新中间自己到自己的数据和路径if ((*dist)[i][j]>((*dist)[i][k]+(*dist)[k][j])&&i!=j)　 {　//将权值和更新，路径也变为中转点(*dist)[i][j] = (*dist)[i][k] + (*dist)[k][j];(*path)[i][j] = (*path)[i][k];}}}}


(2)迪杰斯特拉算法
需要两个数据结构：dist[j]表示起点到j的最短距离，pre[j]表示起点到j的上一个节点

/*n是总的结点数,v是出发结点,dist是距离,pre前一个结点,d是结点间的权值*/
void Dijkstra(int n, int v, vector<int> &dist, vector<int> &pre, vector<vector<int>> &d)
{vector<bool> s(n+1);for (int i = 1; i <= n;i++){dist[i] = d[v][i];if (dist[i] < maxdist) pre[i] = v;else pre[i] = 0;}dist[v] = 0;s[v] = true;for (int i = 2; i <= n;i++){ //总的迭代次数int best = v;int temp = maxdist;for (int j = 1; j <= n;j++){ //找到最小的距离if (!s[j]&&dist[j]<temp){temp = dist[j];best = j;}}s[best] = true;for (int j = 1; j <= n;j++){ //更新dist和pre if (!s[j] && d[best][j] != maxdist){int newdist = dist[best] + d[best][j];if (newdist<dist[j]){dist[j] = newdist;pre[j] = best;}}} }
}


华为2019软件精英挑战赛 车辆路径规划赛题

2.Linux下查看大体积日志文件用什么命令？

如果你已经知道日志输出的关键字的话，使用 grep , 通常需要打印关键字前后的日志。

grep &＃39;key word&＃39; log.txt -A 20 // 列出包括匹配行之后 20 的行。
grep &＃39;key word&＃39; log.txt -B 20 // 列出包括匹配行之前 20 的行。
grep &＃39;key word&＃39; log.txt -C 20 // 列出包括匹配行前后各 20 行。


大文件的话，grep 出来的数据比较多的话，你可以和 less 一起使用

grep `world` copy.log | less


less命令：
less 与 more 类似，但使用 less 可以随意浏览文件，而 more 仅能向前移动，却不能向后移动，而且 less 在查看之前不会加载整个文件

有时候需要将 tail 和 less 命令结合起来使用

tail -n +10000 | less // 从第 10000 开始,使用 less 查看。
tail -n 10000 | less // 查看倒数第 1000 行到文件最后的数据。


https://blog.csdn.net/stupid56862/article/details/93330203

3.Linux查看端口占用的命令？我说的netstat -anp |grep ，问：“|”是什么意思？

查看端口号 netstat

netstat -anp | grep 5623
#其中5623位端口号


通过进程id查找程序 ps

ps -aux | grep pid 进程程序名称


Linux查看端口号 netstat参数

netstat参数说明：
-a　　　　　　　　　　　 显示所有连接和监听端口。
-n　　　　　　　　　　　 以数字形式显示地址和端口号。
-p proto　　　　　 显示 proto 指定的协议的连接；proto 可以是
　　 下列协议之一: TCP、UDP、TCPv6 或 UDPv6。
　　 如果与 -s 选项一起使用以显示按协议统计信息，proto 可以是下列协议之一:
　　 IP、IPv6、ICMP、ICMPv6、TCP、TCPv6、UDP 或 UDPv6。

竖线‘|’ ，在linux中是作为管道符的，将‘|’前面命令的输出作为’|&＃39;后面的输入

Linux grep 命令
Linux grep 命令用于查找文件里符合条件的字符串。
grep 指令用于查找内容包含指定的范本样式的文件，如果发现某文件的内容符合所指定的范本样式，预设 grep 指令会把含有范本样式的那一列显示出来。若不指定任何文件名称，或是所给予的文件名为 -，则 grep 指令会从标准输入设备读取数据。

grep语法

grep [-abcEFGhHilLnqrsvVwxy][-A<显示列数>][-B<显示列数>][-C<显示列数>][-d<进行动作>][-e<范本样式>][-f<范本文件>][--help][范本样式][文件或目录...]


“|”用法
command 1 | command 2 他的功能是把第一个命令command 1执行的结果作为command 2的输入传给command 2，例如:

ls -s|sort -nr


-s 是file size，-n是numeric-sort，-r是reverse，反转
该命令列出当前目录中的文档(含size)，并把输出送给sort命令作为输入，sort命令按数字递减的顺序把ls的输出排序。

ls -s|sort -n


按从小到大的顺序输出。
当然还可进行多次操作，如下面的功能为先去除纯数字，再由 sed将竖线(这里不是管道符号)替换为空格，再将结果取出来排序，再进行结果的选择显示，不明白可查看 排序和分页。

cat filename |grep -v &＃39;^[0-9]*$&＃39; | sed &＃39;s/|/ /g&＃39; |sort -nrk 8 -nrk 9 |tail -n +1 |head -n 10


4.怎么设计高并发的抢单程序？保证货品只被一人抢占？

问题描述
在众多抢购活动中，在有限的商品数量的限制下如何保证抢购到商品的用户数不能大于商品数量，也就是不能出现超卖的问题；还有就是抢购时会出现大量用户的访问，如何提高用户体验效果也是一个问题，也就是要解决秒杀系统的性能问题。

解决超卖的方案
每一个用户只能抢购一件商品的限制；在数据库减库存时加上库存数量判断，库存数量为0时阻止秒杀订单的生成。

数据库加唯一索引：防止用户重复购买
SQL加库存数量判断：防止库存变为负数

解决性能问题

1. 使用Redis缓存预减库存，减少数据库的访问。因为缓存的访问速度比数据库访问快得多。
2. 使用内存标记，减少Redis缓存的访问次数。
3. 使用队列等异步手段，请求先入队缓冲，异步下单，将数据写入数据库，增强用户体验。
   性能解决方案
4. 总体思路就是要减少对数据库的访问，尽可能将数据缓存到Redis缓存中，从缓存中获取数据。

内存标记：
由于接口优化很多基于Redis的缓存操作，当并发很高的时候，也会给Redis服务器带来很大的负担，如果可以减少对Redis服务器的访问，也可以达到的优化的效果。
于是，可以加一个内存map,标记对应商品的库存量是否还有，在访问Redis之前，在map中拿到对应商品的库存量标记，就可以不需要访问Redis 就可以判断没有库存了
1.生成一个map，并在初始化的时候，将所有商品的id为键，标记false 存入map中。
2.在预减库存之前，从map中取标记，若标记为false,说明库存还有。
3.预减库存，当遇到库存不足的时候，将该商品的标记置为true,表示该商品的库存不足。这样，下面的所有请求，将被拦截，无需访问redis进行预减库存。

1.在系统初始化时，将商品的库存数量加载到Redis缓存中；
2.接收到秒杀请求时，在Redis中进行预减库存，当Redis中的库存不足时，直接返回秒杀失败，否则继续进行第3步；
3.将请求放入异步队列中，返回正在排队中；
4.服务端异步队列将请求出队，出队成功的请求可以生成秒杀订单，减少数据库库存，返回秒杀订单详情。
4.用户在客户端申请秒杀请求后，进行轮询，查看是否秒杀成功，秒杀成功则进入秒杀订单详情，否则秒杀失败。

缺陷
由于是通过异步队列写入数据库中，可能存在数据不一致。

Redis缓存更新导致的数据不一致问题与解决办法

其他类似解决方案说明

解决方案1
将存库MySQL迁移到Redis中，所有的写操作放到内存中，由于Redis中不存在锁故不会出现互相等待，并且由于Redis的写性能和读性能都远高于MySQL，这就解决了高并发下的性能问题。然后通过队列等异步手段，将变化的数据异步写入到DB中。

优点：解决性能问题

缺点：没有解决超卖问题，同时由于异步写入DB，存在某一时刻DB和Redis中数据不一致的风险。

解决方案2
引入队列，然后将所有写DB操作在单队列中排队，完全串行处理。当达到库存阀值的时候就不在消费队列，并关闭购买功能。这就解决了超卖问题。

优点：解决超卖问题，略微提升性能。

缺点：性能受限于队列处理机处理性能和DB的写入性能中最短的那个，另外多商品同时抢购的时候需要准备多条队列。

解决方案3
将提交操作变成两段式，先申请后确认。然后利用Redis的原子自增操作（相比较MySQL的自增来说没有空洞），同时利用Redis的事务特性来发号，保证拿到小于等于库存阀值的号的人都可以成功提交订单。然后数据异步更新到DB中。

优点：解决超卖问题，库存读写都在内存中，故同时解决性能问题。

缺点：由于异步写入DB，可能存在数据不一致。另可能存在少买，也就是如果拿到号的人不真正下订单，可能库存减为0，但是订单数并没有达到库存阀值。

https://blog.csdn.net/dazou1/article/details/89310254

三面

1.快排思想实现Top K？

快排实现Topk
时间复杂度：平均O(N)

1. 利用快排的思想实现，每次可以得到一个元素下标，在这个元素下标左边，所有元素比这个元素小， 在这个元素右边，所有元素都比这个元素大
2. 如果右边的元素个数等于K-1，则加上当前元素，达到K个，可知TOPK的元素为这K个；
3. 如果右边的元素个数小于K-1, 则在左边范围寻找K-len个元素
4. 如果右边的元素个数大于K-1, 则在右边范围寻找K个元素

#include
#include
using namespace std;//用快排的思想：例如找49个元素里面第24大的元素，那么按如下步骤：
//1.进行一次快排（将大的元素放在前半段，小的元素放在后半段）, 假设得到的中轴为p
//2.判断 k -1==p - low，如果成立，直接输出a[p]，（因为前半段有k - 1个大于a[p]的元素，故a[p]为第K大的元素）
//3.如果 k -1


//4.如果 k -1 > p - low， 则第k大的元素在后半段，此时更新low = p + 1, 且 k = k - (p - low + 1)，继续步骤1.
//由于常规快排要得到整体有序的数组，而此方法每次可以去掉“一半”的元素，故实际的复杂度不是o(nlgn), 而是o(n)。
class Finder
{
public:int partition(vector<int>&a, int low, int high)//找枢纽{int first = low;int last = high;int key = a[first];//用字表的第一个记录作为枢轴while (first < last){while (a[last] >= key && first < last)--last;swap(a[first], a[last]);while (a[first] <= key && first < last)++first;swap(a[first], a[last]);}return first;//返回一个枢纽}int findKth(vector<int>& a, int low, int high, int k){int p = partition(a, low, high);if (k == p - low + 1)return a[p];else if (k - 1 < p - low)//则第k大的元素在前半段return findKth(a, low, p - 1, k);else //则第k大的元素在后半段return findKth(a, p + 1, high, k - p + low - 1);}
};int main()
{int k = 1;vector<int> v{ 6, 2, 7, 3, 8, 9, 11, 5, 78, 34, 13 };Finder solution;//第k大元素=正序中第(nums.size() - k + 1)个元素cout << solution.findKth(v, 0, v.size() - 1, v.size() - k + 1) << endl;
}


2.TCP为什么三次握手、四次挥手？

TCP为什么要三次握手，tcp为什么可靠？

为什么不能两次握手：（防止已失效的连接请求又传送到服务器端，因而产生错误）

假设改为两次握手，client端发送的一个连接请求在服务器滞留了，这个连接请求是无效的，client已经是closed的状态了，而服务器认为client想要建立一个新的连接，于是向client发送确认报文段，而client端是closed状态，无论收到什么报文都会丢弃。而如果是两次握手的话，此时就已经建立连接了。服务器此时会一直等到client端发来数据，这样就浪费掉很多server端的资源。

三次握手的最主要目的是保证连接是双工的。

由于TCP连接时全双工的，因此，每个方向都必须要单独进行关闭，这一原则是当一方完成数据发送任务后，发送一个FIN来终止这一方向的连接，收到一个FIN只是意味着这一方向上没有数据流动了，即不会再收到数据了，但是在这个TCP连接上仍然能够发送数据，直到这一方向也发送了FIN。首先进行关闭的一方将执行主动关闭，而另一方则执行被动关闭。
（1）第一次挥手：Client发送一个FIN，用来关闭Client到Server的数据传送，Client进入FIN_WAIT_1状态。
（2）第二次挥手：Server收到FIN后，发送一个ACK给Client，确认序号为收到序号+1（与SYN相同，一个FIN占用一个序号），Server进入CLOSE_WAIT状态。
（3）第三次挥手：Server发送一个FIN，用来关闭Server到Client的数据传送，Server进入LAST_ACK状态。
（4）第四次挥手：Client收到FIN后，Client进入TIME_WAIT状态，接着发送一个ACK给Server，确认序号为收到序号+1，Server进入CLOSED状态，完成四次挥手。

为什么需要TIME_WAIT？

TIMEWAIT状态也称为2MSL等待状态。

1）为实现TCP这种全双工（full-duplex）连接的可靠释放

这样可让TCP再次发送最后的ACK以防这个ACK丢失(另一端超时并重发最后的FIN)。这种2MSL等待的另一个结果是这个TCP连接在2MSL等待期间，定义这个连接的插口(客户的IP地址和端口号，服务器的IP地址和端口号)不能再被使用。这个连接只能在2MSL结束后才能再被使用。

2）为使旧的数据包在网络因过期而消失

每个具体TCP实现必须选择一个报文段最大生存时间MSL(Maximum Segment Lifetime)。它是任何报文段被丢弃前在网络内的最长时间。

为什么建立连接是三次握手，而关闭连接却是四次挥手呢？

这是因为服务端在LISTEN状态下，收到建立连接请求的SYN报文后，把ACK和SYN放在一个报文里发送给客户端。而关闭连接时，当收到对方的FIN报文时，仅仅表示对方不再发送数据了但是还能接收数据，我们也未必全部数据都发送给对方了，所以我们不可以立即close，也可以发送一些数据给对方后，再发送FIN报文给对方来表示同意现在关闭连接，因此，我们的ACK和FIN一般都会分开发送。

https://www.cnblogs.com/pengmn/p/10836784.html

3.C++的多态如何实现？

https://blog.csdn.net/qq_37954088/article/details/79947898

4.C++字节对齐怎么做？原因有哪些？

https://blog.csdn.net/fengbingchun/article/details/81270326#comments_14445579

5.redis的rehash是怎么做的？

https://blog.csdn.net/weixin_39590058/article/details/107983734

6.100亿个非重复数和10亿个非重复数，如何计算他们的交集？(除bitmap外的方案)

[leetcode 350]. 两个数组的交集 II（解决百亿数据如何求交集）：https://blog.csdn.net/duchenlong/article/details/107310225

7.微信聊天如何保证消息的顺序性？

消息队列如何保证顺序性

8.淘宝的秒杀系统在设计时候有哪些要考虑的？

1.丢弃订单：最早期，量太大扛不住，直接前端随机reject一些，返回给抢单失败，简单粗暴，但是有效，比如10万人抢100个iPhone，只要能提前预测有大概1万以上的人参与（通过资格确认、报名等方式收集信息），那么直接请求进来以后随机挡回去99%的流量都没有啥问题。

2.优化吞吐：中间有段时间，提前准备一大批机器，服务化、分库分表搞定后端性能，让前端业务可以加一定量的机器，然后搞稳定性，依赖关系，容量规划，做弹性，提升吞吐量。

3.异步队列：然后就是使用可堆积的消息队列或者内存消息队列了，如果抢单具有强顺序，那么先都进队列，然后拿前N（就是库存数）个出来平滑处理，剩下的所有都可以作为失败进行批处理了，甚至还可以做一个定长的队列，再往里写直接提示失败。队列把并发变成串行，从而去掉了锁。

4.内存分配：一些具体的业务，也会考虑预热，提前在每个机器节点内存分配好库存数量，然后直接在内存里处理自己的库存数即可，这样可能也会在极端情况下啊，

5.独立部署：针对不同类型、不同商家、不同来源的商品，部署不同的前端促销集群，这样就把压力分散开了。具体到每个商家，其实量就不大了，双十一销售第一名的商家，并发也不是特别高。

6.服务降级：越重要的抢单，大家越关心自己有没有抢到，而不是特别在意订单立即处理完，也就是说，下单占到位置比处理完成订单要更有价值。比如12306春运抢票，只要告诉用户你抢到了票，但是预计1个小时后订单才会处理完，用户有这个明确预期，就可以了，用户不会立马使用这张票，也不会在意1分钟内处理完还是1小时处理完。

需要注意的是其中部分模式会导致销售不足或者超卖，销售不足可以从抢购里加一些名单补发，也可以加一轮秒杀。超卖比较麻烦，所以一般会多备一点货，比如抢100个iPhone，提前准备105个之类的，也会证明在实际操作里非常有价值。

https://www.zhihu.com/question/27894855/answer/906948755

网易二面

1.数据库事务的ACID分别使用什么技术来保证的？

数据库事务的ACID特性介绍

2.数据库为什么使用B+树？

为什么使用B+树？言简意赅，就是因为：
1.文件很大，不可能全部存储在内存中，故要存储到磁盘上
2.索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数（为什么使用B-/+Tree，还跟磁盘存取原理有关。）
3.局部性原理与磁盘预读，预读的长度一般为页（page）的整倍数，（在许多操作系统中，页得大小通常为4k）
4.数据库系统巧妙利用了磁盘预读原理，将一个节点的大小设为等于一个页，这样每个节点只需要一次I/O就可以完全载入，(由于节点中有两个数组，所以地址连续)。而红黑树这种结构，h明显要深的多。由于逻辑上很近的节点（父子）物理上可能很远，无法利用局部性

https://blog.csdn.net/bigtree_3721/article/details/73151472

3.数据库一条sql语句的执行过程？存储引擎是如何工作的？

sql语句的执行过程

4.计算机在处理++i和i++的区别？

i++ 与 ++i 的主要区别有两个：

1. i++ 返回原来的值，++i 返回加1后的值。
2. i++ 不能作为左值，而++i 可以。

i++ 最后返回的是一个临时变量，而临时变量是右值。

前++和后++的效率问题:

1. 对于内置数据类型，以现在的编译器的优化水平，前++和后++没区别的，这个可以通过看汇编代码证明。
2. 对于自定义数据类型，像STL，前++的效率要高于后++，所以STL中关于iterator都是前++的。

对于内置数据类型，效率相近的原因：前缀法和后缀法没有任何区别，编译器的处理都应该是相同的。

对于自定义数据类型，++i效率比i++效率高的原因： 因为前缀式（++i）可以返回对象的引用，而后缀式（i++）必须产生一个临时对象保存更改前对象的值并返回(实现过自定义类型++运算符定义的就知道)，所以导致在大对象的时候产生了较大的复制开销，引起效率降低 ，因此处理使用者自定义类型（注意不是指内建类型）的时候，应该尽可能的使用前缀式地增/递减，因为他天生体质较佳。

https://blog.csdn.net/asuphy/article/details/13628829?utm_medium=distribute.pc_relevant.none-task-blog-baidujs_title-11&spm=1001.2101.3001.4242