字节北美电面两题

第一题应该先排序 然后对每个 数进行binary search，

1. while left < right:
   
2.      mid = (left + right) / 2
   
3.      if interval[mid][0] <= target <= interval[mid][1]:
   
4.           right = mid
   
5.      else:
   
6.            left =  mid + 1
   
7.     return interval[left]

复制代码

[quote]woshiduga 发表于 2020-12-25 16:47
第一题应该先排序 然后对每个 数进行binary search，

1. while left < right:
   
2.     ...[/quote]
4. left, right弄反了吧，应该是
   
5. 
   
6. [code]while left < right:
   
7.      mid = (left + right) / 2
   
8.      if interval[mid][0] <= target <= interval[mid][1]:
   
9.           left = mid
   
10.      else:
    
11.            right =  mid - 1
    
12.     return interval[left]

复制代码

treeguard 发表于 2020-12-26 07:41
1.1.0.0/22 已经包含了 1.1.1.0/24所能包含的所有IP地址了

明白了，如果要检测是不是有包含关系，那我这个解法就没办法了

woshilxd912 发表于 2020-12-26 09:24
明白了，如果要检测是不是有包含关系，那我这个解法就没办法了

这道题我觉得可以这样 1) 将subnet 转换成interval 2) merge intervals 3) convert intervals into subnets

这个子网掩码的题，没有点网络知识还真是理解不了

treeguard 发表于 2020-12-26 09:34
这道题我觉得可以这样 1) 将subnet 转换成interval 2) merge intervals 3) convert intervals into subne ...

求一份代码

JoyForce 发表于 2020-12-26 09:14
left, right弄反了吧，应该是

[mw_shl_code=java,true]while left < right:

对对 就是大概这个形式，因为题目里面说的是fully overlapped 不然没法binary search

有没有大神能解释下这第二题啥意思？🙏

第一题如果overlap的interval我在想是不是应该先merge? 比如[2, 5]和[3, 4]这个如果找4，那按照二分的逻辑往前找肯定顺序是不对的，我们要不要把[2, 5]跟[3,4] merge在一个index底下，这样保证顺序一致性？

JoyForce 发表于 2020-12-26 09:14
left, right弄反了吧，应该是

[mw_shl_code=java,true]while left < right:

这样写不会有错么，会一直死循环的啊，求大大指正