一亩三分地论坛

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

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

google二面

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

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

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

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

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){
       
}
        int p = new Random().getNextInt(end - start) + start;
        int pivot = array[p];
        swap(array, start, p);
        int pre = start; // will be num < privot
        for(int i = start + 1; i < end; i++){
        if(array[i] > pivot) swap(array, ++pre, i);
}-google 1point3acres
// will arr[pre]> pivot ? pre = start arr[pre] = pivot; pre > start; ar[pre] > pivot
swap(array,start, pre);
int sum = getSum(array,start, pre);
if(sum == k) return getRet(array, 0, pre);
else if(sum < k) return selection(array, target - sum, pre + 1, end);. 1point 3acres 璁哄潧
else return selection(array, target, start, pre);
}
回复 支持 反对

使用道具 举报

Neil_Acton 发表于 2015-11-25 11:47:28 | 显示全部楼层
sevengram 发表于 2015-10-27 15:17
我把楼主的核心程序重新写一下,以供大家参考:. more info on 1point3acres.com
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
vector select_sum_over_target(vector &v, int target) ...

看了一遍代码,这个做法就算不考虑要求返回的是string 不是 frequency 也是错的。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

写几个test case 多跑几遍就能发现问题了。  问题出在 sum > target 的时候,直接移到左边是不对的。这样没有记录潜在解,可能有解得出了无解。

综合感觉,这个题目可能理解有问题。 这题目有quick select是个大胆的想法
但实际上有些牵强。
.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
恭喜楼主,楼主加油~

谢谢啦~ 也祝你早日拿到心仪的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?
. Waral 鍗氬鏈夋洿澶氭枃绔,
我还有一周...要悲剧的感觉
回复 支持 反对

使用道具 举报

 楼主| 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)  , 楼主,这样做,可行吗?. 1point 3acres 璁哄潧

补充内容 (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. more info on 1point3acres.com
那要先排序,时间复杂度不通过

就是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?

先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
但是选择算法(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大,而不是相等,所以边界比较的时候要多注意一下?-google 1point3acres
大概是这个思路不,LZ?

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

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-7 03:57

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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