新鲜出炉Rubrik一面

今天刚面了Rubrik第一轮，两道没见过的题，第一题给了hint才用binary search 做出来的，第二道题也是给了hint，面完以为挂了，但刚收到邮件说可以move on

Quenstion 1: 找所有local maximum，array满足两个

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

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

n1 -> n3，可以改变任何一个edge的start和end node.

Minimum number of swaps to make all nodes good



我是用DFS做的，感觉用union find应该也可以做。

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

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

求问楼主~第一题 left = 8, right = 16 这一段中间的极小值是怎么设计跳过的？

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

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

Galoisgun 发表于 2017-10-12 07:55
求问楼主~第一题 left = 8, right = 16 这一段中间的极小值是怎么设计跳过的？

额，我面试写的，没有跳过，似乎也没法跳过吧

贴个代码，求点大米，顺便求检验一下。

1. class Solution:
   
2.         def localMax(self, nums):
   
3.                 res = []
   
4.                 if nums is None or len(nums) == 0:
   
5.                         return res
   
6. 
   
7.                 start, end = 0, len(nums) - 1
   
8.                 mid = (start + end) / 2
   
9.                 if mid - 1 >= start and mid + 1 <= end:
   
10.                         if nums[mid-1] < nums[mid] > nums[mid+1]:
    
11.                                 res.append(nums[mid])
    
12.                         if abs(nums[mid] - nums[start]) != mid - start:
    
13.                                 res += self.localMax(nums[:mid+1])
    
14.                         if abs(nums[end] - nums[mid]) != end - mid:
    
15.                                 res += self.localMax(nums[mid:])
    
16.                 return res
    
17. 
    
18. s = Solution()
    
19. nums = [1,2,3,4,5,6,5,4,3,4,5,4,3,2,1,2,1]
    
20. print(s.localMax(nums))

复制代码

AllenTang123 发表于 2017-10-12 12:35
贴个代码，求点大米，顺便求检验一下。

如果input是1 2 3 4 5 6 7 8呢？

请问有向图使用array数组中存linkedlist表示的吗？

可以再详细的说下第二题swap 么？ 例子没看懂

1. def func(nums):
   
2.     low, high = 0, len(nums) - 1
   
3.     while low < high:
   
4.         mid = (low + high) / 2
   
5.         if nums[mid] < nums[mid + 1]:
   
6.             low = mid + 1
   
7.         else:
   
8.             high = mid
   
9.     return nums[low]
   
10. 
    
11. 
    
12. nums1 = [1, 2, 3, 4, 5, 6, 7, 8, 7, 6, 5, 4, 3, 4, 5, 6, 7, 6, 5]
    
13. nums2 = [1, 2, 3, 4, 5]
    
14. nums3 = [5, 4, 3, 2, 1]
    
15. 
    
16. assert(func(nums1) == 8)
    
17. assert(func(nums2) == 5)
    
18. assert(func(nums3) == 5)
    

复制代码

补充内容 (2019-2-25 09:20):
瞎了 我还以为是只找一个