字节北美电面两题

markbs123 发表于 2020-12-31 16:14
这样写不会有错么，会一直死循环的啊，求大大指正

我直接copy上一个帖子的代码，只改了left 和right，没仔细看，我又改了一下（不会写python，可能有语法错误）：

1. result = -1;
   
2. while left <= right:
   
3.      mid = (left + right) / 2
   
4.      if interval[mid][0] <= target <= interval[mid][1]:
   
5.           left = mid + 1
   
6.           result = mid
   
7.      else:
   
8.            right =  mid - 1
   
9.     return result == -1 ? null : interval[result]

复制代码

quanatm 发表于 2020-12-26 07:51
前两轮蠡口

劳烦大大能不能给下题号，感谢感谢

woshiduga 发表于 2020-12-26 08:47
第一题应该先排序 然后对每个 数进行binary search，
[mw_shl_code=python,true]while left < right:
    ...

大大能不能多解释一下，sort的时候是按start 升序，end 降序排列的？ 还有这样二分得到的结果貌似不对啊

markbs123 发表于 2021-1-1 09:17
大大能不能多解释一下，sort的时候是按start 升序，end 降序排列的？ 还有这样二分得到的结果貌似不对啊

因为fully covered或者disjoint
比如
[2, 10]
[3, 7]，[6, 10]这种，target是5，利用二叉搜索找到满足条件的最左边的interval [3, 7]，这样肯定得到的range最小啊

JoyForce 发表于 2021-1-1 08:54
我直接copy上一个帖子的代码，只改了left 和right，没仔细看，我又改了一下（不会写python，可能有语法错 ...

感谢大大回我，但我还是有一个问题，如果所有的区间是fully overlapped, 二分是可以的，但楼主给的题目里用例是[[2,3],[2,5],[1,8],[1,18],[20,25]], [20, 25]是exclusive的，二分应该是不行，想来想去貌似只有构建Segment Tree的办法了，想听听大大的建议，感谢感谢

woshiduga 发表于 2021-1-1 09:31
因为fully covered或者disjoint
比如
[2, 10]

感谢感谢，二分如果是全部intervals fully overlapped 没问题，但如果有disjoint的话，就好像不行，大大怎么看

第一题nlogn中的N指啥挺重要的。。。numbers的长度如果是常数的话对于numbers的每个数循环一遍interval就行了最后出来是O(n)?

markbs123 发表于 2021-1-1 09:36
感谢感谢，二分如果是全部intervals fully overlapped 没问题，但如果有disjoint的话，就好像不行，大大 ...

不fully covered 我觉得就只能暴力，因为题目要求 并且说lgn

nlogn, sort 一次 然后 便利一次

问一下lz一般聊天的话是什么内容呀，项目吗，还是行为面试啊，谢谢！