一亩三分地论坛

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

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

FB电面,水过

[复制链接] |试试Instant~ |关注本帖
smallsimple 发表于 2015-4-1 14:22:50 | 显示全部楼层 |阅读模式

2015(1-3月) 码农类 硕士 实习@Facebook - 网上海投 - 技术电面 |Passfresh grad应届毕业生

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

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

x
来报一个FB电面面筋。
一面:白人。 先问了问简历。 然后做题 LC combination sum 类似题。先写了递归的做法。follow up 如果不用递归怎么做。于是又写了非递归做法。结束。. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
中间有让我讨论一些code的detail的东西,比如为什么这样做可行,为什么这样可以避免重复元素等等。
. Waral 鍗氬鏈夋洿澶氭枃绔,
二面(昨天刚面):老印。也是先问了问project。然后做题。第一题,simplify path类似题。写完他发现了个bug (ORZ),然后题示我及时更正了。第二题,Letter Combinations of a Phone number 类似题。很快用递归写完,然后问了个很奇怪的问题,如果用我的程序跑出来结果,如何确定结果是对的。我就开始瞎掰了。说着说着电话掉线了,(我了个汗!)关键是我还不知道什么时候掉的,估计我对着空电话说了好久。然后那头一直没声,发现掉线了。 一会打过来,就说还有什么问题要问,问了个问题之后,我问他要不要再让我解译一下刚才掉线时候说的,他说好。于是又扯了一便。然后他说答的挺好的。我真不知道他怎么觉的好,我自己都觉的我说的不是很清楚。然后就挂了。
本来最开始一听是老印,觉得要悲剧了。不过他说话挺美国范的。一直说great, cool呀什么的。发音也比较清楚。交流起来感觉还挺不错的。

今天拿到offer了。也祝大家能拿到好的offer!. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
-google 1point3acres

评分

1

查看全部评分

haungge0385 发表于 2015-4-9 03:27:39 | 显示全部楼层
把楼主的代码写了个java版本的,佩服能做出来!
  1. public ArrayList<ArrayList<Integer>> combinationSum(int[] candidates, int target) {
  2.                 ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
  3.                 ArrayList<Integer> item = new ArrayList<Integer>();. 1point3acres.com/bbs
  4.                 Stack<ArrayList<Integer>> res_stack = new Stack<ArrayList<Integer>>();
  5.                 Stack<Integer> sum_stack = new Stack<Integer>();
  6.                 Stack<Integer> index_stack = new Stack<Integer>();
  7.                
  8.                 res_stack.push(item);
  9.                 sum_stack.push(0);
  10.                 index_stack.push(0);
  11.                
  12.                 Arrays.sort(candidates);
  13.                
  14.                 while (!res_stack.isEmpty()) {
  15.                         ArrayList<Integer> item_temp = res_stack.pop();
  16.                         int sum = sum_stack.pop();
  17.                         int start = index_stack.pop();
  18.                         . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  19.                         if (sum == target) {
  20.                                 res.add(item_temp);
  21.                         }else if (sum > target) {
  22.                                 continue;
  23.                         }else {.1point3acres缃
  24.                                 for (int i = start; i < candidates.length; i++) {
  25.                                         int newsum = sum + candidates[i];
  26.                                         ArrayList<Integer> item_temp2 =new ArrayList<Integer>(item_temp); -google 1point3acres
  27.                                                        
  28.                                         item_temp2.add(candidates[i]);
  29.                                        
  30.                                         res_stack.push(item_temp2);
  31.                                         sum_stack.push(newsum);
  32.                                         index_stack.push(i);
  33.                                 }
  34.                         }.1point3acres缃
  35.                        
  36.                 }
  37.                 return res;
  38.         }
  39.        
复制代码
回复 支持 1 反对 0

使用道具 举报

yuxrose 发表于 2015-4-1 15:00:50 | 显示全部楼层
晕死,combinations sum也得用非递归写啊。。。。facebook真是魔怔了,每道题都得两种方法。。
lz能说说非递归咋写吗?

恭喜lz!
回复 支持 反对

使用道具 举报

 楼主| smallsimple 发表于 2015-4-1 21:13:07 | 显示全部楼层
yuxrose 发表于 2015-4-1 15:00
晕死,combinations sum也得用非递归写啊。。。。facebook真是魔怔了,每道题都得两种方法。。
lz能说说非 ...

我也是想了挺久。用stack记下目前为止得到的结果,每次pop一个结果出来,看是否满足sum,小于sum的话,就合理加入新的元素,再push进stack。等于sum的话,加入结果。大于sum的话舍弃。其实跟用recursion的思路是一样的,只不过用stack做dfs。
回复 支持 反对

使用道具 举报

seabiscuit119 发表于 2015-4-2 00:30:57 | 显示全部楼层
how long did lz receive the offer from the second phone interview?
回复 支持 反对

使用道具 举报

 楼主| smallsimple 发表于 2015-4-2 00:53:12 | 显示全部楼层
seabiscuit119 发表于 2015-4-2 00:30
how long did lz receive the offer from the second phone interview?

received the offer on the next day.
回复 支持 反对

使用道具 举报

seabiscuit119 发表于 2015-4-2 01:36:34 | 显示全部楼层
smallsimple 发表于 2015-4-2 00:53
received the offer on the next day.

so so fast....
回复 支持 反对

使用道具 举报

seabiscuit119 发表于 2015-4-2 01:37:47 | 显示全部楼层
smallsimple 发表于 2015-4-2 00:53
received the offer on the next day.

Is there a HR call after the second interview or just an email?
回复 支持 反对

使用道具 举报

安静的企鹅 发表于 2015-4-2 01:50:05 | 显示全部楼层
楼主 rp must be too high. 赞一个~
回复 支持 反对

使用道具 举报

 楼主| smallsimple 发表于 2015-4-2 01:50:29 | 显示全部楼层
seabiscuit119 发表于 2015-4-2 01:37
Is there a HR call after the second interview or just an email?

电面完第二天中午收到邮件说晚上打个电话聊聊,让确认下时间。然后晚上电话过来就说给offer了。你也有面他家吗?
回复 支持 反对

使用道具 举报

seabiscuit119 发表于 2015-4-2 03:00:42 | 显示全部楼层
smallsimple 发表于 2015-4-2 01:50
电面完第二天中午收到邮件说晚上打个电话聊聊,让确认下时间。然后晚上电话过来就说给offer了。你也有面 ...

Will have second interview on Friday. Hope to meet Leetcode problems....
回复 支持 反对

使用道具 举报

 楼主| smallsimple 发表于 2015-4-2 03:13:50 | 显示全部楼层
seabiscuit119 发表于 2015-4-2 03:00
Will have second interview on Friday. Hope to meet Leetcode problems....

好像最近问的题都是leetcode上的。祝好运。
回复 支持 反对

使用道具 举报

seabiscuit119 发表于 2015-4-2 03:48:13 | 显示全部楼层
smallsimple 发表于 2015-4-2 03:13
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷好像最近问的题都是leetcode上的。祝好运。

Thx!!  // size
回复 支持 反对

使用道具 举报

siren01 发表于 2015-4-2 05:33:42 | 显示全部楼层
smallsimple 发表于 2015-4-2 01:50
电面完第二天中午收到邮件说晚上打个电话聊聊,让确认下时间。然后晚上电话过来就说给offer了。你也有面 ...

楼主好人,求combinationSum的非递归解法,求code
回复 支持 反对

使用道具 举报

crazybadboy 发表于 2015-4-2 10:55:17 | 显示全部楼层
请问楼主,非递归的是combination sum I 还是combination sum II?
回复 支持 反对

使用道具 举报

haoxuango 发表于 2015-4-2 11:00:43 | 显示全部楼层
楼主一面二面隔了多久
回复 支持 反对

使用道具 举报

yuxrose 发表于 2015-4-2 11:04:49 | 显示全部楼层
siren01 发表于 2015-4-2 05:33. 1point3acres.com/bbs
楼主好人,求combinationSum的非递归解法,求code

求code + 1, lz 好人!
回复 支持 反对

使用道具 举报

ppips 发表于 2015-4-2 11:18:08 | 显示全部楼层
siren01 发表于 2015-4-2 05:33
楼主好人,求combinationSum的非递归解法,求code
-google 1point3acres
仅供参考
  1. public List<List<Integer>> combinationSum(int[] candidates, int target) {
  2.         Arrays.sort(candidates);. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  3.         List<List<List<Integer>>> dp = new ArrayList<List<List<Integer>>>();
    鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  4.         for (int i = 1; i <= target; i++) {
  5.             List<List<Integer>> list_i = new ArrayList<List<Integer>>();
  6.             for (int j = 0; j < candidates.length && candidates[j] <= i; j++) {.鏈枃鍘熷垱鑷1point3acres璁哄潧
  7.                 if (i == candidates[j])
  8.                     list_i.add(Arrays.asList(candidates[j]));. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  9.                 else {. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  10.                     for (List<Integer> l : dp.get(i - 1 - candidates[j])) {
  11.                         if (candidates[j] <= l.get(0)) {
  12.                             List<Integer> tmp = new ArrayList<Integer>();
  13.                             tmp.add(candidates[j]);
  14.                             tmp.addAll(l);
  15.                             if (!list_i.contains(tmp))-google 1point3acres
  16.                                 list_i.add(tmp);
  17.                         }. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  18.                     }
  19.                 }
  20.             }
  21.             dp.add(list_i);
  22.         }
  23.         return dp.get(target - 1);
  24.     }
复制代码
回复 支持 反对

使用道具 举报

ryuichist 发表于 2015-4-2 11:21:44 | 显示全部楼层
不用onsite就拿到offer了啊,双
回复 支持 反对

使用道具 举报

readman 发表于 2015-4-2 12:40:10 | 显示全部楼层
public static ArrayList<ArrayList<Integer>> permutation(int[] ary) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        while (true){
            ArrayList<Integer> tmp = new ArrayList<>();
            for (int i : ary) tmp.add(i);
            res.add(tmp);
            int j = ary.length - 2;
            while ( j >= 0 && ary[j]>=ary[j+1])
                j--;. Waral 鍗氬鏈夋洿澶氭枃绔,
            if (j < 0)
                break;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
            int k = ary.length - 1;
            while (k > j && ary[k] <= ary[j] ). 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                k--;
            swap(ary, j, k);
            reverse(ary, j+1, ary.length - 1);. from: 1point3acres.com/bbs
        }
        return res;
    }
    public static void swap(int[] ary, int i, int j) {
        int tmp = ary[i];
        ary[i] = ary[j];
        ary[j] = tmp;
    }
    public static void reverse(int[] ary, int start, int end) {
        while (start < end){
            swap(ary, start, end);
            start++;
            end--;. Waral 鍗氬鏈夋洿澶氭枃绔,
        }
.1point3acres缃    }

Algorithm L
回复 支持 反对

使用道具 举报

siren01 发表于 2015-4-2 12:45:07 | 显示全部楼层

谢谢共享,看完后有一点,你这外循环从1迭代到target,复杂度还是很高的...三个List吓人
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-6 14:19

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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