<
回复: 8
收起左侧

MS OA 4月

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

2024(4-6月) 码农类General 硕士 全职@microsoft - Other - 在线笔试  | 😃 Positive 🙂 EasyOther | 在职跳槽

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

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

x
130min 3题,都是过去半年内地里的面筋题。
1. notification message truncate to first K characters:
split by space然后考虑几个题目里列出来的corner case就能过,O(n)
2. cover n holes in a row with 2 boards
holes的位置排序,然后对每个(holes[i], holes[i+1])的gap,考虑两块板子分别cover掉gap左右两边的长度就能得到全局最优,O(nlogn) + O(n)
3. total waiting time
您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限查看其他获取积分的方式
当前位置前后分别有多少items已经被处理了,算面积时可以减掉。O(nlogn)。也可以用线段树来做,但是代码太长了,不如TreeSet整题十几行就能写完。

求米~

评分

参与人数 3大米 +7 收起 理由
wez10 + 1 给你点个赞!
sean51623 + 1 很有用的信息!
清道神君 + 5 欢迎分享你知道的情况,会给更多大米奖励!

查看全部评分


上一篇:求robinhood题
下一篇:Pennymac Technology Internship 2024 面经
sean51623 2024-5-4 01:50:00 | 显示全部楼层
本楼:   👍  1
100%
0%
0   👎
全局:   60
100%
0%
0
再補充一些, 我昨天已經收到信not moving forward, 後來自己想有幾個點提醒一下Codility (OA的系統):

* 最後只能submit一次! 可以自己run code無數次, 不過example test cases大概只有3-4個, 也不會有其他的hidden test cases讓你validate, 很需要自己想到潛在的corner cases並修正, 不然一旦提交就不能再改了, 這點我很不熟悉, 跟hackerrank很不一樣 (hackerrank是hidden cases也可以讓你測無數次, 確定都過了再submit就好)

* 蠻建議自己開始之前就都先寫好一個能通過example test cases的版本, 像第一題 (split by space)我覺得很簡單就沒花太多心思, 但是實際寫的時候花的時間比當初預期多了很多(corner cases很多很雜)

整體來說我覺得確實不是很容易的, 能夠第一次看到題目就順利完成的人真的很厲害
回复

使用道具 举报

sean51623 2024-5-2 16:04:51 | 显示全部楼层
本楼:   👍  1
100%
0%
0   👎
全局:   60
100%
0%
0
本帖最后由 sean51623 于 2024-5-2 01:07 编辑

今天下午剛寫完OA, 這題還是沒寫好, 把一些踩了的坑整理一下吧, 大致尋著樓主的思路, 用了PriorityQueue和TreeSet, 小地方後來用自己的想法修改了一下:
  1. public class NCustomerWaitingTime {
  2.     public static void main(String[] args) {
  3.         System.out.println(waitingTime(new int[]{3, 1, 2})); // 13
  4.         System.out.println(waitingTime(new int[]{1, 2, 3, 4})); // 24
  5.         System.out.println(waitingTime(new int[]{7, 7, 7})); // 60
  6.         System.out.println(waitingTime(new int[]{10000})); // 10000
  7.     }

  8.     public static long waitingTime(int[] T) {
  9.         if (T.length == 1) return T[0];
  10.         long result = 0L, increasedArea = 0L;
  11.         
  12.         PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> ((a[1] == b[1]) ? a[0] - b[0] : a[1] - b[1]));
  13.         TreeSet<Integer> ts = new TreeSet<>();
  14.         for (int i = 0 ; i < T.length ; i++) {
  15.             pq.offer(new int[]{i, T[i]});
  16.         }
  17.         
  18.         int lastPolledHeight = 0, rightGap = 0, leftGap = 0;
  19.         long rectangleSizeInTheMiddle = 0L;
  20.         while (!pq.isEmpty()) {
  21.             int[] cur = pq.poll();
  22.             leftGap = cur[0] - ts.headSet(cur[0], false).size() + 1;
  23.             rectangleSizeInTheMiddle = (cur[1] - lastPolledHeight - 1) * (T.length - ts.size());
  24.             increasedArea += (leftGap + rightGap + rectangleSizeInTheMiddle);
  25.             result += increasedArea;

  26.             lastPolledHeight = cur[1];
  27.             rightGap = T.length - 1 - cur[0] - ts.tailSet(cur[0], false).size();
  28.             ts.add(cur[0]);
  29.         }

  30.         return (int)(result % 1000000000L);
  31.     }
  32. }
复制代码
  • 放進PriorityQueue當中的結構是[index, nums[index]], 會依照nums[index]從小到大的順序排序, 若nums[index]相同則比較index由小到大
  • 若這次PriorityQueue poll的結果是[a, nums[a]], 而下一次的結果是[b, nums[b]], 則這兩次中間新增加的面積我把它切成3塊:
  • 首先rightGap是在 nums[a]的高度, 把 (a+1)~(nums.length-1)這個區間也補滿 (要用TreeSet扣掉這區間已經不用補滿的column)
  • leftGap是在nums[b]的高度, 把0~b這個區間補滿 (也是要用TreeSet扣掉這區間已經不用補滿的column)
  • 最後rectangleSizeInTheMiddle是計算 (nums[b]-nums[a]-1)這個區間需要補滿的面積
樓主的code約略簡化了一些, 後來在這個基礎上發展始終漏了一些東西沒能算出正確面積
其實我也不知道我這樣寫對不對, 只是跑過了這題給出的幾個基本test cases, 若有漏掉什麼也歡迎討論.
回复

使用道具 举报

地里匿名用户
匿名用户-T6PXY  2024-4-24 14:42:25 来自APP
本楼:   👍  0
0%
0%
0   👎
请问这是target什么时候的Hiring Event?谢谢!
回复

使用道具 举报

地里匿名用户
匿名用户-FPRXH  2024-4-30 15:51:29
本楼:   👍  0
0%
0%
0   👎
您好请问对于第三题方便详细说一下j是什么吗?“本质就是算面积”是什么意思?实在是脑子不够用了看了4小时这道题了还是没头绪😂
回复

使用道具 举报

 楼主| tongliuu 2024-5-1 02:35:02 | 显示全部楼层
本楼:   👍  0
0%
0%
0   👎
全局:   80
100%
0%
0
本帖最后由 tongliuu 于 2024-4-30 11:41 编辑
匿名用户 发表于 2024-4-30 00:51
您好请问对于第三题方便详细说一下j是什么吗?“本质就是算面积”是什么意思?实在是脑子不够用了看了4小时 ...

eg,arr = [3,1,2,5]可以表示成下面的形式,横轴是i,纵轴是arr[i],可以看作每个x面积是1.
            x
            x
x          x
x      x  x
x  x  x  x
把求sum看作是求面积,那么计算过程依次是:
-- i = 1: w{0, 1} * h{min(1, arr[j])} + w{1, 3} * h{min(1 - 1, arr[j])} => 2 + 0=> 2
-- i = 2: w{0, 2} * h{min(2, arr[j])} + w{2, 3} * h{min(2 - 1, arr[j])} => 5 + 1 => 6
-- i = 0: w{0, 0} * h{min(3, arr[j])} + w{0, 3} * h{min(3 - 1, arr[j])} => 3 + 5 => 8
-- i = 3: w{0, 3} * h{min(5, arr[j])} + w{3, 3} * h{min(5 - 1, arr[j])} => 11 + 0 => 11
回复

使用道具 举报

地里匿名用户
匿名用户-RBGFQ  2024-5-1 13:35:48
本楼:   👍  0
0%
0%
0   👎
tongliuu 发表于 2024-4-30 11:35
eg,arr = [3,1,2,5]可以表示成下面的形式,横轴是i,纵轴是arr,可以看作每个x面积是1.
            x
...

您好,这个算面积看明白了,但是想问一下treeset怎么用?没太想明白。以及为什么有了treeset就能把复杂度从n2 变到 nlogn?
回复

使用道具 举报

 楼主| tongliuu 2024-5-2 01:54:40 | 显示全部楼层
本楼:   👍  0
0%
0%
0   👎
全局:   80
100%
0%
0
本帖最后由 tongliuu 于 2024-5-1 11:03 编辑
匿名用户 发表于 2024-4-30 22:35
您好,这个算面积看明白了,但是想问一下treeset怎么用?没太想明白。以及为什么有了treeset就能把复杂度 ...

算面积是w_left*h_left + w_right*h_right,对每个i它左右两边的h都是确定的,不确定的是w,treeset用来O(log n)判断每个i它左右两边分别有多少个index已经被计算过了,算左右w的时候分别减掉,减掉部分的面积就是之前每一步的和prefix_sum{0 ... i - 1}

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

使用道具 举报

地里匿名用户
匿名用户-RBGFQ  2024-5-4 01:36:20
本楼:   👍  0
0%
0%
0   👎
sean51623 发表于 2024-5-2 01:04
今天下午剛寫完OA, 這題還是沒寫好, 把一些踩了的坑整理一下吧, 大致尋著樓主的思路, 用了PriorityQueue和T ...

终于画了一天的时间看了楼主和你的代码(感谢二位),明白了treeset的用处和算面积。
如果 leftGap 叫 leftLump,rightGap 叫 rightLump,对于我更好理解一点。

我觉得这道题我是写不出的。。。体感非常难。
回复

使用道具 举报

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

本版积分规则

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