一亩三分地论坛

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

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

Google interview

[复制链接] |试试Instant~ |关注本帖
love1point 发表于 2015-4-1 10:54:23 | 显示全部楼层 |阅读模式

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

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

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

x
Just had a interview this afternoon.

One question is below, what is your solution for this? I think this problem is not difficult at not, right.


bob, joe, bob, jane, bob, joe, jack

bob = 3
joe = 2




topN(2) = bob, joe

.鏈枃鍘熷垱鑷1point3acres璁哄潧



. from: 1point3acres.com/bbs


interface TopN {
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  void insert(String query);

  List<String> getTop(int n);
}
. 鍥磋鎴戜滑@1point 3 acres

. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

补充内容 (2015-4-9 01:08):
今天收到HR电话,挂了

评分

2

查看全部评分

Linzertorte 发表于 2015-4-3 09:43:25 | 显示全部楼层
感觉是用hashmap一统计frequence
然后topK的时候用快排的方法,找第n大元素 O(N)   C++里有nth_element这个函数
然后比这个元素大的都返回。
回复 支持 1 反对 0

使用道具 举报

refurbish 发表于 2015-4-1 23:48:21 | 显示全部楼层
HashMap<String, DoublyLinkedListNode> + doubly linked list, insert worst O(n), getTop O(k)
DoublyLinkedListNode contains string and word count, each time insert: if the current word count is greater than previous one, keep swapping until not so
回复 支持 1 反对 0

使用道具 举报

siren01 发表于 2015-4-3 22:45:25 | 显示全部楼层
  1. import java.util.*;
  2. public class TopK {
  3.         public static void topK(int[] array, int k){
  4.                 HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
  5.                 for(int num : array){
  6.                         if(map.containsKey(num)){
  7.                                 map.put(num, map.get(num)+1);. Waral 鍗氬鏈夋洿澶氭枃绔,
  8.                         }
  9.                         else{
  10.                                 map.put(num, 1);
  11.                         }
  12.                 }
  13.                 PriorityQueue<Map.Entry<Integer, Integer>> queue = new PriorityQueue<Map.Entry<Integer, Integer>>(k+1, new .1point3acres缃
  14.                                 Comparator<Map.Entry<Integer, Integer>>(){. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  15.                         public int compare(Map.Entry<Integer, Integer> a, Map.Entry<Integer, Integer> b){-google 1point3acres
  16.                                 if(a == null)
  17.                                         return 1; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  18.                                 else if(b == null). 1point 3acres 璁哄潧
  19.                                         return -1; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  20.                                 else
  21.                                         return a.getValue() - b.getValue();. more info on 1point3acres.com
  22.                         }
  23.                 });
  24.                 for(Map.Entry<Integer, Integer> entry : map.entrySet()){
  25.                         if(queue.size()<k){
  26.                                 queue.add(entry);
  27.                         }
  28.                         else{. 1point 3acres 璁哄潧
  29.                                 if(entry.getValue()>queue.peek().getValue()){
  30.                                         queue.poll();
  31.                                         queue.add(entry);.鐣欏璁哄潧-涓浜-涓夊垎鍦
  32.                                 }
  33.                         }
  34.                 }. From 1point 3acres bbs
  35.         while(queue.size()>0){
  36.                 System.out.println(queue.poll().getKey());
  37.         }
  38.         }
  39.         public static void main(String args[]){
  40.                 int[] array = {1,2,4,5,3,2,1,1,2,3,5,6,6,6,6};
  41.                 topK(array, 3);. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  42.         }
  43. }
复制代码
回复 支持 1 反对 0

使用道具 举报

hit_piggy 发表于 2015-4-1 10:58:09 | 显示全部楼层
第一轮还是第二轮?
回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-4-1 11:02:03 | 显示全部楼层
hit_piggy 发表于 2015-4-1 10:58
第一轮还是第二轮?

first round : )
回复 支持 反对

使用道具 举报

hit_piggy 发表于 2015-4-1 11:20:08 | 显示全部楼层
keep a priority queue is ok I think :D
回复 支持 反对

使用道具 举报

狂暴CNM地 发表于 2015-4-1 11:42:38 | 显示全部楼层
hit_piggy 发表于 2015-4-1 11:20
keep a priority queue is ok I think :D
.鐣欏璁哄潧-涓浜-涓夊垎鍦
PQ的key是频率 insert的时候怎么找到对应的单词? 再加个hash map?
回复 支持 反对

使用道具 举报

hit_piggy 发表于 2015-4-1 11:55:30 | 显示全部楼层
狂暴CNM地 发表于 2015-4-1 11:42. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
PQ的key是频率 insert的时候怎么找到对应的单词? 再加个hash map?

我本来想的是建一个 wrapper class,然后插入pq,但是这样好像也不好找到key。有什么好的想法吗?
回复 支持 反对

使用道具 举报

gbbbb 发表于 2015-4-1 13:59:22 | 显示全部楼层
Hash + Priority queue  插入复杂度O(logN)  getTop复杂度O(NlogN)   如果用平衡二叉树做可以做到getTop复杂度O(N)
回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-4-2 02:41:47 | 显示全部楼层
有人写出具体一点的代码不?
回复 支持 反对

使用道具 举报

EchoO 发表于 2015-4-2 08:46:44 | 显示全部楼层
gbbbb 发表于 2015-4-1 13:59
Hash + Priority queue  插入复杂度O(logN)  getTop复杂度O(NlogN)   如果用平衡二叉树做可以做到getTop复 ...

priority queue如何update呢?如果比如,我再次插入bob,怎么更新pq里的bob的freq
回复 支持 反对

使用道具 举报

EchoO 发表于 2015-4-2 08:48:30 | 显示全部楼层
refurbish 发表于 2015-4-1 23:48
HashMap + doubly linked list, insert worst O(n), getTop O(k)
DoublyLinkedListNode contains string a ...

有点像LRU的实现对吧。
回复 支持 反对

使用道具 举报

refurbish 发表于 2015-4-2 08:54:51 | 显示全部楼层
EchoO 发表于 2015-4-2 08:48
有点像LRU的实现对吧。

恩,不过linked list的操作更像bubble sort
回复 支持 反对

使用道具 举报

sunfish 发表于 2015-4-3 02:49:20 | 显示全部楼层
楼主面完有消息吗,我面完都没人理我啊
回复 支持 反对

使用道具 举报

shinichish 发表于 2015-4-3 03:05:28 | 显示全部楼层
TOP K
CC150上面有这题
回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-4-3 05:37:21 | 显示全部楼层
sunfish 发表于 2015-4-3 02:49.1point3acres缃
楼主面完有消息吗,我面完都没人理我啊

我还没有。估计我悲剧了吧
回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-4-3 05:37:57 | 显示全部楼层
shinichish 发表于 2015-4-3 03:05
TOP K.1point3acres缃
CC150上面有这题

你好,在第几章啊,我还没找到,谢谢
回复 支持 反对

使用道具 举报

shinichish 发表于 2015-4-3 06:59:45 | 显示全部楼层
love1point 发表于 2015-4-2 13:37
你好,在第几章啊,我还没找到,谢谢

Hard那一章~~
回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-4-3 11:13:48 | 显示全部楼层
shinichish 发表于 2015-4-3 06:59. 鍥磋鎴戜滑@1point 3 acres
Hard那一章~~

Hi, I did not find it in Chapter Hard, could you have the screenshot for me? Thank you very much
回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-4-3 11:13:56 | 显示全部楼层

Hi, I did not find it in Chapter Hard, could you have the screenshot for me? Thank you very much
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 10:34

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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