一亩三分地论坛

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

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

非死不可 9/16 面筋

[复制链接] |试试Instant~ |关注本帖
obama555 发表于 2016-9-17 03:39:43 | 显示全部楼层 |阅读模式

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

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

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

x
今天上午面了非死不可,口音挺标准的男人,说是internatinalization组的,上来先来个自我介绍接着就是做题
LC301 Remove Invalid Parentheses,我突然发现这个题我快把答案背下来了,兴奋地上来就写,刷刷写完了,然后小哥叫我给他解释,我解释了半天,能详细有多详细,但是小哥又说看不懂我的code,我还得一点一点讲解,结果一个题做了40分钟,都快末了了,小哥突然说这个题不需要你返回所有的结果,只要一个结果就行,然后我一下子就懵了,本来想重写,小哥说时间来不及了,就这样了。。。
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
面完整个人都不好了,有一股想撞墙的感觉,疯了,要死了,这种情况还能过吗?


补充内容 (2016-9-17 03:41):
感觉自己真要像公司名字一样,非死不可了

评分

4

查看全部评分

本帖被以下淘专辑推荐:

ilovexiao77 发表于 2016-9-17 03:57:47 | 显示全部楼层
看来需要确保在做题之前做好沟通工作啊。。。
帮楼主祈祷onsite
回复 支持 1 反对 0

使用道具 举报

alucardzhou 发表于 2016-9-17 23:20:28 | 显示全部楼层
为楼主祈福
回复 支持 反对

使用道具 举报

zhuhai_ZFC 发表于 2016-9-20 04:35:42 | 显示全部楼层
lz是不是面经没仔细看啊?面经里涉及到这道题90%都是返回一个结果啊。
回复 支持 反对

使用道具 举报

keepworkinghard 发表于 2016-9-20 04:44:27 | 显示全部楼层
lz是怎么拿到面试的呢。
您是明年5月毕业么。
回复 支持 反对

使用道具 举报

xiaoling99 发表于 2016-9-20 04:45:55 | 显示全部楼层
同为楼主祈福
回复 支持 反对

使用道具 举报

iPhD 发表于 2016-9-20 05:03:10 | 显示全部楼层
不能背题呀。。这题如果就返回一个结果的话,2-pass扫两遍就做出来了。。
回复 支持 反对

使用道具 举报

iPhD 发表于 2016-9-20 05:18:38 | 显示全部楼层
问下楼主FB用的什么编辑器电面呀?HackerRank? Collabedit?
回复 支持 反对

使用道具 举报

liurudahai 发表于 2016-9-28 11:56:59 | 显示全部楼层
这道题究竟怎么做?我看很多网上答案都是用bfs,为啥有些人说扫一遍就可以
回复 支持 反对

使用道具 举报

victorsterling 发表于 2016-9-29 02:53:19 | 显示全部楼层
liurudahai 发表于 2016-9-27 22:56
这道题究竟怎么做?我看很多网上答案都是用bfs,为啥有些人说扫一遍就可以

如果是返回所有结果的话,需要考虑所有的可能性,所以要用dfs 把所有的都找一遍。这种难度就属于难一些的。
. 1point3acres.com/bbs
如果只返回一个结果的话,就单纯remove不正确的括号就可以了,one pass就可以,这种难度就属于容易的一些,楼主应该是把简单的题想难了。
回复 支持 反对

使用道具 举报

kobe24 发表于 2016-9-29 03:22:06 | 显示全部楼层
victorsterling 发表于 2016-9-29 02:53. more info on 1point3acres.com
如果是返回所有结果的话,需要考虑所有的可能性,所以要用dfs 把所有的都找一遍。这种难度就属于难一些的 ...

one pass怎么做?能具体说说思路吗
回复 支持 反对

使用道具 举报

victorsterling 发表于 2016-9-29 04:48:49 | 显示全部楼层
kobe24 发表于 2016-9-28 14:22
one pass怎么做?能具体说说思路吗

写的有点麻烦,time complexity O(n), 感觉不是很efficient,在这里抛砖引玉一下
  1. public static String remove(String s) {
  2.                 StringBuilder sb = new StringBuilder();
  3.                 int cur = 0;
  4.                 LinkedList<Integer> list = new LinkedList<>();
  5.                 for (int i = 0; i < s.length(); i++) {
  6.                         if (s.charAt(i) == '(') {
  7.                                 cur++;
  8.                                 list.addLast(i);
  9.                         } else if (s.charAt(i) == ')') {
  10.                                 if (cur > 0) {
  11.                                         cur--;
  12.                                         list.removeLast();.1point3acres缃
  13.                                 }
  14.                         } . more info on 1point3acres.com
  15.                 }
  16.                 cur = 0;
  17.                
  18.                 if (!list.isEmpty()) {
  19.                         int del = list.removeFirst();
  20.                         for (int i = 0; i < s.length(); i++) {
  21.                                 if (i == del) {
  22.                                         if (!list.isEmpty()) {
  23.                                                 del = list.getFirst();
  24.                                         }
  25.                                         continue;. Waral 鍗氬鏈夋洿澶氭枃绔,
  26.                                 }
  27.                                 if (s.charAt(i) == '(') {
  28.                                         cur++;
  29.                                         sb.append(s.charAt(i));-google 1point3acres
  30.                                 } else if (s.charAt(i) == ')') {
  31.                                         if (cur > 0) {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  32.                                                 cur--;
  33.                                                 sb.append(s.charAt(i));.鐣欏璁哄潧-涓浜-涓夊垎鍦
  34.                                         }
  35.                                 } else {
  36.                                         sb.append(s.charAt(i));
  37.                                 }
  38.                         }
  39.                 } else {. more info on 1point3acres.com
  40.                         for (int i = 0; i < s.length(); i++) {
  41.                                 if (s.charAt(i) == '(') {
  42.                                         cur++;
  43.                                         sb.append(s.charAt(i));. From 1point 3acres bbs
  44.                                 } else if (s.charAt(i) == ')') {
  45.                                         if (cur > 0) {
  46.                                                 cur--;
  47.                                                 sb.append(s.charAt(i));
  48.                                         }
  49.                                 } else {
  50.                                         sb.append(s.charAt(i));
  51.                                 }
  52.                         }
  53.                 }
  54.                
  55.                 . 1point 3acres 璁哄潧
  56.                 return sb.toString();
  57.         }
复制代码
回复 支持 反对

使用道具 举报

wopani007 发表于 2016-10-2 14:51:10 | 显示全部楼层
victorsterling 发表于 2016-9-29 04:48
写的有点麻烦,time complexity O(n), 感觉不是很efficient,在这里抛砖引玉一下
. 鍥磋鎴戜滑@1point 3 acres
hi,感觉你去掉了多余的),但是没去掉多余的(

补充内容 (2016-10-2 14:51):
哦,说反了貌似。。。

补充内容 (2016-10-2 14:55):
不好意思看错了,你是对的不过可以从左和右各自遍历一遍。然后得到一个delete list好像更明显一点
回复 支持 反对

使用道具 举报

victorsterling 发表于 2016-10-2 21:37:49 | 显示全部楼层
wopani007 发表于 2016-10-2 01:51
hi,感觉你去掉了多余的),但是没去掉多余的(

补充内容 (2016-10-2 14:51):

对,我写的有点麻烦了,可以从左到右遍历一遍得到delete list, 然后再从右到左得到结果就好了
回复 支持 反对

使用道具 举报

samuelling 发表于 2016-10-3 01:05:23 | 显示全部楼层
/* package codechef; // don't place package name! */
. 1point 3acres 璁哄潧
import java.util.*;
import java.lang.*;. 1point3acres.com/bbs
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */. From 1point 3acres bbs
class Codechef
{
        public static void main (String[] args) throws java.lang.Exception
        {
                // your code goes here
                String res1 = removeInvalid("()())()");
                String res2 = removeInvalid("(a)())()");
                String res3 = removeInvalid(")(");
                . From 1point 3acres bbs
                System.out.println(res1 + " " + res2 + " " + res3);
        }. 1point 3acres 璁哄潧
       
        public static String removeInvalid(String str) {
            // check edge case. visit 1point3acres.com for more.
            if (str == null || str.length() == 0) {
                return str;
            }
            // preprocess
            Stack<Integer> stack = new Stack<Integer>();
            HashSet<Integer> set = new HashSet<Integer>();
            // main
            for (int i = 0; i < str.length(); i++) {
                char ch = str.charAt(i);
                if (ch == '(') {
                    stack.push(i);
                } else if (ch == ')') {. visit 1point3acres.com for more.
                    //case 1 . visit 1point3acres.com for more.
                    if (stack.isEmpty()) {
                        set.add(i);.1point3acres缃
                    } else {
                        stack.pop();
                    }
                }
            }.1point3acres缃
            while (!stack.isEmpty()) {
                set.add(stack.pop());
            } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
            // budao. Waral 鍗氬鏈夋洿澶氭枃绔,
            String result = "";
            for (int i = 0; i < str.length(); i++) {
                char ch = str.charAt(i);
                if (set.contains(i)) {
                    continue;
                }
                result += ch; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
            }
            return result;
        }
}
回复 支持 反对

使用道具 举报

kobe24 发表于 2016-10-3 03:14:33 | 显示全部楼层
samuelling 发表于 2016-10-3 01:05
/* package codechef; // don't place package name! */

import java.util.*;

first pass idea is similar to LC 20 -- valid parenthesis. and second pass is to remove the invalid parenthesis. easy-understanding solution.
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-10 21:40

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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