一亩三分地论坛

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

扫码关注一亩三分地公众号
查看: 2625|回复: 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>不可以
然后求这样的pair的最长长度,<google, leg>的长度=6+3


我开始没听见他说这个dict是sorted,太紧张了唉。


我只好用了个很sb的方法,用每个单词的最后两个字母建了一个map,然后再扫一遍寻找所有的pair. visit 1point3acres.com for more.
分析了复杂度,要分析的很准确, . from: 1point3acres.com/bbs

后来他提醒了一下是sorted,有吭哧写了个带binary search的版本,BinSearch的函数没来得及写.鏈枃鍘熷垱鑷1point3acres璁哄潧

后来又问could we do better 已经没有时间了, 唉 感觉挺简单一题,写的太慢。

不知道有没有其他很简洁的办法。。LZ弱的跟猪一样. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
. visit 1point3acres.com for more.
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
然后三天之后HR打电话来,说did well,被proceed到Youtube了。有种. Waral 鍗氬鏈夋洿澶氭枃绔,
求问有没有类似经历的小伙伴,Youtube和Google貌似在不同的location,难度有什么不一样么

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



评分

2

查看全部评分

Chi2829 发表于 2016-4-8 07:27:05 | 显示全部楼层
请问楼主sorted的意思是按字母表顺序么?比如例子中的dict应该是 apple, about, google, leg, lemma, time 这样的顺序么?
. 1point 3acres 璁哄潧
补充内容 (2016-4-8 07:44):
如果是这样的话,那能否对字典用每个word的last character为key进行排序得到一个新的序列,然后用类似merge sorted list的方法来遍历?平均复杂度会快些么?
回复 支持 反对

使用道具 举报

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

补充内容 (2016-4-8 12:39):. more info on 1point3acres.com
如果例子是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  ...

对,是按字母表顺序。
关于你说的这个方法,我也不是很确定, 建出一个这样的新序列之后怎么样? .鐣欏璁哄潧-涓浜-涓夊垎鍦
[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. 鍥磋鎴戜滑@1point 3 acres
恩,面试官问了一下能不能省些空间,然后又说这个dict是sorted,我才知道原来是排好序的。时间上没改善, ...

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

使用道具 举报

caiqi8877 发表于 2016-4-9 06:17:35 | 显示全部楼层
进击的菜鸟 发表于 2016-4-8 13:32
恩,面试官问了一下能不能省些空间,然后又说这个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. 1point 3acres 璁哄潧

做法:
1. 将每个单词按后两个字母的字母表顺序排序,得到L1. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
2. 两个指针i, j:一个从头扫描原始序列L,另一个扫描新排列好的序列L1-google 1point3acres
3. 如果L 前两个字母 > L1[j] 的后两个字母,i ++;如果L 前两个字母 < L1[j] 的后两个字母,j++;如果相等,那么check L最后的字母是否等于L1[j] 的第一个字母,如果相等,update result

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

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

使用道具 举报

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) {
  2.                 HashMap<String, String> hm = new HashMap<>();
  3.                 int res = 0;
  4.                 //suppose all input are valid. size >= 2
  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)) {. visit 1point3acres.com for more.
  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.                 }. From 1point 3acres bbs
  17.                 return res;. 1point3acres.com/bbs
  18.         }
复制代码
回复 支持 反对

使用道具 举报

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

使用道具 举报

Littles 发表于 2016-4-29 07:27:49 | 显示全部楼层
  1.         private static int max = 0;. 1point3acres.com/bbs
  2.         public static int findPair(String[] words) {

  3.                 if (words == null || words.length == 0) {. Waral 鍗氬鏈夋洿澶氭枃绔,
  4.                         return 0;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  5.                 }
  6.                 for (int i = 0; i < words.length; i++) {
  7.                         if (words[i].length() < 2) {
  8.                                 continue;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  9.                         }
  10.                         binarySearch(words[i].substring(words[i].length()-2), words, words[i].charAt(0), 0, words.length-1, i);.鏈枃鍘熷垱鑷1point3acres璁哄潧
  11.                 }-google 1point3acres
  12.                 return max;. from: 1point3acres.com/bbs
  13.         }
  14.        
  15.         public static void binarySearch(String lastTwo, String[] words, char c, int lo, int hi, int i) {
  16.                 if (lo > hi) {
  17.                         return;
  18.                 }
  19.                 while (lo <= hi) {
  20.                         int mid = lo + (hi-lo)/2;
  21.                         if (words[mid].length() < 2) {
  22.                                 binarySearch(lastTwo, words, c, lo, mid-1, i);
  23.                                 binarySearch(lastTwo, words, c, mid+1, hi, i);
    . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  24.                         } else if (words[mid].startsWith(lastTwo)) {
  25.                                 if (words[mid].charAt(words[mid].length()-1) == c) {-google 1point3acres
  26.                                         max = Math.max(words[i].length()+words[mid].length(), max);
  27.                                 }
  28.                                 binarySearch(lastTwo, words, c, lo, mid-1, i);
  29.                                 binarySearch(lastTwo, words, c, mid+1, hi, i);
  30.                                 return;
  31.                         } else if (words[mid].substring(0,2).compareTo(lastTwo) < 0) {
  32.                                 lo = mid+1;
  33.                         } else {
  34.                                 hi = mid-1;
  35.                         }
  36.                 }       
  37.         }
复制代码
回复 支持 反对

使用道具 举报

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, 2016-12-8 06:21

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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