一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1602|回复: 22
收起左侧

Facebook 11/11/2016 电二

[复制链接] |试试Instant~ |关注本帖
Hualiang 发表于 2016-11-12 03:46:13 | 显示全部楼层 |阅读模式

2017(7-9月) 码农类 硕士 实习@Facebook - 网上海投 - 技术电面 |Otherfresh grad应届毕业生

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
前15分钟先聊人生,然后就出了一题,之前没见过:. from: 1point3acres.com/bbs
Define amazing number as: its value is less than or equal to its index. Given a circular array, find the starting position, such that the total number of amazing numbers in the array is maximized.
Example 1: 0, 1, 2, 3. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
Ouptut: 0.    When starting point at position 0, all the elements in the array are equal to its index. So all the numbers are amazing number.. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
Example 2: 1, 0 , 0
Output: 1.    When starting point at position 1, the array becomes 0, 0, 1. All the elements are amazing number.
If there are multiple positions, return the smallest one.

没做出来,只做了(O^2)brute force 的解法。。。求大神解答

评分

4

查看全部评分

CescTom 发表于 2016-11-13 02:10:05 | 显示全部楼层
写了一下代码,思路大概就是楼上讨论的,这样应该可以做到O(n),空间也是O(n). 鍥磋鎴戜滑@1point 3 acres
  1. public static int amazingNumber(int[] nums) {
  2.         int n = nums.length;

  3.         // Keeps track of all the intervals that after right-shifting index, some numbers become amazing number..鐣欏璁哄潧-涓浜-涓夊垎鍦
  4.         int[] shifts = new int[n];
  5.         for(int i=0; i < n; i++) {
  6.             // If the current number is negative or larger than the biggest index, it won't affect the final result..鐣欏璁哄潧-涓浜-涓夊垎鍦
  7.             if(nums[i] >= n || nums[i] <= 0) continue;

  8.             if(nums[i] > i) {
  9.                 // Right shift index i + 1 --> the current index would be n-1 after shifting
  10.                 shifts[i + 1] += 1;
  11.                 if(nums[i] > i + 1) shifts[i + 1 + n - nums[i]] -= 1;
  12.             } else {
  13.                 // There would be two intervals for each nums[i] <= i
  14.                 shifts[0] += 1;
  15.                 shifts[i - nums[i] + 1] -= 1;

  16.                 if(i != n - 1) shifts[i + 1] += 1;
  17.             }
  18.         }

  19.         int sum = 0, max = 0, index = 0;
  20.         for(int i=0; i < shifts.length; i++) {
  21.             sum += shifts[i];. 1point3acres.com/bbs
  22.             if(sum > max) {
  23.                 max = sum;
  24.                 index = i;
  25.             }
  26.         }

  27.         return index;. more info on 1point3acres.com
  28.     }
复制代码
回复 支持 7 反对 0

使用道具 举报

catinclay 发表于 2016-11-12 04:46:12 | 显示全部楼层
对每个index算出要使这个element成为amazing number,可能的new start point区段(会是一个或两个interval) 然后把所有intervals做meeting room II(LC 253)找最高重合处选最小的,看起来是O(n)但实现麻烦。请其他牛人解答
回复 支持 反对

使用道具 举报

wtcupup 发表于 2016-11-12 05:58:42 | 显示全部楼层
感觉确实需要O(N^2):
pick each position circular array as start index, then do a traversal to calculate amazing numbers, keep a global max
回复 支持 反对

使用道具 举报

gaoyikai90 发表于 2016-11-12 06:23:00 | 显示全部楼层
想了一下,对于给定数组中的每一个数来说,它所在位置的index是固定的。因此,该数要想成为amazing number,会有一个“shift”的范围。shift指starting point由index==0右移的偏移量。该范围是一个连续的区间(可能由最大index循环回0,1.。。), 所以可以新建一个数组count[]用来标定这些区间。每个区间用首尾两个位置通过+1或者-1标定。然后遍历count[], sum += count[i], 并更新最大的amazing number的个数。这种方法应该是O(n)的。 不过由于每个区间可能会跨0,实际操作不容易。
回复 支持 反对

使用道具 举报

catinclay 发表于 2016-11-12 06:39:46 | 显示全部楼层
gaoyikai90 发表于 2016-11-12 06:23. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
想了一下,对于给定数组中的每一个数来说,它所在位置的index是固定的。因此,该数要想成为amazing number ...

跨0的区间就看成两个不同的区间就好了吧

补充内容 (2016-11-12 06:42):. 鍥磋鎴戜滑@1point 3 acres
或是把原本的array复制一次, append起来( 例如原本[1,2,3,4] => [1,2,3,4,1,2,3,4] 这样就能处理跨0的问题(找sum的时候住意只能从index = 0 找到index = length 就好)
回复 支持 反对

使用道具 举报

yuranrobin 发表于 2016-11-12 07:57:27 | 显示全部楼层
gaoyikai90 发表于 2016-11-11 16:23. 1point3acres.com/bbs
想了一下,对于给定数组中的每一个数来说,它所在位置的index是固定的。因此,该数要想成为amazing number ...

你这样已经算是O(N^2)了吧
回复 支持 反对

使用道具 举报

catinclay 发表于 2016-11-12 08:16:20 | 显示全部楼层
yuranrobin 发表于 2016-11-12 07:57
你这样已经算是O(N^2)了吧

应该是O(n)的吧 对于每个 index找区间是O(1)的
回复 支持 反对

使用道具 举报

期末求过 发表于 2016-11-12 10:55:01 | 显示全部楼层
Gas station那个题是不是有点像
回复 支持 反对

使用道具 举报

hello2pig 发表于 2016-11-12 10:57:04 | 显示全部楼层
提供一个思路:从后到前扫一遍记录从当前位置开始到结尾的最大值。 第一个最小的就是所得的结果。 在遍历一遍验证是否争取就可以了。two pass。 O(n)
比如 2,3,0,1  得到的最大值为(3,3,1,1) 那么唯一可能的位置就是index = 2。 从index = 2 开始验证一遍,是就返回index,不是就没结果。


补充内容 (2016-11-12 11:21):. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
不好意思找从index开始值为0的位置 作为起始位。

补充内容 (2016-11-12 11:26):
好像不行 忘了吧。
回复 支持 反对

使用道具 举报

catinclay 发表于 2016-11-12 11:22:49 | 显示全部楼层
hello2pig 发表于 2016-11-12 10:57.鏈枃鍘熷垱鑷1point3acres璁哄潧
提供一个思路:从后到前扫一遍记录从当前位置开始到结尾的最大值。 第一个最小的就是所得的结果。 在遍历一 ...

. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
这个方法感觉不对...
举例子:. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
[4,5,0,1,2,3,4,9]. from: 1point3acres.com/bbs
得到
[9,9,9,9,9,9,9,9]
得到index = 0, 但index = 2才是最佳解
还是我哪里理解错误了?
回复 支持 反对

使用道具 举报

a529384424 发表于 2016-11-12 12:58:32 | 显示全部楼层
我想的是能做到 O nlogn 吧, 遍历一遍数组, 得到每个element的valid shift区间,但是这些区间是无序的,所以要用heap进行维护,找出n个区间同时重叠最多的情况?
回复 支持 反对

使用道具 举报

coldknight 发表于 2016-11-13 00:43:43 | 显示全部楼层
catinclay 发表于 2016-11-12 04:46-google 1point3acres
对每个index算出要使这个element成为amazing number,可能的new start point区段(会是一个或两个interval)  ...
. 1point3acres.com/bbs
可以,但是不需要排序吗?meeting room II要排序的。O(nlogn)
回复 支持 反对

使用道具 举报

coldknight 发表于 2016-11-13 01:35:54 | 显示全部楼层
catinclay 发表于 2016-11-12 06:39
跨0的区间就看成两个不同的区间就好了吧.1point3acres缃
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
补充内容 (2016-11-12 06:42):
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
好像只要找index 0--length-1就可以,所以不用复制,越界的end index ignore就可以吧
回复 支持 反对

使用道具 举报

 楼主| Hualiang 发表于 2016-11-13 03:47:21 | 显示全部楼层
CescTom 发表于 2016-11-13 02:10. visit 1point3acres.com for more.
写了一下代码,思路大概就是楼上讨论的,这样应该可以做到O(n),空间也是O(n)

哎。。。电面的时候没想到- -思路大概对, 就是没做出来, 哈哈
回复 支持 反对

使用道具 举报

catinclay 发表于 2016-11-13 05:41:36 | 显示全部楼层
coldknight 发表于 2016-11-13 00:43
可以,但是不需要排序吗?meeting room II要排序的。O(nlogn)


我说用meeting room2 只是帮助理解, 实际上你是在interval的start标示+1, 在end标示-1, 然后全部index扫一遍就可以了, 类似bucket sort的概念
回复 支持 反对

使用道具 举报

wtcupup 发表于 2016-11-13 06:22:14 | 显示全部楼层
CescTom 发表于 2016-11-13 02:10
写了一下代码,思路大概就是楼上讨论的,这样应该可以做到O(n),空间也是O(n)

假设input array: 0,1,2,3
when i=1, shift array becomes 1,-1,1,0 能具体说说这个shift数组里的elements代表的含义吗?

补充内容 (2016-11-13 15:25):
看懂了,层主大神啊
回复 支持 反对

使用道具 举报

jinyyy666 发表于 2016-11-13 07:36:55 | 显示全部楼层
catinclay 发表于 2016-11-12 04:46
.鐣欏璁哄潧-涓浜-涓夊垎鍦对每个index算出要使这个element成为amazing number,可能的new start point区段(会是一个或两个interval)  ...

有点明白你的意思了,这个方法很巧妙
回复 支持 反对

使用道具 举报

taoqi610 发表于 2016-11-13 09:07:14 | 显示全部楼层
value      x1 x2 x3 x4 x5
index      i1  i2  i3  i4 i5    0 1 2 3 4   鏉ユ簮涓浜.涓夊垎鍦拌鍧.
calculate x3's element's shift range
start position is j :    two situations
start position range   i<j  :    i3<j  &&    i3+n-j  <=x3
                              j<=i:      j<=i3   &&     i3-j <=x3

  1.     public static int amazingnumber(int[] arr) {
  2.         int[] shifts = new int[arr.length+1];. From 1point 3acres bbs
  3.         for (int i=0;i<arr.length;i++ ){
  4.             int x = arr[i];
  5.             int min1 = i-x;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  6.             int max1 = i;

  7.             min1 = Math.max(min1, 0);
  8.             if (min1<=max1){
  9.                 shifts[min1]+=1;
  10.                 shifts[max1+1]+=-1;
  11.             }
  12.             int min2 = i+1;
  13.             min2=Math.max(0,min2);
  14.             int min3 = i+arr.length-x;
  15.             min2=Math.max(min2,min3);

  16.             if (min2< arr.length  ){.鏈枃鍘熷垱鑷1point3acres璁哄潧
  17.                 shifts[min2]+=1;
  18.                 shifts[arr.length]-=1;
  19.             }.1point3acres缃
  20.         }. Waral 鍗氬鏈夋洿澶氭枃绔,

  21.         int curmax=0;
  22.         int sum=0;
  23.         for (int i=0;i<shifts.length;i++){
  24.             sum+=shifts[i];
  25.             curmax=Math.max(curmax,sum);
  26.         }
  27.         return curmax;
  28.     }
复制代码

回复 支持 反对

使用道具 举报

wtcupup 发表于 2016-11-13 14:33:10 | 显示全部楼层
a529384424 发表于 2016-11-12 12:58. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
我想的是能做到 O nlogn 吧, 遍历一遍数组, 得到每个element的valid shift区间,但是这些区间是无序的, ...

遍历一遍数组, 得到每个element的valid shift区间 就已经是O(N^2)了吧? 因为数组可以shift N次,对于每一个元素的话就是 N*N
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-4 06:11

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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