分享一次纽约开庭成功经验

一亩三分地论坛

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

扫描二维码登录本站

最近看过此主题的会员

E轮2.5亿美元融资
K12教育独角兽一起作业诚聘
机器学习/数据统计/教育等职位
码农求职神器Triplebyte:
不用海投
内推多家公司面试
高效直聘+内推,70%面试率
AI帮你免费完善简历
直击全美十万个科技职位
坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
锦晖律师事务所
12月16日
H1B讲座通知
查看: 2473|回复: 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里的每个可能的s
游客,本帖隐藏的内容需要积分高于 188 才可浏览,您当前积分为 0。
查看如何攒积分 Click here for more info.
匆结束。。。

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

评分

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

查看全部评分


上一篇:Google OA
下一篇:lyft phone + onsite
我的人缘0
tonyabracadabra 发表于 2018-6-3 17:39:40 | 显示全部楼层
本楼: 【顶】   66% (2)
 
 
33% (1)   【踩】
全局: 顶  86% (26)
 
 
13% (4)  踩
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
莲藕熊软软 发表于 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 &l
游客,本帖隐藏的内容需要积分高于 10 才可浏览,您当前积分为 0。
查看如何攒积分 Click here for more info.
h()]) return true; //说明substring已经match了p了
         }. check 1point3acres for more.
}
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应该可
游客,本帖隐藏的内容需要积分高于 10 才可浏览,您当前积分为 0。
查看如何攒积分 Click here for more info.
,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的答案了

我觉得这个方法也很棒!
回复

使用道具 举报

我的人缘0
xiaotdl 发表于 2018-3-24 09:10:24 | 显示全部楼层
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  100% (14)
 
 
0% (0)  踩
也可以把pattern变成.*patt
游客,本帖隐藏的内容需要积分高于 10 才可浏览,您当前积分为 0。
查看如何攒积分 Click here for more info.
C10的答案了

评分

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

查看全部评分

回复

使用道具 举报

我的人缘0
zhanglixue 发表于 2018-2-26 09:46:33 | 显示全部楼层
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  96% (51)
 
 
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
当横压一代 发表于 2018-2-24 08:05:36 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  96% (91)
 
 
3% (3)  踩
楼主投的是new grad S
游客,本帖隐藏的内容需要积分高于 10 才可浏览,您当前积分为 0。
查看如何攒积分 Click here for more info.
完全靠运气。
回复

使用道具 举报

我的人缘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吗?看面经感觉题目难度层次不齐。完全靠运气。
-baidu 1point3acres
是的是的,我感觉他们对面试表现的要求应该是蛮高的,可能题目简单一些会容易过一点吧
回复

使用道具 举报

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

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

使用道具 举报

我的人缘1
vtiaocao 发表于 2018-2-24 09:04:46 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  84% (705)
 
 
15% (129)  踩
目前还是传说中的一题nohire,两题hire,三题strong hire……
我感觉他们期待的是这题30行的O(n2)解法你要bug free 15分钟之内秒杀,然后面试官可能还
游客,本帖隐藏的内容需要积分高于 10 才可浏览,您当前积分为 0。
查看如何攒积分 Click here for more info.
)的……)

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

使用道具 举报

我的人缘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,不知道还有没有更好的方法。以我的能力十五分钟根本完成不了
回复

使用道具 举报

游客
请先登录

本版积分规则

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

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

手机版|小黑屋|一亩三分地留学网

GMT+8, 2018-12-14 06:00

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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