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


一亩三分地论坛

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

一亩三分地官方iOS手机应用下载
查看: 5940|回复: 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


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


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


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

求人品求二面.... 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

. 1point3acres.com/bbs
补充内容 (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-google 1point3acres
lz第二题是什么思路?

public String balance(String s) {
        char[] c = s.toCharArray();
        StringBuilder sb = new StringBuilder();
        int left = 0, right = 0;. From 1point 3acres bbs
        for (int i = 0; i < c.length; i++) {
            if (c == '(') {
                left++;
                sb.append('(');
            } else if (c == ')' && right < left) {
                right++;
                sb.append(')');
            }. more info on 1point3acres.com
        }

        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) {. 1point 3acres 璁哄潧
                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)即可
-google 1point3acres

整个过程需要一个O(n)的for loop, DP
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴. from: 1point3acres.com/bbs
补充内容 (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括号的开头和结尾
. from: 1point3acres.com/bbs
当有一个新的更长的括号匹配出现时,更新一下i和j
...
. more info on 1point3acres.com
不对吧..
如果是())()()()
删掉的是中间的‘)’
回复 支持 反对

使用道具 举报

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

我不需要删除操作啊,我只需要记下i,j两个坐标. more info on 1point3acres.com
最后输出一个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) {.鏈枃鍘熷垱鑷1point3acres璁哄潧
        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)就可以了

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

使用道具 举报

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

对,维护的i和j是最长合法括号匹配的起始坐标和结尾坐标,. from: 1point3acres.com/bbs
leetcode原题不是只要输出int吗?这题要是要求输出最大长度的string. 鍥磋鎴戜滑@1point 3 acres
就每次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分别是多少?

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 | 显示全部楼层
woshixuyoudan 发表于 2016-2-27 12:03. 1point 3acres 璁哄潧
对呀 要输出()()()

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

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

使用道具 举报

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

請問樓主
原 leetcode 題輸出會是 ()(). From 1point 3acres bbs
所以跟原本 leetcode 題目不太一樣囉?
https://leetcode.com/problems/longest-valid-parentheses/. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
回复 支持 反对

使用道具 举报

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

恩恩..可能我没有仔细看leetcode的原题. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
你说的对 是不太一样 应该是这样

())()() -> ()()(). 1point3acres.com/bbs
()(()    -> ()()
)(        ->
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-7-26 09:04

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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