推荐:数据科学课程和书籍清单以及培训讲座


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 1768|回复: 11
收起左侧

Facebook Nov 7 电面面经

[复制链接] |试试Instant~ |关注本帖
majia67 发表于 2016-11-14 11:17:17 | 显示全部楼层 |阅读模式

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

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

x
看地里面FB的面经不是很多,过来贡献一下~

我的fb电面有点坎坷。第一次约的时候,因为手机是小米5国内版,可能是制式支持得不好,国人大哥打了两次电话过来愣是接不到电话,直接给reschedule了,当时心里真是万马奔腾……无奈只好又等了两周,期间果断去换了一部iphone。

第二次电面我的是一位印度大哥,口音不大,人非常Nice,一开始迟到了几分钟一个劲地跟我道歉。

先是问了一下project,曾经遇到的难关以及解决的思路。我就选了一个之前参加的大数据比赛讲了一下,但是印度大哥觉得technical challenge不够,结果比预想的讲得详细……当时心里就有点慌。
-google 1point3acres
然后就是做题。第一题是给一个字符串,里面包含三种括号,问这个括号表达式是不是平衡的。这道题之前做Cloudera OA的时候遇到过,用一个stack扫一遍即可。需要特别注意一些corner cases,比如string为空,出现括号以外的字符如何处理,最后stack是否为空等等。印度大哥比较满意,不过还是被他发现了一个bug,就是如果一开始的string是null如何处理。

第二题是第一题的follow up,删掉最少的字符,使得一个不平衡的括号表达式变得平衡,返回任意一种解法均可。这道题一开始我想复杂了,用了bfs + 搜索剪枝来做。写完代码,印度大哥表示太复杂了,提示只需要简单修改一下第一问的代码。于是我猛然想到,第一问中判定false的情况,如何纠正才能使得结果字符串平衡?简而言之,如果遇到多余的右括号,就直接删去。如果扫完一遍之后stack里面还有剩余的左括号,也直接删去。按照这个思路说了一遍,印度大哥表示满意,因为时间有限,没有让写代码。

其实感觉面得不是特别理想,主要是第二题反应的不够快,被自己绕进去了,以致于没有来得及写出最终代码。所幸遇到人品很好的印度大哥,周五收到了HR通知onsite的邮件。

希望对大家有所帮助。祝大家都能找到理想的工作:)

评分

2

查看全部评分

本帖被以下淘专辑推荐:

xiaozhuxiaozhu 发表于 2016-11-14 11:33:48 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
第2题的思路,应该不能保证,得到的结果是删除掉最少情况的结果。. Waral 鍗氬鏈夋洿澶氭枃绔,
应该还得bfs来做。
用第2题的思路,怎么打印出一个结果呢?stack 上面放index?. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
. 鍥磋鎴戜滑@1point 3 acres
补充内容 (2016-11-14 11:35):
你的follow up,还是三种括号都在么?

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

jiangyntz 发表于 2016-11-14 11:41:18 | 显示全部楼层
关注一亩三分地微博:
Warald
同问去括号那题如何记录index?
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-11-14 11:45:46 | 显示全部楼层
jiangyntz 发表于 2016-11-14 11:41
同问去括号那题如何记录index?

建立一个char[] 长度为原来的string长度,没个位置映射原char在string中的位置。
但是,如果这题这么做,就是大改,不是随便改一下第1题就可以了。
所以想问下lz,到底是怎么做的。
回复 支持 反对

使用道具 举报

 楼主| majia67 发表于 2016-11-15 03:06:30 | 显示全部楼层
xiaozhuxiaozhu 发表于 2016-11-14 11:33
第2题的思路,应该不能保证,得到的结果是删除掉最少情况的结果。
应该还得bfs来做。. 鍥磋鎴戜滑@1point 3 acres
用第2题的思路,怎 ...

不好意思忘记说明,follow up里面只会出现一种括号。. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
思路应该是没有问题的,因为相当于删除使原来的式子平衡的障碍,所以是最少的删除次数。

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-11-15 03:07:07 | 显示全部楼层
majia67 发表于 2016-11-15 03:06
不好意思忘记说明,follow up里面只会出现一种括号。
思路应该是没有问题的,因为相当于删除使原来的式 ...

如果只有1中括号,就是面经高频原题了。
回复 支持 反对

使用道具 举报

 楼主| majia67 发表于 2016-11-15 03:08:34 | 显示全部楼层
xiaozhuxiaozhu 发表于 2016-11-14 11:45
建立一个char[] 长度为原来的string长度,没个位置映射原char在string中的位置。
但是,如果这题这么做 ...
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
当时面试官问我的时候,我是说把左括号的位置记录到stack里面,因为只有一种括号的情况下,不需要记录是哪一种括号。不过现在想想觉得用一个boolean数组记录一下第i个位置是否删除可能更好一些,因为右括号也需要记录是否删除,单用一个stack比较勉强。
回复 支持 反对

使用道具 举报

 楼主| majia67 发表于 2016-11-15 03:10:36 | 显示全部楼层
xiaozhuxiaozhu 发表于 2016-11-15 03:07. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
如果只有1中括号,就是面经高频原题了。
.1point3acres缃
看来是我功课做得不够仔细了,之前没有在地里面看到唉…
回复 支持 反对

使用道具 举报

wangxinbo1123 发表于 2017-1-24 07:40:17 | 显示全部楼层
第一题follow up:.1point3acres缃
  1. string balance(string& str) {
  2.         stack<int> stk;. more info on 1point3acres.com
  3.         for(int i = 0; i < str.size(); i++) {
  4.                 if(str[i] == '(') stk.push(i);
  5.                 else if(str[i] == ')') {
  6.                         if(stk.empty() || str[stk.top()] != '(') stk.push(i);
  7.                         else stk.pop();
  8.                 }
  9.         }
  10.         while(stk.size()) {
  11.                 str.erase(stk.top(), 1);
  12.                 stk.pop();
  13.         }
  14.         return str;
  15. }. more info on 1point3acres.com
复制代码
回复 支持 反对

使用道具 举报

 楼主| majia67 发表于 2017-1-24 13:45:21 | 显示全部楼层

最后直接erase恐怕不行吧,stack里面存的下标是原string的下标,erase每次都会改变string
回复 支持 反对

使用道具 举报

wangxinbo1123 发表于 2017-1-25 05:27:56 | 显示全部楼层
majia67 发表于 2017-1-24 13:45
最后直接erase恐怕不行吧,stack里面存的下标是原string的下标,erase每次都会改变string
. visit 1point3acres.com for more.
从后往前erase,erase之前的下标都没有被改变
回复 支持 反对

使用道具 举报

 楼主| majia67 发表于 2017-1-26 03:11:35 | 显示全部楼层
wangxinbo1123 发表于 2017-1-25 05:27
从后往前erase,erase之前的下标都没有被改变
.1point3acres缃
原来如此!非常聪明的想法
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-7-29 01:14

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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