一亩三分地论坛

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

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

Snapchat 电面挂经

[复制链接] |试试Instant~ |关注本帖
wwjk2003 发表于 2016-2-17 07:04:44 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 硕士 全职@Snapchat - 网上海投 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
Snapchat google hangout 一个帅帅的中国小哥面的。 上来照例介绍了下自己,问了下简历的项目。然后出题,第一题是valid palindrome。判断是不是合法的palindrome。第二题说给一个string,可以add/delete/change,还可以combine几种来使他变为合法的palindrome。比如:ebabc可以先删了中间的a再把c改成e。问最少需要几步。这个好难,没答上来。希望小哥放一马,给个onsite。

评分

2

查看全部评分

sheepmiemies 发表于 2016-3-11 12:35:52 | 显示全部楼层
感觉第二题还是可以用动态规划。
M[i, j]表示从i到j这个子串需要的修改次数,那么:
1. 如果s == s[j], M[i, j] =  M[i+1, j-1]
2. 如果不等:
(1)删左边,M[i+1, j] + 1;  删右边,M[i, j-1] + 1
鏉ユ簮涓浜.涓夊垎鍦拌鍧. (2)添在左边,M[i, j-1] + 1; 添在右边, M[i+1, j] + 1;. from: 1point3acres.com/bbs
(3)任意修改左边或者右边也类似。所以
. visit 1point3acres.com for more.M[i, j] = min(M[i+1, j], M[i, j - 1]) + 1. 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

补充内容 (2016-3-11 12:41):
(3)写错了。。。应该是任意改一个的话变成M[i+1, j-1] + 1
最后是M[i, j] = min(M[i+1, j], M[i, j - 1], M[i+1, j-1]) + 1.

评分

1

查看全部评分

回复 支持 2 反对 1

使用道具 举报

haoxuango 发表于 2016-2-18 13:00:50 | 显示全部楼层
木易wen 发表于 2016-2-18 12:18.鐣欏璁哄潧-涓浜-涓夊垎鍦
http://www.geeksforgeeks.org/dynamic-programming-set-28-minimum-insertions-to-form-a-palindrome/ 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
要 ...
. Waral 鍗氬鏈夋洿澶氭枃绔,
跟我想的一样, 应该就是这个思路
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
补充内容 (2016-2-18 13:46):
而且例子中的是不是只要最左边的改成a就好了
回复 支持 1 反对 0

使用道具 举报

JamesJi 发表于 2016-2-17 07:11:29 | 显示全部楼层
第二题类似edit distance
回复 支持 反对

使用道具 举报

木易wen 发表于 2016-2-18 12:18:10 | 显示全部楼层
http://www.geeksforgeeks.org/dynamic-programming-set-28-minimum-insertions-to-form-a-palindrome/ 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
要是可以change的话加个条件吧 比如里面的第一种情况再加个 min(findMinInsertions(str, l + 1, h - 1) + 1, ...)
回复 支持 反对

使用道具 举报

todayand 发表于 2016-2-18 13:16:24 | 显示全部楼层
LZ是内推还是网申的?
回复 支持 反对

使用道具 举报

 楼主| wwjk2003 发表于 2016-2-19 03:53:15 | 显示全部楼层
todayand 发表于 2016-2-18 13:16
LZ是内推还是网申的?
. visit 1point3acres.com for more.
网申的 字数字数
回复 支持 反对

使用道具 举报

xingrunzhi 发表于 2016-2-19 04:00:30 | 显示全部楼层
第二题好像在哪里见过,具体怎么做了忘记了。。。丢人
回复 支持 反对

使用道具 举报

hison7463 发表于 2016-2-19 05:19:07 | 显示全部楼层
感觉比edit distance还要难很多,至少edit distance给出了最终的string,电面题都这种难度。。。
回复 支持 反对

使用道具 举报

hzyslddm 发表于 2016-3-2 08:56:39 | 显示全部楼层
感觉有点像leetcode shortese palindrom 和 longest palindrom substring。贡献个思路,先找出最长的palindrom substring, 然后根据两边的剩余的substring再看怎么改,比如右边剩余子串reverse一下,再和左边剩余子串求edit distance。像ebabc,其实只要e换成c就可以了
回复 支持 反对

使用道具 举报

Nammmi 发表于 2016-3-11 12:46:17 | 显示全部楼层
我同学也是这个题,不过他挺厉害的一下就写出来了,还没出结果。
回复 支持 反对

使用道具 举报

wangmengcathy 发表于 2016-4-15 06:55:49 | 显示全部楼层
sheepmiemies 发表于 2016-3-11 12:35
感觉第二题还是可以用动态规划。
M表示从i到j这个子串需要的修改次数,那么:. from: 1point3acres.com/bbs
1. 如果s == s[j], M =  M
...

这个思路正解,紧张的情况下确实不容易马上想出来。。。  
        public static int minPalindromeDP(String s) {
                int n = s.length();
                // dp[j] means minimum number needed to make substring s(i..j) palindrome
                int[][] dp = new int[n][n];
                for(int l = 1; l < n; l++) {
                        for(int i = 0, j = l; j < n; i++, j++) {
                                dp[j] = s.charAt(i) == s.charAt(j) ? dp[i + 1][j - 1] : Math.min(dp[i + 1][j - 1], Math.min(dp[i + 1][j], dp[j - 1])) + 1;
                        } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
                }
                return dp[0][n - 1];
        }
回复 支持 反对

使用道具 举报

newbiee 发表于 2016-4-19 11:12:03 | 显示全部楼层
难道不是和reverse string求edit distance么?

补充内容 (2016-4-19 11:17):
具体的说是前半部和后半部的reverse求edit distance, . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
e.g1: ebabc, 前半部: eb(a奇数长,可忽略)   与cb(后半部的reverse)
e.g2  abacba    求 aba, 与abc (后半部的reverse) 求edit distance;
. visit 1point3acres.com for more.
补充内容 (2016-4-19 11:28):
e.g1 补充, 奇数长的情况应该是两种情况取min,   eb与cb, eba与cb,. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
      例子如cdaeffead  这样子的话cdaef与dafe的edit distance比cdae与daef的更小
回复 支持 反对

使用道具 举报

newbiee 发表于 2016-4-19 11:30:04 | 显示全部楼层
感觉 sheepmiemies 的思路更简单直接些
回复 支持 反对

使用道具 举报

tellmethough 发表于 2016-4-23 00:35:31 | 显示全部楼层
可以挑选自己  擅长的 类型马   比如  list  或者  vector  之类的   一定要 按照 小哥的 意思 解题吗  
回复 支持 反对

使用道具 举报

jerryyu3000 发表于 2016-5-2 05:12:54 | 显示全部楼层
ebabc 把c改成e 不就是?
回复 支持 反对

使用道具 举报

weijinchuan10 发表于 2016-10-31 06:43:50 | 显示全部楼层
int findMinimumDistance(String s){
    int[][] dp = new int[s.length()][s.length()];
    for(int l=2; l<=s.length(); l++){
        for(int i=0; i<=s.length()-l; i++){
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴    int start = i, end = start+l-1;
    if(s.charAt(start) == s.charAt(end)){
    dp[start][end] = dp[start+1][end-1];
}else{
    dp[start][end] = Math.min(1+dp[start][end-1], Math.min(1+dp[start+1][end], 1+dp[start+1][end-1]));
}
}
}
. 1point3acres.com/bbsreturn dp[0][s.length()-1];. 鍥磋鎴戜滑@1point 3 acres
}
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 08:16

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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