一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1445|回复: 6
收起左侧

SnapChat电面

[复制链接] |试试Instant~ |关注本帖
GavinM 发表于 2016-4-20 23:23:35 | 显示全部楼层 |阅读模式

2016(4-6月) 码农类 硕士 全职@Snapchat - 内推 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
昨天的电面,面的是国人大哥,首先感谢下他,感觉还是挺照顾我的。发帖求人品求onsite。先聊了聊我的简历。然后coding. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
第一题:valid palindrome
第二题:给一个string,算出把他变成palindrome的最少操作数。操作包括,增加,删减以及修改。
都是地里有过的面经题,解法别人的帖子里也有,这里就不赘述了。如果不懂的可以留言。
. 1point 3acres 璁哄潧

评分

2

查看全部评分

yueliu2366 发表于 2016-4-20 23:52:15 | 显示全部楼层
祝楼主好运!
第二题,dp做法吧?
dp[i][j] = (s.charAt(i) == s.charAt(j)) ?  dp[i + 1][j - 1] : Math.min(dp[i + 1][j], dp[i][j - 1]) + 1;
回复 支持 反对

使用道具 举报

 楼主| GavinM 发表于 2016-4-21 00:48:49 | 显示全部楼层
yueliu2366 发表于 2016-4-20 23:52
祝楼主好运!
第二题,dp做法吧?
dp[j] = (s.charAt(i) == s.charAt(j)) ?  dp[j - 1] : Math.min(dp[j] ...

是的。Math.min里面再加个dp[i + 1][j - 1]。因为你可以修改i或者j中一个。
回复 支持 反对

使用道具 举报

yueliu2366 发表于 2016-4-21 00:58:08 | 显示全部楼层
GavinM 发表于 2016-4-21 00:48.1point3acres缃
是的。Math.min里面再加个dp[j - 1]。因为你可以修改i或者j中一个。

我以为只能插入,原来也可以修改。多谢提醒。
回复 支持 反对

使用道具 举报

missing 发表于 2016-5-5 05:53:19 | 显示全部楼层
贴一个网上找来的办法:http://stackoverflow.com/questions/4737791/how-to-convert-a-string-into-a-palindrome-with-minimum-number-of-operations. From 1point 3acres bbs
. visit 1point3acres.com for more.
"Perform Levenshtein distance on the string and its reverse. The solution will be the minimum of the operations in the diagonal of the DP array going from bottom-left to top-right, as well as each entry just above and just below the diagonal..鏈枃鍘熷垱鑷1point3acres璁哄潧
This works because the entries along the diagonal represent the minimum edits required to make the first i and last N-i characters of the string equal and the entries just above and just below represent the minimum for strings ending up with odd-length where the middle (left-over) character doesn't match against anything." 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

我觉得挺有道理。。
回复 支持 反对

使用道具 举报

Mark6 发表于 2016-5-5 10:34:28 | 显示全部楼层
楼主过了吗?多久之后收到消息的啊?
回复 支持 反对

使用道具 举报

 楼主| GavinM 发表于 2016-5-5 23:13:35 | 显示全部楼层
Mark6 发表于 2016-5-5 10:34
楼主过了吗?多久之后收到消息的啊?

过了,第二天得到的消息。他家很快的。
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

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

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-3 08:30

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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