2020年滴滴精选面试题及答案
1. 寻找两个有序数组的中位数
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) { double ret = -1; vector<double> buff; //合并两个数组 for (auto e : nums1) buff.push_back(e); for (auto a : nums2) buff.push_back(a); //将合并后的结果进行排序 sort(buff.begin(), buff.end()); int size3 = buff.size(); //获取中位数 if (size3 % 2 == 0) { ret = ((buff[size3 / 2] + buff[size3 / 2 - 1]) / 2); } else { ret = buff[size3 / 2]; } return ret; }
2.C++实现线程安全的单例模式
懒汉模式: class singleton { protected: singleton() { pthread_mutex_init(&mutex); } private: static singleton* p; public: static pthread_mutex_t mutex; static singleton* initance(); }; pthread_mutex_t singleton::mutex; singleton* singleton::p = NULL; singleton* singleton::initance() { if (p == NULL) { pthread_mutex_lock(&mutex); if (p == NULL) p = new singleton(); pthread_mutex_unlock(&mutex); } return p; }
3.数组中有三个数字出现超过1/4,求这三个数字?
#include <iostream> using namespace std; //求x!中k因数的个数。 int Grial(int x,int k) { int Ret = 0; while (x) { Ret += x / k; x /= k; } return Ret; } int main() { cout << Grial(10, 2) << endl; return 0; } //假设要求一个n!中k的因子个数,那么必然满足例如以下的规则。 //即x=n/k+n/k^2+n/k^3...(直到n/k^x小于0); #include <iostream> using namespace std; int Grial(int x, int k) { int count = 0; int n = x; while (n) { n &= (n - 1); count++; } return x - count; } int main() { cout << Grial(3, 2) << endl; return 0; } //找出数组中出现次数超过数组一半的数字。 #include <iostream> using namespace std; int Grial(int a[], int n) { int count=0; int key; for (int i = 0; i < n; i++) { if (count == 0) { key = a[i]; count = 1; } else { if (key == a[i]) { count++; } else { count--; } } } return key; } int main() { int a[] = {1,2,3,4,5,6,3,3,3,3,3}; cout<<Grial(a, sizeof(a) / sizeof(int))<<endl; return 0; } #include <iostream> //上一题的扩展,有3个数字出现次数超过1/4。 using namespace std; void Grial(int a[], int n) { if (n <= 3)return; int count1=0, key1=0; int count2=0, key2=0; int count3=0, key3=0; for (int i = 0; i < n; i++) { if (!count1 && key2 != a[i] && key3 != a[i]) { count1++; key1 = a[i]; } else if (key1 == a[i]) { count1++; } else if (key2!=a[i] && key3!=a[i]) { count1--; } if (!count2 &&key3 != a[i] && key1!=a[i]) { count2++; key2 = a[i]; } else if (key2 == a[i]) { count2++; } else if (key1!=a[i] && key3!=a[i]) { count2--; } if (!count3 && key1!=a[i] && key2!=a[i]) { count3++; key3 = a[i]; } else if (key3 == a[i]) { count3++; } else if (key1!=a[i] && key2!=a[i]) { count3--; } } cout << key1 << endl; cout << key2 << endl; cout << key3 << endl; } int main() { int a[] = {1,5,5,5,5,2,3,1,2,2,1,1,1,2}; Grial(a, sizeof(a) / sizeof(int)); return 0; }
4.1-2n的数存储在空间为n的数组中,找出出现两次的数字,时间复杂度O(n),空间复杂度O(1)
/* 奇数零次 偶数零次 0 奇数 一次 偶数 零次 -1 奇数 两次 偶数 零次 -2 奇数 零次 偶数 一次-3 奇数 一次 偶数 一次-4 奇数 两次 偶数 一次-5 奇数 零次 偶数 两次-6 奇数一次 偶数 两次-7 奇数两次 偶数两次-8 */ public class Main { public static void main(String[] args) { int[] nums = {1, 3, 5, 15, 7, 8, 5, 3, 6, 15}; findNumber(nums, nums.length); print(nums); } public static void findNumber(int[] nums, int length) { for (int i = 0; i < length; ) { if (nums[i] <= 0){ i++; continue; } int index = nums[i] / 2; boolean isOdd = (nums[i] % 2 == 0) ? false : true; switch (nums[index]) { case 0: if (isOdd == true) { nums[index] = -1; } else { nums[index] = -3; } break; case -1: if (isOdd == true) { nums[index] = -2; } else { nums[index] = -4; } break; case -2: nums[index] = -3; break; case -3: if (isOdd == true) { nums[index] = -4; } else { nums[index] = -6; } break; case -4: if (isOdd == true) { nums[index] = -5; } else { nums[index] = -7; } break; case -5: nums[index] = -6; break; case -6: nums[index] = -7; break; case -7: nums[index] = -8; break; default: swap(nums, i, index); if (isOdd) { nums[index] = -1; } else { nums[index] = -3; } continue; } nums[i++]=0; } } public static void swap(int[] nums, int i, int j){ int temp =nums[i]; nums[i]=nums[j]; nums[j]=temp; } public static void print(int[] nums) { for (int i = 0; i < nums.length; i++) { if (nums[i] == -2) { System.out.println(i * 2 + 1); } else if (nums[i] == -6) { System.out.println(i * 2); } else if (nums[i] == -8) { System.out.println(i * 2); System.out.println(i * 2 + 1); } } } }
5.长度为1的线段,随机在其上选择两点,将线段分为三段,问这3段能组成一个三角形的概率是多少?
可行域是
请在这里输入引用内容
x+y+z=1,0<x,y,z<1
请在这里输入引用内容
显然,可行域与我的博客一条长度为1的线段,随机剪两刀,求有一根大于0.5的概率问题一样。
要令三段成为一个三角形,必须满足
请在这里输入引用内容
x+y>z, x+z>y, y+z>x
请在这里输入引用内容
∣x−y∣<z,∣x−z∣<y,∣y−z∣<x
又x+y+z=1,当x+y=z 时,有z=0.5 z=0.5z=0.5,因此当x,y,z 中有一个大于0.5时,就无法成立一个三角形。
当x−y=z时,将x−y=z代入x+y+z=1,可得x=0.5。因此当x,y,z中有一个大于0.5时,就无法成立一个三角形。
因此解空间刚好与一条长度为1的线段,随机剪两刀,求有一根大于0.5的概率相反。而一条长度为1的线段,随机剪两刀,求有一根大于0.5的概率的概率为0.75。因此这3段能组成一个三角形的概率是多少是1−0.75=0.25。
6.智能指针的实现原理?
智能指针的基本原理就是将指针通过对象去管理,delete的操作利用析构函数执行, 而析构函数的调用是根据这个对象的作用域来确定的,离开了作用域,析构函数被调用。 delete的操作也将被执行。
7.请解释什么是C10K问题,后来是怎么解决的?
1.C10K问题
互联网还不够普及,用户也不多。一台服务器同时在线100个用户估计在当时已经算是 大型应用了。所以并不存在什么C10K的难题。互联网的爆发期应该是在www网站,浏 览器,雅虎出现后。最早的互联网称之为Web1.0,互联网大部分的使用场景是下载一 个Html页面,用户在浏览器中查看网页上的信息。这个时期也不存在C10K问题。
Web2.0时代到来后就不同了,一方面是普及率大大提高了,用户群体几何倍增长。另 一方面是互联网不再是单纯的浏览万维网网页,逐渐开始进行交互,而且应用程序的逻 辑也变的更复杂,从简单的表单提交,到即时通信和在线实时互动。C10K的问题才体 现出来了。每一个用户都必须与服务器保持TCP连接才能进行实时的数据交互。 Facebook这样的网站同一时间的并发TCP连接可能会过亿。
腾讯QQ也是有C10K问题的,只不过他们是用了UDP这种原始的包交换协议来实现的, 绕开了这个难题。当然过程肯定是痛苦的。如果当时有epoll技术,他们肯定会用TCP。 后来的手机QQ,微信都采用TCP协议。
这时候问题就来了,最初的服务器都是基于进程/线程模型的,新到来一个TCP连接, 就需要分配1个进程(或者线程)。而进程又是操作系统最昂贵的资源,一台机器无法 创建很多进程。如果是C10K就要创建1万个进程,那么操作系统是无法承受的。如果 是采用分布式系统,维持1亿用户在线需要10万台服务器,成本巨大,也只有Facebook, Google,雅虎才有财力购买如此多的服务器。这就是C10K问题的本质。
实际上当时也有异步模式,如:select/poll模型,这些技术都有一定的缺点,如selelct 最大不能超过1024,poll没有限制,但每次收到数据需要遍历每一个连接查看哪个连 接有数据请求。
2.解决方案
解决这一问题,主要思路有两个:
一个是对于每个连接处理分配一个独立的进程/线程;
另一个思路是用同一进程/线程来同时处理若干连接。
请在这里输入引用内容
每个进程/线程同时处理多个连接
1.传统思路
最简单的方法是循环挨个处理各个连接,每个连接对应一个 socket,当所有 socket 都 有数据的时候,这种方法是可行的。
但是当应用读取某个 socket 的文件数据不 ready 的时候,整个应用会阻塞在这里等 待该文件句柄,即使别的文件句柄 ready,也无法往下处理。
思路:直接循环处理多个连接。
问题:任一文件句柄的不成功会阻塞住整个应用。
请在这里输入引用内容
2.select
要解决上面阻塞的问题,思路很简单,如果我在读取文件句柄之前,先查下它的状态, ready 了就进行处理,不 ready 就不进行处理,这不就解决了这个问题了嘛?
于是有了 select 方案。用一个 fd_set 结构体来告诉内核同时监控多个文件句柄,当 其中有文件句柄的状态发生指定变化(例如某句柄由不可用变为可用)或超时,则调用 返回。之后应用可以使用 FD_ISSET 来逐个查看是哪个文件句柄的状态发生了变化。
这样做,小规模的连接问题不大,但当连接数很多(文件句柄个数很多)的时候,逐个 检查状态就很慢了。因此,select 往往存在管理的句柄上限(FD_SETSIZE)。同时, 在使用上,因为只有一个字段记录关注和发生事件,每次调用之前要重新初始化 fd_set 结构体。
int select(int nfds, fd_set *readfds, fd_set *writefds, fd_set *exceptfds, struct timeval *timeout);
思路:有连接请求抵达了再检查处理。
问题:句柄上限+重复初始化+逐个排查所有文件句柄状态效率不高。
请在这里输入引用内容
3.poll
poll 主要解决 select 的前两个问题:通过一个 pollfd 数组向内核传递需要关注的 事件消除文件句柄上限,同时使用不同字段分别标注关注事件和发生事件,来避免重复 初始化。
int poll(struct pollfd *fds, nfds_t nfds, int timeout);
思路:设计新的数据结构提供使用效率。
问题:逐个排查所有文件句柄状态效率不高。
请在这里输入引用内容
4.epoll
既然逐个排查所有文件句柄状态效率不高,很自然的,如果调用返回的时候只给应用提 供发生了状态变化(很可能是数据 ready)的文件句柄,进行排查的效率不就高多了么。
epoll 采用了这种设计,适用于大规模的应用场景。
实验表明,当文件句柄数目超过 10 之后,epoll 性能将优于 select 和 poll;当文 件句柄数目达到 10K 的时候,epoll 已经超过 select 和 poll 两个数量级。
int epoll_wait(int epfd, struct epoll_event *events, int maxevents, int timeout);
思路:只返回状态变化的文件句柄。
问题:依赖特定平台(Linux)。
因为Linux是互联网企业中使用率最高的操作系统,Epoll就成为C10K killer、高并 发、高性能、异步非阻塞这些技术的代名词了。
请在这里输入引用内容
5.libevent
由于epoll, kqueue, IOCP每个接口都有自己的特点,程序移植非常困难,于是需要对 这些接口进行封装,以让它们易于使用和移植,其中libevent库就是其中之一。跨平 台,封装底层平台的调用,提供统一的 API,但底层在不同平台上自动选择合适的调用。
按照libevent的官方网站,libevent库提供了以下功能:当一个文件描述符的特定事 件(如可读,可写或出错)发生了,或一个定时事件发生了,libevent就会自动执行 用户指定的回调函数,来处理事件。目前,libevent已支持以下接口/dev/poll, kqueue, event ports, select, poll 和 epoll。Libevent的内部事件机制完全是基于所使用 的接口的。因此libevent非常容易移植,也使它的扩展性非常容易。目前,libevent 已在以下操作系统中编译通过:Linux,BSD,Mac OS X,Solaris和Windows。
8.使用“反向代理服务器”的优点是什么?
(1)提高访问速度
由于目标主机返回的数据会存在代理服务器的硬盘中,因此下一次客户再访问相同的站点数据时,会直接从代理服务器的硬盘中读取,起到了缓存的作用,尤其对于热门站点能明显提高请求速度。
(2)防火墙作用
由于所有的客户机请求都必须通过代理服务器访问远程站点,因此可在代理服务器上设限,过滤某些不安全信息。
(3)通过代理服务器访问不能访问的目标站点
互联网上有许多开发的代理服务器,客户机可访问受限时,可通过不受限的代理服务器访问目标站点,通俗说,我们使用的***浏览器就是利用了代理服务器,可直接访问外网。