谈谈使用过的几款咖啡机

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货

最近看过此主题的会员

H1B/绿卡遥遥无期
又不想回国
来东南亚最大的互联网集团工作?
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
查看: 1831|回复: 35
收起左侧

非死不可店面跪经

[复制链接] |试试Instant~ |关注本帖
我的人缘0
qjdehouse 发表于 2018-2-24 06:33:07 | 显示全部楼层 |阅读模式
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】

2018(1-3月) 码农类General 硕士 全职@Facebook - 内推 - 技术电面  | Fail | fresh grad应届毕业生

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

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

x
2.13 做完的电面,刚刚收到消息说not moving forward了。。。

题目是一道hard题,leetcode 10改。给一个regression expression,问在另一个string里面有没有和他匹配的substring。面之前我刚刚看过这一题,还以为撞了大运。。。没想到。。。哎。 我的回答是把string里的每个可能的substring拿出来比较是不是match,发现有的话就返回true。具体比较的思路讲了很久,用二维dp做的。很紧张,吭哧吭哧的写完代码之后,面试官好像还是有点confused,又给他解释了一遍之后,他问时间复杂度,然后问怎么优化,我想了一会儿把时间复杂度从n^4优化到了n^3,然后没时间写了。十天后收到了拒信。面试官应该是白人,面试过程中他比较冷淡,我几乎没有停止讲话,很多次中途试图跟他交流,发现他回复的也很慢,不知什么情况。最后的问问题环节,我感觉他也是想匆匆结束。。。. more info on 1point3acres

本来觉得很有希望的,哎。。。期待落空,拒信连连的滋味真不好受。。。也不知道问题出在了哪里,应该还是自己能力不够,经验不足吧

评分

参与人数 1大米 +3 收起 理由
yiliaobailiao + 3 给你点个赞!

查看全部评分


上一篇:Google OA
下一篇:lyft phone + onsite
我的人缘0
莲藕熊软软 发表于 2018-2-24 08:48:08 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
只是看所有subarray,中间和LC一样做dp,match了就return,是不是O(n^3)啊?
input是s和p, p是pattern的话,.1point3acres网
在原本LC题的两层循环外面再套一层循环s的每一位,相当于把每一位设为substring的起始点
. visit 1point3acres for more.大概意思就是

for(int i = 0; i < s.length(); i++){
         初始化一个新的boolean[][]
         for(int j = i+1; j < s.length()+1; j++){
               for(int k = 1; k < p.length()+1; k++){
                         这段和LC一样
               }
               if(dp[j-i][p.length()]) return true; //说明substring已经match了p了
         }
}.留学论坛-一亩-三分地
return false;
回复 支持 2 反对 0

使用道具 举报

我的人缘0
pureklkl 发表于 2018-6-10 13:22:00 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
34楼那个答案错的,简单反例就是 string = "zzzabc", pattern = "abc"

在一个字符串里找子串本身就要kmp之类的才能做到O(n),个人感觉做出n3应该可以了吧,要是硬要做n2估计kmp变种之类的
. 牛人云集,一亩三分地
不过fb现在出啥难题也不奇怪就是了。。。

补充内容 (2018-6-10 13:33):
想多了,只要找起点就行,n^2稍微改改,遇到与pattern第一个字符相同的直接给true当起点就行
回复 支持 0 反对 1

使用道具 举报

我的人缘0
tonyabracadabra 发表于 2018-6-3 17:39:40 | 显示全部楼层
  此人我要顶:
 
100% (1) 【我投】
  此人我要踩:
 
0% (0) 【我投】
Po一个答案~其实和原题就差三行代码

[Java] 纯文本查看 复制代码
public boolean isMatch(String s, String p) {
        int n1 = s.length(), n2 = p.length();
        boolean[][] dp = new boolean[n1 + 1][n2 + 1];
        
        dp[0][0] = true;
        
        // 初始化match nothing
        for (int j = 1; j <= n2; j++) {
            if (p.charAt(j - 1) == '*') {dp[0][j] = dp[0][j - 2];
            }
        }

        for (int i = 1; i <= n1; i++) {
            for (int j = 1; j <= n2; j++) {
                if (p.charAt(j - 1) == '*') {// abc ab*c
                    dp[i][j] = dp[i][j - 2] || (dp[i - 1][j] && (s.charAt(i - 1) == p.charAt(j - 2) || p.charAt(j - 2) == '.'));
                } else {
                    dp[i][j] = dp[i - 1][j - 1] && (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '.');
                }
            }
        }
        
// 这是和原题唯一不同的地方
for (int i = 1; i <= n1; i++) {
    if (dp[i][n2]) return true;
        }
        
        return false;
}


回复 支持 0 反对 1

使用道具 举报

我的人缘0
 楼主| qjdehouse 发表于 2018-4-1 02:59:06 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
xiaotdl 发表于 2018-3-24 09:10
也可以把pattern变成.*pattern.*, 这样就可以直接默写LC10的答案了

我觉得这个方法也很棒!
回复 支持 1 反对 0

使用道具 举报

我的人缘0
zhanglixue 发表于 2018-2-26 09:46:33 | 显示全部楼层
  此人我要顶:
 
100% (1) 【我投】
  此人我要踩:
 
0% (0) 【我投】
qjdehouse 发表于 2018-2-26 07:40
我研究了一下你的代码,但我没明白这个代码有没有考虑到所有substring?还有中间idx2和idx1是不是用混啦 ...
. from: 1point3acres
举个例子吧
       a  c  a  b  b. 1point 3acres 论坛
  | t  t   t  t   t  t
a| f  t.  f.  t.  f. f
. | f  f.  t.  f.  t. f
*| f  f.  f.  t.  t. t

举了个例子,上面是原字符串"acabb",左边是正则表达式"a.*", 参看dp的第二行,a其实匹配了2个字串,原字符串里有两个a。相比于leetcode上的题目,转折点就在这里,原题目,第二个a应该是false。
回复 支持 1 反对 0

使用道具 举报

我的人缘0
yexiaojiaycc 发表于 2018-2-24 08:05:36 | 显示全部楼层
  此人我要顶:
 
100% (2) 【我投】
  此人我要踩:
 
0% (0) 【我投】
楼主投的是new grad SDE吗?看面经感觉题目难度层次不齐。完全靠运气。
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| qjdehouse 发表于 2018-2-24 08:19:41 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
yexiaojiaycc 发表于 2018-2-24 08:05
楼主投的是new grad SDE吗?看面经感觉题目难度层次不齐。完全靠运气。
. 围观我们@1point 3 acres
是的是的,我感觉他们对面试表现的要求应该是蛮高的,可能题目简单一些会容易过一点吧
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

我的人缘0
yexiaojiaycc 发表于 2018-2-24 08:57:46 | 显示全部楼层
  此人我要顶:
 
100% (2) 【我投】
  此人我要踩:
 
0% (0) 【我投】
qjdehouse 发表于 2018-2-24 08:19
是的是的,我感觉他们对面试表现的要求应该是蛮高的,可能题目简单一些会容易过一点吧

是啊,宁愿做2个medium的也不想遇到一个hard的。楼主运气不好。。。
回复 支持 反对

使用道具 举报

我的人缘0
vtiaocao 发表于 2018-2-24 09:04:46 | 显示全部楼层
  此人我要顶:
 
73% (27) 【我投】
  此人我要踩:
 
27% (11) 【我投】
目前还是传说中的一题nohire,两题hire,三题strong hire……. From 1point 3acres bbs
我感觉他们期待的是这题30行的O(n2)解法你要bug free 15分钟之内秒杀,然后面试官可能还藏了一题期待给你hire……

不过这题DP怎么做到O(n4)的。。。不是O(n*m)跑一遍就完了吗(我倒是知道O(2^(n+m))的……). more info on 1point3acres

要是没见过真的只能说自己刷题不行了……
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| qjdehouse 发表于 2018-2-24 09:23:11 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
vtiaocao 发表于 2018-2-24 09:04
目前还是传说中的一题nohire,两题hire,三题strong hire……
我感觉他们期待的是这题30行的O(n2)解法你要 ...

因为他问的题目是在一个string里找匹配的substring,我第一个想到的就是遍历所有的substring起点和终点。二维DP填表的复杂度是n^2, 找substringn^2, 就是n^4了
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| qjdehouse 发表于 2018-2-24 09:28:12 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
莲藕熊软软 发表于 2018-2-24 08:48. 一亩-三分-地,独家发布
只是看所有subarray,中间和LC一样做dp,match了就return,是不是O(n^3)啊?
input是s和p, p是pattern的话 ...

是的n^3就可以解决了~和substring比较同时填dp,遇到不对的就扔掉重新开始,这个是最后面试官问我优化时讨论说的
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| qjdehouse 发表于 2018-2-24 09:33:57 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
yexiaojiaycc 发表于 2018-2-24 08:57
是啊,宁愿做2个medium的也不想遇到一个hard的。楼主运气不好。。。

找工作要么得有很强的实力,要么有不错的运气。只能继续努力提高实力了!
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| qjdehouse 发表于 2018-2-24 09:37:57 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
qjdehouse 发表于 2018-2-24 09:23. 牛人云集,一亩三分地
因为他问的题目是在一个string里找匹配的substring,我第一个想到的就是遍历所有的substring起点和终点。 ...

优化之后n^3,不知道还有没有更好的方法。以我的能力十五分钟根本完成不了
回复 支持 反对

使用道具 举报

我的人缘0
zhanglixue 发表于 2018-2-26 01:04:54 | 显示全部楼层
  此人我要顶:
 
100% (1) 【我投】
  此人我要踩:
 
0% (0) 【我投】
写了一个o(n^2)的解法供讨论,楼主面试可能太紧张了吧,效果会适得其反。
isMatch(String s1, String s2) {
        if(s2.isEmpty()) return s1.isEmpty();
        char[] chs1 = s1.toCharArray();
        char[] chs2 = s2.toCharArray();
        int m = chs2.length, n = chs1.length;
        int[][] dp = new int[m+1][n+1];
        for(int i=0;i<=n;++i) dp[0][i] = true;. From 1point 3acres bbs
        dp[0][0] = true;
        for(int i=1;i<=m;++i) {
                int idx1 = i - 1;
                for(int j=1;j<=n;++j) {
                        int idx2 = j - 1;.本文原创自1point3acres论坛
                        if(chs2[idx2]=='.') {
                                dp[i][j] = dp[idx1][idx2];
                        } else if(chs2[idx2]=='*') {
                                if(dp[idx1][idx2]) {
                                        if(chs2[idx2-1]=='.') {
                                                while(j<=n) {.本文原创自1point3acres论坛
                                                        dp[i][j] = true;
                                                        ++j;
                                                }
                                        } else {. Waral 博客有更多文章,
                                                while(j<=n && chs2[j-1]==chs1[idx1]) {
                                                        dp[i][j] = true;.留学论坛-一亩-三分地
                                                        ++j;. 围观我们@1point 3 acres
                                                }
                                        }
                                }
                                break;
                        } else {
                                dp[i][j] = chs2[idx2]==chs1[idx1] && dp[idx1][idx2];
                        }
                }. 一亩-三分-地,独家发布
        }
        for(int i=1;i<=n;++i) if(dp[m][i]) return true;
        return false;
}
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| qjdehouse 发表于 2018-2-26 07:40:58 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
zhanglixue 发表于 2018-2-26 01:04
写了一个o(n^2)的解法供讨论,楼主面试可能太紧张了吧,效果会适得其反。. 1point3acres
isMatch(String s1, String s2)  ...

我研究了一下你的代码,但我没明白这个代码有没有考虑到所有substring?还有中间idx2和idx1是不是用混啦?不太明白,可以解释一下吗~谢谢
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| qjdehouse 发表于 2018-2-26 09:54:45 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
zhanglixue 发表于 2018-2-26 09:46. more info on 1point3acres
举个例子吧
       a  c  a  b  b
  | t  t   t  t   t  t

wow!神奇!谢谢你啦!!我真的是还有很多有待提高的地方
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| qjdehouse 发表于 2018-2-26 11:47:58 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
zhanglixue 发表于 2018-2-26 09:46
举个例子吧
       a  c  a  b  b
  | t  t   t  t   t  t

我又研究了一下,发现还是有点问题,dp[j]的结果应该不是只依赖于dp[i - 1][j - 1],我觉得chs2[j] == '*'的时候,还应该判断一下其他情况,因为x*可以匹配x出现0次或1次或多次,这三种情况是和dp表格前面的不同位置有关的。你举得例子如果是匹配a.*和ac的话,return的就是false了,但结果应该是true. 一亩-三分-地,独家发布
. visit 1point3acres for more.
还是多谢你给的方法啦!我完全没有想到呢
回复 支持 反对

使用道具 举报

我的人缘0
hpnhxxwn 发表于 2018-2-26 17:46:28 | 显示全部楼层
  此人我要顶:
 
33% (1) 【我投】
  此人我要踩:
 
67% (5) 【我投】
把pattern前面加上.*, 最后加上.*,再用原题的解法解行不行
回复 支持 反对

使用道具 举报

我的人缘0
zhanglixue 发表于 2018-2-27 00:12:26 | 显示全部楼层
  此人我要顶:
 
100% (1) 【我投】
  此人我要踩:
 
0% (0) 【我投】
qjdehouse 发表于 2018-2-26 11:47
我又研究了一下,发现还是有点问题,dp[j]的结果应该不是只依赖于dp[j - 1],我觉得chs2[j] == '*'的时候 ...

呵呵 我随便写了一下,里面可能有问题,没检查。你可以重写一下,看看是不是有逻辑错误。
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| qjdehouse 发表于 2018-2-28 10:57:54 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
hpnhxxwn 发表于 2018-2-26 17:46. from: 1point3acres
把pattern前面加上.*, 最后加上.*,再用原题的解法解行不行

那样会不会多出很多true的情况啊?
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| qjdehouse 发表于 2018-2-28 10:58:18 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
zhanglixue 发表于 2018-2-27 00:12
呵呵 我随便写了一下,里面可能有问题,没检查。你可以重写一下,看看是不是有逻辑错误。

逻辑很好!应该没有问题
回复 支持 反对

使用道具 举报

我的人缘0
hpnhxxwn 发表于 2018-2-28 13:57:29 | 显示全部楼层
  此人我要顶:
 
33% (1) 【我投】
  此人我要踩:
 
67% (5) 【我投】
qjdehouse 发表于 2018-2-28 10:57. 牛人云集,一亩三分地
那样会不会多出很多true的情况啊?

我理解的题意是,只要在string里面找到一个substring match就行了。.*match 前面的和后面的,当中match上pattern就行。这样理解对吗?

从我工作的经验来看,比如说用vim,.*xxx.*就能match上xxx。
回复 支持 反对

使用道具 举报

游客
请先登录

本版积分规则

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

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

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

custom counter

GMT+8, 2018-6-24 17:14

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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