传说中的谷歌招聘委员会成员之一,从幕后走出来,教你学系统设计!


一亩三分地论坛

 找回密码
 获取更多干活,快来注册
天天打游戏、照样领工资、还办H1B
这份工作你要不要?
把贵司招聘信息放这里
查看: 3589|回复: 15
收起左侧

非死不可 9/16 面筋

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

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

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

x
今天上午面了非死不可,口音挺标准的男人,说是internatinalization组的,上来先来个自我介绍接着就是做题
LC301 Remove Invalid Parentheses,我突然发现这个题我快把答案背下来了,兴奋地上来就写,刷刷写完了,然后小哥叫我给他解释,我解释了半天,能详细有多详细,但是小哥又说看不懂我的code,我还得一点一点讲解,结果一个题做了40分钟,都快末了了,小哥突然说这个题不需要你返回所有的结果,只要一个结果就行,然后我一下子就懵了,本来想重写,小哥说时间来不及了,就这样了。。。.1point3acres缃

面完整个人都不好了,有一股想撞墙的感觉,疯了,要死了,这种情况还能过吗?


补充内容 (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,为啥有些人说扫一遍就可以
. From 1point 3acres bbs
如果是返回所有结果的话,需要考虑所有的可能性,所以要用dfs 把所有的都找一遍。这种难度就属于难一些的。. visit 1point3acres.com for more.

如果只返回一个结果的话,就单纯remove不正确的括号就可以了,one pass就可以,这种难度就属于容易的一些,楼主应该是把简单的题想难了。
回复 支持 反对

使用道具 举报

kobe24 发表于 2016-9-29 03:22:06 | 显示全部楼层
victorsterling 发表于 2016-9-29 02:53
如果是返回所有结果的话,需要考虑所有的可能性,所以要用dfs 把所有的都找一遍。这种难度就属于难一些的 ...
.鏈枃鍘熷垱鑷1point3acres璁哄潧
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();
  13.                                 }
  14.                         }
  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;
  26.                                 }. Waral 鍗氬鏈夋洿澶氭枃绔,
  27.                                 if (s.charAt(i) == '(') {
  28.                                         cur++;
  29.                                         sb.append(s.charAt(i));
  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 {. visit 1point3acres.com for more.
  40.                         for (int i = 0; i < s.length(); i++) {
  41.                                 if (s.charAt(i) == '(') {. From 1point 3acres bbs
  42.                                         cur++;
  43.                                         sb.append(s.charAt(i));
  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.                
  56.                 return sb.toString();
  57.         }
复制代码
回复 支持 反对

使用道具 举报

wopani007 发表于 2016-10-2 14:51:10 | 显示全部楼层
victorsterling 发表于 2016-9-29 04:48
写的有点麻烦,time complexity O(n), 感觉不是很efficient,在这里抛砖引玉一下
. Waral 鍗氬鏈夋洿澶氭枃绔,
hi,感觉你去掉了多余的),但是没去掉多余的(. Waral 鍗氬鏈夋洿澶氭枃绔,

补充内容 (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.1point3acres缃
hi,感觉你去掉了多余的),但是没去掉多余的(. more info on 1point3acres.com

补充内容 (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.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */. visit 1point3acres.com for more.
class Codechef. 1point 3acres 璁哄潧
{
        public static void main (String[] args) throws java.lang.Exception
        {
                // your code goes here
                String res1 = removeInvalid("()())()");
                String res2 = removeInvalid("(a)())()");
                String res3 = removeInvalid(")(");
                .鏈枃鍘熷垱鑷1point3acres璁哄潧
                System.out.println(res1 + " " + res2 + " " + res3);
        }
       
        public static String removeInvalid(String str) {
            // check edge case
            if (str == null || str.length() == 0) {
                return str;. more info on 1point3acres.com
            }
            // 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);-google 1point3acres
                if (ch == '(') {
                    stack.push(i);
                } else if (ch == ')') {
                    //case 1 . visit 1point3acres.com for more.
                    if (stack.isEmpty()) {
                        set.add(i);
                    } else {
                        stack.pop();
                    }
                }
            }
            while (!stack.isEmpty()) {
                set.add(stack.pop());
            }. 1point3acres.com/bbs
            // budao
            String result = "";. from: 1point3acres.com/bbs
            for (int i = 0; i < str.length(); i++) {
                char ch = str.charAt(i);
                if (set.contains(i)) {
                    continue;
                }. more info on 1point3acres.com
                result += ch;
            }
            return result;
        } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
}
回复 支持 反对

使用道具 举报

kobe24 发表于 2016-10-3 03:14:33 | 显示全部楼层
samuelling 发表于 2016-10-3 01:05. 1point 3acres 璁哄潧
/* 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.
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-9-26 04:52

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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