一亩三分地论坛

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

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

10/3Facebook电面

[复制链接] |试试Instant~ |关注本帖
tanpf5 发表于 2016-10-4 08:29:03 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 硕士 全职@Facebook - 内推 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
2个小时前面完的facebook fulltime电面
刚才找了半天,第一题lc应该没有原题,remove parentheses:. 鍥磋鎴戜滑@1point 3 acres
给一个字符串,里面有小括号和各种字符,remove最少次数得到一个括号匹配的字符串。.鏈枃鍘熷垱鑷1point3acres璁哄潧
跟301 Remove Invalid Parentheses貌似很像但做法完全不一样,具体其实不难,用stack来模拟就好。
第二题k closest points,竟然把Amazon的OA题拿来用。。相信做了Amazon OA的同学应该不在话下
.鏈枃鍘熷垱鑷1point3acres璁哄潧


补充内容 (2016-10-4 18:48):
.鏈枃鍘熷垱鑷1point3acres璁哄潧已拿到onsite

评分

6

查看全部评分

xiaozhuxiaozhu 发表于 2016-10-4 08:50:46 | 显示全部楼层
    public String removeInvalidParantheses(String s) {
           
        String firstPass = "";
        int left = 0, right = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴            if (c == '(') {
                left++;
                firstPass+='(';
            } else if (c == ')' && right<left) {
                right++; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
                firstPass+=')';
            } else if (c != ')' && c != '(') {. From 1point 3acres bbs
                firstPass+=c;
            }
        }

        left = 0;.鏈枃鍘熷垱鑷1point3acres璁哄潧
        right = 0;.鐣欏璁哄潧-涓浜-涓夊垎鍦
        StringBuilder sb = new StringBuilder();
        for(int i = firstPass.length()-1;i>=0;i--)
        {.鐣欏璁哄潧-涓浜-涓夊垎鍦
                char c = firstPass.charAt(i);
            if (c == ')') {
                right++;
                sb.append(')');
            } else if (c == '(' && left < right) {. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                left++;
                sb.append('(');. Waral 鍗氬鏈夋洿澶氭枃绔,
            } else if (c != ')' && c != '(') {
                sb.append(c);.鐣欏璁哄潧-涓浜-涓夊垎鍦
            }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
        }
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
        return sb.reverse().toString();. 鍥磋鎴戜滑@1point 3 acres
    }
回复 支持 2 反对 0

使用道具 举报

xiaozhuxiaozhu 发表于 2016-10-4 08:39:50 | 显示全部楼层
tanpf5 发表于 2016-10-4 08:34
原来这样,结果我第一题做了半个小时。。还好第二题我倒背如流。。

第1题, two pass.
用两个变量, int left, int right.
从头扫第1遍的时候, 加进去所有left,如果right不大于left, 就加进去stringbuilder。这样保证“)”都有相对应的"("。
第2遍,从第1次的stringbuilder的末尾扫,加进去所有 ), 如果left 不大于 right, 加进去所有 (。
第2遍pass的时候,解决了第1pass, “(”比 “)“多的情况。
回复 支持 1 反对 0

使用道具 举报

xiaozhuxiaozhu 发表于 2016-10-4 08:33:28 | 显示全部楼层
恭喜拿onsite.
第1题是面经高频原题。
回复 支持 反对

使用道具 举报

 楼主| tanpf5 发表于 2016-10-4 08:34:56 | 显示全部楼层
xiaozhuxiaozhu 发表于 2016-10-4 08:33
恭喜拿onsite.
第1题是面经高频原题。

原来这样,结果我第一题做了半个小时。。还好第二题我倒背如流。。
回复 支持 反对

使用道具 举报

leixiang5 发表于 2016-10-4 08:38:06 | 显示全部楼层
第一题貌似是leetcode题目吧?
回复 支持 反对

使用道具 举报

kobe24 发表于 2016-10-4 08:39:08 | 显示全部楼层
k-closest points to origin ?
回复 支持 反对

使用道具 举报

 楼主| tanpf5 发表于 2016-10-4 08:47:42 | 显示全部楼层
xiaozhuxiaozhu 发表于 2016-10-4 08:39
第1题, two pass.
用两个变量, int left, int right.-google 1point3acres
从头扫第1遍的时候, 加进去所有left,如果right ...

这个方法不错,具体在空间复杂度上比我的方法好
回复 支持 反对

使用道具 举报

liuzxiao 发表于 2016-10-4 08:53:13 | 显示全部楼层
第一题是tag 里面的那个的简单版
回复 支持 反对

使用道具 举报

iPhD 发表于 2016-10-4 08:55:20 | 显示全部楼层
求楼主把第二题的代码发下好吗?大谢!
回复 支持 反对

使用道具 举报

 楼主| tanpf5 发表于 2016-10-4 08:55:44 | 显示全部楼层
liuzxiao 发表于 2016-10-4 08:53
第一题是tag 里面的那个的简单版

算简单版吧,不过hard那题我用的bfs,所以这题其实对我来说跟那个题相当于两个题,毕竟做法完全不一样
回复 支持 反对

使用道具 举报

 楼主| tanpf5 发表于 2016-10-4 08:56:13 | 显示全部楼层
kobe24 发表于 2016-10-4 08:39. 鍥磋鎴戜滑@1point 3 acres
k-closest points to origin ?

是,不过就算不是origin也很简单,就是处理稍微麻烦了点
回复 支持 反对

使用道具 举报

iPhD 发表于 2016-10-4 09:23:38 | 显示全部楼层
xiaozhuxiaozhu 发表于 2016-10-4 08:50. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
public String removeInvalidParantheses(String s) {. 1point 3acres 璁哄潧
           
        String firstPass = "";

大神,能把第二题代码也发下吗?多谢啦
回复 支持 反对

使用道具 举报

gaocan1992 发表于 2016-10-4 09:31:01 | 显示全部楼层
讲一讲第一题和301的区别可以么
回复 支持 反对

使用道具 举报

johnjavabean 发表于 2016-10-4 09:33:58 | 显示全部楼层
求问楼主怎么拿到面试的...什么时候投的/找人内推的?
回复 支持 反对

使用道具 举报

kobe24 发表于 2016-10-4 09:35:46 | 显示全部楼层
tanpf5 发表于 2016-10-4 08:56
是,不过就算不是origin也很简单,就是处理稍微麻烦了点
. more info on 1point3acres.com
楼主用的是maxheap吗
回复 支持 反对

使用道具 举报

kobe24 发表于 2016-10-4 09:36:30 | 显示全部楼层
gaocan1992 发表于 2016-10-4 09:31. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
讲一讲第一题和301的区别可以么

fb这题只要返回一个结果  但是LC那题要返回所有的结果  用BFS
回复 支持 反对

使用道具 举报

 楼主| tanpf5 发表于 2016-10-4 09:38:07 | 显示全部楼层
kobe24 发表于 2016-10-4 09:35.鏈枃鍘熷垱鑷1point3acres璁哄潧
楼主用的是maxheap吗

是的,时间复杂度nlogk基本就可以了
回复 支持 反对

使用道具 举报

 楼主| tanpf5 发表于 2016-10-4 09:39:05 | 显示全部楼层
johnjavabean 发表于 2016-10-4 09:33
求问楼主怎么拿到面试的...什么时候投的/找人内推的?

内推,算是强推吧,直接把我简历给hr,第二天就联系我了
回复 支持 反对

使用道具 举报

gaocan1992 发表于 2016-10-4 09:42:13 | 显示全部楼层
xiaozhuxiaozhu 发表于 2016-10-3 16:39. visit 1point3acres.com for more.
第1题, two pass.
用两个变量, int left, int right.
从头扫第1遍的时候, 加进去所有left,如果right ...

非常感谢,确实听说第一题和lc不一样
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-4 03:48

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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