一亩三分地论坛

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

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

Google 新鲜电面。。 攒人品

[复制链接] |试试Instant~ |关注本帖
_yInnovation 发表于 2016-1-26 04:20:27 | 显示全部楼层 |阅读模式

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

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

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

x
刚面完就来地理回馈攒人品了。。 面的感觉很一般。。 . 1point 3acres 璁哄潧
一道题:. 鍥磋鎴戜滑@1point 3 acres
给一个非常大的, unique的dictionary. 要求找出所有能够组成palindrome的pair.
比如:
[abcd, dcba, lls, s, sssll]
那么就返回:. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
[abcd, dcba]
[lls, s].鏈枃鍘熷垱鑷1point3acres璁哄潧
[lls, sssll]

聊完Proj开始写题。 一上来先暴力来的n^2 * k的。。。然后就蒙B了。。 在小哥一步一步的带领下,figure out了一个n * k^2的。。。。(k是average length of word). 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

评分

5

查看全部评分

johnjavabean 发表于 2016-1-26 05:54:09 | 显示全部楼层
我给一个solution吧

  1. vector<pair<string, string> > palindomPair(vector<string> &words) {
  2.     vector<pair<string, string> > rst;
  3.     unordered_set<string> dict;
  4.     for(int i = 0; i < words.size(); i ++) {
  5.         dict.insert(words[i]);
  6.     }. Waral 鍗氬鏈夋洿澶氭枃绔,
  7.     for(int i = 0; i < words.size(); i ++) {
  8.         int len = words[i].size();
  9.         for(int l = 0; l <= len; l ++) {
  10.             string sub1 = words[i].substr(0, l);. 1point3acres.com/bbs
  11.             string sub2 = words[i].substr(l, len-l);
  12.             if(isPal(sub2)){.1point3acres缃
  13.                 string tmp = sub1;
  14.                 reverse(tmp.begin(), tmp.end());. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  15.                 if(dict.find(tmp) != dict.end() && words[i] != tmp) {. 1point 3acres 璁哄潧
  16.                     rst.push_back(pair<string, string>(words[i], tmp));
  17.                 }
  18.             }
  19.             if(isPal(sub1)){. 1point 3acres 璁哄潧
  20.                 string tmp = sub2;
  21.                 reverse(tmp.begin(), tmp.end());
  22.                 if(dict.find(tmp) != dict.end() && words[i] != tmp) {
  23.                     rst.push_back(pair<string,string>(tmp, words[i]));
  24.                 }
  25.             }
  26.         }
  27.     }
  28.     return rst;
  29. }
复制代码


觉得有帮助各位请给点大米

评分

5

查看全部评分

回复 支持 3 反对 0

使用道具 举报

dimi 发表于 2016-8-21 23:41:49 | 显示全部楼层
leetcode 336最新加了这个题目。
回复 支持 1 反对 0

使用道具 举报

xiaozhuxiaozhu 发表于 2016-3-9 10:46:31 | 显示全部楼层
bobzhang2004 发表于 2016-3-9 10:30. 鍥磋鎴戜滑@1point 3 acres
我跑了下你的代码,还是有问题啊,会有ba ab , 和ab ba
  1.         public static boolean isP(String word)
  2.         {
  3.                 int start =0;
  4.                 int end = word.length()-1;
  5.                 while(start<end)
  6.                 {
  7.                         if(word.charAt(start)!=word.charAt(end))
  8.                         {
  9.                                 return false;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  10.                         }. 1point3acres.com/bbs
  11.                         start++;.1point3acres缃
  12.                         end--;
  13.                 }
  14.                 return true;
  15.         }
  16.         public static HashSet<ArrayList<String>> findPairs(ArrayList<String> input)
  17.         {
  18.                 HashSet<ArrayList<String>> new_results = new HashSet();. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  19.                 Set<String> set = new HashSet<String>();
  20.                 for(int i=0; i < input.size();i++). 1point3acres.com/bbs
  21.                 {
  22.                         set.add(input.get(i));
  23.                 }
  24.                
  25.                 for(int i=0; i < input.size();i++)
  26.                 {
  27.                         int length = input.get(i).length();
  28.                         String temp = input.get(i);
  29.                         for(int j =0; j<= length;j++)
  30.                         {
  31.                                 String can1 =  temp.substring(0, j);
  32.                                 String can2 = temp.substring(j,length);. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  33.                                 if(isP(can2))
  34.                                 {
  35.                                         String reverse_can1 = new StringBuilder(can1).reverse().toString();
  36.                                         if(set.contains(reverse_can1)&&!reverse_can1.equals(temp))
  37.                                         { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  38.                                                 if(!new_results.contains(new ArrayList<>(Arrays.asList(temp,reverse_can1)))&&!new_results.contains(new ArrayList<>(Arrays.asList(reverse_can1,temp))))
  39.                                                 {
  40.                                                         new_results.add(new ArrayList<>(Arrays.asList(temp,reverse_can1)));

  41.                                                 }
  42.                                         }
  43.                                 }. more info on 1point3acres.com
  44.                                 if(isP(can1))
  45.                                 {
  46.                                         String reverse_can2 = new StringBuilder(can2).reverse().toString();. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  47.                                         if(set.contains(reverse_can2)&&!reverse_can2.equals(temp)). 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  48.                                         {
  49.                                                 //ArrayList<String> temp_result = new ArrayList<String>();
  50.                                                 if(!new_results.contains(new ArrayList<>(Arrays.asList(temp,reverse_can2)))&&!new_results.contains(new ArrayList<>(Arrays.asList(reverse_can2,temp)))). 1point3acres.com/bbs
  51.                                                 {
  52.                                                         new_results.add(new ArrayList<>(Arrays.asList(temp,reverse_can2)));

  53.                                                 }

  54.                                         }
  55.                                 }
  56.                         }
  57.                         -google 1point3acres

  58.                 }
  59.                
  60.                
  61.                 return new_results;. Waral 鍗氬鏈夋洿澶氭枃绔,
  62.         }
复制代码

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

dietpepsi 发表于 2016-1-26 06:43:49 | 显示全部楼层
CareerCup上有这道题,Google,9个月前的,http://careercup.com/question?id=4879869638868992
回复 支持 1 反对 0

使用道具 举报

dolphin_wby 发表于 2016-1-26 04:57:05 | 显示全部楼层
lz能说一下优化后的思路吗?非常感谢~
回复 支持 反对

使用道具 举报

 楼主| _yInnovation 发表于 2016-1-26 05:02:42 | 显示全部楼层
dolphin_wby 发表于 2016-1-26 04:57
lz能说一下优化后的思路吗?非常感谢~

晚上写一个pseudocode好了。。
回复 支持 反对

使用道具 举报

虾米酱 发表于 2016-1-26 05:29:49 | 显示全部楼层
可以先把所有单词存进set,然后每个单词找palindrome,然后看set里是否存在这个string么
回复 支持 反对

使用道具 举报

 楼主| _yInnovation 发表于 2016-1-26 05:34:45 | 显示全部楼层
虾米酱 发表于 2016-1-26 05:29
可以先把所有单词存进set,然后每个单词找palindrome,然后看set里是否存在这个string么

大概思路是这样的
回复 支持 反对

使用道具 举报

johnjavabean 发表于 2016-1-26 05:44:32 | 显示全部楼层
这是fb的题啊.....
回复 支持 反对

使用道具 举报

dolphin_wby 发表于 2016-1-26 05:45:17 | 显示全部楼层

那如果是lls,那它的palindrome是不是有s*ll, s,要这些都查一遍set是吗?
回复 支持 反对

使用道具 举报

johnjavabean 发表于 2016-1-26 05:49:12 | 显示全部楼层
虾米酱 发表于 2016-1-26 05:29
可以先把所有单词存进set,然后每个单词找palindrome,然后看set里是否存在这个string么

这个是不对的,比如aabca和acbaa,这两个连起来可以构成palindrome,但是你在set里面是查不到的
回复 支持 反对

使用道具 举报

 楼主| _yInnovation 发表于 2016-1-26 06:04:11 | 显示全部楼层
johnjavabean 发表于 2016-1-26 05:44. 鍥磋鎴戜滑@1point 3 acres
这是fb的题啊.....
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
。。。不是说电面应该简单点么。。
回复 支持 反对

使用道具 举报

 楼主| _yInnovation 发表于 2016-1-26 06:06:48 | 显示全部楼层
johnjavabean 发表于 2016-1-26 05:54. 鍥磋鎴戜滑@1point 3 acres
我给一个solution吧

这个solution是对的。 赞。。大神就是大神。。
回复 支持 反对

使用道具 举报

johnjavabean 发表于 2016-1-26 06:13:57 | 显示全部楼层
_yInnovation 发表于 2016-1-26 06:06
这个solution是对的。 赞。。大神就是大神。。

不是大神,只是因为见过,我第一次最好也只做出了nlognk
回复 支持 反对

使用道具 举报

xiaobao9 发表于 2016-1-26 06:28:45 | 显示全部楼层

是不是只判断if(isPal(sub2)) 就可以了, 不要再判断if(isPal(sub1))了,否则会把一个pair算两次
回复 支持 反对

使用道具 举报

 楼主| _yInnovation 发表于 2016-1-26 06:35:56 | 显示全部楼层
xiaobao9 发表于 2016-1-26 06:28
是不是只判断if(isPal(sub2)) 就可以了, 不要再判断if(isPal(sub1))了,否则会把一个pair算两次

不是。 要考虑放前面和放后面。 一个pair里,走到比较短的那个是没法看到更长的那个的。你看inner loop。
回复 支持 反对

使用道具 举报

 楼主| _yInnovation 发表于 2016-1-26 06:48:02 | 显示全部楼层
dietpepsi 发表于 2016-1-26 06:43. 1point3acres.com/bbs
CareerCup上有这道题,Google,9个月前的,http://careercup.com/question?id=4879869638868992

。。。。小弟我只看了看地里这个月的面经。。。。 而且。算法的复杂度应该是n*k^2吧 检查回文串需要O(k).
回复 支持 反对

使用道具 举报

xiaobao9 发表于 2016-1-26 06:50:22 | 显示全部楼层
_yInnovation 发表于 2016-1-26 06:35
不是。 要考虑放前面和放后面。 一个pair里,走到比较短的那个是没法看到更长的那个的。你看inner loop。

对的。是不能删掉一个判断。但以上code会返回[abcd, dcba]和[dcba, abcd]
回复 支持 反对

使用道具 举报

iwofr 发表于 2016-1-26 06:59:06 | 显示全部楼层
. 1point3acres.com/bbs
请问isPal是什么函数啊,是is palindrome的意思吗?为什么要判断substring是不是palindrome啊?
回复 支持 反对

使用道具 举报

dietpepsi 发表于 2016-1-26 07:00:34 | 显示全部楼层
_yInnovation 发表于 2016-1-26 06:48-google 1point3acres
。。。。小弟我只看了看地里这个月的面经。。。。 而且。算法的复杂度应该是n*k^2吧 检查回文串需要O(k).

是的,我觉得worst case怎样也需要nk^2。不过不是因为isPal。
如果你用Manacher进行预处理,那么O(nk)的预处理时间就能让你O(1)来任意查substring回文。
问题在于取prefix再去set里面查,怎样也要k^2所以这个优化就不太有意义了。

补充内容 (2016-1-26 07:08):
suffix复杂度跟prefix一样就不说了.鏈枃鍘熷垱鑷1point3acres璁哄潧

每一个k长度的word,有k个prefix,每一个prefix即使把取它出来算成O(1),去HashSet里面查找还是O(k),因为要算Hashcode。何况取prefix也是要O(k)的,所以怎样都要k^2。
回复 支持 反对

使用道具 举报

dietpepsi 发表于 2016-1-26 07:02:20 | 显示全部楼层
但是如果用比较复杂的数据结构,比如Trie的话,也许有更优解,我没太想清楚
. from: 1point3acres.com/bbs
补充内容 (2016-1-26 07:11):. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
如果用Trie,那么我们查找一个word的O(k)的过程中能知道它所有的prefix是不是在这个集合里,如果像我说的,我们有Manacher做好的预处理,则平均O(nk)是可以做到的。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-10 15:33

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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