推荐:数据科学课程和书籍清单以及培训讲座


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 7889|回复: 28
收起左侧

Facebook 11/11/2016 电二

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

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

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

x
前15分钟先聊人生,然后就出了一题,之前没见过:
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.. visit 1point3acres.com for more.
If there are multiple positions, return the smallest one..1point3acres缃

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

评分

5

查看全部评分

本帖被以下淘专辑推荐:

CescTom 发表于 2016-11-13 02:10:05 | 显示全部楼层
写了一下代码,思路大概就是楼上讨论的,这样应该可以做到O(n),空间也是O(n)
. from: 1point3acres.com/bbs
  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. visit 1point3acres.com for more.
  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];. Waral 鍗氬鏈夋洿澶氭枃绔,
  22.             if(sum > max) {
  23.                 max = sum;.1point3acres缃
  24.                 index = i;
  25.             }
  26.         }

  27.         return index;
  28.     }
复制代码
回复 支持 12 反对 0

使用道具 举报

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
回复 支持 0 反对 1

使用道具 举报

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

使用道具 举报

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):
或是把原本的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
想了一下,对于给定数组中的每一个数来说,它所在位置的index是固定的。因此,该数要想成为amazing number ...

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

使用道具 举报

catinclay 发表于 2016-11-12 08:16:20 | 显示全部楼层
yuranrobin 发表于 2016-11-12 07:57
你这样已经算是O(N^2)了吧
. visit 1point3acres.com for more.
应该是O(n)的吧 对于每个 index找区间是O(1)的
回复 支持 反对

使用道具 举报

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

使用道具 举报

hello2pig 发表于 2016-11-12 10:57:04 | 显示全部楼层
提供一个思路:从后到前扫一遍记录从当前位置开始到结尾的最大值。 第一个最小的就是所得的结果。 在遍历一遍验证是否争取就可以了。two pass。 O(n). 鍥磋鎴戜滑@1point 3 acres
比如 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
提供一个思路:从后到前扫一遍记录从当前位置开始到结尾的最大值。 第一个最小的就是所得的结果。 在遍历一 ...


这个方法感觉不对...
举例子:
[4,5,0,1,2,3,4,9].1point3acres缃
得到
[9,9,9,9,9,9,9,9]
得到index = 0, 但index = 2才是最佳解. more info on 1point3acres.com
还是我哪里理解错误了?
回复 支持 反对

使用道具 举报

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
对每个index算出要使这个element成为amazing number,可能的new start point区段(会是一个或两个interval)  ...

可以,但是不需要排序吗?meeting room II要排序的。O(nlogn)
回复 支持 反对

使用道具 举报

coldknight 发表于 2016-11-13 01:35:54 | 显示全部楼层
catinclay 发表于 2016-11-12 06:39
跨0的区间就看成两个不同的区间就好了吧

补充内容 (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 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
写了一下代码,思路大概就是楼上讨论的,这样应该可以做到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. 鍥磋鎴戜滑@1point 3 acres
when i=1, shift array becomes 1,-1,1,0 能具体说说这个shift数组里的elements代表的含义吗?. from: 1point3acres.com/bbs

补充内容 (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.1point3acres缃
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];
  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);. more info on 1point3acres.com

  16.             if (min2< arr.length  ){
  17.                 shifts[min2]+=1;
  18.                 shifts[arr.length]-=1;
  19.             }
  20.         }

  21.         int curmax=0;
  22.         int sum=0;. visit 1point3acres.com for more.
  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
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-8-18 13:22

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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