没结婚也能买房啊!大波士顿地区买房小tips

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推多家公司面试
[Google级团队]:实时大数据分析领域践行者
北京/深圳-大数据/搜索/机器学习职位
日志易机器大数据行业践行者Web/大数据/机器学习等职位-北京or深圳
把贵司招聘信息放这里
查看: 1464|回复: 32
收起左侧

非死不可店面跪经

[复制链接] |试试Instant~ |关注本帖
qjdehouse 发表于 2018-2-24 06:33:07 | 显示全部楼层 |阅读模式

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

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

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

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

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

评分

1

查看全部评分

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

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

使用道具 举报

yexiaojiaycc 发表于 2018-2-24 08:05:36 | 显示全部楼层
楼主投的是new grad SDE吗?看面经感觉题目难度层次不齐。完全靠运气。
回复 支持 反对

使用道具 举报

 楼主| qjdehouse 发表于 2018-2-24 08:19:41 | 显示全部楼层
yexiaojiaycc 发表于 2018-2-24 08:05
楼主投的是new grad SDE吗?看面经感觉题目难度层次不齐。完全靠运气。
.鐣欏璁哄潧-涓浜-涓夊垎鍦
是的是的,我感觉他们对面试表现的要求应该是蛮高的,可能题目简单一些会容易过一点吧
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

vtiaocao 发表于 2018-2-24 09:04:46 | 显示全部楼层
目前还是传说中的一题nohire,两题hire,三题strong hire……
我感觉他们期待的是这题30行的O(n2)解法你要bug free 15分钟之内秒杀,然后面试官可能还藏了一题期待给你hire…….鐣欏璁哄潧-涓浜-涓夊垎鍦

不过这题DP怎么做到O(n4)的。。。不是O(n*m)跑一遍就完了吗(我倒是知道O(2^(n+m))的……)
. 1point 3acres 璁哄潧
要是没见过真的只能说自己刷题不行了……
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

 楼主| qjdehouse 发表于 2018-2-24 09:28:12 | 显示全部楼层
莲藕熊软软 发表于 2018-2-24 08:48
只是看所有subarray,中间和LC一样做dp,match了就return,是不是O(n^3)啊?
input是s和p, p是pattern的话 ...
. more info on 1point3acres.com
是的n^3就可以解决了~和substring比较同时填dp,遇到不对的就扔掉重新开始,这个是最后面试官问我优化时讨论说的
回复 支持 反对

使用道具 举报

 楼主| qjdehouse 发表于 2018-2-24 09:33:57 | 显示全部楼层
yexiaojiaycc 发表于 2018-2-24 08:57
是啊,宁愿做2个medium的也不想遇到一个hard的。楼主运气不好。。。
. 鍥磋鎴戜滑@1point 3 acres
找工作要么得有很强的实力,要么有不错的运气。只能继续努力提高实力了!
回复 支持 反对

使用道具 举报

 楼主| qjdehouse 发表于 2018-2-24 09:37:57 | 显示全部楼层
qjdehouse 发表于 2018-2-24 09:23
因为他问的题目是在一个string里找匹配的substring,我第一个想到的就是遍历所有的substring起点和终点。 ...
. 1point 3acres 璁哄潧
优化之后n^3,不知道还有没有更好的方法。以我的能力十五分钟根本完成不了
回复 支持 反对

使用道具 举报

zhanglixue 发表于 2018-2-26 01:04:54 | 显示全部楼层
写了一个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];
. Waral 鍗氬鏈夋洿澶氭枃绔,        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) {
                                                        dp[i][j] = true;
                                                        ++j;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
                                                }
                                        } else {. 鍥磋鎴戜滑@1point 3 acres
                                                while(j<=n && chs2[j-1]==chs1[idx1]) {
                                                        dp[i][j] = true;
                                                        ++j;
                                                }
                                        }
                                }
                                break;
                        } else {. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
                                dp[i][j] = chs2[idx2]==chs1[idx1] && dp[idx1][idx2];
                        }
                }
        }. 鍥磋鎴戜滑@1point 3 acres
        for(int i=1;i<=n;++i) if(dp[m][i]) return true;
        return false;
}
回复 支持 反对

使用道具 举报

 楼主| qjdehouse 发表于 2018-2-26 07:40:58 | 显示全部楼层
zhanglixue 发表于 2018-2-26 01:04
写了一个o(n^2)的解法供讨论,楼主面试可能太紧张了吧,效果会适得其反。. more info on 1point3acres.com
isMatch(String s1, String s2)  ...
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
我研究了一下你的代码,但我没明白这个代码有没有考虑到所有substring?还有中间idx2和idx1是不是用混啦?不太明白,可以解释一下吗~谢谢
回复 支持 反对

使用道具 举报

zhanglixue 发表于 2018-2-26 09:46:33 | 显示全部楼层
qjdehouse 发表于 2018-2-26 07:40
我研究了一下你的代码,但我没明白这个代码有没有考虑到所有substring?还有中间idx2和idx1是不是用混啦 ...
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
举个例子吧
       a  c  a  b  b
  | t  t   t  t   t  t. From 1point 3acres bbs
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。
回复 支持 反对

使用道具 举报

 楼主| qjdehouse 发表于 2018-2-26 09:54:45 | 显示全部楼层
zhanglixue 发表于 2018-2-26 09:46
举个例子吧
       a  c  a  b  b
  | t  t   t  t   t  t

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

使用道具 举报

 楼主| qjdehouse 发表于 2018-2-26 11:47:58 | 显示全部楼层
zhanglixue 发表于 2018-2-26 09:46
举个例子吧. more info on 1point3acres.com
       a  c  a  b  b. from: 1point3acres.com/bbs
  | 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 3acres 璁哄潧
还是多谢你给的方法啦!我完全没有想到呢
回复 支持 反对

使用道具 举报

hpnhxxwn 发表于 2018-2-26 17:46:28 | 显示全部楼层
把pattern前面加上.*, 最后加上.*,再用原题的解法解行不行
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

 楼主| qjdehouse 发表于 2018-2-28 10:57:54 | 显示全部楼层
hpnhxxwn 发表于 2018-2-26 17:46
把pattern前面加上.*, 最后加上.*,再用原题的解法解行不行

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

使用道具 举报

 楼主| qjdehouse 发表于 2018-2-28 10:58:18 | 显示全部楼层
zhanglixue 发表于 2018-2-27 00:12
呵呵 我随便写了一下,里面可能有问题,没检查。你可以重写一下,看看是不是有逻辑错误。

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

使用道具 举报

hpnhxxwn 发表于 2018-2-28 13:57:29 | 显示全部楼层
qjdehouse 发表于 2018-2-28 10:57
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴那样会不会多出很多true的情况啊?

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

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

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2018-4-21 21:53

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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