一亩三分地论坛

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

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

[facebook]第一轮技术电面

[复制链接] |试试Instant~ |关注本帖
spoonfree 发表于 2016-6-3 02:57:28 | 显示全部楼层 |阅读模式

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

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

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

x
今天面了一个半星期前约的电面,国人小哥面的,题目不是很难,两道题各写一个函数,statement如下:-google 1point3acres
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
1. merge two arrays in-place
. 1point3acres.com/bbs例子:
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,也就是'('的index, 每当遇到closed parenthesis就执行一次pop操作。
注意两种unbalanced的情况:
1. 出现多余的')':
    对应情况就是stack为空,但遇到了一个')'。. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
2. 出现多余的'(':
    对应情况就是遍历结束,stack未空

解决这两种情况即可。
对于java,我们需要把string转换成char array来做,因为在java中string is immutable.

follow-up:
Q:分析复杂度,问怎么不用stack来做?.1point3acres缃
A:想了一会儿,感觉用two-pointer可行,一个指头, 一个指尾, 头index找'(', 找到就移动尾index找')'。面试官虽然没说,但一开始反应有点惊讶,说明他头脑里准备的是另一个解法。这里就请各位大神不吝赐教了,你们的解法是什么然后我觉得我的解法也行的通,所以跟他说了下,他也表示认同,但需要回去检验下。欢迎大家参与讨论!

就是这样。

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

评分

7

查看全部评分

mdyuki1016 发表于 2016-6-8 10:47:30 | 显示全部楼层
不用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();. From 1point 3acres bbs
        for (char c : s.toCharArray()) {.1point3acres缃
            sb.append(c);
            if (c == '(') {
                l++;
            } else if (c == ')') {. more info on 1point3acres.com
                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--) {. 1point 3acres 璁哄潧
            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

查看全部评分

回复 支持 2 反对 0

使用道具 举报

Wingszero 发表于 2016-6-3 05:44:10 | 显示全部楼层
spoonfree 发表于 2016-6-3 03:57
恩,我这里表述得不是很清楚,把unpaired的括号变成paired的形式指 维持原来已经配对的括号, 解决掉那些 ...

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

使用道具 举报

laonawuli 发表于 2016-6-8 13:27:30 | 显示全部楼层
mdyuki1016 发表于 2016-6-7 18:47
不用stack, 使用 counter 记录违规的括号, 两个loop, 第一个从左到右删')', 第二个从右到左删'('

public ...
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
不错不错。其实可以不用insert(0, c). 直接最后sb.reverse().toString() 就好了。
回复 支持 1 反对 0

使用道具 举报

Nirvason 发表于 2016-6-3 04:20:10 | 显示全部楼层
第二题是不是类似lc 301 Remove invalid parentheses?
回复 支持 1 反对 0

使用道具 举报

Wingszero 发表于 2016-6-3 03:19:10 | 显示全部楼层
“balance的意思就是把原来string里unpaired的括号变成paired的形式。”

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

使用道具 举报

 楼主| spoonfree 发表于 2016-6-3 03:57:07 | 显示全部楼层
Wingszero 发表于 2016-6-3 03:19
“balance的意思就是把原来string里unpaired的括号变成paired的形式。”

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

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

使用道具 举报

 楼主| spoonfree 发表于 2016-6-3 03:58:37 | 显示全部楼层
有没有版主支持新人一记大米?
回复 支持 反对

使用道具 举报

dajiang 发表于 2016-6-3 05:43:56 | 显示全部楼层
用两个变量代替stack中的括号数?
回复 支持 反对

使用道具 举报

Wingszero 发表于 2016-6-3 05:46:17 | 显示全部楼层
Nirvason 发表于 2016-6-3 04:20
第二题是不是类似lc 301 Remove invalid parentheses?
-google 1point3acres
蛮不一样,LC这道只减不增,最短,并返回所有情况。
回复 支持 反对

使用道具 举报

 楼主| spoonfree 发表于 2016-6-3 09:25:21 | 显示全部楼层
Nirvason 发表于 2016-6-3 04:20
第二题是不是类似lc 301 Remove invalid parentheses?
.鏈枃鍘熷垱鑷1point3acres璁哄潧
这题只用找出一种可能解就好,所以复杂度没lc 301高。
回复 支持 反对

使用道具 举报

 楼主| spoonfree 发表于 2016-6-3 09:36:50 | 显示全部楼层
我按照只有删除括号的操作重写了下代码
  1. public class balance {
  2.         String solution (String string) {.鏈枃鍘熷垱鑷1point3acres璁哄潧
  3.                 int countOpen = 0, countClose = 0;
  4.                 char[] str =  string.toCharArray();. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  5.                 StringBuilder res = new StringBuilder();
  6.                 .鏈枃鍘熷垱鑷1point3acres璁哄潧
  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] == ')') {.1point3acres缃
  14.                                         if(countOpen == 0) str[i] = '#';. 1point3acres.com/bbs
  15.                                         else countOpen--;
  16.                                 }
  17. . 鍥磋鎴戜滑@1point 3 acres

  18.                         if(countClose >= 0) {. visit 1point3acres.com for more.
  19.                                 if(str[j] == ')') {
  20.                                         countClose++;
  21.                                 }
  22.                                 else if(str[j] == '(') {
  23.                                         if(countClose == 0) str[j] = '#';
  24.                                         else countClose--;
  25.                                 }
  26.                         }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  27.                         i++;
  28.                         j--;
  29.                        
  30.                 }
  31.                 if(i == j) {
  32.                         if(str[i] == '(') countOpen++;
  33.                         if(str[j] == ')') countClose++;
  34.                 }.1point3acres缃
  35.                
  36.                 if(countOpen > countClose) {. From 1point 3acres bbs
  37.                         int count = countOpen - countClose;
  38.                         while(count > 0) {
  39.                                 if(str[i] == '(') {
  40.                                         str[i] = '#';
  41.                                         count--;.1point3acres缃
  42.                                 }
  43.                                 i--;
  44.                         }
  45.                 }
  46.                 else {. more info on 1point3acres.com
  47.                         int count = countClose - countOpen;.1point3acres缃
  48.                         while(count > 0) {
  49.                                 if(str[j] == ')') {
  50.                                         str[j] = '#';
  51.                                         count--;
  52.                                 }
  53.                                 j++;
  54.                         }
  55.                 }
  56.                
  57.                 for(i = 0; i < str.length; i++) {
  58.                         if(str[i] != '#') {. from: 1point3acres.com/bbs
  59.                                 res.append(str[i]);
  60.                         }
  61.                 }
  62.                
  63.                 return res.toString();. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  64.         }
  65. }
复制代码

. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
我发给面试我的小哥看了下,他人很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.. from: 1point3acres.com/bbs
回复 支持 反对

使用道具 举报

duduhaha 发表于 2016-6-3 10:29:59 | 显示全部楼层
面试官那个思路很好,我写了个代码如下:

string getValidString(const string s) {
  int left = 0, right = 0;
  string temp, result;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  
  for (auto c : s) {. from: 1point3acres.com/bbs
    if (c == '(') {
      left++;
      temp.push_back(c);
    } else if (c == ')') {
      if (left > 0) {
        left--;
        temp.push_back(c);
      }
    } else
      temp.push_back(c);
  }. 1point3acres.com/bbs
  
  for (int i = temp.size() - 1; i >= 0; i--)
    if (temp[i] == ')') {
      right++;
      result.push_back(')');
    } else if (temp[i] == '(') {. more info on 1point3acres.com
      if (right > 0) {
        right--;
        result.push_back('(');
      }.鐣欏璁哄潧-涓浜-涓夊垎鍦
    } else. more info on 1point3acres.com
      result.push_back(temp[i]);.鏈枃鍘熷垱鑷1point3acres璁哄潧
  
   reverse(result.begin(), result.end());
  
  return result;
}

评分

4

查看全部评分

回复 支持 反对

使用道具 举报

houqingniao 发表于 2016-6-3 12:14:53 | 显示全部楼层
为啥不用stack?
回复 支持 反对

使用道具 举报

poormm 发表于 2016-6-7 07:17:24 | 显示全部楼层
楼主过了么
回复 支持 反对

使用道具 举报

997562971@qq.co 发表于 2016-8-1 12:22:40 | 显示全部楼层
这题问的有点漏洞。如果随便返回一个结果。那我直接把‘)’和‘(’都去掉就完了。
所以,我猜面试官一定是要求任意一个最佳解。
我觉得。用个int记录‘(’的数量减去‘)’的数量。从头到尾撸一遍,遇到数量等于0,并且')'的情况,直接跳过,否则加入答案。就完了。。
回复 支持 反对

使用道具 举报

dimi 发表于 2016-8-22 13:04:10 | 显示全部楼层
很详细 蛮不错的。感谢楼主。
回复 支持 反对

使用道具 举报

stephaniede 发表于 2016-8-25 02:39:57 | 显示全部楼层
mdyuki1016 发表于 2016-6-7 19:47. 1point 3acres 璁哄潧
不用stack, 使用 counter 记录违规的括号, 两个loop, 第一个从左到右删')', 第二个从右到左删'('. 鍥磋鎴戜滑@1point 3 acres
.鐣欏璁哄潧-涓浜-涓夊垎鍦
public ...

l定义成delR和delL里面的local变量?
回复 支持 反对

使用道具 举报

cicean 发表于 2016-9-5 13:41:57 | 显示全部楼层
spoonfree 发表于 2016-6-3 09:36. more info on 1point3acres.com
我按照只有删除括号的操作重写了下代码

"  return res.toString();"
res.toString, print 出来 这个个string是个乱码
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-4 20:50

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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