San Jose各个房价 <1.5m 区域买房总结

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
把贵司招聘信息放这里
查看: 4181|回复: 15
收起左侧

非死不可 9/16 面筋

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

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

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

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

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

面完整个人都不好了,有一股想撞墙的感觉,疯了,要死了,这种情况还能过吗?. 围观我们@1point 3 acres


补充内容 (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?
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

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

使用道具 举报

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

如果是返回所有结果的话,需要考虑所有的可能性,所以要用dfs 把所有的都找一遍。这种难度就属于难一些的。

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

使用道具 举报

kobe24 发表于 2016-9-29 03:22:06 | 显示全部楼层
victorsterling 发表于 2016-9-29 02:53
如果是返回所有结果的话,需要考虑所有的可能性,所以要用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();
  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.                                 }
  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));. 围观我们@1point 3 acres
  37.                                 }
  38.                         }
  39.                 } else {
  40.                         for (int i = 0; i < s.length(); i++) {
  41.                                 if (s.charAt(i) == '(') {.留学论坛-一亩-三分地
  42.                                         cur++;
  43.                                         sb.append(s.charAt(i));. Waral 博客有更多文章,
  44.                                 } else if (s.charAt(i) == ')') {
  45.                                         if (cur > 0) {
  46.                                                 cur--;
  47.                                                 sb.append(s.charAt(i));
  48.                                         }
  49.                                 } else {. 1point 3acres 论坛
  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,在这里抛砖引玉一下
. 1point 3acres 论坛
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.本文原创自1point3acres论坛
hi,感觉你去掉了多余的),但是没去掉多余的(
. more info on 1point3acres
补充内容 (2016-10-2 14:51):

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

使用道具 举报

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

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Codechef. 1point 3acres 论坛
{. from: 1point3acres
        public static void main (String[] args) throws java.lang.Exception
        {
                // your code goes here
                String res1 = removeInvalid("()())()");
                String res2 = removeInvalid("(a)())()");. 一亩-三分-地,独家发布
                String res3 = removeInvalid(")(");
                .留学论坛-一亩-三分地
                System.out.println(res1 + " " + res2 + " " + res3);
        }
       
        public static String removeInvalid(String str) {
            // check edge case
            if (str == null || str.length() == 0) {
                return str;
            }
            // preprocess. 1point 3acres 论坛
            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 == ')') {
                    //case 1
                    if (stack.isEmpty()) {
                        set.add(i);
                    } else {
                        stack.pop();
                    }. Waral 博客有更多文章,
                }
            }
            while (!stack.isEmpty()) {
                set.add(stack.pop());
            }
            // budao
            String result = "";
            for (int i = 0; i < str.length(); i++) {
                char ch = str.charAt(i);
                if (set.contains(i)) {
                    continue;.1point3acres网
                }.留学论坛-一亩-三分地
                result += ch;
            }. visit 1point3acres for more.
            return result;
        }
}
回复 支持 反对

使用道具 举报

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

使用道具 举报

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

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

custom counter

GMT+8, 2018-5-26 20:49

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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