一亩三分地论坛

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

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

Facebook 10.25 二面

[复制链接] |试试Instant~ |关注本帖
zzhmxf 发表于 2016-10-26 04:59:58 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 博士 实习@Facebook - 内推 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
一个大概欧洲或者美国小哥吧, 人很nice, 经常说it's ok。两道题都是面经常见题,楼主刷了很久很久的面经,一个月就对付facebook这一家公司了,希望能过!1. move zeors, 要求minimize writes。楼主看到他贴了这道题上来,太兴奋了,写了个两个指针一起从左往右的方法。写完了才发现要minimize writes. 于是重新写,左右指针相撞的方法,重新写,结果出了个小bug... 面试官提醒有bug后,自己发现了,赶紧改了。

2. decode ways, 一开始提了下backtracking,说复杂度太高,后来就dp了,dp 写完之后,优化了一下空间复杂度。

楼主面的时候感觉有点紧张,跪求小哥给过啊给过!

评分

1

查看全部评分

1451427216 发表于 2016-11-6 05:59:50 | 显示全部楼层
111180611 发表于 2016-10-26 06:26. 1point 3acres 璁哄潧
感觉楼主代码有问题
1.没有保持非零元素的相对顺序(可能没有要求)
2.没有把0移到右边(可能没有要求 ...
  1. int moveZeroesWithMinimumSetps(vector<int>& nums)
  2. {-google 1point3acres
  3.         int left = 0, right = nums.size() - 1;
  4.         while (left < right)
  5.         {. 鍥磋鎴戜滑@1point 3 acres
  6.                 while (left < right && nums[left] != 0)left++;
  7.                 while (left < right && nums[right] == 0)right--;
  8.                 if (left < right)nums[left++] = nums[right--];
  9.         }
  10.         return left;
  11. }
复制代码
回复 支持 1 反对 0

使用道具 举报

 楼主| zzhmxf 发表于 2016-10-26 05:55:33 | 显示全部楼层
zzhmxf 发表于 2016-10-26 05:53
public int moveZeros(int[] nums) {                int left = 0, right = nums.length - 1;                while (left < right) {         ...

代码只需要返回最后有效数组的长度,有效长度之外的数字是什么无所谓,原先input里面的数字不一定要保持原来的相对顺序。所以思路就是,把右边的非0元素移动到左边的0元素位置。这样就可以minimize writes.
回复 支持 1 反对 0

使用道具 举报

yeyelovenimo 发表于 2016-10-26 05:07:43 | 显示全部楼层
楼主这妥的不能更妥了
回复 支持 反对

使用道具 举报

bananapancake 发表于 2016-10-26 05:10:48 | 显示全部楼层
bless楼主!请问move zeros那个两个指针相撞的写法是什么?相当于partition?

补充内容 (2016-10-26 05:30):
如果只按照partition写的话元素相对顺序就变了啊。两个指针重写的确是必须n次,swap的方法写的次数大概能少点。
回复 支持 反对

使用道具 举报

iPhD 发表于 2016-10-26 05:11:58 | 显示全部楼层
楼主稳了!求细说下move zero怎么减少write?什么叫左右指针相撞?方便细说下,或给个代码吗?面试官有要求非0元素相对顺序保持一致吗?求楼主说得详细点!我也马上要二面了,也准备了快2个月了。。。大谢!

补充内容 (2016-10-26 05:19):
move zero那题要求减少write看到好多次了,但一直不知道怎么做,求求楼主说详细点!!真的很感激!!
回复 支持 反对

使用道具 举报

leixiang5 发表于 2016-10-26 05:13:26 | 显示全部楼层
- -写出两道的..基本上没什么问题..
回复 支持 反对

使用道具 举报

wtcupup 发表于 2016-10-26 05:20:46 | 显示全部楼层
楼主,能贴一下你的move zeros那题的代码吗
回复 支持 反对

使用道具 举报

 楼主| zzhmxf 发表于 2016-10-26 05:53:29 | 显示全部楼层
        public int moveZeros(int[] nums) {
                int left = 0, right = nums.length - 1;
                while (left < right) {
                        if (nums[left] != 0) {
                                left++;
                                continue;
                        }
                        while (left < right) {
                                if (nums[right] != 0) {
                                        break;
                                }
                                right--;
                        }
                        if (left < right) {
                                nums[left] = nums[right];
                                left++;
                                right--;
                        }
                }
               
                return left;
        }

回复 支持 反对

使用道具 举报

 楼主| zzhmxf 发表于 2016-10-26 06:02:16 | 显示全部楼层
iPhD 发表于 2016-10-26 05:11
楼主稳了!求细说下move zero怎么减少write?什么叫左右指针相撞?方便细说下,或给个代码吗?面试官有要求 ...
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
phd君我之前刷面经看到无数你的回复啊。
回复 支持 反对

使用道具 举报

111180611 发表于 2016-10-26 06:26:05 | 显示全部楼层
zzhmxf 发表于 2016-10-26 05:53
public int moveZeros(int[] nums) {                int left = 0, right = nums.length - 1;                while (left < right) {         ...

感觉楼主代码有问题.1point3acres缃
1.没有保持非零元素的相对顺序(可能没有要求)
2.没有把0移到右边(可能没有要求,或者说是为了减少write做的牺牲)
3.楼主代码不太简洁
回复 支持 反对

使用道具 举报

 楼主| zzhmxf 发表于 2016-10-26 07:51:14 | 显示全部楼层
111180611 发表于 2016-10-26 06:26. visit 1point3acres.com for more.
感觉楼主代码有问题
1.没有保持非零元素的相对顺序(可能没有要求)
-google 1point3acres2.没有把0移到右边(可能没有要求 ...

1. 我已经说了不用保持原来的顺序
2. 为了减少writes
3. 面试官满意了就好
回复 支持 反对

使用道具 举报

iPhD 发表于 2016-10-26 07:56:48 | 显示全部楼层
zzhmxf 发表于 2016-10-26 06:02
phd君我之前刷面经看到无数你的回复啊。

对,我这周二面。。。。面试官说了不用把0全部移到最右边?不然你的代码没有把0移到后面去?
回复 支持 反对

使用道具 举报

 楼主| zzhmxf 发表于 2016-10-26 08:00:27 | 显示全部楼层
iPhD 发表于 2016-10-26 07:56
对,我这周二面。。。。面试官说了不用把0全部移到最右边?不然你的代码没有把0移到后面去?
. 1point 3acres 璁哄潧
不用,面试官说的很清楚,只要求有效长度内的是所有非零元素就可以。如果把0换到右边会增加writes。
回复 支持 反对

使用道具 举报

weii 发表于 2016-10-26 12:09:50 | 显示全部楼层
zzhmxf 发表于 2016-10-26 08:00
不用,面试官说的很清楚,只要求有效长度内的是所有非零元素就可以。如果把0换到右边会增加writes。

啊 看了很多面经,看到LZ这个终于明白什么叫最小writes了 希望我和LZ一样的好运,能遇到这样的题!
回复 支持 反对

使用道具 举报

hyxu2006 发表于 2016-11-19 08:40:31 | 显示全部楼层
求问LZ最后结果? 我感觉我碰到了跟你一样的第一题。 这个小哥Nice么?
回复 支持 反对

使用道具 举报

 楼主| zzhmxf 发表于 2016-11-20 16:40:00 | 显示全部楼层
hyxu2006 发表于 2016-11-19 08:40
求问LZ最后结果? 我感觉我碰到了跟你一样的第一题。 这个小哥Nice么?

过了。。。。
回复 支持 反对

使用道具 举报

hyxu2006 发表于 2016-11-21 03:25:25 | 显示全部楼层
zzhmxf 发表于 2016-11-20 16:40. Waral 鍗氬鏈夋洿澶氭枃绔,
过了。。。。

好的,谢谢楼主
回复 支持 反对

使用道具 举报

鼓頔娜夫 发表于 2016-11-23 02:00:23 | 显示全部楼层
打听一下~ lz team match的进展如何~
回复 支持 反对

使用道具 举报

 楼主| zzhmxf 发表于 2016-11-23 02:23:29 | 显示全部楼层
鼓頔娜夫 发表于 2016-11-23 02:00
打听一下~ lz team match的进展如何~

上周刚面了第一个组。还没消息。你也在team match吗?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 20:39

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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