详谈如何最大化利用career fair

一亩三分地论坛

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

最近看过此主题的会员

坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
前Google华人高管创立
面试offer一键直通
Leap.ai助你进入热门独角兽
查看: 2292|回复: 37
收起左侧

非死不可店面跪经

[复制链接] |试试Instant~
我的人缘0
qjdehouse 发表于 2018-2-24 06:33:07 | 显示全部楼层 |阅读模式
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  83% (5)
 
 
16% (1)  踩

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,然后没时间写了。十天后收到了拒信。面试官应该是白人,面试过程中他比较冷淡,我几乎没有停止讲话,很多次中途试图跟他交流,发现他回复的也很慢,不知什么情况。最后的问问题环节,我感觉他也是想匆匆结束。。。

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

评分

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

查看全部评分


上一篇:Google OA
下一篇:lyft phone + onsite
我的人缘0
tonyabracadabra 发表于 2018-6-3 17:39:40 | 显示全部楼层
本楼: 【顶】   66% (2)
 
 
33% (1)   【踩】
全局: 顶  85% (24)
 
 
14% (4)  踩
Po一个答案~其实和原题就差三行代码
. visit 1point3acres for more.
[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;
}

.本文原创自1point3acres论坛
回复

使用道具 举报

我的人缘0
莲藕熊软软 发表于 2018-2-24 08:48:08 | 显示全部楼层
本楼: 【顶】   100% (2)
 
 
0% (0)   【踩】
全局: 顶  100% (5)
 
 
0% (0)  踩
只是看所有subarray,中间和LC一样做dp,match了就return,是不是O(n^3)啊?
input是s和p, p是pattern的话,
在原本LC题的两层循环外面再套一层循环s的每一位,相当于把每一位设为substring的起始点
大概意思就是

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;
回复

使用道具 举报

我的人缘0
pureklkl 发表于 2018-6-10 13:22:00 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
100% (1)   【踩】
全局: 顶  75% (3)
 
 
25% (1)  踩
34楼那个答案错的,简单反例就是 string = "zzzabc", pattern = "abc". 留学申请论坛-一亩三分地

在一个字符串里找子串本身就要kmp之类的才能做到O(n),个人感觉做出n3应该可以了吧,要是硬要做n2估计kmp变种之类的. 1point3acres

不过fb现在出啥难题也不奇怪就是了。。。 . from: 1point3acres

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

使用道具 举报

我的人缘0
 楼主| qjdehouse 发表于 2018-4-1 02:59:06 | 显示全部楼层
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  83% (5)
 
 
16% (1)  踩
xiaotdl 发表于 2018-3-24 09:10
也可以把pattern变成.*pattern.*, 这样就可以直接默写LC10的答案了
. more info on 1point3acres
我觉得这个方法也很棒!

21.000+ students read the Road to learn React. The course weaves all the opinionated roadmaps into one roadmap to master React. It gives you all the fundamentals in React. You will build a Hacker News App along the way.

回复

使用道具 举报

我的人缘0
xiaotdl 发表于 2018-3-24 09:10:24 | 显示全部楼层
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  100% (12)
 
 
0% (0)  踩
也可以把pattern变成.*pattern.*, 这样就可以直接默写LC10的答案了

评分

参与人数 1大米 +10 收起 理由
xh_pku + 10 这种方法可行!

查看全部评分

回复

使用道具 举报

我的人缘0
zhanglixue 发表于 2018-2-26 09:46:33 | 显示全部楼层
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  96% (49)
 
 
3% (2)  踩
qjdehouse 发表于 2018-2-26 07:40
我研究了一下你的代码,但我没明白这个代码有没有考虑到所有substring?还有中间idx2和idx1是不是用混啦 ...

举个例子吧
       a  c  a  b  b
  | t  t   t  t   t  t
a| f  t.  f.  t.  f. f
. | f  f.  t.  f.  t. f. 1point3acres
*| f  f.  f.  t.  t. t

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

使用道具 举报

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

使用道具 举报

我的人缘0
 楼主| qjdehouse 发表于 2018-2-24 08:19:41 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  83% (5)
 
 
16% (1)  踩
yexiaojiaycc 发表于 2018-2-24 08:05
楼主投的是new grad SDE吗?看面经感觉题目难度层次不齐。完全靠运气。

是的是的,我感觉他们对面试表现的要求应该是蛮高的,可能题目简单一些会容易过一点吧
回复

使用道具 举报

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

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

使用道具 举报

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

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

要是没见过真的只能说自己刷题不行了……

Learn React.js, Redux & Immutable.js while building a weather app

回复

使用道具 举报

我的人缘0
 楼主| qjdehouse 发表于 2018-2-24 09:23:11 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  83% (5)
 
 
16% (1)  踩
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)
 
 
0% (0)   【踩】
全局: 顶  83% (5)
 
 
16% (1)  踩
莲藕熊软软 发表于 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)
 
 
0% (0)   【踩】
全局: 顶  83% (5)
 
 
16% (1)  踩
yexiaojiaycc 发表于 2018-2-24 08:57
是啊,宁愿做2个medium的也不想遇到一个hard的。楼主运气不好。。。

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

使用道具 举报

我的人缘0
 楼主| qjdehouse 发表于 2018-2-24 09:37:57 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  83% (5)
 
 
16% (1)  踩
qjdehouse 发表于 2018-2-24 09:23
因为他问的题目是在一个string里找匹配的substring,我第一个想到的就是遍历所有的substring起点和终点。 ...

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

使用道具 举报

我的人缘0
zhanglixue 发表于 2018-2-26 01:04:54 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  96% (49)
 
 
3% (2)  踩
写了一个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;
        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;
                        if(chs2[idx2]=='.') {. 牛人云集,一亩三分地
                                dp[i][j] = dp[idx1][idx2];
                        } else if(chs2[idx2]=='*') {
                                if(dp[idx1][idx2]) {
                                        if(chs2[idx2-1]=='.') {
                                                while(j<=n) {. visit 1point3acres for more.
                                                        dp[i][j] = true;
                                                        ++j;
                                                }
                                        } else {
                                                while(j<=n && chs2[j-1]==chs1[idx1]) {
                                                        dp[i][j] = true;
                                                        ++j;. 牛人云集,一亩三分地
                                                }
                                        }.本文原创自1point3acres论坛
                                }. 1point 3acres 论坛
                                break;
                        } else {
                                dp[i][j] = chs2[idx2]==chs1[idx1] && dp[idx1][idx2];
                        }
                }
        }. Waral 博客有更多文章,
        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)
 
 
0% (0)   【踩】
全局: 顶  83% (5)
 
 
16% (1)  踩
zhanglixue 发表于 2018-2-26 01:04
写了一个o(n^2)的解法供讨论,楼主面试可能太紧张了吧,效果会适得其反。
isMatch(String s1, String s2)  ...

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

使用道具 举报

我的人缘0
 楼主| qjdehouse 发表于 2018-2-26 09:54:45 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  83% (5)
 
 
16% (1)  踩
zhanglixue 发表于 2018-2-26 09:46
举个例子吧
       a  c  a  b  b
  | t  t   t  t   t  t

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

使用道具 举报

我的人缘0
 楼主| qjdehouse 发表于 2018-2-26 11:47:58 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  83% (5)
 
 
16% (1)  踩
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. 围观我们@1point 3 acres

还是多谢你给的方法啦!我完全没有想到呢
回复

使用道具 举报

我的人缘0
hpnhxxwn 发表于 2018-2-26 17:46:28 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  75% (12)
 
 
25% (4)  踩
把pattern前面加上.*, 最后加上.*,再用原题的解法解行不行
回复

使用道具 举报

我的人缘0
zhanglixue 发表于 2018-2-27 00:12:26 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  96% (49)
 
 
3% (2)  踩
qjdehouse 发表于 2018-2-26 11:47
我又研究了一下,发现还是有点问题,dp[j]的结果应该不是只依赖于dp[j - 1],我觉得chs2[j] == '*'的时候 ...
来源一亩.三分地论坛.
呵呵 我随便写了一下,里面可能有问题,没检查。你可以重写一下,看看是不是有逻辑错误。
回复

使用道具 举报

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

那样会不会多出很多true的情况啊?
回复

使用道具 举报

我的人缘0
 楼主| qjdehouse 发表于 2018-2-28 10:58:18 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  83% (5)
 
 
16% (1)  踩
zhanglixue 发表于 2018-2-27 00:12. 围观我们@1point 3 acres
呵呵 我随便写了一下,里面可能有问题,没检查。你可以重写一下,看看是不是有逻辑错误。

逻辑很好!应该没有问题
回复

使用道具 举报

我的人缘0
hpnhxxwn 发表于 2018-2-28 13:57:29 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  75% (12)
 
 
25% (4)  踩
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

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

GMT+8, 2018-9-24 17:10

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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