一亩三分地论坛

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

一亩三分地官方iOS手机应用下载
查看: 4447|回复: 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 . from: 1point3acres.com/bbs
我说直接在string上删除其实是产生新的string,也是要extra space
面试官说python和c++可以浓缩啊  那我们假设java也可以吧= =   我说stringbuilder就是可以删除啊
面试官说 那你当输入stringbuilder吧  然后我写了一个删除多余的括号的代码
面试官说 你这个删除一个应该是要O(n)吧 那你删除这么多很费时间啊  你能不能不这样-google 1point3acres
我迷茫了..我说能不能点hint. From 1point 3acres bbs
他说  那我们假设 每次删除一个或者同时删除多个都是O(n)  我说那我用一个list记录下来要删除的index吧
他说  那你还要extra space  我想了一下  我说那就用一个index来记录valid的那种  (类似remove zeros和remove duplicated items in sorted array的思路)  然后删掉后面的那一坨
不记得他说了啥。。大概意思就是可以吧  然后他给我了一个建议就是把所有要删除的位置上的character改成”#“  最后一起删掉有”#“的位置-google 1point3acres

。。。


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

.鐣欏璁哄潧-涓浜-涓夊垎鍦
面试官整体说话有点没睡醒的感觉,不是很热情但是态度总体都还可以  后来也有笑一下什么的 没口音-google 1point3acres
电话中间断了两次。。斯巴达。。

求人品求二面...
. 1point 3acres 璁哄潧

补充内容 (2016-2-28 05:02):-google 1point3acres
第二题不是原题  说错了
()()))()  -> ()()(). 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
)(( ->
(())(() -> (())()

补充内容 (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. more info on 1point3acres.com
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++) {
            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

最后输出 str.substring(i,j+1)即可


整个过程需要一个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括号的开头和结尾
. visit 1point3acres.com for more.
当有一个新的更长的括号匹配出现时,更新一下i和j. 1point 3acres 璁哄潧
...

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

使用道具 举报

aangel 发表于 2016-2-27 08:34:39 | 显示全部楼层
woshixuyoudan 发表于 2016-2-27 08:27
不对吧..
如果是())()()()
删掉的是中间的‘)’
. 1point 3acres 璁哄潧
我不需要删除操作啊,我只需要记下i,j两个坐标
最后输出一个string.substring(i,j+1)就可以了-google 1point3acres
. visit 1point3acres.com for more.
比如最长的长度是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. from: 1point3acres.com/bbs
我不需要删除操作啊,我只需要记下i,j两个坐标
最后输出一个string.substring(i,j+1)就可以了
. 1point 3acres 璁哄潧
不是很理解..  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是最长合法括号匹配的起始坐标和结尾坐标,
. 1point 3acres 璁哄潧leetcode原题不是只要输出int吗?这题要是要 ...
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
如果是())()()的i和j分别是多少?
回复 支持 反对

使用道具 举报

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

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 | 显示全部楼层

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

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

使用道具 举报

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

使用道具 举报

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

恩恩..可能我没有仔细看leetcode的原题
你说的对 是不太一样 应该是这样. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
-google 1point3acres
())()() -> ()()()
()(()    -> ()(). visit 1point3acres.com for more.
)(        ->
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-4-30 16:43

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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