一亩三分地论坛

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

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

[找工就业] Google 电面

[复制链接] |试试Instant~ |关注本帖
y颜慕一 发表于 2016-3-31 10:05:23 | 显示全部楼层 |阅读模式

2016(1-3月)-[]MIS硕士+3个月-1年 - 网上海投| 码农类全职@Googlefresh grad应届毕业生

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

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

x
LZ是网上海投的,先是OA,题目是地里最新的,然后15分钟HR主要是HR告诉你电面之前的注意事项,然后就是前两天电面
题目是find the minimum number of characters that needs to be added to make a string be a palindrome,比如abc,最少要加2个character变成abcba或者cbabc

评分

1

查看全部评分

本帖被以下淘专辑推荐:

hyj143 发表于 2016-3-31 10:34:19 | 显示全部楼层
电面就来KMP。。
不过N^2的算法我觉得应该还是可以过。。
回复 支持 反对

使用道具 举报

yueliu2366 发表于 2016-3-31 10:56:55 | 显示全部楼层
请问楼主,OA地里最新的指的是哪个版本呢?能否给个链接或者描述一下题目?
回复 支持 反对

使用道具 举报

adiggo 发表于 2016-3-31 11:46:55 | 显示全部楼层
[quote][url=forum.php?mod=redirect
. 1point 3acres 璁哄潧
请问kmp 解法怎么搞……
回复 支持 反对

使用道具 举报

simplessssss 发表于 2016-4-1 10:49:39 | 显示全部楼层
这个应该是dp吧,kmp那条题只能在开始加chars或者在结尾加,这个应该是每个地方都可以加吧
回复 支持 反对

使用道具 举报

ccrjohn8787 发表于 2016-4-17 21:51:04 | 显示全部楼层
dp解法看string 头尾字母是不是一样
回复 支持 反对

使用道具 举报

不问岁月任风歌 发表于 2016-4-17 23:23:11 | 显示全部楼层
楼主这题能再具体一点吗?比如说添加的时候原来string的string不能动,还是新加的字符随便插哪里都可以?
回复 支持 反对

使用道具 举报

yueliu2366 发表于 2016-4-18 05:11:46 | 显示全部楼层
这题应该用不到KMP吧。
解法一:(递归解法,暴力穷举)
public int findMin(String s) {
        if (s == null || s.length() == 0) {
            return 0;. Waral 鍗氬鏈夋洿澶氭枃绔,
        }
        return dfs(s, 0, s.length() - 1);
    }
    . 1point3acres.com/bbs
    int dfs(String s, int l, int r) { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
        if (l == r) {
            return 0;. visit 1point3acres.com for more.
        }
        if (l == r - 1) {
            return s.charAt(l) == s.charAt(r - 1) ? 0 : 1;
        }
        
        return s.charAt(l) == s.charAt(r) ? dfs(s, l + 1, r - 1) : Math.min(dfs(s, l - 1, r), dfs(s, l, r + 1)) + 1;. Waral 鍗氬鏈夋洿澶氭枃绔,
    }

解法二(递归:时间是O(n^2))
状态方程: dp[i][j] 表示字符串s.substring(i, j + 1)变成palindrome需要插入的最小值

public int findMin(String s) {      
        int dp[][] = new int[s.length()][s.length()];
        //dp初始化
        for(int i = 0; i < s.length(); i++) {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
            dp[i][i] = 0;
            if (i < s.length() - 1) {
                dp[i][i + 1] = s.charAt(i) == s.charAt(i + 1) ? 0 : 1;
            }
        }
        //dp主体,
        for(int i = s.length() - 3; i >= 0; i--) {
            for(int j = i + 2; j < s.length(); j++) {
                if (s.charAt(i) == s.charAt(j)) {.1point3acres缃
                    dp[i][j] = dp[i + 1][j - 1];
                } else {
                    dp[i][j] = Math.min(dp[i + 1][j], dp[i][j - 1]) + 1;
                }
            }
        }
        return dp[0][s.length() - 1];
    }
回复 支持 反对

使用道具 举报

ykwwind 发表于 2016-4-18 05:18:17 | 显示全部楼层
http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=185787&page=1#pid2393890. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

稍麻烦的版本,一回事...
回复 支持 反对

使用道具 举报

jy_121 发表于 2016-4-27 09:36:54 | 显示全部楼层
yueliu2366 发表于 2016-4-18 05:11. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
这题应该用不到KMP吧。
解法一:(递归解法,暴力穷举)-google 1point3acres
public int findMin(String s) {
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
你好,我想问下为什么首尾不相等时只要加1个就能变成回文呢?谢谢
回复 支持 反对

使用道具 举报

yueliu2366 发表于 2016-4-27 10:10:11 | 显示全部楼层
jy_121 发表于 2016-4-27 09:36.1point3acres缃
你好,我想问下为什么首尾不相等时只要加1个就能变成回文呢?谢谢

假如首位不等,举个例子来说,比如"abcde", 那么为了使它变成回文,有且仅有两种做法(如果不先把最外侧的匹配了,任凭中间怎么插入,都不可能把它变成回文):
1. 在字符串首加一个e,变成"eabcde",然后还要继续操作中间那些部分
2. 在字符串尾部加一个a,变成"abcdea",然后还要继续操作中间那些部分. Waral 鍗氬鏈夋洿澶氭枃绔,
这两种做法,可以包括所有情况,而且都做了一个插入的操作,所以都是要加1的,然后取两者的最小值就可以了


补充内容 (2016-4-27 10:12):
打错了,第一句是“假如收尾不相等”

补充内容 (2016-4-27 10:13):. from: 1point3acres.com/bbs
我的天又错了,是“假如首尾字符不相等”
回复 支持 反对

使用道具 举报

jy_121 发表于 2016-4-27 11:11:27 | 显示全部楼层
yueliu2366 发表于 2016-4-27 10:10-google 1point3acres
假如首位不等,举个例子来说,比如"abcde", 那么为了使它变成回文,有且仅有两种做法(如果不先把最外侧 ...

明白了,谢谢
回复 支持 反对

使用道具 举报

fanfeng 发表于 2016-5-8 02:02:21 | 显示全部楼层
用python写了一个dp的算法,是真的这么简单吗...还是我有地方没考虑到...

def palindrome(s):
    m = [[0 for i in range(len(s))] for j in range(len(s))].鐣欏璁哄潧-涓浜-涓夊垎鍦
    for i in range(len(s)-1, -1, -1):
        for j in range(i+1, len(s), 1):
            if s[i] == s[j]:. Waral 鍗氬鏈夋洿澶氭枃绔,
                m[i][j] = m[i+1][j-1]. more info on 1point3acres.com
            else:.1point3acres缃
                m[i][j] = 1 + min(m[i][j-1], m[i+1][j]). 鍥磋鎴戜滑@1point 3 acres
             鏉ユ簮涓浜.涓夊垎鍦拌鍧.
    return m[0][len(s)-1]
回复 支持 反对

使用道具 举报

Altynai 发表于 2016-6-26 20:15:09 | 显示全部楼层
这题可以用manacher algorithm 算一遍回文,然后再扫一遍字符串,可以做到o(n)
回复 支持 反对

使用道具 举报

unsmilecat 发表于 2016-6-27 22:44:05 | 显示全部楼层
Altynai 发表于 2016-6-26 20:15
这题可以用manacher algorithm 算一遍回文,然后再扫一遍字符串,可以做到o(n)

Manacher只能用来做最长回文子串,而此处需要求最长回文子序列,所以只能通过串和它的反转做一次LCS;
. from: 1point3acres.com/bbs 这题是POJ 1159,老题了
回复 支持 反对

使用道具 举报

zhihaosun 发表于 2016-10-24 16:10:19 | 显示全部楼层
左右substring记忆化搜索递归,O(N^2)解
回复 支持 反对

使用道具 举报

woliside 发表于 2016-10-24 22:19:26 | 显示全部楼层
找出longest palindrome,然后比较长度?

补充内容 (2016-10-24 22:20):
看错了,忽略我
回复 支持 反对

使用道具 举报

cgxy1991 发表于 2016-12-3 16:21:58 | 显示全部楼层
左右暴力穷举O(n^2)解法,感觉面试够了
  1. <blockquote>class Solution{
复制代码

补充内容 (2016-12-3 16:22):
这什么情况。。。
回复 支持 反对

使用道具 举报

cgxy1991 发表于 2016-12-3 16:22:39 | 显示全部楼层
左右暴力穷举O(n^2)解法,感觉面试够了

class Solution{
        public String findPalin(String s){
                if(isPalin(s)) return s;
                String res = "";
                int min = Integer.MAX_VALUE;
                for(int i=1;i<s.length();i++){
                        StringBuilder sb = new StringBuilder();
                        for(int j=i;j<s.length();j++){
                                sb.append(s.charAt(j));
                        }
                        String str = sb.reverse().append(s).toString();
                        if(isPalin(str)){
                                if(str.length() < min) {
                                        min = str.length();.鏈枃鍘熷垱鑷1point3acres璁哄潧
                                        res = str;
                                }
                        }. visit 1point3acres.com for more.
                }. From 1point 3acres bbs
                for(int i=s.length()-2;i>=0;i--){
                        StringBuilder sb = new StringBuilder(s);
                        for(int j=i;j>=0;j--){. Waral 鍗氬鏈夋洿澶氭枃绔,
                                sb.append(s.charAt(j));
                        }
                        String str = sb.toString();
                        if(isPalin(str)){
                                if(str.length() < min) {
                                        min = str.length();
                                        res = str;
                                }
                        }.1point3acres缃
                }
                return res;. From 1point 3acres bbs
        }
        private boolean isPalin(String s){
                int from = 0, to = s.length()-1;
                while(from < to)
                        if(s.charAt(from++) != s.charAt(to--)) return false;
                return true;
        }
}
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

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

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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