一亩三分地论坛

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

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

Facebook intern phone interview一面

[复制链接] |试试Instant~ |关注本帖
woshixuyoudan 发表于 2016-2-27 06:09:13 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 硕士 实习@Facebook - 校园招聘会 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
1.two sum2.Longest Valid Parentheses  https://leetcode.com/problems/longest-valid-parentheses/
但是输出string


follow up:
因为我用的是StringBuilder输出的结果,然后他说  那你这样要copy原来的string 能不能不用出来extra space
我说直接在string上删除其实是产生新的string,也是要extra space
面试官说python和c++可以浓缩啊  那我们假设java也可以吧= =   我说stringbuilder就是可以删除啊
面试官说 那你当输入stringbuilder吧  然后我写了一个删除多余的括号的代码
面试官说 你这个删除一个应该是要O(n)吧 那你删除这么多很费时间啊  你能不能不这样
我迷茫了..我说能不能点hint
他说  那我们假设 每次删除一个或者同时删除多个都是O(n)  我说那我用一个list记录下来要删除的index吧
他说  那你还要extra space  我想了一下  我说那就用一个index来记录valid的那种  (类似remove zeros和remove duplicated items in sorted array的思路)  然后删掉后面的那一坨
不记得他说了啥。。大概意思就是可以吧  然后他给我了一个建议就是把所有要删除的位置上的character改成”#“  最后一起删掉有”#“的位置
. 1point3acres.com/bbs
。。。


我觉得好灵活..题目倒是见过 但是follow up感觉完全看面试官心情。。


面试官整体说话有点没睡醒的感觉,不是很热情但是态度总体都还可以  后来也有笑一下什么的 没口音
电话中间断了两次。。斯巴达。。

求人品求二面...

. visit 1point3acres.com for more.
补充内容 (2016-2-28 05:02):.1point3acres缃
第二题不是原题  说错了
()()))()  -> ()()()
)(( ->
(())(() -> (())()

补充内容 (2016-2-29 09:57):
一面过了 准备onsite

评分

4

查看全部评分

本帖被以下淘专辑推荐:

 楼主| woshixuyoudan 发表于 2016-3-1 04:33:29 | 显示全部楼层
frank11118 发表于 2016-3-1 03:46. Waral 鍗氬鏈夋洿澶氭枃绔,
請問有空間複雜度為 O(1) 的版本嗎? 謝謝 :-)
. 鍥磋鎴戜滑@1point 3 acres
对于java来说是不可能的 因为要重新创建一个string作为结果

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

1064no1carry 发表于 2016-2-27 07:46:22 | 显示全部楼层
lz第二题是什么思路?
回复 支持 反对

使用道具 举报

 楼主| woshixuyoudan 发表于 2016-2-27 07:47:14 | 显示全部楼层
1064no1carry 发表于 2016-2-27 07:46
lz第二题是什么思路?

.鏈枃鍘熷垱鑷1point3acres璁哄潧public String balance(String s) {
        char[] c = s.toCharArray();
        StringBuilder sb = new StringBuilder();
        int left = 0, right = 0;
        for (int i = 0; i < c.length; i++) {-google 1point3acres
            if (c == '(') {
                left++;
                sb.append('(');
            } else if (c == ')' && right < left) {
                right++;
                sb.append(')');
            }
        }

        c = sb.toString().toCharArray();
        sb = new StringBuilder();
        left = 0;
. from: 1point3acres.com/bbs         right = 0;
        for (int i = c.length - 1; i >= 0; i--) {
            if (c == ')') {
                right++;
                sb.append(')');
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴            } else if (c == '(' && left < right) {
                left++;
                sb.append('(');
            }
        }
        return sb.reverse().toString();
    }
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-2-27 07:54:37 | 显示全部楼层
你填写完问卷以后,多久收到的面试通知
回复 支持 反对

使用道具 举报

 楼主| woshixuyoudan 发表于 2016-2-27 07:55:16 | 显示全部楼层
xiaozhuxiaozhu 发表于 2016-2-27 07:54
你填写完问卷以后,多久收到的面试通知

on campus转为电面的  没有填问卷
回复 支持 反对

使用道具 举报

找工专用小马甲 发表于 2016-2-27 08:08:19 | 显示全部楼层
马上要面facebook 看面经都是考hard... 感觉很虚
回复 支持 反对

使用道具 举报

aangel 发表于 2016-2-27 08:22:12 | 显示全部楼层
设两个指针 i,j,指向当前最长valid括号的开头和结尾

当有一个新的更长的括号匹配出现时,更新一下i和j
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
最后输出 str.substring(i,j+1)即可
. 1point 3acres 璁哄潧

整个过程需要一个O(n)的for loop, DP

补充内容 (2016-2-27 08:25):
时间复杂度O(n),空间O(1)吧
回复 支持 反对

使用道具 举报

 楼主| woshixuyoudan 发表于 2016-2-27 08:27:04 | 显示全部楼层
aangel 发表于 2016-2-27 08:22
设两个指针 i,j,指向当前最长valid括号的开头和结尾

当有一个新的更长的括号匹配出现时,更新一下i和j
...
. 鍥磋鎴戜滑@1point 3 acres
不对吧..
如果是())()()()
删掉的是中间的‘)’
回复 支持 反对

使用道具 举报

aangel 发表于 2016-2-27 08:34:39 | 显示全部楼层
woshixuyoudan 发表于 2016-2-27 08:27
不对吧..
如果是())()()()
删掉的是中间的‘)’

我不需要删除操作啊,我只需要记下i,j两个坐标
最后输出一个string.substring(i,j+1)就可以了

比如最长的长度是6,结果是输出()()()

补充内容 (2016-2-27 08:38):.鏈枃鍘熷垱鑷1point3acres璁哄潧
不需要用到stringbuilder这里
回复 支持 反对

使用道具 举报

1064no1carry 发表于 2016-2-27 10:15:05 | 显示全部楼层
woshixuyoudan 发表于 2016-2-27 07:47
public String balance(String s) {
        char[] c = s.toCharArray();
        StringBuilder sb = ...
. 鍥磋鎴戜滑@1point 3 acres
多谢!LZ这正反扫一遍的方法很巧。
回复 支持 反对

使用道具 举报

 楼主| woshixuyoudan 发表于 2016-2-27 10:32:43 | 显示全部楼层
aangel 发表于 2016-2-27 08:34
. from: 1point3acres.com/bbs 我不需要删除操作啊,我只需要记下i,j两个坐标
最后输出一个string.substring(i,j+1)就可以了

不是很理解..  i 和 j 是开头和结尾吗?
回复 支持 反对

使用道具 举报

aangel 发表于 2016-2-27 10:38:45 | 显示全部楼层
woshixuyoudan 发表于 2016-2-27 10:32. 1point 3acres 璁哄潧
不是很理解..  i 和 j 是开头和结尾吗?

对,维护的i和j是最长合法括号匹配的起始坐标和结尾坐标,. From 1point 3acres bbs
leetcode原题不是只要输出int吗?这题要是要求输出最大长度的string
就每次DP的时候更新一下i和j就好了,.1point3acres缃
for loop结束的时候 return s.substring(i,j+1);
回复 支持 反对

使用道具 举报

 楼主| woshixuyoudan 发表于 2016-2-27 10:40:07 | 显示全部楼层
aangel 发表于 2016-2-27 10:38
对,维护的i和j是最长合法括号匹配的起始坐标和结尾坐标,
leetcode原题不是只要输出int吗?这题要是要 ...

如果是())()()的i和j分别是多少?
回复 支持 反对

使用道具 举报

aangel 发表于 2016-2-27 11:35:50 | 显示全部楼层
woshixuyoudan 发表于 2016-2-27 10:40
如果是())()()的i和j分别是多少?

. Waral 鍗氬鏈夋洿澶氭枃绔,3和6啊,leetcode原题不是考虑最长的合法substring吗?
难道这题要求不是substring,而是要输出()()()
回复 支持 反对

使用道具 举报

 楼主| woshixuyoudan 发表于 2016-2-27 12:03:21 | 显示全部楼层
aangel 发表于 2016-2-27 11:35
3和6啊,leetcode原题不是考虑最长的合法substring吗?
难道这题要求不是substring,而是要输出()()()

对呀 要输出()()()
回复 支持 反对

使用道具 举报

aangel 发表于 2016-2-27 12:16:39 | 显示全部楼层

恩,我找到题目出处了,
应该就是这道题

http://www.1point3acres.com/bbs/thread-125084-1-1.html
回复 支持 反对

使用道具 举报

frank11118 发表于 2016-2-27 14:30:10 | 显示全部楼层

請問樓主
原 leetcode 題輸出會是 ()()
所以跟原本 leetcode 題目不太一樣囉?
https://leetcode.com/problems/longest-valid-parentheses/
回复 支持 反对

使用道具 举报

 楼主| woshixuyoudan 发表于 2016-2-28 02:36:53 | 显示全部楼层
frank11118 发表于 2016-2-27 14:30
請問樓主
原 leetcode 題輸出會是 ()(). more info on 1point3acres.com
所以跟原本 leetcode 題目不太一樣囉?

恩恩..可能我没有仔细看leetcode的原题
你说的对 是不太一样 应该是这样
. more info on 1point3acres.com
())()() -> ()()()
()(()    -> ()()
)(        ->
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-4 00:19

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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