聊聊跟三哥三姐面试和共事的经历

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
把贵司招聘信息放这里
查看: 7994|回复: 70
收起左侧

google二面

[复制链接] |试试Instant~ |关注本帖
mm豆 发表于 2015-4-18 00:40:01 | 显示全部楼层 |阅读模式

2015(4-6月) 码农类General 硕士 全职@Google - 内推 - 技术电面  | Pass | fresh grad应届毕业生

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

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

x
input: 一个文件,包含了很多单词,可以全部装入内存一个target number : t
output: 一个单词的最小set,这些单词的出现的频率的总和大于等于t
比如,文件中 A 500次,B 300, C 200, D100, t = 1000.  结果为 A,B, C.
实际上就是求频率最高的一些单词,这个单词的总频率大于target。 我用了selection algorithm去解决的这个问题。

评分

2

查看全部评分

 楼主| mm豆 发表于 2015-5-29 22:37:22 | 显示全部楼层
public static List<Integer> getPopularQueries(int[] array, int target) {. 1point3acres
        ArrayList<Integer> ret=  selection(array, target, 0, array.length - 1);
}.本文原创自1point3acres论坛
private ArrayList<Integer> selection(int[] array, int target, int start, int end){
        if(start == end) {
return  getRet(array, 0, start);
                //if(target == array[start]) return getRet(array, 0, start);
                //else if(target < array[start]) return getRet(array, 0, start); sum of 0 ~start > target; .1point3acres网
                //else return getRet(array,0, start);
}else if (start > end){
        . visit 1point3acres for more.
}
        int p = new Random().getNextInt(end - start) + start;. 围观我们@1point 3 acres
        int pivot = array[p];
        swap(array, start, p);. 1point 3acres 论坛
        int pre = start; // will be num < privot
        for(int i = start + 1; i < end; i++){
        if(array[i] > pivot) swap(array, ++pre, i);
}. 牛人云集,一亩三分地
// will arr[pre]> pivot ? pre = start arr[pre] = pivot; pre > start; ar[pre] > pivot
swap(array,start, pre);
int sum = getSum(array,start, pre);. from: 1point3acres
if(sum == k) return getRet(array, 0, pre);
else if(sum < k) return selection(array, target - sum, pre + 1, end);
else return selection(array, target, start, pre);
}
回复 支持 反对

使用道具 举报

Neil_Acton 发表于 2015-11-25 11:47:28 | 显示全部楼层
sevengram 发表于 2015-10-27 15:17
我把楼主的核心程序重新写一下,以供大家参考:

.本文原创自1point3acres论坛vector select_sum_over_target(vector &v, int target) ...

看了一遍代码,这个做法就算不考虑要求返回的是string 不是 frequency 也是错的。
. 1point 3acres 论坛
写几个test case 多跑几遍就能发现问题了。  问题出在 sum > target 的时候,直接移到左边是不对的。这样没有记录潜在解,可能有解得出了无解。

综合感觉,这个题目可能理解有问题。 这题目有quick select是个大胆的想法. from: 1point3acres
但实际上有些牵强。

我的感觉就是一个 map + sort的题
回复 支持 1 反对 0

使用道具 举报

muancy 发表于 2015-4-18 00:43:16 | 显示全部楼层
恭喜楼主,楼主加油~
回复 支持 反对

使用道具 举报

 楼主| mm豆 发表于 2015-4-18 00:52:18 | 显示全部楼层
muancy 发表于 2015-4-18 00:43. visit 1point3acres for more.
恭喜楼主,楼主加油~

谢谢啦~ 也祝你早日拿到心仪的offer
回复 支持 反对

使用道具 举报

sunfish 发表于 2015-4-18 00:54:47 | 显示全部楼层
恭喜mm,mm怎么啥时去onsite?
回复 支持 反对

使用道具 举报

 楼主| mm豆 发表于 2015-4-18 00:55:38 | 显示全部楼层
sunfish 发表于 2015-4-18 00:54
恭喜mm,mm怎么啥时去onsite?

还没定,你什么时候去onsite?
回复 支持 反对

使用道具 举报

sunfish 发表于 2015-4-18 01:00:44 | 显示全部楼层
mm豆 发表于 2015-4-18 00:55
还没定,你什么时候去onsite?
. more info on 1point3acres
我还有一周...要悲剧的感觉
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

 楼主| mm豆 发表于 2015-4-18 01:04:21 | 显示全部楼层
sunfish 发表于 2015-4-18 01:00
我还有一周...要悲剧的感觉

好好准备,我觉得你挺厉害的,马上就offer了
回复 支持 反对

使用道具 举报

houqingniao 发表于 2015-4-18 01:17:10 | 显示全部楼层
greedy 从频率最高的往下找 可以吧
回复 支持 反对

使用道具 举报

 楼主| mm豆 发表于 2015-4-18 01:19:30 | 显示全部楼层
houqingniao 发表于 2015-4-18 01:17
greedy 从频率最高的往下找 可以吧

那要先排序,时间复杂度不通过
回复 支持 反对

使用道具 举报

mkcing 发表于 2015-4-18 02:15:19 | 显示全部楼层
既然可以全部装入内存,用一个map<String, Integer>, 来对每个单词计数,一旦发现某个单词的频率超过 t, 就加入输出的set,   run time 是 O(n)  , 楼主,这样做,可行吗?

补充内容 (2015-4-18 02:16):
靠,题意理解错了,不要嘲笑我
回复 支持 反对

使用道具 举报

mkcing 发表于 2015-4-18 02:24:18 | 显示全部楼层
靠,这个题将 quicksort 改造下, run time可以在 O(n)内
回复 支持 反对

使用道具 举报

houqingniao 发表于 2015-4-18 02:47:47 | 显示全部楼层
mm豆 发表于 2015-4-18 01:19. 一亩-三分-地,独家发布
那要先排序,时间复杂度不通过
.留学论坛-一亩-三分地
就是keep选kth 高的,直到达到t。。

那应该怎么做啊?
回复 支持 反对

使用道具 举报

sunfish 发表于 2015-4-18 02:50:11 | 显示全部楼层
mm豆 发表于 2015-4-18 01:04
好好准备,我觉得你挺厉害的,马上就offer了

mm真是正能量,mm也加油!
回复 支持 反对

使用道具 举报

 楼主| mm豆 发表于 2015-4-18 04:48:08 | 显示全部楼层
houqingniao 发表于 2015-4-18 02:47
就是keep选kth 高的,直到达到t。。
. visit 1point3acres for more.
那应该怎么做啊?

是的 就是选择算法
回复 支持 反对

使用道具 举报

wangxinlei 发表于 2015-4-28 09:22:38 来自手机 | 显示全部楼层
没太理解意思啊?
回复 支持 反对

使用道具 举报

wangxinlei 发表于 2015-4-28 09:24:16 来自手机 | 显示全部楼层
是不是先hashtable统计每个词的出现个数,再把hashtable里的数初始化到maxheap中,然后每次pop?
回复 支持 反对

使用道具 举报

 楼主| mm豆 发表于 2015-4-30 12:04:54 | 显示全部楼层
wangxinlei 发表于 2015-4-28 09:24
是不是先hashtable统计每个词的出现个数,再把hashtable里的数初始化到maxheap中,然后每次pop?

先hashtable统计每个词的出现个数, 是的。用heap 也可以,但是选择算法的时间复杂度更好
回复 支持 反对

使用道具 举报

wangxinlei 发表于 2015-5-1 05:36:10 | 显示全部楼层
mm豆 发表于 2015-4-30 12:04. 一亩-三分-地,独家发布
先hashtable统计每个词的出现个数, 是的。用heap 也可以,但是选择算法的时间复杂度更好

但是选择算法(quick select, median of medians)都是选第k个大的元素,然后再把array里所有小于这个的数字都加起来。但是这道题你事先不会知道要选择多少个元素,就是k不知道啊,所以要怎么应用呢??
回复 支持 反对

使用道具 举报

 楼主| mm豆 发表于 2015-5-1 08:39:52 | 显示全部楼层
wangxinlei 发表于 2015-5-1 05:36-google 1point3acres
但是选择算法(quick select, median of medians)都是选第k个大的元素,然后再把array里所有小于这个的数 ...

每次选择的时候,将left part相加和k比大小
回复 支持 反对

使用道具 举报

小桶 发表于 2015-5-2 09:11:16 | 显示全部楼层
先扫一遍所有单词,放到字典里统计次数,这个用O(n). 一亩-三分-地,独家发布
把统计结果扔到一个数组里,O(k),k是不同单词的个数,最好再shuffle一下这个数组?. 一亩-三分-地,独家发布
然后quick select,每次算左边一部分的和,和t比较。一般情况下,O(n)。
不过我们要找的和可能要比target大,而不是相等,所以边界比较的时候要多注意一下?
大概是这个思路不,LZ?. Waral 博客有更多文章,

补充内容 (2015-5-1 19:11):
quick select是O(k)
回复 支持 反对

使用道具 举报

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2018-5-22 18:41

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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