一亩三分地论坛

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

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

Twitter 电话技术面试(刚刚完事就来报面经)

[复制链接] |试试Instant~ |关注本帖
老冯123 发表于 2015-9-30 05:56:48 | 显示全部楼层 |阅读模式

2015(7-9月) 码农类 硕士 全职@Twitter - 网上海投 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
Twitter 电面 刚完事,面经奉上。

给一组string "a a b b c c beta beta beta alpha"
n = 2;
要求返回一个List<String> 含有的是出现次数最多的n个, 也就是说如果n=1 list中只有出现次数最多的那个也就是beta, 如果是n=2, list当中出现beta, a b c, 因为a b c都出现两次,算是第二出线多的。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
所以就是n是几,就返回几个数吧,按出现频率来。

开始的思路是, hashmap, + array存出现次数,再arrays.sort(),在获取hashmap当中的key, 印度小哥说不好, 你再想想,我马上说用一个int max 来记录出现次数最多的,找到最多的然后再找第二多的。. Waral 鍗氬鏈夋洿澶氭枃绔,
小哥说,不错,这个方法处理数据不大的时候是可以得,接着问,能不能用one pass的形式?
想了一会,疑问句:“PriorityQueue?”  小哥说,嗯,说说吧,就是每个出现单词出现的次数都扔进priorityQueue里面,它自动排序嘛
小哥说,那你打代码吧
这里还有一个情况是每一个word之间都是有空格的,两个pointer, start end一个数空格 一个不数空格来获取每一个word。. more info on 1point3acres.com

打完之后,发现小哥说了句:“that looks good for me” 心里搜一个口气。
最后小哥又让我写了几个Unit test。
我就随便考虑了三种请况。  1. s = null || ""  2. s = "a b b" n =1   3. s = "a b b a b c" n =2
然后用assert(result.get(i从0到N)).equals(目标单词)
小哥说不错。-google 1point3acres
求人品,要求不多,让我去onsite见识一下场面就可以了。
(准备的豆子问题没有考,也没有自我介绍,上来就码,弄题意弄了将近十分钟,一是信号不算天好,二是印度口音懂的人都懂)



补充内容 (2015-9-30 09:50):
被拒,唉

评分

4

查看全部评分

bobzhang2004 发表于 2015-9-30 06:22:11 来自手机 | 显示全部楼层
楼主怎么通过数字找到string呢?定义一个class?如果数量相同,怎么用priorityqueue?
回复 支持 反对

使用道具 举报

wegnahz 发表于 2015-9-30 08:48:50 | 显示全部楼层
这题可以linear吧,把(word, freq) 转到 (freq, set(word)),然后展开到一个vector里,用quick select选前k大。
回复 支持 反对

使用道具 举报

wegnahz 发表于 2015-9-30 08:48:57 | 显示全部楼层
这题可以linear吧,把(word, freq) 转到 (freq, set(word)),然后展开到一个vector里,用quick select选前k大。
回复 支持 反对

使用道具 举报

 楼主| 老冯123 发表于 2015-9-30 09:51:06 | 显示全部楼层
bobzhang2004 发表于 2015-9-30 06:22
楼主怎么通过数字找到string呢?定义一个class?如果数量相同,怎么用priorityqueue?

数量相同就都要
回复 支持 反对

使用道具 举报

tbu 发表于 2015-9-30 09:59:01 | 显示全部楼层
"用一个int max 来记录出现次数最多的,找到最多的然后再找第二多的" 这段没看懂哇, LZ可以再解释下你的方法吗?
回复 支持 反对

使用道具 举报

林微熙 发表于 2015-9-30 10:21:31 | 显示全部楼层
这么快就有结果啊
回复 支持 反对

使用道具 举报

yemingliang 发表于 2015-9-30 10:30:21 | 显示全部楼层
能问下楼主是自己投的还是内推拿到面试的?
回复 支持 反对

使用道具 举报

LawranceH 发表于 2015-9-30 10:44:58 | 显示全部楼层
楼主感觉是什么原因挂了? 看你分享的过程 感觉没问题啊。
回复 支持 反对

使用道具 举报

returning 发表于 2015-12-7 09:18:21 | 显示全部楼层
用priority queue的话,如何一遍更新count呢?你的解法是已经获得每个单词出现的次数,然后再放进priority queue,对吧?其实我觉得,如果对空间没要求的话,可以hash map加bst,hashMap的key是单词,value是出现的次数,bst里面维护的是struct{count,key},按照出现的count的大小排序,如果出现的次数相同,那么按照key排序,所以每遇到一个新的单词,就是去更新bst,同时更新hashmap。这样虽然可以一次遍历就搞定,但是空间开销大。和你的方法比较时间的话,假设一共有K个单词,其中N个单词是不同的,heapfy开销是N,从heap里面取出n个最大一共开销是N+lgN*n,一共开销是K+N+lgN*n。如果是我的bst的办法,每次更新新的key,其实开销是大于你的方法的。结论就是,你被阿三黑了。
回复 支持 反对

使用道具 举报

ohuohuo 发表于 2016-3-22 03:41:42 | 显示全部楼层
wegnahz 发表于 2015-9-30 08:48
这题可以linear吧,把(word, freq) 转到 (freq, set(word)),然后展开到一个vector里,用quick select选前k ...

光quick select不就nlogn了吗。。
回复 支持 反对

使用道具 举报

ohuohuo 发表于 2016-3-22 04:47:53 | 显示全部楼层
可以用一个HashMap<String,Integer> 和一个TreeMap<Integer,Set<String>> 来搞。走一遍输入的string,hashmap里存《单词,频数》,treemap里存《频数,Set《单词》》。这样最后过一遍n,就可以了。linear的复杂度
回复 支持 反对

使用道具 举报

hison7463 发表于 2016-3-23 09:35:41 | 显示全部楼层
ohuohuo 发表于 2016-3-22 04:47. more info on 1point3acres.com
可以用一个HashMap 和一个TreeMap 来搞。走一遍输入的string,hashmap里存《单词,频数》,treemap里存《频 ...

TreeMap的插入可不是O(1)时间哦,所以你在hashmap转到treemap那一步的时候实际上是nlogn了,quickselect在平均情况下是O(n)
回复 支持 反对

使用道具 举报

ohuohuo 发表于 2016-3-23 11:10:12 | 显示全部楼层
hison7463 发表于 2016-3-23 09:35
TreeMap的插入可不是O(1)时间哦,所以你在hashmap转到treemap那一步的时候实际上是nlogn了,quickselec ...

对,red-black tree是nlogn,不知道怎么居然忽略了
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-5 01:14

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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