May 2009 - May 2017 论坛八周年-你的足迹,我的骄傲


一亩三分地论坛

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

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

Facebook intern phone interview一面

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

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

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

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

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


follow up:
因为我用的是StringBuilder输出的结果,然后他说  那你这样要copy原来的string 能不能不用出来extra space . 鍥磋鎴戜滑@1point 3 acres
我说直接在string上删除其实是产生新的string,也是要extra space
面试官说python和c++可以浓缩啊  那我们假设java也可以吧= =   我说stringbuilder就是可以删除啊. from: 1point3acres.com/bbs
面试官说 那你当输入stringbuilder吧  然后我写了一个删除多余的括号的代码. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
面试官说 你这个删除一个应该是要O(n)吧 那你删除这么多很费时间啊  你能不能不这样
我迷茫了..我说能不能点hint
他说  那我们假设 每次删除一个或者同时删除多个都是O(n)  我说那我用一个list记录下来要删除的index吧
他说  那你还要extra space  我想了一下  我说那就用一个index来记录valid的那种  (类似remove zeros和remove duplicated items in sorted array的思路)  然后删掉后面的那一坨. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
不记得他说了啥。。大概意思就是可以吧  然后他给我了一个建议就是把所有要删除的位置上的character改成”#“  最后一起删掉有”#“的位置

。。。


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


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

求人品求二面...


补充内容 (2016-2-28 05:02):
第二题不是原题  说错了
()()))()  -> ()()()
)(( ->
(())(() -> (())()

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

评分

4

查看全部评分

本帖被以下淘专辑推荐:

 楼主| woshixuyoudan 发表于 2016-3-1 04:33:29 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
frank11118 发表于 2016-3-1 03:46
請問有空間複雜度為 O(1) 的版本嗎? 謝謝 :-)

对于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第二题是什么思路?

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++) {.1point3acres缃
            if (c == '(') {
                left++;
                sb.append('(');
            } else if (c == ')' && right < left) {
                right++;
                sb.append(')');
            }
        }

        c = sb.toString().toCharArray();. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
        sb = new StringBuilder();
        left = 0;
        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
. 鍥磋鎴戜滑@1point 3 acres
最后输出 str.substring(i,j+1)即可


整个过程需要一个O(n)的for loop, DP
. Waral 鍗氬鏈夋洿澶氭枃绔,
补充内容 (2016-2-27 08:25):
时间复杂度O(n),空间O(1)吧
回复 支持 反对

使用道具 举报

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

当有一个新的更长的括号匹配出现时,更新一下i和j
...

不对吧..
如果是())()()()
删掉的是中间的‘)’
回复 支持 反对

使用道具 举报

aangel 发表于 2016-2-27 08:34:39 | 显示全部楼层
woshixuyoudan 发表于 2016-2-27 08:27. From 1point 3acres bbs
不对吧.. 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
如果是())()()()
删掉的是中间的‘)’

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

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

补充内容 (2016-2-27 08:38):. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
不需要用到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 = ...

多谢!LZ这正反扫一遍的方法很巧。
回复 支持 反对

使用道具 举报

 楼主| woshixuyoudan 发表于 2016-2-27 10:32:43 | 显示全部楼层
aangel 发表于 2016-2-27 08:34. 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
不是很理解..  i 和 j 是开头和结尾吗?

对,维护的i和j是最长合法括号匹配的起始坐标和结尾坐标,
leetcode原题不是只要输出int吗?这题要是要求输出最大长度的string
就每次DP的时候更新一下i和j就好了,
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分别是多少?

3和6啊,leetcode原题不是考虑最长的合法substring吗?. from: 1point3acres.com/bbs
难道这题要求不是substring,而是要输出()()()
回复 支持 反对

使用道具 举报

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

使用道具 举报

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

恩,我找到题目出处了, 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
应该就是这道题

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

使用道具 举报

frank11118 发表于 2016-2-27 14:30:10 | 显示全部楼层
. visit 1point3acres.com for more.
請問樓主
原 leetcode 題輸出會是 ()() 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
所以跟原本 leetcode 題目不太一樣囉?
https://leetcode.com/problems/longest-valid-parentheses/. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
回复 支持 反对

使用道具 举报

 楼主| woshixuyoudan 发表于 2016-2-28 02:36:53 | 显示全部楼层
frank11118 发表于 2016-2-27 14:30. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
請問樓主
原 leetcode 題輸出會是 ()()
所以跟原本 leetcode 題目不太一樣囉?
. 鍥磋鎴戜滑@1point 3 acres
恩恩..可能我没有仔细看leetcode的原题
你说的对 是不太一样 应该是这样

())()() -> ()()()
()(()    -> ()()
)(        ->
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-5-25 22:32

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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