一亩三分地论坛

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

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

人生巅峰, FB 电面已跪, 新鲜面经奉上

[复制链接] |试试Instant~ |关注本帖
wy193777 发表于 2015-3-20 10:19:23 | 显示全部楼层 |阅读模式

2015(1-3月) 码农类 硕士 实习@Facebook - 内推 - 技术电面 |Fail

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

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

x
晚上刚刚面得, 因为周二有了Amazon的offer, 本来下周四, 催着变成这周四了. 完全没见过的新题,
Given a string with parentheses, return a string with balanced parentheses by removing the fewest characters possible. You cannot add anything to the string.

Examples:. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

balance("()") -> "()"
balance(")(") -> ""
balance("(((((") -> ""
balance("(()()(") -> "()()"
balance(")(())(") -> "(())"
balance(")(())(") != "()()"

就是删去string里面没有close的括号, 值留下close的括号

. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷


补充内容 (2015-3-20 10:21):
另外, 亚马逊最近好像又开始招实习了. 如果各位没有投过赶快投, 我周围另外两个哥们上网投也拿到电面了. 另外更正一下, 我也是直接在网页上投的, 没有内推.
. 1point3acres.com/bbs求加米. . 1point3acres.com/bbs

补充内容 (2015-3-20 10:25):
另外, Facebook最近有开始招实习了.....面完太激动.......

评分

5

查看全部评分

本帖被以下淘专辑推荐:

Justice 发表于 2015-4-6 23:31:46 | 显示全部楼层
从左往右扫,如果右括号个数多于左括号,删除。
再从右往左扫,左括号个数多于右括号,删除。
O(N)。
代码:

string solve(string s) {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
    int N = s.size();
    int i,j,k,L = 0,R = 0;
    for (i = 0;i < N;i++) {. 1point3acres.com/bbs
        if (s[i] == '(') L++;
        if (s[i] == ')') R++;
        if (R > L) {
            s[i] = '*';
            R--;. 1point3acres.com/bbs
        }
    }
    R = 0;
    L = 0;
    for (i = N - 1;i >= 0;i--) {
        if (s[i] == ')') R++;
        if (s[i] == '(') L++;
        if (L > R) {
            s[i] = '*';
            L--;
        }
    }
    string t = "";
    for (i = 0;i < N;i++) {
        if (s[i] != '*') t.push_back(s[i]);
    }
    return t;
}
回复 支持 7 反对 0

使用道具 举报

shawlin 发表于 2015-3-20 10:30:14 | 显示全部楼层
LZ FB没找人内推就拿店面了?投了多久有消息的啊
回复 支持 反对

使用道具 举报

 楼主| wy193777 发表于 2015-3-20 10:32:59 | 显示全部楼层
shawlin 发表于 2015-3-20 10:30
LZ FB没找人内推就拿店面了?投了多久有消息的啊
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
上周五投, 周六HR联系我, 让我再确定一下岗位. 周日我回复, 周一邮件安排到下周四, 周二接到亚马逊offer, 晚上发邮件希望提前, 周三早上回复提前到周四下午.
回复 支持 反对

使用道具 举报

 楼主| wy193777 发表于 2015-3-20 10:33:06 | 显示全部楼层
shawlin 发表于 2015-3-20 10:30. From 1point 3acres bbs
LZ FB没找人内推就拿店面了?投了多久有消息的啊

上周五投, 周六HR联系我, 让我再确定一下岗位. 周日我回复, 周一邮件安排到下周四, 周二接到亚马逊offer, 晚上发邮件希望提前, 周三早上回复提前到周四下午.
回复 支持 反对

使用道具 举报

asd55178608 发表于 2015-3-20 11:04:30 | 显示全部楼层
楼主能问下是直接去amazon job 上投得吗?
回复 支持 反对

使用道具 举报

 楼主| wy193777 发表于 2015-3-20 11:10:47 | 显示全部楼层
asd55178608 发表于 2015-3-20 11:04
楼主能问下是直接去amazon job 上投得吗?

amazon是内推的, facebook是网上投的.
回复 支持 反对

使用道具 举报

seabiscuit119 发表于 2015-3-20 11:26:27 | 显示全部楼层
how did lz solve this problem?
回复 支持 反对

使用道具 举报

yuxrose 发表于 2015-3-20 11:30:42 | 显示全部楼层
lz, 这题和Longest valid parentheses是不是有关系啊?
回复 支持 反对

使用道具 举报

 楼主| wy193777 发表于 2015-3-20 11:31:53 | 显示全部楼层
seabiscuit119 发表于 2015-3-20 11:26
how did lz solve this problem?

我没做出来. 不过目前的想法是把字符都加入链表, 然后根据情况删头删尾. 细节还没想好. 当时做的有明显bug.
回复 支持 反对

使用道具 举报

siren01 发表于 2015-3-20 13:48:47 | 显示全部楼层
leetcode上有类似的,就是找最长合法的parentheses, 用stack来做的,然后找到最长的合法后输出,复杂度O(n)
回复 支持 反对

使用道具 举报

Deckardmzr 发表于 2015-3-20 13:51:29 | 显示全部楼层
思路就是Longest valid parentheses,只是输出不同,亲测可行
回复 支持 反对

使用道具 举报

DQ总是重名 发表于 2015-3-20 14:20:45 | 显示全部楼层
Deckardmzr 发表于 2015-3-20 13:51
思路就是Longest valid parentheses,只是输出不同,亲测可行
. From 1point 3acres bbs
求看代码~
回复 支持 反对

使用道具 举报

干.什么 发表于 2015-3-20 21:46:03 | 显示全部楼层
  1. public class BalanceUnbalancedParentheses {
  2.     public static String balance(String str) {
  3.         if (str == null || str.length() == 0) return "";. more info on 1point3acres.com
  4.         Stack<Integer> stack = new Stack<Integer>();. Waral 鍗氬鏈夋洿澶氭枃绔,
  5.         int start = -1, end = -1;
  6.         for (int i = 0; i < str.length(); i++) {
  7.             char c = str.charAt(i);
  8.             if (c == '(') {
  9.                 stack.push(i);
  10.             } else if (c == ')') {
  11.                 if (!stack.isEmpty() && str.charAt(stack.peek()) == '(') {
  12.                     start = stack.pop();. more info on 1point3acres.com
  13.                     end = i;
  14.                 }
  15.             }
  16.         }
  17.         return (start == -1 || end == -1) ? "" : str.substring(start, end + 1);. more info on 1point3acres.com
  18.     }

  19.     public static void main(String[] args) {.1point3acres缃
  20.         BalanceUnbalancedParentheses sol = new BalanceUnbalancedParentheses();. 1point3acres.com/bbs
  21.         System.out.println(sol.balance(")()"));. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  22.         System.out.println(sol.balance(")(())("));. Waral 鍗氬鏈夋洿澶氭枃绔,
  23.         System.out.println(sol.balance("()")); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  24.         System.out.println(sol.balance("(((((("));
  25.         System.out.println(sol.balance(")("));
  26.     }
  27. }
复制代码
回复 支持 反对

使用道具 举报

Deckardmzr 发表于 2015-3-20 23:47:55 | 显示全部楼层
. 鍥磋鎴戜滑@1point 3 acres
转专业小白,代码比较丑,也是借鉴了大神的思路
  1. public static String balance(String s) {
  2.             if(s==null || s.length()==0)
  3.                 return "";.1point3acres缃
  4.             LinkedList<Integer> stack = new LinkedList<Integer>();
  5.             int start = 0;
  6.             StringBuilder res = new StringBuilder();. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  7.             String tmp = "";
  8.             for(int i=0;i<s.length();i++)
  9.             {
  10.                 if(s.charAt(i)=='(')
  11.                 {
  12.                     stack.push(i);
  13.                 }
  14.                 else
  15.                 {
  16.                     if(stack.isEmpty())
  17.                     {
  18.                         start = i+1;
  19.                     }.鏈枃鍘熷垱鑷1point3acres璁哄潧
  20.                     else
  21.                     {
  22.                         stack.pop();
  23.                         -google 1point3acres
  24.                         if(stack.isEmpty())
  25.                         {. 鍥磋鎴戜滑@1point 3 acres
  26.                                 res.append(s.substring(start, i+1));
  27.                                 tmp = "";. Waral 鍗氬鏈夋洿澶氭枃绔,
  28.                         }
  29.                         else
  30.                         {
  31.                                 tmp = s.substring(stack.peek()+1, i+1);
  32.                         }
  33.                         . visit 1point3acres.com for more.
  34.                     }
  35.                 }
  36.             }. From 1point 3acres bbs
  37.             res.append(tmp);. 1point 3acres 璁哄潧
  38.             return res.toString();
  39.         }
复制代码
回复 支持 反对

使用道具 举报

Deckardmzr 发表于 2015-3-20 23:49:22 | 显示全部楼层

这样好像过不了"()(()" 这样不连在一起的case吧
回复 支持 反对

使用道具 举报

averillzheng 发表于 2015-3-20 23:55:54 | 显示全部楼层
这不应该跪呀。用stack一个一个char读。遇到不匹配就pop,多么的容易呀。
回复 支持 反对

使用道具 举报

lucaz 发表于 2015-3-21 00:21:35 来自手机 | 显示全部楼层

. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴不应该是遇到匹配就pop吗
来自: iPhone客户端
回复 支持 反对

使用道具 举报

干.什么 发表于 2015-3-21 01:14:22 | 显示全部楼层
Deckardmzr 发表于 2015-3-20 23:49
这样好像过不了"()(()" 这样不连在一起的case吧
. 1point 3acres 璁哄潧
是,没考虑这种情况,我修改了一下代码,多谢~
  1. public class BalanceUnbalancedParentheses {.鏈枃鍘熷垱鑷1point3acres璁哄潧
  2.     public static String balance(String str) {
  3.         if (str == null || str.length() == 0) return "";
  4.         Stack<Integer> stack = new Stack<Integer>();
  5.         int top = 0, prev = 0;
  6.         String res = "";. visit 1point3acres.com for more.
  7.         for (int i = 0; i < str.length(); i++) {
  8.             char c = str.charAt(i);
  9.             if (c == '(') {
  10.                 stack.push(i);
  11.             } else if (c == ')') {. more info on 1point3acres.com
  12.                 if (stack.isEmpty()) {
  13.                     top = 0;
  14.                 } else {. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  15.                     top = stack.pop();
  16.                     if (top > prev) {
  17.                         res += str.substring(top, i + 1);
  18.                     } else {. 1point 3acres 璁哄潧
  19.                         res = str.substring(top, i + 1);.鐣欏璁哄潧-涓浜-涓夊垎鍦
  20.                     }
  21.                     prev = top;
  22.                 }
  23.             }
  24.         }
  25.         return res;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  26.     }
  27. 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  28.     public static void main(String[] args) {
  29.         BalanceUnbalancedParentheses sol = new BalanceUnbalancedParentheses();
  30.         System.out.println(sol.balance(")()"));
  31.         System.out.println(sol.balance(")(())("));
  32.         System.out.println(sol.balance("()"));
  33.         System.out.println(sol.balance("(((((("));
  34.         System.out.println(sol.balance(")("));. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  35.         System.out.println(sol.balance("())()"));
  36.         System.out.println(sol.balance("())())))()()"));
  37.     }
  38. }
复制代码
回复 支持 反对

使用道具 举报

干.什么 发表于 2015-3-21 01:17:17 | 显示全部楼层
averillzheng 发表于 2015-3-20 23:55
这不应该跪呀。用stack一个一个char读。遇到不匹配就pop,多么的容易呀。
. 1point3acres.com/bbs
没有太明白你的意思,我感觉不是那么容易,因为题目中有要求说:

Remove the fewest characters possible.
. 1point3acres.com/bbs
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
所以每次遇到匹配的括号是要考虑是追加还是替换
回复 支持 反对

使用道具 举报

pyemma 发表于 2015-3-21 01:35:21 | 显示全部楼层
找出所有的最长匹配括号然后拼接在一起?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-10 10:59

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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