🐶面经

Andy_balabala 发表于 2022-2-22 21:34
感谢楼主分享，能讲讲你是怎么优化第一题当interval是固定length的吗？
还有动物实研室是可以用公共祖先二 ...

可以建bucket，然后每次更新bucket就好

对，就是bfs，很简单

Surge_nan 发表于 2022-2-23 22:40
感谢楼主的回复，不过为什么size固定的时候就不需要merge了呢？难道这种情况下给的interval不会重叠吗？

建bucket就好

mron 发表于 2022-2-23 11:48
这也太效率了吧面完当天就收集好了feedback么。。

差不多，有offer催的，hr很给力

laoxiang33 发表于 2022-2-23 09:07
楼主能具体说一下第四题么？是有向图，无向图，输入是matrix还是啥？是咋做的呢？ 多谢

一个matrix，2d array

TDKPSY 发表于 2022-2-23 08:57
我的想法是merge interval以后存在treemap里， 在你判断target interval的时候，不需要遍历所有的merged  ...

我是直接merge的，nlogn，他也没要求优化，觉得这个复杂度已经可以了

edwardsun007 发表于 2022-2-22 23:03
第一个 是给了先给一组interval 然后查看另外一个interval是否和他们重合吗？

是看是否被cover

第一题的这个follow up如果所有interval的长度都是一样的话应该是可以O(n)时间和O(1)空间做的，直接循环一遍一个个interval比较就好。它和原题的关键差别在于不会出现把被检查的目标区间砍成一段一段的，所以只要维护一对起止点就行。

1. bool isIntervalCovered(vector<int>& intervalStarts, int intervalLength, int target) {
   
2.   int targetStart = target, targetEnd = target + intervalLength;
   
3.   for (int start: intervalStarts) {
   
4.     if (start < targetEnd && start + intervalLength > targetStart) {
   
5.       if (start >= targetStart) {
   
6.         targetEnd = start;
   
7.       } else {
   
8.         targetStart = start + intervalLength;
   
9.       }
   
10.     }
    
11.   }
    
12.   return targetStart >= targetEnd;
    
13. }

复制代码

第一题我想的是segment tree，先建tree，再在tree里查region里的count是不是等于region的大小

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

jhdyss 发表于 2022-2-24 02:22
一个matrix，2d array

必须经过几个点的follow up， 楼主能不能分享一下思路？谢谢