Google interview

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.

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

>

}

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

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);
   
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
    
14.                                 Comparator<Map.Entry<Integer, Integer>>(){
    
15.                         public int compare(Map.Entry<Integer, Integer> a, Map.Entry<Integer, Integer> b){
    
16.                                 if(a == null)
    
17.                                         return 1;
    
18.                                 else if(b == null)
    
19.                                         return -1;
    
20.                                 else
    
21.                                         return a.getValue() - b.getValue();
    
22.                         }
    
23.                 });
    
24.                 for(Map.Entry<Integer, Integer> entry : map.entrySet()){
    
25.                         if(queue.size()<k){
    
26.                                 queue.add(entry);
    
27.                         }
    
28.                         else{
    
29.                                 if(entry.getValue()>queue.peek().getValue()){
    
30.                                         queue.poll();
    
31.                                         queue.add(entry);
    
32.                                 }
    
33.                         }
    
34.                 }
    
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. }

复制代码

感觉是用hashmap一统计frequence
然后topK的时候用快排的方法,找第n大元素 O(N)   C++里有nth_element这个函数
然后比这个元素大的都返回。

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

第一轮还是第二轮？

hit_piggy 发表于 2015-4-1 10:58
第一轮还是第二轮？

first round : )

keep a priority queue is ok I think :D

hit_piggy 发表于 2015-4-1 11:20
keep a priority queue is ok I think :D

PQ的key是频率 insert的时候怎么找到对应的单词？ 再加个hash map?

狂暴CNM地 发表于 2015-4-1 11:42
PQ的key是频率 insert的时候怎么找到对应的单词？ 再加个hash map?

我本来想的是建一个 wrapper class，然后插入pq，但是这样好像也不好找到key。有什么好的想法吗？

Hash + Priority queue  插入复杂度O(logN)  getTop复杂度O(NlogN)   如果用平衡二叉树做可以做到getTop复杂度O(N)

有人写出具体一点的代码不？

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies