一亩三分地论坛

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

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

Facebook Intern 电面一轮 + Onsite一轮

[复制链接] |试试Instant~ |关注本帖
堕落的猴子 发表于 2015-4-5 12:44:20 | 显示全部楼层 |阅读模式

2015(4-6月) 码农类 硕士 实习@Facebook - 内推 - 技术电面 Onsite |Other其他

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

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

x
2015暑假Intern,星期五刚结束onsite,特地发来攒人品。
土木转行所以细节可能粗糙,请谅解。

感想:
0,其实我1月初投过,当时没在招人,催了下HR就被挂了。最近听说同学又拿到面试,就特地再找了联系我同学的那个recruiter点对点问,成功拿到。
1,他们家果然很多leetcode原题,然后考到了不要太开心,记住那些解法的复杂度,他们会和你聊是否可以时间换空间,或者空间换时间。因为很多原题,所以电面的时候千万别谦虚,把leetcode开着吧。
2,culture fit这个部分虽然没有直接问,但是感觉到还是存在的,他们一般都会问下为啥选FB,你的兴趣方向什么的,这个可以参考他们家的5个core values,对着说几个点就好了。
3,他们家onsite就早上过去一轮coding就结束了,然后吃午饭+和前intern聊天+校区逛一圈就结束了。如果催得紧的话,似乎可以当天出结果。不催的话,目前感觉流程也很快。. 鍥磋鎴戜滑@1point 3 acres

电面:
1,做messenger的白人小哥,感觉就相当有热情,上来先聊了下项目和为啥转行。
2,phone letter combination原题,不过不要求返回list,只要打印出来就好。我一开始只记得原题,然后用list存储结果,然后被提醒了把额外空间砍掉,就是一个单纯的dfs而已了。
3,decode ways原题,问了下dp和递归的空间时间比较。
4,因为聊得太欢,结束了他还特地转达我的HR说我下一轮的时候多注意空间复杂度和分析,多好的白人小哥呐。给你个赞。. from: 1point3acres.com/bbs

Onsite:
1,面试官略微迟到,白人小哥看起来没睡醒,找房间又找了几分钟才找到空房间,然后找不到擦子,用纸擦板子又擦了一阵。
2,第一题,把数列里的0移到数列尾巴。。。感觉他明显是想放水啊!但是我没感觉到啊!我当时就傻逼了啊!说自己做过啊!还说我知道你接下来要问我如何减少数据迁移所以不用swap用write啊!你说我为何要作死呢。。。
3,然后他说很感谢我说实话,说来下一题吧,停顿了三秒(妈蛋,我当时就不安了):给N个数,找出其中k个乘积最大的数,不需要连续。和leetcode那道题的联系度很低。

一开始分析了下暴力法要N^k,而且暴力法得用递归写,放弃之。然后分析如何优化,提出了一个把正负数分开排序然后分析所有k种情况(0负k正,2负k-2正,然后选数字总是选正数里最大的几个和负数里最小的几个),一路比较直到没有提升。不过他说没见过这个思路,提示我用绝对值排序(也就是-1 1 -2 2 -3 3 .... -99 100)然后问我能怎么分析。当时就被他带进了绝对值排序的思路,后来想了下这个排序会非常难分析,因为可能存在-1000000和-0.1在排序后的数组两端,最坏情况还是要把整个数组扫描完,还不说要做大量的正负检查和对比,总之最后尽力分析了一些case之后时间不够了。他给了我邮件说有啥想法可以follow up,当时整个下午就一直在想。

最后终于想到,把正负数按照-1 -2 -3 -4 .. -99 -100 100 99 98...1这样排列,这样乘积最大的必然是中间的k个连续数字。设定两个指针,间距k,左指针在第一个正数上,右指针在第k个正数。然后慢慢往负数那边移动,每次比较新包含的2个负数的乘积和去掉的两个正数的乘积,最好常数时间,最差O(k)。当然因为k可能比正数数量多,所以要处理好不少特殊case。完了仔细一想,这特么不就是我中间提到的那个思路么!不过考虑到分数啊0啊溢出啊7788的他都是途中一边说一边加,而且他说没见过我中间那种思路,可能真的就是他临时想到的吧。

以上就是这样,希望大家引以为鉴,对方放水要好好领情别作死。。。
最后祝福自己一记,让我再来一次也未必会更好,尽力了就没有遗憾。. Waral 鍗氬鏈夋洿澶氭枃绔,


评分

2

查看全部评分

 楼主| 堕落的猴子 发表于 2015-10-23 02:02:20 | 显示全部楼层
JamesJi 发表于 2015-10-23 01:48
不用swap用write
这句话猴哥可以详细解释一下吗

就是直接A[l] = A[r],A[r]上什么值留下来无所谓了。

评分

1

查看全部评分

回复 支持 2 反对 0

使用道具 举报

siren01 发表于 2015-4-6 06:44:45 | 显示全部楼层
siren01 发表于 2015-4-6 06:26
up~ 有大神解释下这题解法么?

按照楼主的思想写的,感觉一次想到不容易,当一个演员是多么的重要
  1. public static long maxK_Product(Integer[] num, int k){
  2.                 if(num==null || num.length==0 || k<=0 || k>num.length)
  3.                         return 0;
  4.                 long result = Long.MIN_VALUE;
  5.                 Arrays.sort(num, new Comparator<Integer>(){
  6.                         public int compare(Integer a, Integer b){
  7.                                 if((long)(a*b)>0){
  8.                                         return b - a;. Waral 鍗氬鏈夋洿澶氭枃绔,
  9.                                 }
  10.                                 else if((long) (a*b)==0){. From 1point 3acres bbs
  11.                                         if(a==0)
  12.                                                 return 1;
  13.                                         else
  14.                                                 return -1;
  15.                                 }.鏈枃鍘熷垱鑷1point3acres璁哄潧
  16.                                 else{
  17.                                         return a>0 ? 1 : -1;
  18.                                 }
  19.                         }
  20.                 });
  21.                 long tmp = 1;. more info on 1point3acres.com
  22.                 int count = 0;
  23.                 for(int i=0; i<num.length; ++i){
  24.                         if(num[i]==0){
  25.                                 result = Math.max(0, result);
  26.                                 break;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  27.                         }
  28.                         count++;.鐣欏璁哄潧-涓浜-涓夊垎鍦
  29.                         tmp *= num[i];
  30.                         if(count==k){
  31.                                 result = Math.max(result, tmp);
  32.                                 tmp = tmp/num[i+1-k];
  33.                                 count--;
  34.                         }
  35.                 }
  36.                 return result;
  37.         }
复制代码
回复 支持 1 反对 0

使用道具 举报

lch04 发表于 2015-4-5 13:36:43 | 显示全部楼层
土木同胞握手
你这个不一定挂吧。我感觉还是很有希望的。
当然,见过的题就不要太诚实了。
回复 支持 反对

使用道具 举报

haungge0385 发表于 2015-4-6 01:34:07 | 显示全部楼层
可以详细说一下k个乘积最大的数吗?是怎样的N个数?
是给N,比如N=3,k=2, 那么   -1,-2,-3,1,2,3,,然后最大是2*3吗?
回复 支持 反对

使用道具 举报

 楼主| 堕落的猴子 发表于 2015-4-6 05:46:22 | 显示全部楼层
haungge0385 发表于 2015-4-6 01:34
可以详细说一下k个乘积最大的数吗?是怎样的N个数?
是给N,比如N=3,k=2, 那么   -1,-2,-3,1,2,3,,然 ...

噢,随机的N个数,我上面举例只是方便对比。. visit 1point3acres.com for more.

就是一个有N个数的数组而已。
回复 支持 反对

使用道具 举报

siren01 发表于 2015-4-6 06:05:21 | 显示全部楼层
额....啥都不说了,直接上代码,楼主加油!
  1.         public static long maxK_Product(Integer[] num, int k){
  2.                 if(num==null || num.length==0 || k<=0 || k>num.length)
  3.                         return 0;
  4.                 long result = Long.MIN_VALUE;
  5.                 Arrays.sort(num, new Comparator<Integer>(){
  6.                         public int compare(Integer a, Integer b){
  7.                                 return Math.abs(b) - Math.abs(a);. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  8.                         }
  9.                 });. 1point 3acres 璁哄潧
  10.                 long tmp = 1;
  11.                 int count = 0;
  12.                 for(int i=0; i<num.length; ++i){
  13.                         if(num[i]==0)
  14.                                 return Math.max(0, result);
  15.                         count++;
  16.                         tmp *= num[i];
  17.                         if(count==k){
  18.                                 result = Math.max(result, tmp);
  19.                                 tmp = tmp/num[i+1-k];
  20.                                 count--;
  21.                         }
  22.                 }. Waral 鍗氬鏈夋洿澶氭枃绔,
  23.                 return result;. From 1point 3acres bbs
  24.         }
复制代码

补充内容 (2015-4-6 06:06):
按照绝对值排序是对的,{-3,-2,-1,0,1,2,3} --》 {0,1,-1,2,-2,-3,3},然后直接乘一个除一个就好了,类似一个k size 的window

补充内容 (2015-4-6 06:09):
貌似确实有cases没处理对,我待会改好再post
回复 支持 反对

使用道具 举报

siren01 发表于 2015-4-6 06:26:23 | 显示全部楼层
siren01 发表于 2015-4-6 06:05
额....啥都不说了,直接上代码,楼主加油!.1point3acres缃
. 1point 3acres 璁哄潧
补充内容 (2015-4-6 06:06):

up~ 有大神解释下这题解法么?
回复 支持 反对

使用道具 举报

 楼主| 堕落的猴子 发表于 2015-4-6 09:52:29 | 显示全部楼层
siren01 发表于 2015-4-6 06:26
up~ 有大神解释下这题解法么?

你这个办法,给你一个比如 -1, 2, 3, 4, 5, 6, 7, 8, 9, 10, -10000,然后k等于3,你试试看。。。

我说的办法可以说省掉了一大堆case的处理,最多移动k/2次就能找到结果了,简直不能更棒,我感觉面试官都未必想到了!
回复 支持 反对

使用道具 举报

 楼主| 堕落的猴子 发表于 2015-4-8 11:36:13 | 显示全部楼层
地里攒人品果然有用,offer已发!
回复 支持 反对

使用道具 举报

头像被屏蔽
zcy1848 发表于 2015-4-11 17:53:44 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

ccgogo123 发表于 2015-6-26 04:38:40 | 显示全部楼层
说说我的想法:
Sort the input and then think about the following two cases:
1. k is larger than the length or all elements are negative or positive
Compute the product of the k rightmost elements
2. Otherwise
Two pointers say i and j initially at the beginning and the end respectively. Traverse the sorted array until we find k numbers and during the traversal, we keep track of the largest product met so far. Every step, we compare a * a[i + 1] with a[j] and pick up the larger one and multiply it by the largest product so far. Update the number of elements we choose so far. Here is the code:
  1. public long findLeastProduct(int[] nums, int k) {
  2.         long product = 1;

  3.         Arrays.sort(nums);
  4.         //special case when k is larger than the length or all elements are negative or positive
  5.         if (k >= nums.length || nums[nums.length - 1] <= 0 || nums[0] >= 0) {
  6.             for (int i = nums.length - 1; i >= Math.max(0, nums.length - k); i--) {
  7.                 product *= nums[i];
  8.             }
  9.         }else {
  10.             int l = 0, r = nums.length - 1;
  11.             while (k > 0) { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  12.                 if (nums[l] * nums[l + 1] > nums[r]) {
  13.                     product *= nums[l] * nums[l + 1];
  14.                     l += 2;
  15.                     k -= 2;
  16.                 }else {
  17.                     product *= nums[r--];
  18.                     k--;
  19.                 }. visit 1point3acres.com for more.
  20.             }
  21.             if (product < 0) product = product / nums[r + 1] * nums[l] * nums[l + 1];
  22.         }
  23.         return product;
  24.     }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

  25.     @Test
  26.     public void test() {. more info on 1point3acres.com
  27.         int[] nums = {-1, 2, 3, 4, 5, 6, 7, 8, 9, 10, -10000};
  28.         System.out.println(findLeastProduct(nums, 3));
  29.     }
复制代码


补充内容 (2015-6-26 04:40):
Modify the 22 line:
if (product < 0) product = product / (nums[r + 1] * nums[l]) * nums[l + 1];
回复 支持 反对

使用道具 举报

ccgogo123 发表于 2015-6-26 04:53:19 | 显示全部楼层
晕菜,刚刚查处了bug,对上个帖子做个更正:
  1. public long findLeastProduct(int[] nums, int k) {
  2.         long product = 1;
  3. . 1point3acres.com/bbs
  4.         Arrays.sort(nums);
  5.         //special case when k is larger than the length or all elements are negative or positive. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  6.         if (k >= nums.length || nums[nums.length - 1] <= 0 || nums[0] >= 0) {
  7.             for (int i = nums.length - 1; i >= Math.max(0, nums.length - k); i--) {
  8.                 product *= nums[i];
  9.             }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  10.         }else {
  11.             int l = 0, r = nums.length - 1;
  12.             while (k > 0) {. 鍥磋鎴戜滑@1point 3 acres
  13.                 if (k == 1) {
  14.                     if (nums[r] >= 0) product *= nums[r];
  15.                     else product = product / nums[r + 1] * nums[l] * nums[l + 1];
  16.                     k--;
  17.                 } else if (nums[l] * nums[l + 1] > nums[r]) {
  18.                     product *= nums[l] * nums[l + 1];
  19.                     l += 2;
  20.                     k -= 2;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  21.                 }else {
  22.                     product *= nums[r--];. Waral 鍗氬鏈夋洿澶氭枃绔,
  23.                     k--;
  24.                 }. 1point3acres.com/bbs
  25.             }
  26.         }
  27.         return product;. from: 1point3acres.com/bbs
  28.     }

  29.     @Test
  30.     public void test() {
  31.         int[] nums = {-1, -2, -3, -4, 5, 6, 7};
  32.         System.out.println(findLeastProduct(nums, 4));
  33.     }
复制代码
回复 支持 反对

使用道具 举报

 楼主| 堕落的猴子 发表于 2015-8-10 01:22:17 | 显示全部楼层
ccgogo123 发表于 2015-6-26 04:53
晕菜,刚刚查处了bug,对上个帖子做个更正:

Exactly,现在回头来看,这题大概就一个普通的算法题,不过还是很巧妙的就是。

这种先排序的思路,都快被各种O(n)的题目给挤压没了。
回复 支持 反对

使用道具 举报

xiaoma318 发表于 2015-8-24 07:00:08 | 显示全部楼层
绝对值排序挺好思考的感觉~排好后取 K 个最大的,如果负数个数是 even,那就完事了;如果是 odd,那么两种方法,减少一个负数,或者增加一个负数,两种情况比较下哪个大就好了。
回复 支持 反对

使用道具 举报

frederickyl 发表于 2015-8-24 10:51:53 | 显示全部楼层
ccgogo123 发表于 2015-6-26 04:53
晕菜,刚刚查处了bug,对上个帖子做个更正:

有个test case不对,{-7, -7, -2, -1, 0, 0, 9}, 结果应该是98(-7*-7*-2*-1), 但你的程序结果是0
回复 支持 反对

使用道具 举报

youto 发表于 2015-10-16 10:57:48 | 显示全部楼层
ccgogo123 发表于 2015-6-26 04:53
晕菜,刚刚查处了bug,对上个帖子做个更正:

这个代码不能解决:-7 ~ -1的case
回复 支持 反对

使用道具 举报

JamesJi 发表于 2015-10-23 01:48:53 | 显示全部楼层
不用swap用write
这句话猴哥可以详细解释一下吗
回复 支持 反对

使用道具 举报

invinsibility 发表于 2016-2-12 09:39:01 | 显示全部楼层
xiaoma318 发表于 2015-8-24 07:00
绝对值排序挺好思考的感觉~排好后取 K 个最大的,如果负数个数是 even,那就完事了;如果是 odd,那么两种 ...

我和你想的方法一样
回复 支持 反对

使用道具 举报

frank11118 发表于 2016-2-14 11:18:08 | 显示全部楼层
堕落的猴子 发表于 2015-10-23 02:02
就是直接A[l] = A[r],A[r]上什么值留下来无所谓了。
. From 1point 3acres bbs
請問 A[r] 不用覆寫成 0 嗎?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

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

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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