美团面试

美团一面

1. 算法

给定一个整形数组arr,已知其中所有的值都是非负的,将这个数组看作一个容器,请返回容器能装多少水。
输入: [3,1,2,5,2,4]
输出: 5
image.png

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. 什么是死锁,什么时候会发生死锁,死锁避免的方法有哪些?
  • 说到死锁产生的四个条件。比如进程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)
  1. 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;
       }
    };

基本问题

  1. 遇到的最影响深刻的事情,对你影响最大的事情说说看
  2. vector分配内存的方式,内存分配不够怎么办?如何避免这种拷贝的出现?
  3. map、unordered_map、vector、list的区别和用处
  4. 三个盒子,有一个有礼物,选一个,我会帮你在剩下两个中去掉一个空的,请问是保持现有得到礼物的概率大,还是选另一个概率大?
  5. 反问,问我有什么offer想做啥

评论

暂无评论