《数据科学面试40+真题讲解》,K神本年度最后一次开课


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 7785|回复: 70
收起左侧

google二面

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

2015(4-6月) 码农类 硕士 全职@Google - 内推 - 技术电面 |Passfresh 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) {
        ArrayList<Integer> ret=  selection(array, target, 0, array.length - 1);
}
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;
                //else return getRet(array,0, start);
}else if (start > end){ 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
       
}. from: 1point3acres.com/bbs
        int p = new Random().getNextInt(end - start) + start;
        int pivot = array[p];. 1point3acres.com/bbs
        swap(array, start, p);. Waral 鍗氬鏈夋洿澶氭枃绔,
        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. 1point 3acres 璁哄潧
swap(array,start, pre);. visit 1point3acres.com for more.
int sum = getSum(array,start, pre);. Waral 鍗氬鏈夋洿澶氭枃绔,
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
我把楼主的核心程序重新写一下,以供大家参考:. 鍥磋鎴戜滑@1point 3 acres
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
vector select_sum_over_target(vector &v, int target) ...

看了一遍代码,这个做法就算不考虑要求返回的是string 不是 frequency 也是错的。

写几个test case 多跑几遍就能发现问题了。  问题出在 sum > target 的时候,直接移到左边是不对的。这样没有记录潜在解,可能有解得出了无解。
. From 1point 3acres bbs
综合感觉,这个题目可能理解有问题。 这题目有quick select是个大胆的想法. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
但实际上有些牵强。
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
我的感觉就是一个 map + sort的题
回复 支持 1 反对 0

使用道具 举报

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

使用道具 举报

 楼主| mm豆 发表于 2015-4-18 00:52:18 | 显示全部楼层
muancy 发表于 2015-4-18 00:43.鏈枃鍘熷垱鑷1point3acres璁哄潧
恭喜楼主,楼主加油~

谢谢啦~ 也祝你早日拿到心仪的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?

我还有一周...要悲剧的感觉
回复 支持 反对

使用道具 举报

 楼主| mm豆 发表于 2015-4-18 01:04:21 | 显示全部楼层
sunfish 发表于 2015-4-18 01:00
我还有一周...要悲剧的感觉
. more info on 1point3acres.com
好好准备,我觉得你挺厉害的,马上就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。。.鐣欏璁哄潧-涓浜-涓夊垎鍦
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
那应该怎么做啊?

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

使用道具 举报

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?
. 1point 3acres 璁哄潧
先hashtable统计每个词的出现个数, 是的。用heap 也可以,但是选择算法的时间复杂度更好
回复 支持 反对

使用道具 举报

wangxinlei 发表于 2015-5-1 05:36:10 | 显示全部楼层
mm豆 发表于 2015-4-30 12:04.鏈枃鍘熷垱鑷1point3acres璁哄潧
先hashtable统计每个词的出现个数, 是的。用heap 也可以,但是选择算法的时间复杂度更好
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
但是选择算法(quick select, median of medians)都是选第k个大的元素,然后再把array里所有小于这个的数字都加起来。但是这道题你事先不会知道要选择多少个元素,就是k不知道啊,所以要怎么应用呢??
回复 支持 反对

使用道具 举报

 楼主| mm豆 发表于 2015-5-1 08:39:52 | 显示全部楼层
wangxinlei 发表于 2015-5-1 05:36
但是选择算法(quick select, median of medians)都是选第k个大的元素,然后再把array里所有小于这个的数 ...
. Waral 鍗氬鏈夋洿澶氭枃绔,
每次选择的时候,将left part相加和k比大小
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-11-23 23:19

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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