一亩三分地论坛

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

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

facebook 电面

[复制链接] |试试Instant~ |关注本帖
herz 发表于 2014-9-26 12:31:21 | 显示全部楼层 |阅读模式

2014(7-9月) 码农类 硕士 全职@Facebook - 内推 - 技术电面 |Pass

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

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

x
承蒙地上的伙伴内推,今天电面了非死不可,面完后半小时接到onsite的通知,不得不佩服fb hr的办事效率! 面我是老印,感觉蛮苛刻的,狂抠我细节,即使我代码100%能过也很短总让我这里简化一下那里简化一下,最后可能还是挑不出大毛病就让我过吧。
呈上面经:
1. 把数组里面非零整数弄到左边,零的弄到右边,要求交换次数最少。
我用的是一头一尾两个指针,满足条件就交换,扫到相遇为止
follow up:
1. 减少(i<j)的判断次数。PS:可能是由于我实现方法不是每次只移一下,而是移到0和非0为止,像qsort一样,while里面有两个while,和他标准答案不同,这样需要的边界判断就多了
2. 算法复杂度,假如有n个元素和k个0,问交换的次数

2.给出一个无重复数字的array,输出其subset。 例如[1, 2],输出[] [1] [2] [1, 2]
我一开始用了dfs,面试官check过无误后让我写成iterative. 稍微想了一下,就用位运算做了,每个独立subset都可以用长度为array大小的二进制串表示,0代表不存在,1代表存在,只要从0 枚举到2^n-1就 ok了。
需要注意的是,如果用int来代表状态的话最多只要31位,也就是array超过31个元素就不行了,这时要用01 vector去高精度模拟二进制串。

祝各位好运,求大米加分

. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

评分

10

查看全部评分

blesscol 发表于 2014-9-30 12:35:07 | 显示全部楼层
public static void partition(int[] A){.1point3acres缃
        int idx = 0;. from: 1point3acres.com/bbs
        for(int i = 0; i < A.length; i++){
            if(A[i] != 0){. Waral 鍗氬鏈夋洿澶氭枃绔,
                A[idx++] = A[i];
            }
        }
        while(idx < A.length){. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
            A[idx++] = 0;
        }
}

评分

1

查看全部评分

回复 支持 3 反对 0

使用道具 举报

pyemma 发表于 2014-11-25 08:15:00 | 显示全部楼层
kongweihan 发表于 2014-11-23 19:36
第二题另一种方法是从空ArrayList开始,循环数组,每个数都把现有的set复制一遍加上当前的数
愿楼主已经拿 ...
. 1point3acres.com/bbs
没错,可以开个ArrayList增量式的添加元素,但是这种做法只有在没有duplicate的时候是正确的。
回复 支持 1 反对 0

使用道具 举报

lhh_NJU 发表于 2014-9-30 11:34:23 | 显示全部楼层
herz 发表于 2014-9-26 16:20
阿三鸡蛋里面挑刺而已,它后来给出自己的答案,后来细想和我比较的次数完全相等,只是写出来少写两个(i

我后来自己写了一下, 确实会有很多边界检测. 不过这个东西很重要的说, 我在FB实习过, 我在的那个对代码质量挺高的, code review的时候如果你有哪怕一丁点冗余的代码也不会让你过的。
回复 支持 1 反对 0

使用道具 举报

shinichish 发表于 2014-9-26 14:37:55 | 显示全部楼层
预祝LZ披荆斩棘,斩获offer
回复 支持 1 反对 0

使用道具 举报

sally216 发表于 2014-9-26 12:56:31 | 显示全部楼层
谢分享. 1point3acres.com/bbs
2. 超过31位那组合得多大啊,也没有实际意义吧。
回复 支持 反对

使用道具 举报

 楼主| herz 发表于 2014-9-26 12:59:10 | 显示全部楼层
sally216 发表于 2014-9-26 12:56
谢分享
2. 超过31位那组合得多大啊,也没有实际意义吧。

对啊,这是烙印interviewer follow up的问题……我当时也没想到,只说这种复杂度几何级数增长的问题 array size不能太大
回复 支持 反对

使用道具 举报

lhh_NJU 发表于 2014-9-26 16:02:22 | 显示全部楼层
求问第一题的标准答案是什么啊? 想不出比你更好的。。
回复 支持 反对

使用道具 举报

 楼主| herz 发表于 2014-9-26 16:20:53 | 显示全部楼层
lhh_NJU 发表于 2014-9-26 16:02
求问第一题的标准答案是什么啊? 想不出比你更好的。。

阿三鸡蛋里面挑刺而已,它后来给出自己的答案,后来细想和我比较的次数完全相等,只是写出来少写两个(i<j)
回复 支持 反对

使用道具 举报

yk527 发表于 2014-9-27 00:27:54 | 显示全部楼层
herz 发表于 2014-9-26 16:20
阿三鸡蛋里面挑刺而已,它后来给出自己的答案,后来细想和我比较的次数完全相等,只是写出来少写两个(i

如果较真来说数据非常大的话少两个比较可能比你效率高5%-10%, 我reference编程珠玑里面猜的, 不知道对不对.
回复 支持 反对

使用道具 举报

 楼主| herz 发表于 2014-9-27 01:36:15 | 显示全部楼层
yk527 发表于 2014-9-27 00:27
如果较真来说数据非常大的话少两个比较可能比你效率高5%-10%, 我reference编程珠玑里面猜的, 不知道对不 ...
. visit 1point3acres.com for more.
有可能,不过我是按照标准快排改的,高中开始就那么写了…看来以后刷leetcode还是得看discuss里面人家的写法
回复 支持 反对

使用道具 举报

22691482 发表于 2014-9-30 11:44:51 | 显示全部楼层
感觉难度没有很大啊。。。但是FB我找人内推了三个星期还没鸟我
回复 支持 反对

使用道具 举报

mumblingrabbit 发表于 2014-10-3 22:17:03 | 显示全部楼层
稍微想了一下。。。好腻害
回复 支持 反对

使用道具 举报

 楼主| herz 发表于 2014-10-5 05:24:23 | 显示全部楼层
mumblingrabbit 发表于 2014-10-3 22:17
稍微想了一下。。。好腻害

学长见笑了,我也是ZJU的 :)
回复 支持 反对

使用道具 举报

kongweihan 发表于 2014-11-24 11:36:00 | 显示全部楼层
第二题另一种方法是从空ArrayList开始,循环数组,每个数都把现有的set复制一遍加上当前的数.1point3acres缃
愿楼主已经拿到offer了!
回复 支持 反对

使用道具 举报

averillzheng 发表于 2014-11-25 10:23:20 | 显示全部楼层
lhh_NJU 发表于 2014-9-30 11:34
我后来自己写了一下, 确实会有很多边界检测. 不过这个东西很重要的说, 我在FB实习过, 我在的那个对代码质 ...
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
有这么恐怖吗?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-7 21:02

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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