一亩三分地

 找回密码 注册账号

扫描二维码登录本站

微信公众号
扫码关注公众号
留学申请号
扫码关注留学申请公众号
查看: 12492|回复: 24
收起左侧

[facebook]第一轮技术电面

[复制链接] |只看干货 |美国面经, 码农类general, facebook, 面试经验
我的人缘0

升级   1%


分享帖子到朋友圈
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (42)
 
 
0% (0)    👎

2016(4-6月) 码农类General 硕士 全职@Facebook - 内推 - 技术电面  | Other | fresh grad应届毕业生

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

您需要 登录 才可以下载或查看,没有帐号?注册账号

x
今天面了一个半星期前约的电面,国人小哥面的,题目不是很难,两道题各写一个函数,statement如下:

1. merge two arrays in-place
例子:
a = [2,4,6,8, _, _, _, _]
b = [1,3,5,7]

Note:_代表空的位置,用以merge。a的actual length与b一样,并且a的空余位置足够放入b。a, b都是sorted array,要求in-place merge两个array。
感受:题目条件明确,简单思路就是从两个数列的尾部(这个例子中对于a是从8开始)比较,哪个更大就放在a的末端。需要注意到当a被遍历完后,要将b剩下的数字照搬到a的前端。

2. balance parentheses in a string
例子:
"(a)()" -> "(a)()"
"((bc)" -> "(bc)"
")))a((" -> "a"
"(a(b)" ->"(ab)" or "a(b)"

Note: balance的意思就是把原来string里unpaired的括号变成paired的形式。如果有多个可能的结果, 比如上述最后一种情况,我们就只需要输出一个对的结果即可,所以这点简化了题目的难度。
感受: 遍历string, 用一个stack存储每个open parenthesis的index,也就是'('的i
游客,本帖隐藏的内容需要积分高于 188 才可浏览,您当前积分为 0。
查看如何攒积分 Click here for more info.
4.gif" smilieid="112" border="0" alt="" />然后我觉得我的解法也行的通,所以跟他说了下,他也表示认同,但需要回去检验下。欢迎大家参与讨论!

就是这样。

希望进入下一轮吧,顺便求点大米!

评分

参与人数 8大米 +142 收起 理由
dundun1990 + 1 很有用的信息!
Aaron_Liu + 3 感谢分享!
lefthook + 3 很有用的信息!
stephaniede + 5 感谢分享!
xiaozhuxiaozhu + 10 感谢分享!
laonawuli + 10 感谢分享!
whdawn + 50
candy_shmily + 60

查看全部评分


上一篇:好伤心,但是很不知道为什么一直被rej
下一篇:Amazon 电面当时hackerrank coding?
我的人缘0

升级   6.67%

本楼: 👍   100% (7)
 
 
0% (0)   👎
全局: 👍   95% (39)
 
 
4% (2)    👎
不用stack, 使用 counter 记录违规的括号, 两个loop, 第一个从左到右删')', 第二个从右到左删'('

public class Solution {
    public List<String> removeInvalidParentheses(String s) {
        s = delR(s);
        s = delL(s);
        return s;
    }
   
    private String delR(String s) {
        StringBuilder sb= new StringBuilder();
        for (char c : s.toCharArray()) {
            sb.append(c);
            if (c == '(') {
                l++;
            } else if (c == ')') {
                if (l > 0) l--;
                else {
                    sb.deleteCharAt(sb.length() - 1);
                }
            }
        }
        return sb.toString();
    }
   
   
    private String delL(String s) {
        StringBuilder sb= new StringBuilder();
        for (int i = s.length()-1; i >= 0; i--) {
            char c = s.charAt(i);
            sb.insert(0,c);
            if (c == ')') {
                l++;
            } else if (c == '(') {
                if (l > 0) l--;
                else sb.deleteCharAt(0);
            }
        }
        return sb.toString();
    }
}

评分

参与人数 1大米 +10 收起 理由
laonawuli + 10 感谢分享!

查看全部评分

回复

使用道具 举报

我的人缘0

升级   37.5%

本楼: 👍   100% (2)
 
 
0% (0)   👎
全局: 👍   89% (82)
 
 
10% (10)    👎
spoonfree 发表于 2016-6-3 03:57
恩,我这里表述得不是很清楚,把unpaired的括号变成paired的形式指 维持原来已经配对的括号, 解决掉那些 ...

稍微想了一下space O(1), one pass的做法:
用一个int来维护,遇到左括号+1, 右括号-1, <0就直接去掉当前右括号,最后结果>0就往后补齐右括号。
回复

使用道具 举报

我的人缘0

升级   0.25%

本楼: 👍   100% (1)
 
 
0% (0)   👎
全局: 👍   99% (175)
 
 
0% (1)    👎
mdyuki1016 发表于 2016-6-7 18:47
不用stack, 使用 counter 记录违规的括号, 两个loop, 第一个从左到右删')', 第二个从右到左删'('

public ...

不错不错。其实可以不用insert(0, c). 直接最后sb.reverse().toString() 就好了。
回复

使用道具 举报

我的人缘0

升级   37.5%

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   89% (82)
 
 
10% (10)    👎
“balance的意思就是把原来string里unpaired的括号变成paired的形式。”

那为什么:")))a((" -> "a" 而不是 ”((()))a(())“ ? 否则的话所有testcase直接去掉所有括号就成立了。。
回复

使用道具 举报

我的人缘0

升级   1%

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (42)
 
 
0% (0)    👎
Wingszero 发表于 2016-6-3 03:19
“balance的意思就是把原来string里unpaired的括号变成paired的形式。”

那为什么:")))a((" -> "a" 而 ...

恩,我这里表述得不是很清楚,把unpaired的括号变成paired的形式指 维持原来已经配对的括号, 解决掉那些未配对的括号。至于你怎么解决,是删除冗余括号还是添加括号,自己选择。当时面试官给我的例子,看上去是删除,所以我就默认是删除了。把括号都删除,这题就没意思了呀!
回复

使用道具 举报

我的人缘0

升级   1%

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (42)
 
 
0% (0)    👎
有没有版主支持新人一记大米?
回复

使用道具 举报

我的人缘0

升级   93.33%

本楼: 👍   100% (1)
 
 
0% (0)   👎
全局: 👍   100% (8)
 
 
0% (0)    👎
第二题是不是类似lc 301 Remove invalid parentheses?
回复

使用道具 举报

我的人缘0

升级   83.75%

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (11)
 
 
0% (0)    👎
用两个变量代替stack中的括号数?
回复

使用道具 举报

我的人缘0

升级   37.5%

本楼: 👍   100% (1)
 
 
0% (0)   👎
全局: 👍   89% (82)
 
 
10% (10)    👎
Nirvason 发表于 2016-6-3 04:20
第二题是不是类似lc 301 Remove invalid parentheses?

蛮不一样,LC这道只减不增,最短,并返回所有情况。
回复

使用道具 举报

我的人缘0

升级   1%

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (42)
 
 
0% (0)    👎
Nirvason 发表于 2016-6-3 04:20
第二题是不是类似lc 301 Remove invalid parentheses?

这题只用找出一种可能解就好,所以复杂度没lc 301高。
回复

使用道具 举报

我的人缘0

升级   1%

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (42)
 
 
0% (0)    👎
我按照只有删除括号的操作重写了下代码
  1. public class balance {
  2.         String solution (String string) {
  3.                 int countOpen = 0, countClose = 0;
  4.                 char[] str =  string.toCharArray();
  5.                 StringBuilder res = new StringBuilder();
  6.                
  7.                 int i = 0, j = str.length - 1;
  8.                
  9.                 while(i < j) {
  10.                         if(str[i] == '(') {
  11.                                         countOpen++;
  12.                                 }
  13.                         else if(str[i] == ')') {
  14.                                         if(countOpen == 0) str[i] = '#';
  15.                                         else countOpen--;
  16.                                 }


  17.                         if(countClose >= 0) {
  18.                                 if(str[j] == ')') {
  19.                                         countClose++;
  20.                                 }
  21.                                 else if(str[j] == '(') {
  22.                                         if(countClose == 0) str[j] = '#';
  23.                                         else countClose--;
  24.                                 }
  25.                         }
  26.                         i++;
  27.                         j--;
  28.                        
  29.                 }
  30.                 if(i == j) {
  31.                         if(str[i] == '(') countOpen++;
  32.                         if(str[j] == ')') countClose++;
  33.                 }
  34.                
  35.                 if(countOpen > countClose) {
  36.                         int count = countOpen - countClose;
  37.                         while(count > 0) {
  38.                                 if(str[i] == '(') {
  39.                                         str[i] = '#';
  40.                                         count--;
  41.                                 }
  42.                                 i--;
  43.                         }
  44.                 }
  45.                 else {
  46.                         int count = countClose - countOpen;
  47.                         while(count > 0) {
  48.                                 if(str[j] == ')') {
  49.                                         str[j] = '#';
  50.                                         count--;
  51.                                 }
  52.                                 j++;
  53.                         }
  54.                 }
  55.                
  56.                 for(i = 0; i < str.length; i++) {
  57.                         if(str[i] != '#') {
  58.                                 res.append(str[i]);
  59.                         }
  60.                 }
  61.                
  62.                 return res.toString();
  63.         }
  64. }
复制代码


我发给面试我的小哥看了下,他人很nice的帮我看了下,然后分享了一个更好的思路。我也分享给大家以供参考。

I've read through your final code and it appears to be working - I haven't found a counter example yet. A much cleaner way to do this is do 2 rounds of scans with a counter on open parens first and one with a counter on close parens. The first scan finds all unmatched close parens and the second one finds all unmatched open parens (similar to what you did in your loop). This way you don't have to handle the case when two pointers meet.
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

隐私提醒:
■拉群请前往同学同事飞友|拉群结伴版块,其他版块拉群,帖子会被自动删除
■论坛不能删帖,为防止被骚扰甚至人肉,不要公开留微信等联系方式,请以论坛私信方式发送。
■特定版块可以超级匿名:https://tools.1point3acres.com/thread
■其他版块匿名方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

手机版|||一亩三分地

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

Some icons made by Freepik from flaticon.com

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