Rubrik 电面 2017 May

面了两轮Rubrik的电面，第一轮是算法题，先是求maximum continuous subarray, 然后一个follow-up: 如果限定这个subarray的长度不大于k，该怎么办？
用的prefix求解，对于followup，同时maintain一个k位之前的prefix和maxPrefix就行了。一个ABC小哥面的我，人很nice，我做followup的时候卡住了，他各种提示。

接着收到邀请进行第二轮phone interview，说是system design相关的。

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

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

面试官是个中国小哥，感觉和他聊得还不错。他提出apply所有delta的时候可以只apply所需要查询的key对应的change，我一开始没反应过来，后来他给了个例子我才明白他的意思。做了相应的更改后面试时间基本到了，然后问了他两个team相关的问题。

本来感觉这次phone interview应该能过，但今天还是收到了reject。哎，发个面经攒人品。

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

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

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

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

自己尝试着写了一个 不知道对不对

1. public static int MaximumSubarrayK (int[] nums, int k) {
   
2.             int len = nums.length;
   
3.             if (len == 0 || k == 0) return 0;
   
4.             int prefix = 0;
   
5.             int max = nums[0];
   
6.             int s = nums[0];
   
7.            
   
8.             for(int i = 1; i < len; i++) {
   
9.                     if (s >0) {
   
10.                             // when reaching the size k, we should either continue the current subarray or
    
11.                             // we start from the current element
    
12.                             if (i - prefix >= k) {
    
13.                                     if (s - nums[prefix] > nums[i]) {
    
14.                                             s -= nums[prefix++];
    
15.                                     } else {
    
16.                                             s = nums[i];
    
17.                                             prefix = i;
    
18.                                     }
    
19.                             } else {
    
20.                                     s += nums[i];
    
21.                             }
    
22.                     // start from current element and update the prefix
    
23.                     } else {
    
24.                             s = nums[i];
    
25.                             prefix = i;
    
26.                     }
    
27.                     max = Math.max(max, s);
    
28.             }
    
29.             return max;
    
30.     }

复制代码

楼主 怎么设计 Snapshot这个class的？还是pre-define的？

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

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

看来楼主遇到了跟我一样的面试官，这个人感觉就没打算让人过

followup，同时maintain一个k位之前的prefix和maxPrefix就行了第一个prefix 可以理解因该就是out of bound k 的扣掉maxPrefix 这个怎解呢? 我只想到用treeMap 扣掉prefix 然后找一个in bound 的such as cur_sum - treemap.getSmallest() 最大? 楼主能给个栗子吗? thansk

第一题是求max subarray sum 吗?

第一题用红黑树 multiset

LeetCodeOJ 发表于 2017-5-12 23:09
第一题用红黑树 multiset

是不是只有用红黑树才可以知道这个maximum subarray具体的范围是什么？

求问LZ 第一题的followup解法能讲详细一点嘛？ 跪谢