美团后台研发面试题题库

1、线程和进程的区别 进程： 并发执行的程序在执行过程中分配和管理资源的基本单位 进程的执行过程是线性的，进程的切换保护资源。 线程： 是CPU调度的基本单位 线程共享进程中的资源，线程的切换并不影响计算机软硬件资源的分配。 2、中断和异常的区别 中断： 系统停止当前正在运行的程序而转向其他服务 异常： 软件运行过程中的一种开发过程中没有考虑到的程序错误 也称为同步中断，在指令执行结束后发生的中断 3虚拟内存和虚拟地址 虚拟内存： 程序使用的内存，利用外存来扩充内存，需要内存映射 虚拟地址： 由页号和偏移量组成，位数与地址总线的位数相同 4、死锁 必要条件： （1）互斥条件：一个资源每次只能被一个进程使用 （2）请求与保持条件：进程因请求资源而阻塞时，对获得的资源保持不放 （3）不剥夺条件：已获得资源，未使用完之前不能被剥夺 （4）循环等待条件： 解决方法： （1）死锁预防：破坏死锁产生的条件 （2）死锁避免：每次申请之前判断是否安全（银行家算法） （3）死锁检测：（超时法和等待图法） （4）死锁解除 5、内联函数和宏定义 宏定义： 预编译阶段 不做类型检查 内联函数： 编译阶段 做类型检查 短小函数 频繁调用造成内存膨胀 6、数据库索引 唯一索引 索引值唯一，但允许有空值 主键索引 特殊的唯一索引，但不允许有空值 普通索引 组合索引 多个属性值构成的索引 7、聚集索引&非聚集索引 聚集索引 索引键值的逻辑顺序决定了数据的物理储存顺序 叶子节点就是数据块 非聚集索引 索引键值的逻辑顺序与数据的物理顺序可能不一致 叶子结点是指向对应数据块的指针 B+树&平衡二叉树 B+数 所有关键字出现在叶子节点 非叶节点是索引，叶子节点是 储存 更适合做文件索引系统 查找性能接近二分查找树 8、设计模式 1、简单工厂模式：针对同样的数据，不同的操作用同样的接口。由工厂类创建不同的产品，不同的产品都是抽象类的继承类。2、工厂方法：针对同样的数据，不同的操作使用不同的接口。3、抽象工厂：针对不同的数据，不同的操作使用不同的接口。 9、10亿个数找10个频率最高的 1、利用hash方法把数据集分成几个部分。2、利用hash统计每一部分的词频。3、利用堆排序求出每个数据集的前k个。4、合并每个数据集的前k个。 10、1001里两个重复的数字 抑或 11、最大回文子串 动态规划，记录左边回文的最大右边界 12、100层楼丢两个鸡蛋 不等式约束求最大值 13、三狼过河智力题 深度优先搜索 14、斐波那契数列的变形 跑楼梯 15、二叉树层次遍历（如何只遍历某一层） 队列实现， 16、链表反转 注意参数取值 17、二叉树后序遍历，递归和非递归 18、常用排序算法的稳定性 快排，堆排，希尔排序不稳定，举例子 19、为什么静态单例对象？ 单例模式唯一的实例必须为静态 不能创建对象，只能通过类中的接口来调用类中创建的对象。 使用类名直接调用类中的方法，所以类中的成员函数和数据成员必须是静态的。 20、linux系统的特点 开放性，多用户，多任务，良好的界面，设备独立性:操作系统把所有的设备统一当作文件来处理，可靠的安全系统，良好的移植性：适应各种平台，丰富的网络功能。 21、多进程和多线程 前者开销大，后者开销小（数据，资源角度），前者更加独立。 22、多线程编程要点，如何保证线程间数据访问的安全性 负载平衡，发挥每个核的作用。互斥和同步。 23、一棵有序的二叉树中搜索到给定值 二叉排序树 24、C++的内存分配机制 1、内存区：栈、堆、全局/静态、常量。2、类中通过栈中指针在堆内部申请空间。 25、C++面向对象的特点 基本特征：抽象、封装、继承、多态 26、虚函数（作用及实现） 参考简单工厂模式。 27、http协议（请求方式get和post的区别，不同的状态码，URL规格，404是什么错误） get:请求读取，post:请求添加信息，1xx: 通知信息，2xx：成功，3xx:重定向，4xx：客户端出错，5xx:服务器出错，<协议>://<主机域名>:<端口号>/<具体路径>，not found 28、网页的推荐是怎么实现的（cookie,session是什么？储存在什么位置，起什么作用？） cookie记录访问网页的情况。Cookie保存在客户端，session保存在服务器端。 29、10亿个11位的号码中找给定号码是否存在 bool过滤器 30、linux系统中的常用命令 cd,gcc,ls(文件列表),grep,cp(拷贝所有文件),find,mv(移动文件),rm(删除),ps(查看某一时刻进程的运行结果)，tar(打包)，time（测算一个命令的执行时间） 31、I/O多路复用（select，poll，epoll各自的原理，区别，如何使用） 通过一种机监视多个描述符，一旦就绪方可运行。Select: 每次调用，都需要把文件描述符从用户态拷贝进内核态；从内核态遍历所有的文件描述符；支持的文件数量小。 32、项目中遇到的最大困难，如何解决，项目的最大成就 33、找出数组中最大的连续和 动态规划，当前最大值 34、三个线程按照顺序输出 35、hash表和B+树的优势 **数据库索引** 1、唯一索引hash占明显优势。2、范围查找B+树占明显优势。3、B+树查找速度不会有太大波动。 36、合并两个有序链表 37、数据库范式 2NF：非主属性完全函数依赖于码。3NF:非主属性不传递依赖于码。BCNF: 任何函数以来都含有码。 38、快速排序算法（手写） 递归&非递归 39、单例模式中的多线程问题如何解决 懒汉模式：加同步锁，双重检测锁定、静态内部类（类似恶汉模式）。 40、数据库，左右连接，内链接 内链接：只有两个表相匹配的行才在结果中出现。外连接：左外连接，右外连接，完整外部连接。 41、二叉树的遍历 前中后非递归 42、linux命令查看CPU的使用情况 top 43、CPU load命令 进程对列的长度（CPU做多少工作） 44、数据库事务的隔离级别 55 45、脏读，幻读，丢失修改 （读完另一方RoLLBack）、(读完对方已修改再读)、（改完别人又改） 46、锁的类型（排他锁、共享锁） 排他锁（X锁）：只允许加锁一方读取和修改数据其它不能加任何类型的锁。共享锁（S锁）：加锁一方和其它的只能读，其它只能加S锁。 47、字母字符串排序，AaB 重新定义比较函数 48、字符串找出不重复的字符组成的子串 hash表 49、消息队列 不懂 50、页面置换算法 FIFO，LRU,LFU(最不长使用) 51、抖动 刚被置换出的页面马上又被使用 52、缺页中断 页表没有，调入内存 53、条件概率 盒子有球问题 54、九宫格交换棋子 55、数据库隔离级别 1、可读取未确认：写事务阻止写事务，但未阻止读事务（脏数据）。2、可读取确认：写事务阻止读写事务，但读事务不阻止其它事务（不可重复度）。3、可重复读：读事务阻止写事务，但不阻止其它事务（丢失修改）。 56、绳子覆盖数轴上的点 两个端点，小于前走，大于后走 57、2sum和ksum问题 hash方法或排序后左右夹逼，ksum通过遍历转化为2sum问题。 58、数据库failover 59、AQS（如何管理线程，实现公平锁和非公平锁） 60、蓄水池问题 61、实现大数相乘 字符串储存，注意进位 62、操作系统磁盘的了解 物理结构：盘片、磁道、扇区。逻辑结构：引导控制块（系统从该分区引导操作系统有关信息），分区控制块（分区的详细信息）。调度算法：FCFS、SSTF、SCAN、C-SCAN 63、linux shell 64、操作系统内存碎片 65、编程实现：1！+…+N！ 66、sql查询语句 67、volitile关键字，内存屏障和重排序 68、分布式session三种实现方式和优缺点 69、重建二叉树 70、二份查找 左右边界 71、字符串全排列(时间复杂度) 递归算法（按次序交换两个字符的位置），O(n!) 72、数组有正有负，移到两边 快速排序，中轴为0，swap(a[index++],a[i]); 73、判断整数是否为2，4，8的幂次方 return x&(x-1)==0; return x&(x-1)==0&&x&0x55555555!=0; int i; for(i=0;n!=1;i++) n=n>>1; return x&(x-1)&&i%3==0; 74、旋转有序数组，找到其中的一个值（leetcode） 确定左边有序还是右边有序 75、nat协议 网络层协议：网络地址转换，将本地IP地址转换为全球IP地址，使专用网内部的主机与因特网上的主机通信。 76、arp协议 数据链路层：地址解析协议（由IP地址获得MA地址），在本局域网内广播发送请求，响应数据帧是单波发送。（NAPT） 77、ip地址和mac地址的区别 ip地址:网络层地址，包含网络号和主机号，点分十进制表示IPv4 32位,IPv6 128位。 mac地址：物理地址，适配器地址,数据链路层的地址。 78、常见的单例模式 单例模式：某一实体类只需存在一个对象就可以满足所有的业务需求。1、其他类无法初始化该类的对象（构造函数为私有类型）。2、该类可以在类中实例化一个唯一的自身对象（静态对象）。3、当前类可以向外界提供一个唯一的接口来提供实例，并返回一个该类的对象（静态函数）。 恶汉模式： 实例在加载类时建立。线程安全（其他类不能修改实例） 懒汉模式： 其他类调用该类的获取方法时创建实例。线程不安全（多个线程创建多个实例） 81、观察者模式用法，实现 82、hash解决冲突的方法，如何保证多个hash函数不会出现死循环 83、如何破坏单例 反射机制和序列化机制 84、64G内存如何设置堆大小#美团##C++工程师#