一亩三分地论坛

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

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

发一个Google面经

[复制链接] |试试Instant~ |关注本帖
进击的菜鸟 发表于 2016-4-8 04:57:32 | 显示全部楼层 |阅读模式

2016(4-6月) 码农类 博士 全职@Google - Other - 技术电面 |Otherfresh grad应届毕业生

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

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

x
这周二面的Google,太紧张了 脑袋木木的开始聊了聊简历
然后问了很多关于C++的知识,继承多态虚函数之类的,简单提了提虚函数表以及一些hash table的实现

coding题目是这样的,一个字典,里面很多单词,例如
google, leg, about, lemma, apple, time.鏈枃鍘熷垱鑷1point3acres璁哄潧
找这样的pair <A, B>,有两个条件, (1) A单词的后两个字母和B单词的前两个字母一样 (2)A单词的第一个字母和B单词的最后一个字母一样,例如<google, leg>就是一个合格的pair,<apple, lemma>也是一个合格的pair, <about, time>不可以. 鍥磋鎴戜滑@1point 3 acres
然后求这样的pair的最长长度,<google, leg>的长度=6+3

. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
我开始没听见他说这个dict是sorted,太紧张了唉。. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴


我只好用了个很sb的方法,用每个单词的最后两个字母建了一个map,然后再扫一遍寻找所有的pair
分析了复杂度,要分析的很准确,

后来他提醒了一下是sorted,有吭哧写了个带binary search的版本,BinSearch的函数没来得及写

后来又问could we do better 已经没有时间了, 唉 感觉挺简单一题,写的太慢。 . visit 1point3acres.com for more.
. visit 1point3acres.com for more.
不知道有没有其他很简洁的办法。。LZ弱的跟猪一样


然后三天之后HR打电话来,说did well,被proceed到Youtube了。有种
求问有没有类似经历的小伙伴,Youtube和Google貌似在不同的location,难度有什么不一样么

Anyway,已经做好move on的准备了。。总比直接挂了好。。


. visit 1point3acres.com for more.

评分

2

查看全部评分

Chi2829 发表于 2016-4-8 07:27:05 | 显示全部楼层
请问楼主sorted的意思是按字母表顺序么?比如例子中的dict应该是 apple, about, google, leg, lemma, time 这样的顺序么?

补充内容 (2016-4-8 07:44):.1point3acres缃
如果是这样的话,那能否对字典用每个word的last character为key进行排序得到一个新的序列,然后用类似merge sorted list的方法来遍历?平均复杂度会快些么?
回复 支持 反对

使用道具 举报

captor 发表于 2016-4-8 12:28:07 | 显示全部楼层
同问楼主,sorted是什么意思?例子不是sorted的呀。. visit 1point3acres.com for more.

补充内容 (2016-4-8 12:39):
如果例子是googlz, lag, lbg, lcg,..... lzg.我觉得binarysearch,时间上也没什么改善吧。
建立两个map来hash, 一个是hash 首字母+最后两个字母,第二个hash头两个字母+最后一个字母,边hash边找,记录最长pair
回复 支持 反对

使用道具 举报

 楼主| 进击的菜鸟 发表于 2016-4-8 12:29:42 | 显示全部楼层
captor 发表于 2016-4-8 12:28
同问楼主,sorted是什么意思?例子不是sorted的呀。

不好意思,写的例子不是很清楚,sorted就是说这个vector<string>是按照字母表的顺序排序的,就是“ apple, about, google, leg, lemma, time” 这样
回复 支持 反对

使用道具 举报

 楼主| 进击的菜鸟 发表于 2016-4-8 12:34:01 | 显示全部楼层
Chi2829 发表于 2016-4-8 07:27
请问楼主sorted的意思是按字母表顺序么?比如例子中的dict应该是 apple, about, google, leg, lemma, time  ...
. visit 1point3acres.com for more.
对,是按字母表顺序。
关于你说的这个方法,我也不是很确定, 建出一个这样的新序列之后怎么样?
[apple, about, google, leg, lemma, time]
扫描第一个apple, 后两个字母是le,然后Binary Search到leg到lemma这个范围,我面的时候写的就是挨个检查。你说的这个merge list是啥意思?没太明白 可以举个栗子么
回复 支持 反对

使用道具 举报

 楼主| 进击的菜鸟 发表于 2016-4-8 13:32:50 | 显示全部楼层
captor 发表于 2016-4-8 12:28
同问楼主,sorted是什么意思?例子不是sorted的呀。

补充内容 (2016-4-8 12:39):
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
恩,面试官问了一下能不能省些空间,然后又说这个dict是sorted,我才知道原来是排好序的。时间上没改善,只是不用build map

嗯 ~~你补充内容里的这个方法我感觉挺好的~~
回复 支持 反对

使用道具 举报

captor 发表于 2016-4-8 22:34:39 | 显示全部楼层
进击的菜鸟 发表于 2016-4-8 13:32
恩,面试官问了一下能不能省些空间,然后又说这个dict是sorted,我才知道原来是排好序的。时间上没改善, ...

哦哦,原来是要省空间。
回复 支持 反对

使用道具 举报

caiqi8877 发表于 2016-4-9 06:17:35 | 显示全部楼层
进击的菜鸟 发表于 2016-4-8 13:32. from: 1point3acres.com/bbs
恩,面试官问了一下能不能省些空间,然后又说这个dict是sorted,我才知道原来是排好序的。时间上没改善, ...

楼主,节省空间体现在哪里呢,不太明白
回复 支持 反对

使用道具 举报

 楼主| 进击的菜鸟 发表于 2016-4-9 11:10:52 | 显示全部楼层
caiqi8877 发表于 2016-4-9 06:17
楼主,节省空间体现在哪里呢,不太明白

不用建map存map了呀
回复 支持 反对

使用道具 举报

Chi2829 发表于 2016-4-15 11:17:23 | 显示全部楼层
进击的菜鸟 发表于 2016-4-8 12:34
对,是按字母表顺序。
关于你说的这个方法,我也不是很确定, 建出一个这样的新序列之后怎么样?
[app ...

不好意思好久没上。看了半天才想起来我自己当时的想法。。。

已知:input已经有序了,序列L
-google 1point3acres
做法:
1. 将每个单词按后两个字母的字母表顺序排序,得到L1
2. 两个指针i, j:一个从头扫描原始序列L,另一个扫描新排列好的序列L1. 1point3acres.com/bbs
3. 如果L 前两个字母 > L1[j] 的后两个字母,i ++;如果L 前两个字母 < L1[j] 的后两个字母,j++;如果相等,那么check L最后的字母是否等于L1[j] 的第一个字母,如果相等,update result

这个做法的问题是,如果有很多前两个字母重复的情况的话,复杂度还是挺高,可以考虑其他的优化,例如leetcode 288类似的处理。具体没有想好。. 鍥磋鎴戜滑@1point 3 acres

楼主最近有想到好的解法么?
回复 支持 反对

使用道具 举报

woridage1 发表于 2016-4-15 20:44:11 | 显示全部楼层
做一个函数取后两个字母,然后遍历所有单词,相同后缀中最长的记录一下长度,取出这个后缀,用折半查找从序列里找到位置,然后前后比较,比较出最大数字,取出来相加。遍历加折半  nlogn,不知道这样做可以不可以,请指教~
回复 支持 反对

使用道具 举报

woridage1 发表于 2016-4-15 20:52:49 | 显示全部楼层
或者做一个map<string, pair<int 前缀最大,int 后缀最大>> 遍历一遍,每个单词取前缀存到map对应string的pair->first,取后缀存到对应pair->second。当然每次都存的是max值,这个就涉及到一个问题,如果一个单词前缀和后缀相同的话,能不能算一对,不能的话就得把这个特殊情况给处理一下。
回复 支持 反对

使用道具 举报

兔流感阿义 发表于 2016-4-18 18:46:32 | 显示全部楼层
  1.         public int longestPair(List<String> input) {. 1point 3acres 璁哄潧
  2.                 HashMap<String, String> hm = new HashMap<>();
  3.                 int res = 0;
  4.                 //suppose all input are valid. size >= 2. more info on 1point3acres.com
  5.                 for (String s : input) {
  6.                         String _key = s.substring(s.length() - 1) + s.substring(0, 2);
  7.                         System.out.println(_key);
  8.                         if (hm.containsKey(_key)) {
  9.                                 res = Math.max(s.length() + hm.get(_key).length(), res);
  10.                         }
  11.                         String key = s.substring(0, 1) + s.substring(s.length() - 2);
  12.                         String value = hm.get(key);
  13.                         if (value == null || value.length() < s.length()) {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  14.                                 hm.put(key, s);
  15.                         }
  16.                 }
  17.                 return res;. Waral 鍗氬鏈夋洿澶氭枃绔,
  18.         }
复制代码
回复 支持 反对

使用道具 举报

houqingniao 发表于 2016-4-26 03:35:39 | 显示全部楼层
最长的 apple+lemma吧?
回复 支持 反对

使用道具 举报

Littles 发表于 2016-4-29 07:27:49 | 显示全部楼层
  1.         private static int max = 0;
  2.         public static int findPair(String[] words) {
  3. . 1point 3acres 璁哄潧
  4.                 if (words == null || words.length == 0) { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  5.                         return 0;
  6.                 }
  7.                 for (int i = 0; i < words.length; i++) {
  8.                         if (words[i].length() < 2) {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  9.                                 continue;
  10.                         }
  11.                         binarySearch(words[i].substring(words[i].length()-2), words, words[i].charAt(0), 0, words.length-1, i);
  12.                 }
  13.                 return max;. Waral 鍗氬鏈夋洿澶氭枃绔,
  14.         }
  15.        
  16.         public static void binarySearch(String lastTwo, String[] words, char c, int lo, int hi, int i) {
  17.                 if (lo > hi) {
  18.                         return;
  19.                 }
  20.                 while (lo <= hi) {-google 1point3acres
  21.                         int mid = lo + (hi-lo)/2;
  22.                         if (words[mid].length() < 2) {
  23.                                 binarySearch(lastTwo, words, c, lo, mid-1, i);
  24.                                 binarySearch(lastTwo, words, c, mid+1, hi, i);
  25.                         } else if (words[mid].startsWith(lastTwo)) {
  26.                                 if (words[mid].charAt(words[mid].length()-1) == c) {
  27.                                         max = Math.max(words[i].length()+words[mid].length(), max);
  28.                                 }
  29.                                 binarySearch(lastTwo, words, c, lo, mid-1, i);
  30.                                 binarySearch(lastTwo, words, c, mid+1, hi, i);
  31.                                 return;
  32.                         } else if (words[mid].substring(0,2).compareTo(lastTwo) < 0) {. 1point3acres.com/bbs
  33.                                 lo = mid+1;
  34.                         } else {
  35.                                 hi = mid-1;
  36.                         }
  37.                 }       
  38.         }
复制代码
回复 支持 反对

使用道具 举报

wangmengcathy 发表于 2016-4-30 01:12:24 | 显示全部楼层

一次遍历需要俩map吧
回复 支持 反对

使用道具 举报

jjustc 发表于 2016-6-17 05:33:47 | 显示全部楼层
这题如果 要省时间 那可以用俩map 如果 要省空间可以用 binary search

问一下 最后面试官说could we do better 是指的什么呀?…… 想不出哪方面可以还优化了呢。。。。谢谢!
回复 支持 反对

使用道具 举报

何打发123 发表于 2016-10-23 03:05:47 | 显示全部楼层
感谢分享! 请问楼主不论是建立map还是二分找 最坏情况复杂度都可能是n^2对吗?~ 就是所有单词的前两位都和后两位相同?~
回复 支持 反对

使用道具 举报

何打发123 发表于 2016-10-23 03:12:40 | 显示全部楼层

这个map的value应该是arraylist 因为可能有多个string都是这样的开头加结尾0.0
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2017-1-22 01:52

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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