首先面试官竟然先自我介绍起来了, 介绍了组内的业务和技术栈
随后问了些实习的问题
给你一整年的关键词的数据, 关键词可以被视作字符串, 一天大概50亿条. 存储在100台机器上, 求top100频率最高的字符串
(我的思路是每台机器先map成关键词到频率的字符串, 然后相同的关键词shuffle到同一台机器上, 再reduce. 最后每台机器上取top100, 汇总到一台机器上是1w个最后再取整体的top100)
面试官问, 假如有一些关键词要被视为同一个关键词呢? 比如”北京鲜花”和”鲜花北京”或”土豆”和”马铃薯”这样的算一个关键词, 这样该怎么计算呢?
你刚才讲的1w个里面取前top100, 那该怎么做呢? (优先队列)
那如果存在并列的情况呢? 比如 1,2,….,99, 100, 100, 100, 101 的top100就是[1,2,....,99, 100, 100, 100]这102个元素.(我一开始答得是排序, 但是很慢, 后来想出来了, 还是用优先队列, top100是100, 那么我记录下这个100, 再把数组中所有的100添加到top里面)
java一个进程不同线程的栈是共享的吗, 栈里面存储哪些数据?
编程题,
1
2
3
| 15分钟自己实现优先队列的push和pop方法并且实现n个里面选前k个最大
我感觉就是在为难我, 还说阿里的笔试我做的不好, 美名其曰考察我的代码能力， 我感觉就是人招满了, 找个借口拒绝我
写的一般吧, 代码里还是有些问题的
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
| class Heap{
Pair[] values = new Pair[n];
int size = 0;
void push(Pair pair){
values[++size] = pair;
int i = size;
Pair parent = values[i/2];
while(i / 2 > 0){
if(values[i].second < parent.second){
Pair tmp = values[i/2];
value[i/2] = value[i];
value[i] = tmp;
i = i / 2;
}
else{
break;
}
}
}
Pair pop(){
Pair ret = values[1];
values[1] = values[size];
--size;
int i = 1;
while(i * 2 <= size){
Pair left = values[i * 2];
Pair right = values[i * 2 + 1];
if(right == null){
if(values[i].second > left.second){
Pair tmp = values[i];
values[i] = left;
values[i * 2] = tmp;
}
else{
break;
}
}
else{
if(values[i].second > Math.min(left.second, right.second)){
if(left.second > right.second){
Pair tmp = values[i];
values[i] = right;
values[i * 2 + 1] = tmp;
}
else{
Pair tmp = values[i];
values[i] = left;
values[i * 2] = tmp;
}
}
else{
break;
}
}
}
return ret;
}
}
List<Pair> topK(List<Pair> pairs, int k){
Heap heap = makeHeap();
for(Pair pair : pairs){
if(heap.size < k){
heap.push(pair);
}
else{
Pair top = heap.top();
if(top.second < pair.second){
heap.pop();
heap.push(pair);
}
}
}
return new ArrayList<Pair>(heap);
}
|