回复: 28
收起左侧

Facebook 11/11/2016 电二

本楼:   👍  1
50%
50%
1   👎
全局:   25
89%
11%
3

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

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

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

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 i
您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限查看其他获取积分的方式
f there are multiple positions, return the smallest one.

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

评分

参与人数 5大米 +45 收起 理由
agraynel + 2 gas station 变种?
yezhangpost + 3 感谢分享!
skye_luobopi + 5 感谢分享!
ellewoods2015 + 5 感谢分享!
夏虫不知雪花 + 30

查看全部评分


上一篇:啊哭那 capital Big Data 电面面经
下一篇:11.11.2016 11AM 店面

本帖被以下淘专辑推荐:

CescTom 2016-11-13 02:10:05 | 显示全部楼层
本楼:   👍  13
100%
0%
0   👎
全局:   46
100%
0%
0
写了一下代码,思路大概就是楼上讨论的,这样应该可以做到O(n),空间也是O(n)
  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];
  22.             if(sum > max) {
  23.                 max = sum;
  24.                 index = i;
  25.             }
  26.         }

  27.         return index;
  28.     }
复制代码
回复

使用道具 举报

wtcupup 2016-11-12 05:58:42 | 显示全部楼层
本楼:   👍  0
0%
100%
1   👎
全局:   1008
74%
26%
357
感觉确实需要O(N^2):
pick each position circular array as start index, then do a traversal to calculate amazing numbers, keep a global max
回复

使用道具 举报

taoqi610 2016-11-13 09:07:14 | 显示全部楼层
本楼:   👍  0
0%
0%
0   👎
全局:   335
98%
2%
6
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];
  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  ){
  17.                 shifts[min2]+=1;
  18.                 shifts[arr.length]-=1;
  19.             }
  20.         }

  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.     }
复制代码

回复

使用道具 举报

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

使用道具 举报

gaoyikai90 2016-11-12 06:23:00 | 显示全部楼层
本楼:   👍  0
0%
0%
0   👎
全局:   444
95%
5%
25
想了一下,对于给定数组中的每一个数来说,它所在位置的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 | 显示全部楼层
本楼:   👍  0
0%
0%
0   👎
全局:   21
100%
0%
0
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 | 显示全部楼层
本楼:   👍  0
0%
0%
0   👎
全局:   63
100%
0%
0
gaoyikai90 发表于 2016-11-11 16:23
想了一下,对于给定数组中的每一个数来说,它所在位置的index是固定的。因此,该数要想成为amazing number ...

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

使用道具 举报

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

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

使用道具 举报

期末求过 2016-11-12 10:55:01 | 显示全部楼层
本楼:   👍  0
0%
0%
0   👎
全局:   43
98%
2%
1
Gas station那个题是不是有点像
回复

使用道具 举报

hello2pig 2016-11-12 10:57:04 | 显示全部楼层
本楼:   👍  0
0%
0%
0   👎
全局:   128
67%
33%
63
提供一个思路:从后到前扫一遍记录从当前位置开始到结尾的最大值。 第一个最小的就是所得的结果。 在遍历一遍验证是否争取就可以了。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 | 显示全部楼层
本楼:   👍  0
0%
0%
0   👎
全局:   21
100%
0%
0
hello2pig 发表于 2016-11-12 10:57
提供一个思路:从后到前扫一遍记录从当前位置开始到结尾的最大值。 第一个最小的就是所得的结果。 在遍历一 ...


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

使用道具 举报

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

本版积分规则

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