美团面试
文章目录
美团一面
1. 算法
给定一个整形数组arr,已知其中所有的值都是非负的,将这个数组看作一个容器,请返回容器能装多少水。
输入: [3,1,2,5,2,4]
输出: 5
42. 接雨水
//注意返回值类型是long long
long long maxWater(vector<int>& arr) {
int left = 0, right = arr.size()-1;
int leftMax = arr[left], rightMax = arr[right];
long long res = 0;
while (left < right) {
if (arr[left] < arr[right) {
++left;
if (leftMax < arr[left]) {
leftMax = arr[left];
}
res += leftMax - arr[left];
} else {
--right;
if (rightMax < arr[right]) {
rightMax = arr[right];
}
res += rightMax - arr[right];
}
}
return res;
}2. 问题
- 什么是死锁,什么时候会发生死锁,死锁避免的方法有哪些?
- 说到死锁产生的四个条件。比如进程1有a,请求b;进程2有b请求a,陷入这种循环等待的场景就称为死锁
- 银行家算法可以防止进入不安全状态
2.你提到银行家算法,详细讲下。除了银行家算法还有什么死锁避免的方式吗?
- 每个进程都会保存当前已获得资源、系统总资源和剩余资源数目,如果占据当前资源会进入不安全状态就不会占据
- 还可以通过规定每个线程只能占有一个锁资源
- 使所有进程请求资源的顺序一致,以防止发生资源的循环嵌套
3.从浏览器输入URL的过程
4.进程和线程的区别
5.有哪些排序算法?复杂度是多少?这个复杂度是怎么计算的?哪些排序算法是稳定的,哪些不稳定?
- 冒泡、直接插入、快排、堆排序、归并
- 冒泡稳定o(n2), 直接插入稳定o(n2), 快排不稳定o(nlogn), 堆排不稳定 o(nlogn), 归并 o(nlogn)
6.为什么归并排序的时间复杂度是o(nlogn)? - 有2路、多路的归并。主要是对不同的子序列进行排序,然后合并多个子序列
分为两步,一个是划分、一个是合并
- 合并的复杂度是o(n)
- 划分的过程不断递归,每次将一个o(n)的问题转换为两个o(n/2)的问题
- 相加最后得到的时间复杂度就是o(nlogn)
- B树和B+树的区别,适用场景是什么?
B树(B-树)
- 每个节点都存储数据,关键字由小到大排列
- 主要应用在文件系统
B+树
- 只有叶子结点存储数据,其他节点存储索引
- 叶子节点之间形成有序链表
- 优点:单一节点存储的元素更多, 查询效率更稳定,适用于区间访问
11.问下面这个结构体占用多少内存,内存是如何组织的?
struct B{
char a;
int b;
char c;
};- 答错了。我说的占用8个内存空间,a占一个,b占4个,c字节对其占3个
- 实际上是占用12个内存空间。三个原则,首地址需要是存放最宽数据成员的整数倍,总大小是最宽数据成员的整数倍。所以a占用1个字节,但是int的首地址需要整除4,所以添加了3个字节空间,所以a占4个,b占4个;又因为总大小要是B的整数倍,所以c占4个,总共占用12个
美团二面
算法 25. K 个一组翻转链表
问了下时间复杂度和空间复杂度
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* reverseKGroup(ListNode* head, int k) { ListNode *dummy = new ListNode(-1); dummy->next = head; ListNode *pre = dummy; ListNode *end = dummy; while (end->next != nullptr) { for (int i = 0; i < k && end != nullptr; i++) { end = end->next; } if (end == nullptr) { break; } ListNode *start = pre->next; ListNode *next = end->next; end->next = nullptr; pre->next = reverse(start); start->next = next; pre = start; end = pre; } return dummy->next; } ListNode *reverse(ListNode *head) { ListNode *pre = nullptr, *cur = head; while (cur) { ListNode *q = cur->next; cur->next = pre; pre = cur; cur = q; } return pre; } };
基本问题
- 遇到的最影响深刻的事情,对你影响最大的事情说说看
- vector分配内存的方式,内存分配不够怎么办?如何避免这种拷贝的出现?
- map、unordered_map、vector、list的区别和用处
- 三个盒子,有一个有礼物,选一个,我会帮你在剩下两个中去掉一个空的,请问是保持现有得到礼物的概率大,还是选另一个概率大?
- 反问,问我有什么offer想做啥

评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论