由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - 菜鸟向大家请教个面试题
相关主题
A家一道题那道经典的求和问题
刚看到的一道google面试题问一道算法题
发个evernote的code challengeHashTable space complexity?
twittier的onsite挂了,来问个常见题FB电面面经
请教个面试题google youtube interview, 莫名被拒。。。。。。
上午偷闲把TopKFrequentWords写出来了amazon 一道题
请教一道题求高手解答cs 面试题?
一个N个数的int数组如何找到3个majority的数?感恩发面经-Amazon第一轮电面
相关话题的讨论汇总
话题: int话题: integer话题: 数组话题: 个数
进入JobHunting版参与讨论
1 (共1页)
w*********6
发帖数: 114
1
有一个数组有M个元素,没有sort的,找出最大的N个数的和,但是N个数是可以重复的
,例如A= 【2,9,3,9,1,7,8,2,8,9】, N= 2, 结果是9*3 + 8*2 = 43. 要求时间O(M)
。请问大家怎么做?
谢谢大家
l*****7
发帖数: 55
2
能先拿个hash map过一遍吗?之后再对hasp map 的keys进行partition。
应该有更好的办法。

M)

【在 w*********6 的大作中提到】
: 有一个数组有M个元素,没有sort的,找出最大的N个数的和,但是N个数是可以重复的
: ,例如A= 【2,9,3,9,1,7,8,2,8,9】, N= 2, 结果是9*3 + 8*2 = 43. 要求时间O(M)
: 。请问大家怎么做?
: 谢谢大家

w*********6
发帖数: 114
3
面试的人说不需要用hashtable...

【在 l*****7 的大作中提到】
: 能先拿个hash map过一遍吗?之后再对hasp map 的keys进行partition。
: 应该有更好的办法。
:
: M)

a*********4
发帖数: 7
4
how about using a minQ/minHeap with size N? but that would have O(MlogN)
time, not exactly O(M)

【在 l*****7 的大作中提到】
: 能先拿个hash map过一遍吗?之后再对hasp map 的keys进行partition。
: 应该有更好的办法。
:
: M)

l****i
发帖数: 2772
5
partition, selection algorithm.
z****e
发帖数: 54598
6
元素本身的值也就是89那些

数组长度有对应关系没?
是不是数组元素的值都<数组长度?
m****s
发帖数: 131
7
如果不能用额外空间。用partition找到前N大的数字。。
如果可以用额外空间,用一个set之类的排序的容器把前N大的数字在一次扫描后存储下
来。。。
y**********a
发帖数: 824
8
quickselect 就可以了
g***j
发帖数: 1275
9
如果有重复的怎么找前n大的数?

【在 m****s 的大作中提到】
: 如果不能用额外空间。用partition找到前N大的数字。。
: 如果可以用额外空间,用一个set之类的排序的容器把前N大的数字在一次扫描后存储下
: 来。。。

n*****n
发帖数: 5277
10
重复的数算一个

【在 g***j 的大作中提到】
: 如果有重复的怎么找前n大的数?
相关主题
上午偷闲把TopKFrequentWords写出来了那道经典的求和问题
请教一道题问一道算法题
一个N个数的int数组如何找到3个majority的数?HashTable space complexity?
进入JobHunting版参与讨论
w*********6
发帖数: 114
11
好像还真说了数组元素在0~9之间。这个有关系?我还真没意识到哟。。。
但长度可以很短。

【在 z****e 的大作中提到】
: 元素本身的值也就是89那些
: 跟
: 数组长度有对应关系没?
: 是不是数组元素的值都<数组长度?

w*********6
发帖数: 114
12
我擦。。。不会是用个数组统计一下0~9的每个数出现的次数就可以了吧。。。多谢提
醒。。。

【在 z****e 的大作中提到】
: 元素本身的值也就是89那些
: 跟
: 数组长度有对应关系没?
: 是不是数组元素的值都<数组长度?

y**********a
发帖数: 824
13
int max(int[]A, n) {
Map m=new HashMap<>();
for (int a:A)
if (!m.containsKey(a)) m.put(a,a);
else m.put(a, m.get(a)+a);
int[] B=new int[m.size()];
int i=0;
for (int key:m.keySet()) B[i++]=m.get(key);
int k=quickSelect(B, n), c=n, s=0;
for (int i=0;i=B[k]) s+=B[i];
return s+c*B[k];
}
n****o
发帖数: 239
14
复杂度要求O(M)的话,还是要用Hashtable吧。
T*****u
发帖数: 7103
15
不能存最大两数和两数出现的次数吗,边扫边更新
r*******k
发帖数: 1423
16
ft,这不是太弱智了么
数组sum[10]
碰到i,就累加到sum[i]去
然后这10个数找最大的两个

【在 w*********6 的大作中提到】
: 好像还真说了数组元素在0~9之间。这个有关系?我还真没意识到哟。。。
: 但长度可以很短。

1 (共1页)
进入JobHunting版参与讨论
相关主题
感恩发面经-Amazon第一轮电面请教个面试题
求解一道面试题上午偷闲把TopKFrequentWords写出来了
请教一个函数默认返回值的问题,纠结很久了请教一道题
一道大数组shuffle的题一个N个数的int数组如何找到3个majority的数?
A家一道题那道经典的求和问题
刚看到的一道google面试题问一道算法题
发个evernote的code challengeHashTable space complexity?
twittier的onsite挂了,来问个常见题FB电面面经
相关话题的讨论汇总
话题: int话题: integer话题: 数组话题: 个数