回复: 28
收起左侧

Rubrik 电面 2017 May

 
本楼:   👍  1
100%
0%
0   👎
全局:   9
100%
0%
0

2017(4-6月) 码农类General 硕士 全职@rubrik - 猎头 - 技术电面  | Fail | 在职跳槽

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
面了两轮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即刻解锁阅读权限查看其他获取积分的方式

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

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



上一篇:ziprecruiter
下一篇:求职告一段落, 分享一道uber面试题

本帖被以下淘专辑推荐:

  • · Rubrik|主题: 18, 订阅: 3
 楼主| xlusjtu 2017-5-13 14:35:43 | 显示全部楼层
本楼:   👍  2
100%
0%
0   👎
全局:   9
100%
0%
0
草袋豆子 发表于 2017-5-13 00:55
是不是只有用红黑树才可以知道这个maximum subarray具体的范围是什么?

Sorry之前描述有错误,followup是求长度不小于K的maximum subarray sum。

Example:
// [-4, -2, 1, -3], k = 2   ->   -1   [-2, 1]
// [1, 1, 1, 1, 1, 1], k = 3  ->  6

不需要红黑树,maintain当前prefix,prefixK(k位以前的prefix),minPrefixK(k位以前看到的最小的prefix)就行了。O(N)遍历一遍同时更新这些变量。
回复

使用道具 举报

endofunctor 2017-7-25 13:22:09 | 显示全部楼层
本楼:   👍  0
0%
0%
0   👎
全局:   140
85%
15%
25
可能有bug,求轻拍
一面第一题followup,如果是求大于k的:
  1. int find(vector<int>& v, int k) {
  2.   vector<int> sum(v.size() + 1, 0);
  3.   //0 -4, -6, -5, -8                                                                                                                        
  4.   for (int i = 0; i < v.size(); ++i) {
  5.     sum[i + 1] = sum[i] + v[i];
  6.   }
  7.   int x = 0;
  8.   int y = 0;
  9.   int diff = sum[k];
  10.   for (int i = k + 1; i < sum.size(); ++i) {
  11.     ++y;
  12.     if (sum[y] < sum[x]) {
  13.       x = y;
  14.     }
  15.     diff = max(diff, sum[i] - sum[x]);
  16.   }
  17.   return diff;
  18. }
复制代码

如果是求长度小于等于k的子数组,则可以用一个单调队列,每个元素对应cumulative sum的下标,每次iteration时,如果队首元素越界,则出队列,然后将当前元素与队首元素求差,然后维护队列单调性(出队入队):
  1. int find2(vector<int>& v, int k) {
  2.   deque<int> dq;
  3.   vector<int> sum(v.size() + 1, 0);
  4.   //0 -4, -6, -5, -8                                                                                                                        
  5.   // 0 1 2 3 4 5 6                                                                                                                           
  6.   for (int i = 0; i < v.size(); ++i) {
  7.     sum[i + 1] = sum[i] + v[i];
  8.   }
  9.   int diff = INT_MIN;
  10.   for (int i = 0; i < k + 1; ++i) {
  11.     if (not dq.empty())
  12.       diff = max(diff, sum[i] - sum[dq.front()]);
  13.     while (not dq.empty() && sum[dq.back()] > sum[i]) {
  14.       dq.pop_back();
  15.     }
  16.     dq.push_back(i);
  17.   }
  18.   for (int i = k + 1; i < sum.size(); ++i) {
  19.     if (i - k - 1 >= dq.front()) {
  20.       dq.pop_front();
  21.     }
  22.     if (not dq.empty())
  23.       diff = max(diff, sum[i] - sum[dq.front()]);
  24.     while (not dq.empty() && sum[dq.back()] > sum[i]) {
  25.       dq.pop_back();
  26.     }
  27.     dq.push_back(i);
  28.   }
  29.   return diff;
  30. }
复制代码

补充内容 (2017-7-25 13:23):
脑抽了,两个循环可以merge到一起的。。。
扫码关注一亩三分地求职移民公众号
更多干货内容等你发现
回复

使用道具 举报

dukecat0613 2017-5-13 05:00:27 | 显示全部楼层
本楼:   👍  0
0%
0%
0   👎
全局:   70
92%
8%
6
自己尝试着写了一个 不知道对不对
  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.     }
复制代码
回复

使用道具 举报

sophie729 2017-5-12 11:22:58 | 显示全部楼层
本楼:   👍  0
0%
0%
0   👎
全局:   117
98%
2%
2
楼主 怎么设计 Snapshot这个class的?还是pre-define的?
回复

使用道具 举报

 楼主| xlusjtu 2017-5-12 11:40:49 | 显示全部楼层
本楼:   👍  0
0%
0%
0   👎
全局:   9
100%
0%
0
sophie729 发表于 2017-5-12 11:22
楼主 怎么设计 Snapshot这个class的?还是pre-define的?

我就把它作为timestamp的
class Snapshot {
  long timestamp;
}
不是pre-define的,你可以有其它的设计,我也不知道我的做法是不是好。
回复

使用道具 举报

cynthiazp 2017-5-12 14:17:20 | 显示全部楼层
本楼:   👍  0
0%
0%
0   👎
全局:   452
97%
3%
15
看来楼主遇到了跟我一样的面试官,这个人感觉就没打算让人过
回复

使用道具 举报

say543 2017-5-12 15:13:45 | 显示全部楼层
本楼:   👍  0
0%
0%
0   👎
全局:   122
92%
8%
11
followup,同时maintain一个k位之前的prefix和maxPrefix就行了第一个prefix 可以理解因该就是out of bound k 的扣掉maxPrefix 这个怎解呢? 我只想到用treeMap 扣掉prefix 然后找一个in bound 的such as cur_sum - treemap.getSmallest() 最大? 楼主能给个栗子吗? thansk
回复

使用道具 举报

oio14644 2017-5-12 22:53:25 | 显示全部楼层
本楼:   👍  0
0%
0%
0   👎
全局:   321
86%
14%
51
第一题是求max subarray sum 吗?
回复

使用道具 举报

LeetCodeOJ 2017-5-12 23:09:44 | 显示全部楼层
本楼:   👍  0
0%
0%
0   👎
全局:   28
50%
50%
28
第一题用红黑树 multiset
回复

使用道具 举报

草袋豆子 2017-5-13 00:55:25 | 显示全部楼层
本楼:   👍  0
0%
0%
0   👎
全局:   100
55%
45%
81
LeetCodeOJ 发表于 2017-5-12 23:09
第一题用红黑树 multiset

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

使用道具 举报

dukecat0613 2017-5-13 02:01:20 | 显示全部楼层
本楼:   👍  0
0%
0%
0   👎
全局:   70
92%
8%
6
求问LZ 第一题的followup解法能讲详细一点嘛? 跪谢
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

Advertisement
>
快速回复 返回顶部 返回列表