传说中的谷歌招聘委员会成员之一,从幕后走出来,教你学系统设计!


一亩三分地论坛

 找回密码
 获取更多干活,快来注册
Babeltime游戏工作室招工程师、美术和策划
Tubi TV招安卓、前端和机器学习工程师
把贵司招聘信息放这里
查看: 2213|回复: 6
收起左侧

SnapChat电面

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

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

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

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

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

评分

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. 鍥磋鎴戜滑@1point 3 acres
是的。Math.min里面再加个dp[j - 1]。因为你可以修改i或者j中一个。
. 鍥磋鎴戜滑@1point 3 acres
我以为只能插入,原来也可以修改。多谢提醒。
回复 支持 反对

使用道具 举报

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

"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.. visit 1point3acres.com for more.
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.". from: 1point3acres.com/bbs

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

使用道具 举报

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

使用道具 举报

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

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

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-9-21 22:27

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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