[八我司] 介绍一下Uber tech stack和各个大组的情况

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
把贵司招聘信息放这里
查看: 8963|回复: 28
收起左侧

Facebook 11/11/2016 电二

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

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

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

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

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.
If there are multiple positions, return the smallest one.

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

评分

5

查看全部评分

本帖被以下淘专辑推荐:

CescTom 发表于 2016-11-13 02:10:05 | 显示全部楼层
写了一下代码,思路大概就是楼上讨论的,这样应该可以做到O(n),空间也是O(n)
  1. public static int amazingNumber(int[] nums) {
  2.         int n = nums.length;
  3. . visit 1point3acres for more.
  4.         // Keeps track of all the intervals that after right-shifting index, some numbers become amazing number.
  5.         int[] shifts = new int[n];
  6.         for(int i=0; i < n; i++) {
  7.             // If the current number is negative or larger than the biggest index, it won't affect the final result.
  8.             if(nums[i] >= n || nums[i] <= 0) continue;
  9. . more info on 1point3acres
  10.             if(nums[i] > i) {
  11.                 // Right shift index i + 1 --> the current index would be n-1 after shifting
  12.                 shifts[i + 1] += 1;. 留学申请论坛-一亩三分地
  13.                 if(nums[i] > i + 1) shifts[i + 1 + n - nums[i]] -= 1;
  14.             } else {
  15.                 // There would be two intervals for each nums[i] <= i 来源一亩.三分地论坛.
  16.                 shifts[0] += 1;
  17.                 shifts[i - nums[i] + 1] -= 1;.留学论坛-一亩-三分地

  18.                 if(i != n - 1) shifts[i + 1] += 1;
  19.             }
  20.         }
  21. . from: 1point3acres
  22.         int sum = 0, max = 0, index = 0;
  23.         for(int i=0; i < shifts.length; i++) {
  24.             sum += shifts[i];
  25.             if(sum > max) {
  26.                 max = sum;
  27.                 index = i;
  28.             }. Waral 博客有更多文章,
  29.         }

  30.         return index;
  31.     }
复制代码
回复 支持 13 反对 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. From 1point 3acres 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)的
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

期末求过 发表于 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
. more info on 1point3acres
这个方法感觉不对....1point3acres网
举例子:
[4,5,0,1,2,3,4,9]. 围观我们@1point 3 acres
得到
[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
对每个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. more info on 1point3acres
跨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)
. from: 1point3acres
哎。。。电面的时候没想到- -思路大概对, 就是没做出来, 哈哈
回复 支持 反对

使用道具 举报

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

我说用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)
. 1point 3acres 论坛
假设input array: 0,1,2,3
when i=1, shift array becomes 1,-1,1,0 能具体说说这个shift数组里的elements代表的含义吗?
. From 1point 3acres 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. 留学申请论坛-一亩三分地
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;. From 1point 3acres bbs
  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.             }. 围观我们@1point 3 acres
  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.     }
复制代码

回复 支持 反对

使用道具 举报

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

使用道具 举报

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

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

custom counter

GMT+8, 2018-5-25 21:24

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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