一亩三分地论坛

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

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

google 电面

[复制链接] |试试Instant~ |关注本帖
yezhangpost 发表于 2016-10-30 01:01:38 | 显示全部楼层 |阅读模式

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

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

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

x
10/25 google 电面,

中国小哥电面,人非常的nice,题目超乎想象的简单。

第一题,从文件中读出字符串,输出字符串,但是重复的字符串只输出一次。
             我的解释(1) Hashset (2) sort (3)create trie, google的电面总是想的很复杂,说了trie,并且说了trie比hashSet省空间,但是小哥没有让接着说。做了第一solution的代码,好简单,不敢相信。. 1point 3acres 璁哄潧
              follow up  文件非常大,不能load 到memory 怎么办。 我的solution,大的文件切成若干小块,把小块load到memory,sort,再写回disk。然后再用priorityQueue merge sort各个小块。重复的skip-google 1point3acres
              小哥表示对这个方案满意
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
第二题  给一个数组,里面有正负数,让找到不相邻的两个数,他们的和最大,输出最大和。
            dp解决,很简单。

题目超乎想象的简单,第二天通知onsite. 鍥磋鎴戜滑@1point 3 acres

评分

2

查看全部评分

本帖被以下淘专辑推荐:

  • · google|主题: 57, 订阅: 5
jyt0532 发表于 2016-10-30 13:14:58 | 显示全部楼层
不需要dp的 array 一個max就夠了 max[i] 記錄 num[0...i]最大值
max_sum = max(max_sum, num[i] + max[i-2])
回复 支持 3 反对 0

使用道具 举报

美女的 发表于 2016-10-30 01:26:20 | 显示全部楼层
过几天面,谢谢楼主分享
回复 支持 反对

使用道具 举报

a598165394 发表于 2016-10-30 08:22:21 | 显示全部楼层
求问楼主为什么merge sort小块可以有用,假设每个小块是abcd , abcd, abcd。sort每个小块并不能去重吧
回复 支持 反对

使用道具 举报

 楼主| yezhangpost 发表于 2016-10-30 08:47:02 | 显示全部楼层
a598165394 发表于 2016-10-30 08:22
求问楼主为什么merge sort小块可以有用,假设每个小块是abcd , abcd, abcd。sort每个小块并不能去重吧

merge 就是为了去重,你看看external sort 怎么做的,网上有介绍。
回复 支持 反对

使用道具 举报

a598165394 发表于 2016-10-30 08:51:40 | 显示全部楼层
yezhangpost 发表于 2016-10-30 08:47
merge 就是为了去重,你看看external sort 怎么做的,网上有介绍。
. 1point 3acres 璁哄潧
好的额,谢楼主。祝onsite顺利~
回复 支持 反对

使用道具 举报

a598165394 发表于 2016-10-30 08:51:49 | 显示全部楼层
yezhangpost 发表于 2016-10-30 08:47
merge 就是为了去重,你看看external sort 怎么做的,网上有介绍。
.1point3acres缃
好的额,谢楼主。祝onsite顺利~
回复 支持 反对

使用道具 举报

mingruiyrh 发表于 2016-10-30 09:07:07 | 显示全部楼层
问一下楼主内推后多久通知电面的啊?
回复 支持 反对

使用道具 举报

 楼主| yezhangpost 发表于 2016-10-30 09:15:43 | 显示全部楼层
mingruiyrh 发表于 2016-10-30 09:07
问一下楼主内推后多久通知电面的啊?

我很快,内推后一天就让做oa了,oa做完了也就1天就通知电话面试了
回复 支持 反对

使用道具 举报

syjohnson 发表于 2016-10-30 10:30:31 | 显示全部楼层
请问lz第二题, 我想到的是开2个数组,一个max[i]表示前i个数里最大的数,另一个dp[i]表示前i个数里两数相加最大和,dp[i] = Math.max(dp[i - 1], nums[i] + dp[i - 2]), 最终return dp[len - 1]。请问你有更好的优化方法吗?总觉得space complexity可以更优
回复 支持 反对

使用道具 举报

 楼主| yezhangpost 发表于 2016-10-30 11:19:58 | 显示全部楼层
syjohnson 发表于 2016-10-30 10:30
请问lz第二题, 我想到的是开2个数组,一个max表示前i个数里最大的数,另一个dp表示前i个数里两数相加最大 ...

空间可以优化,你再想想,不需要一个extra 数组。只是维护当前最大两个不相邻数的和,当前除了这个元素的最大值,当前包含这个元素的最大值。
回复 支持 反对

使用道具 举报

syjohnson 发表于 2016-10-30 11:40:34 | 显示全部楼层
yezhangpost 发表于 2016-10-30 11:19
空间可以优化,你再想想,不需要一个extra 数组。只是维护当前最大两个不相邻数的和,当前除了这个元素的 ...

你这样的话必须是数组里没有重复元素吧?不然像[1,2,5,3,5]走到最后一个5,发现prevMax = 5, cur = 5, cur ==prevMax,不是默认就不加了?. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
另外请问你的意思是只开一个extra array还是根本不用开extra array呢?麻烦解释下你的优化吧,谢谢!
回复 支持 反对

使用道具 举报

syjohnson 发表于 2016-10-30 23:06:24 | 显示全部楼层
jyt0532 发表于 2016-10-30 13:14
不需要dp的 array 一個max就夠了 max 記錄 num[0...i]最大值
max_sum = max(max_sum, num + max)

多谢!终于想通了
回复 支持 反对

使用道具 举报

发表于 2016-10-31 12:20:55 | 显示全部楼层
第二题空间上不需要数组,就两个变量就行。
prevMax,用来对应num数组里0..i-2的最大值,
ans,用来记录当前找到的最大和,.鏈枃鍘熷垱鑷1point3acres璁哄潧
然后用 ans = Math.max(ans, prevMax + num[i])
回复 支持 反对

使用道具 举报

发表于 2016-10-31 12:32:38 | 显示全部楼层
@yezhangpost
请问楼主,第一题内存和硬盘储存转换这部分有没有推荐的学习资料?谢谢!
挺多地方不明白,大文件分成小文件之后,能不能小文件读进来存到hashset,然后直接把hashset的内容储存到硬盘?
另外为什么能用priorityQueue merge sort所有小文件?priorityQueue不也是在内存里运行的吗?假如每个小文件里的string不重复,会不会仍然导致内存溢出?. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
回复 支持 反对

使用道具 举报

cezheng2 发表于 2016-10-31 20:09:42 | 显示全部楼层
我也觉得楼主说的priority queue merge sort众多小文件比较奇怪, 我的想法是先把整个大文件读一次每读一个计算hash值存到对应的小文件里,然后相同的字串肯定在同一个文件里,再一个一个文件读取输出,重复的跳过 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

补充内容 (2016-10-31 20:13):
哦,表示理解错了楼主的意思。。。priority queue存的是每个小块当前的进度,每次选出最小的一个输出,然后保存上一个输出的值,然后下一个取出的值是上个输出的值的话就跳过
回复 支持 反对

使用道具 举报

chaosMonkey 发表于 2016-11-3 00:47:58 | 显示全部楼层
第二个题这么写应该没问题吧. visit 1point3acres.com for more.
  1. int adjacentMax(vector<int>& nums){
  2.     int maxPre = nums[0];
  3.     int res = INT_MIN;
  4.     for(int i = 2; i < nums.size(); i++){
  5.         res = max(res, nums[i] + maxPre);
  6.         maxPre = max(maxPre, nums[i - 1]);
  7.     } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  8.     return res;
  9. }
复制代码
回复 支持 反对

使用道具 举报

fightinus 发表于 2016-11-21 06:34:06 | 显示全部楼层
lz你电面feedback给的好快的,第二天就给了。。我15号面的,现在还没有。。估计药丸。。。我的也是超级简单。美国小哥面的。
回复 支持 反对

使用道具 举报

忆梦前尘 发表于 6 天前 | 显示全部楼层
a598165394 发表于 2016-10-29 16:51. 1point 3acres 璁哄潧
好的额,谢楼主。祝onsite顺利~

你好,请问你最后找到外部排序的教程了么。。。我隐约感觉排序是对string的hashcode排序,但是理解还不到位。。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-4 06:01

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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