i*********7
发帖数: 348 | 1 How to find if a number is present >= (n / 2) times in an array of size
n?
关于这个题目，有没有时间复杂度是O(n)，空间复杂度是O(1)的解？
另外还有一题：
一百万个amazon product id，问过去一小时销售量top 10的id。 | s********r
发帖数: 137 | 2 MapReduce would be a more scalable solution. For more information, please
refer to the introduction to Hadoop or other MapReduce tutorials:
http://developer.yahoo.com/hadoop/tutorial/module4.html
---------------------------------------------------------
http://www.mitbbs.com/article_t/JobHunting/32078421.html
4.bar raiser: 一百万个amazon product id，问过去一小时销售量top 10的(map-
reduce) | s******n
发帖数: 3946 | 3 int number=a[0];
int count=1;
for (int i=1; i
if (a[i]!=number) {
count--;
if (count==0) {
number = a[i];
count = 1;
}
} else count++;
}
return number; | i*********7
发帖数: 348 | 4 这个只对绝对众数有效。也就是大于n/2的时候，但是等于n/2的时候，是无效的。
【在 s******n 的大作中提到】
: int number=a[0];
: int count=1;
: for (int i=1; i: if (a[i]!=number) {
: count--;
: if (count==0) {
: number = a[i];
: count = 1;
: }
: } else count++;
| S******t
发帖数: 151 | 5 Simple modification is to add another loop to check if there's a number
which has appeared [n/2] times.
【在 i*********7 的大作中提到】
: 这个只对绝对众数有效。也就是大于n/2的时候，但是等于n/2的时候，是无效的。
| w****x
发帖数: 2483 | 6
第一题是微软的, 这题我感觉没啥意思.
第二题因该市每个product分散存储在很多台机器上, 每台机器对自己存储的product
id做hashing, hashing的结果发送到另外对应的机器上, 这样分散的product id就会只
聚集在特定目标机器上, 因为只有100万个product id是不是可以把所有统计出来的
, count> pair 发送到同一台机器上, 因为只需要top 10, 所以不认为需要selection
algorithm或堆, 只需要用一个大小10的数组, 每次遍历这10个id对应的count,找出最
小的那个, 如果新的count大于最小的这个就替换它.
【在 i*********7 的大作中提到】
: How to find if a number is present >= (n / 2) times in an array of size
: n?
: 关于这个题目，有没有时间复杂度是O(n)，空间复杂度是O(1)的解？
: 另外还有一题：
: 一百万个amazon product id，问过去一小时销售量top 10的id。
| s******n
发帖数: 3946 | 7 yes，run another loop that exclude this number and also count the number.
If the count>=n/2, then it's it; if count
the right answer by excluding another number.
【在 S******t 的大作中提到】
: Simple modification is to add another loop to check if there's a number
: which has appeared [n/2] times.
| m*****k
发帖数: 731 | 8 take 2, if same, keep, otherwise discard both, keep doing until you can not
discard anyone.
【在 i*********7 的大作中提到】
: 这个只对绝对众数有效。也就是大于n/2的时候，但是等于n/2的时候，是无效的。
| l*********8
发帖数: 4642 | 9 As iverson1407 said, the program doesn't work for the number that appears
exactly n/2 times when n is even.
Another problem: probably there is no such number existing in the array.
// Find the number(s) that appear
// Input:
// int * a, input array
// size_t n, length of the array
// Output:
/// int mode[2], store the mode nubmers found.
// return:
// int, how many mode numbers found. (0, 1 or 2)
//
int
FindModeNumber(int *a, size_t n, int modeNumbers[2])
{
if (n<2)
return n;
int count = 1;
int mode = a[0];
for (int i=1; i
if(a[i] != mode)
if (--count == 0)
mode = a[i];
}
int modeCount = 0; // how many mode numbers found.
if (VerifyModeNumber(a, n, mode) )
modeNumbers[ modeCount++ ] = mode;
if (count == 1 && mode == a[n-1])
if (VerifyModeNumber(a, n, a[n-2]) )
modeNumbers[ modeCount++ ] = a[n-2];
return modeCount;
}
bool
VerifyModeNumber(int *a, size_t n, int mode)
{
int count=0;
for (int i=0; i
if (a[i]==mode)
++count;
return count>= (n+1)/2;
}
【在 s******n 的大作中提到】
: int number=a[0];
: int count=1;
: for (int i=1; i: if (a[i]!=number) {
: count--;
: if (count==0) {
: number = a[i];
: count = 1;
: }
: } else count++;
| b***d
发帖数: 87 | 10 每次遍历还不如用堆，时间开销明显少很多。
每次遍历这10个id对应的count,找出最
小的那个, 如果新的count大于最小的这个就替换它.
【在 w****x 的大作中提到】
:
: 第一题是微软的, 这题我感觉没啥意思.
: 第二题因该市每个product分散存储在很多台机器上, 每台机器对自己存储的product
: id做hashing, hashing的结果发送到另外对应的机器上, 这样分散的product id就会只
: 聚集在特定目标机器上, 因为只有100万个product id是不是可以把所有统计出来的: , count> pair 发送到同一台机器上, 因为只需要top 10, 所以不认为需要selection
: algorithm或堆, 只需要用一个大小10的数组, 每次遍历这10个id对应的count,找出最
: 小的那个, 如果新的count大于最小的这个就替换它.
|
|
