一亩三分地论坛

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

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

google电面2.16

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

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

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

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

x
新鲜的google店面,电话准时打来, 面试官大哥先介绍一下他是做什么的,然后聊了5分钟简历。. from: 1point3acres.com/bbs
进入正题。

bana nab
cooc ooc. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
abedd eba. From 1point 3acres bbs
先问从这些pairs中发现了什么, 回,拼起来回文。
给定一个List<String> 从里面找出可以拼成回文的所有pair。
一开始强行两个循环, 大哥揪了好多细节。说着程序跑起来得上天了, 得优化一下。.鐣欏璁哄潧-涓浜-涓夊垎鍦
由于前面时间花了比较多, 优化代码大哥说写伪代码就好。

第一次发帖。祝大家offer多多. from: 1point3acres.com/bbs

评分

3

查看全部评分

MarineGo 发表于 2016-2-17 12:07:47 | 显示全部楼层
可以用Hash Set来做吧。. Waral 鍗氬鏈夋洿澶氭枃绔,
比如说,对于"bana”, 可以把“nab”和“anab”存入Hashset里。如果再找到一样的,就组成pair了。
时间复杂度是O(N)。
回复 支持 0 反对 2

使用道具 举报

nole 发表于 2016-2-17 15:12:25 | 显示全部楼层
Here is the implementation in Java.
.鏈枃鍘熷垱鑷1point3acres璁哄潧

  1.   public List<List<String>> pairPalindrome(List<String> words) {
  2.     List<List<String>> result = new ArrayList<>();
  3.     if (words == null || words.size() == 0) {
  4.       return result;
  5.     }
  6.     Set<String> dict = new HashSet<>(words);
  7.     for (String word : words) {
  8.       int len = word.length();. more info on 1point3acres.com
  9.       for (int i = 0; i < len; i++) {
  10.         String prefix = word.substring(0, i);
  11.         String suffix = word.substring(i);. 鍥磋鎴戜滑@1point 3 acres
  12.         String reversPrefix = reverse(prefix);
  13.         String reverseSuffix = reverse(suffix);
  14.         if (isPalindrome(prefix) && dict.contains(reverseSuffix)) {
  15.           result.add(new ArrayList<>(Arrays.asList(word, reverseSuffix)));. visit 1point3acres.com for more.
  16.           dict.remove(reverseSuffix);
  17.         }

  18.         if (isPalindrome(suffix) && dict.contains(reversPrefix)) {
  19.           result.add(new ArrayList<>(Arrays.asList(word, reversPrefix)));
  20.           dict.remove(reversPrefix);. visit 1point3acres.com for more.
  21.         }
  22.       }
  23.     }.1point3acres缃
  24.     return result;
  25.   }-google 1point3acres

  26.   private boolean isPalindrome(String word) {
  27.     int start = 0, end = word.length() - 1;
  28.     while (start < end) {. 鍥磋鎴戜滑@1point 3 acres
  29.       if (word.charAt(start) != word.charAt(end)) {
  30.         return false;. more info on 1point3acres.com
  31.       }
  32.       start++; end--;
  33.     }
  34.     return true;
  35.   }

  36.   private String reverse(String word) {
  37.     char[] chars = word.toCharArray();
  38.     int start = 0, end = chars.length - 1;
  39.     while (start < end) {. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  40.       char temp = chars[start];
    . more info on 1point3acres.com
  41.       chars[start] = chars[end];
  42.       chars[end] = temp;.1point3acres缃
  43.       start++; end--;
  44.     }.鏈枃鍘熷垱鑷1point3acres璁哄潧
  45.     return new String(chars);
  46.   }
复制代码
回复 支持 0 反对 1

使用道具 举报

yang841841 发表于 2016-2-17 15:20:51 | 显示全部楼层
xhuaoe 发表于 2016-2-17 13:31
可以用Trie树吧,把所有字符串倒过来存进树里,然后对每个字符串都在树里找满足条件的串。另外为了避免重复 ...

这个思路是对的,其实就是先建立后缀树,再在里面匹配~~
一个小问题是,每次匹配成功后,如果匹配结果是某个后缀的前缀,那么还要看剩下没匹配的那串是否回文,如果不回文还是不行
回复 支持 1 反对 0

使用道具 举报

大炼金师 发表于 2016-2-17 12:33:12 | 显示全部楼层
qwang310 发表于 2016-2-17 12:20
还有啥组合,能举个例子吗?

bana cdddcanab

比如这种?
回复 支持 1 反对 0

使用道具 举报

lpx1989 发表于 2016-2-17 11:59:45 | 显示全部楼层
一下子想不出好办法,楼主最后优化的解法是什么
回复 支持 反对

使用道具 举报

monkeyee 发表于 2016-2-17 12:03:04 | 显示全部楼层
怎样避免遍历所有的string pair?
回复 支持 反对

使用道具 举报

bingo1995 发表于 2016-2-17 12:08:59 | 显示全部楼层
MarineGo 发表于 2016-2-17 12:07
可以用Hash Set来做吧。
比如说,对于"bana”, 可以把“nab”和“anab”存入Hashset里。如果再找到一样的 ...
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
你这显然不对  可以和bana组合成回文串的有无数个
回复 支持 反对

使用道具 举报

qwang310 发表于 2016-2-17 12:20:12 | 显示全部楼层
bingo1995 发表于 2016-2-17 12:08
你这显然不对  可以和bana组合成回文串的有无数个

还有啥组合,能举个例子吗?
回复 支持 反对

使用道具 举报

lpx1989 发表于 2016-2-17 12:21:55 | 显示全部楼层
我在想会不会用什么前缀数据结构存储,比如Trie tree,两个配对的字符串必然最多有一个字符不同。
回复 支持 反对

使用道具 举报

mymax2009 发表于 2016-2-17 13:08:08 | 显示全部楼层
一亩三分地严打"顶""好贴""收藏了"之类的垃圾回复帖!被警告三次,系统会自动封杀ID!

想支持楼主,请点击帖子下方的"好苗""分享""收藏"键,酌情给楼主加大米(系统不扣你自己的分)。
积分不够看不了帖子,请参考论坛导航里的"帮助","新手提纲"里有攒积分指南
回复 支持 反对

使用道具 举报

mymax2009 发表于 2016-2-17 13:09:51 | 显示全部楼层
晕,我发了什么鬼。。。。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
有没有大神给点思路?  O(n)的有木有?
回复 支持 反对

使用道具 举报

mymax2009 发表于 2016-2-17 13:11:32 | 显示全部楼层
lpx1989 发表于 2016-2-17 12:21
我在想会不会用什么前缀数据结构存储,比如Trie tree,两个配对的字符串必然最多有一个字符不同。

楼上的这个例子bana cdddcanab 就不止一个字符不同了
回复 支持 反对

使用道具 举报

xhuaoe 发表于 2016-2-17 13:31:15 | 显示全部楼层
可以用Trie树吧,把所有字符串倒过来存进树里,然后对每个字符串都在树里找满足条件的串。另外为了避免重复使用同一个串,可以修改一下树的结点,记录各个串的索引或地址,最后进行比较。时间大概是 O(kn),k 是pair数,n是平均长度。
回复 支持 反对

使用道具 举报

jill_8668 发表于 2016-2-17 13:48:03 | 显示全部楼层
用trie来寻找可能的pair,大概思路如下:
for(String s : list){
     String rs = s.reverse();
     search res in trie tree(can find possible string)
     add s in to trie tree
}
不知是否有更好的解法

. 鍥磋鎴戜滑@1point 3 acres 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
补充内容 (2016-2-17 13:49):. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
typo: res -> rs
回复 支持 反对

使用道具 举报

mymax2009 发表于 2016-2-17 13:54:13 | 显示全部楼层
xhuaoe 发表于 2016-2-17 13:31
可以用Trie树吧,把所有字符串倒过来存进树里,然后对每个字符串都在树里找满足条件的串。另外为了避免重复 ...

同学能细点说吗? 在树里找满足条件的串,这个要怎么找呢? 比如树里已经有了anab(原串bana),现在遇到新串nab,该从哪开始search呢?a?n?
回复 支持 反对

使用道具 举报

lpx1989 发表于 2016-2-17 14:02:12 | 显示全部楼层
jill_8668 发表于 2016-2-17 01:48. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
用trie来寻找可能的pair,大概思路如下:
for(String s : list){
     String rs = s.reverse();

这里需要注意一个地方,我想法是插入trie的时候,先去重,如果发现到叶子的时候还多一个字符或者刚好不多,就ok符合
回复 支持 反对

使用道具 举报

xhuaoe 发表于 2016-2-17 14:19:43 | 显示全部楼层
mymax2009 发表于 2016-2-17 13:54. from: 1point3acres.com/bbs
同学能细点说吗? 在树里找满足条件的串,这个要怎么找呢? 比如树里已经有了anab(原串bana),现在遇到 ...

从两个串的第一个字母开始比较,直到到达某个串的尾部。
这种情况不是回文的:nabbana。首先比较a和n,发现不同,放弃。
反过来则是回文的:bananab。nab这个串在树里是ban,所以bana和ban可以一直比较下去,直到ban的尾部。所以bana+nab是回文串。
回复 支持 反对

使用道具 举报

jill_8668 发表于 2016-2-17 14:19:53 | 显示全部楼层
lpx1989 发表于 2016-2-17 14:02
这里需要注意一个地方,我想法是插入trie的时候,先去重,如果发现到叶子的时候还多一个字符或者刚好不多 ...

我的想法是只从trie中找出可能的pair。
比如 abcdc, ba,我们先把abcdc加入了trie,遇到ba时,我们去trie中寻找a开头的,然后进一步寻找ab开头的,此时ab开头的string是abcdc,那么我们再次核对,abcdc是否可以和ba组成回文;如果trie里面还有其他ab开头的string,比如abda,我们也把这个string取出来和ba进行核对,是否可以组成回文,发现不行,就不加入结果集。

当然也可能ba先加入trie,但思路是一样的。
回复 支持 反对

使用道具 举报

mymax2009 发表于 2016-2-17 14:33:50 | 显示全部楼层
xhuaoe 发表于 2016-2-17 14:19-google 1point3acres
从两个串的第一个字母开始比较,直到到达某个串的尾部。
这种情况不是回文的:nabbana。首先比较a和n, ...
. 1point 3acres 璁哄潧
bana 和ban比到的ban的末尾, 可是还是需要判定多出来的字符是不是回文吧? 比如这里的‘a’,. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
或者说这个例子   abcccgccc  和ba, 比较完ab之后还要判断cccgccc,这个有什么办法吗?  
回复 支持 反对

使用道具 举报

xhuaoe 发表于 2016-2-17 14:44:54 | 显示全部楼层
mymax2009 发表于 2016-2-17 14:33
bana 和ban比到的ban的末尾, 可是还是需要判定多出来的字符是不是回文吧? 比如这里的‘a’,. from: 1point3acres.com/bbs
或者说这 ...

脑抽了把这个给忘了……最简单的方法就是比较完以后直接检查,但是这样的话时间就会增加到 O(k'n),k'是这种两边对称中间不知道的pair的数目。
回复 支持 反对

使用道具 举报

mymax2009 发表于 2016-2-17 14:47:05 | 显示全部楼层
jill_8668 发表于 2016-2-17 14:19
我的想法是只从trie中找出可能的pair。
比如 abcdc, ba,我们先把abcdc加入了trie,遇到ba时,我们去tr ...

我觉得你这个办法可行,但是trie的话我觉得先遍历一边所有的string把逆串trie建立好,O(n*k),然后再遍历每个string,在树里找有可能的pair,O(n*k),最后再判定这些可能的pair里哪些是真的回文?(这一步的worse case应该是O(n2)吧?)
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-4 23:41

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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