一亩三分地论坛

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

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

FB新鲜出炉的电面

[复制链接] |试试Instant~ |关注本帖
zzz1322 发表于 2016-6-5 02:38:51 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 硕士 全职@Facebook - 内推 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
第一轮电面:1. LC 191 Number of 1 Bits
2. 给2D平面上的N个点,求离原点最近的K个点

第二轮电面:
1. 有一个数组,里面有0和非0元素,要求把所有非0元素移动到数组的前端,并返回非0元素的个数,非零元素顺序随意。非零元素之后数组有什么我们不关心。要求最小化写入次数。
2. Decode Ways

. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
补充内容 (2016-6-7 23:14):
已经拿到onsite

评分

2

查看全部评分

黑莓小白 发表于 2016-6-8 00:56:30 | 显示全部楼层
laonawuli 发表于 2016-6-5 11:45
·1. 有一个数组,里面有0和非0元素,要求把所有非0元素移动到数组的前端,并返回非0元素的个数,非零元素 ...
. 鍥磋鎴戜滑@1point 3 acres
感觉两个pointer, 左边找第一个0, 右边找第一个非0, 两边推进

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

laonawuli 发表于 2016-6-5 10:59:07 | 显示全部楼层
请问楼主第二题怎么弄的?
回复 支持 反对

使用道具 举报

 楼主| zzz1322 发表于 2016-6-5 11:01:38 | 显示全部楼层
laonawuli 发表于 2016-6-5 10:59
请问楼主第二题怎么弄的?
. Waral 鍗氬鏈夋洿澶氭枃绔,
我用了一个size为k的最大堆。当然也可以用类似快排的做法
回复 支持 反对

使用道具 举报

blackrose 发表于 2016-6-5 11:04:06 | 显示全部楼层
facebook 校招开始了?
回复 支持 反对

使用道具 举报

laonawuli 发表于 2016-6-5 11:43:39 | 显示全部楼层
zzz1322 发表于 2016-6-4 19:01
我用了一个size为k的最大堆。当然也可以用类似快排的做法
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
请问第二题有详细的描述吗?LC上有没有?
回复 支持 反对

使用道具 举报

laonawuli 发表于 2016-6-5 11:44:31 | 显示全部楼层
另外decode ways 是和LC上完全相同的返回所有可能性的数量int, 还是说返回所有结果List<String>?
回复 支持 反对

使用道具 举报

 楼主| zzz1322 发表于 2016-6-5 11:45:24 | 显示全部楼层
blackrose 发表于 2016-6-5 11:04.鏈枃鍘熷垱鑷1point3acres璁哄潧
facebook 校招开始了?

我也不知道,我是内推进去的,4月份推的
回复 支持 反对

使用道具 举报

laonawuli 发表于 2016-6-5 11:45:45 | 显示全部楼层
·1. 有一个数组,里面有0和非0元素,要求把所有非0元素移动到数组的前端,并返回非0元素的个数,非零元素顺序随意。非零元素之后数组有什么我们不关心。要求最小化写入次数。·
. from: 1point3acres.com/bbs
这题用一个pointer自加,是不是就已经是最小化写入次数了?感觉不知道该在哪个点优化了
回复 支持 反对

使用道具 举报

 楼主| zzz1322 发表于 2016-6-5 11:46:39 | 显示全部楼层
laonawuli 发表于 2016-6-5 11:43
请问第二题有详细的描述吗?LC上有没有?

没有。一个二维平面上,给定N个点,求离原点最近的前K个点。
回复 支持 反对

使用道具 举报

 楼主| zzz1322 发表于 2016-6-5 11:50:04 | 显示全部楼层
laonawuli 发表于 2016-6-5 11:45
·1. 有一个数组,里面有0和非0元素,要求把所有非0元素移动到数组的前端,并返回非0元素的个数,非零元素 ...

一个pointer不是最佳的方案。我说了这个方案,貌似小哥很不满意,问我有没有其他的方案,我想了半天没想出来。
比如[1,0,3,0,6,7,0,4,0,0],按照一个pointer从前往后扫,结果应该是[1,3,6,7,4,7,0,4,0,0],长度为5
回复 支持 反对

使用道具 举报

laonawuli 发表于 2016-6-5 11:52:37 | 显示全部楼层
zzz1322 发表于 2016-6-4 19:46
没有。一个二维平面上,给定N个点,求离原点最近的前K个点。

. from: 1point3acres.com/bbs 所以跟 LC的 215. Kth Largest Element in an Array   很像
回复 支持 反对

使用道具 举报

 楼主| zzz1322 发表于 2016-6-5 11:53:46 | 显示全部楼层
laonawuli 发表于 2016-6-5 11:44. more info on 1point3acres.com
另外decode ways 是和LC上完全相同的返回所有可能性的数量int, 还是说返回所有结果List?

和LC完全相同
回复 支持 反对

使用道具 举报

 楼主| zzz1322 发表于 2016-6-5 11:54:38 | 显示全部楼层
laonawuli 发表于 2016-6-5 11:52.鐣欏璁哄潧-涓浜-涓夊垎鍦
所以跟 LC的 215. Kth Largest Element in an Array   很像
. 鍥磋鎴戜滑@1point 3 acres
是的,很相似。不过O(n)的做法不太好写,边界很容易写错
回复 支持 反对

使用道具 举报

laonawuli 发表于 2016-6-5 11:57:53 | 显示全部楼层
zzz1322 发表于 2016-6-4 19:54
是的,很相似。不过O(n)的做法不太好写,边界很容易写错

卧槽这题怎么O(n)? 不应该是 nLogn么

补充内容 (2016-6-4 19:58):
说错  nLogK
回复 支持 反对

使用道具 举报

blackrose 发表于 2016-6-5 12:00:47 | 显示全部楼层
laonawuli 发表于 2016-6-5 11:57
卧槽这题怎么O(n)? 不应该是 nLogn么

补充内容 (2016-6-4 19:58):
. from: 1point3acres.com/bbs
估计楼主说错了,heap 的 time complexity 和 quick select一样。。。。
回复 支持 反对

使用道具 举报

 楼主| zzz1322 发表于 2016-6-5 12:03:50 | 显示全部楼层
laonawuli 发表于 2016-6-5 11:57. From 1point 3acres bbs
卧槽这题怎么O(n)? 不应该是 nLogn么

补充内容 (2016-6-4 19:58):
.鐣欏璁哄潧-涓浜-涓夊垎鍦
nlogk是用堆的,O(n)的是用快排的partition。每次随机抽取一个元素,把数组分为小于这个元素和大于这个元素的两个部分,这样,由于是随机的抽取的,期望就是把数组平均分成两半,所以T(n) = T(n / 2) + O(n)。根据主定理,T(n) = O(n)。可以参考一下我LC这道题的代码。
  1. import java.util.Random;

  2. public class Solution {. 1point 3acres 璁哄潧
  3.    
  4.     Random r = new Random();
  5.    
  6.     private void swap(int[] nums, int i, int j) {
  7.         int t = nums[i];
  8.         nums[i] = nums[j];
  9.         nums[j] = t;
  10.     }
  11.     .鐣欏璁哄潧-涓浜-涓夊垎鍦
  12.     private int kth(int[] nums, int left, int right, int k) {
  13.         int i = left, n = right;
  14.         int mid = r.nextInt(right - left + 1) + left;
  15.         int pivot = nums[mid];
  16.         for(int j = left; j <= n;) {
  17.             if(nums[j] > pivot) swap(nums, i++, j++);. more info on 1point3acres.com
  18.             else if(nums[j] < pivot) swap(nums, j, n--);. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  19.             else ++j;
  20.         }. 鍥磋鎴戜滑@1point 3 acres
  21.         if(k + left < i) return kth(nums, left, i - 1, k);
  22.         else if(k + left <= n) return nums[k + left];
  23.         else return kth(nums, n + 1, right, k - (n - left + 1));
  24.     }
  25.    
  26.     public int findKthLargest(int[] nums, int k) {
  27.         return kth(nums, 0, nums.length - 1, k - 1);.鐣欏璁哄潧-涓浜-涓夊垎鍦
  28.     }
  29. }
复制代码
回复 支持 反对

使用道具 举报

laonawuli 发表于 2016-6-5 12:12:58 | 显示全部楼层
zzz1322 发表于 2016-6-4 20:03
nlogk是用堆的,O(n)的是用快排的partition。每次随机抽取一个元素,把数组分为小于这个元素和大于这个元 ...

确实比heap复杂多了。你当时用的heap还是partition?另外为毛给你搞了两轮电面。。。

补充内容 (2016-6-4 20:14):
看到你上面说了用heap了
回复 支持 反对

使用道具 举报

blackrose 发表于 2016-6-5 12:13:40 | 显示全部楼层
zzz1322 发表于 2016-6-5 12:03
nlogk是用堆的,O(n)的是用快排的partition。每次随机抽取一个元素,把数组分为小于这个元素和大于这个元 ...
. visit 1point3acres.com for more.
Parition 是N time 吧, 因为可以recursion,所以是nlgn, 堆的话,先push进去所有元素 nlgn time,再找kth KnLgn 吧。。。怎么突然感觉这么凌乱
回复 支持 反对

使用道具 举报

Wingszero 发表于 2016-6-5 18:00:24 | 显示全部楼层
zzz1322 发表于 2016-6-5 11:50. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
一个pointer不是最佳的方案。我说了这个方案,貌似小哥很不满意,问我有没有其他的方案,我想了半天没想 ...

这道题不就是Move zeroes么,为什么你的test case是这个结果...
回复 支持 反对

使用道具 举报

yueliu2366 发表于 2016-6-5 21:07:57 | 显示全部楼层
第二轮第一题不是lc move zeroes吗? 求教有何不同?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 06:26

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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