CareerCup

use a hash table keeping count of the elements occurring( most common) Now find the element with maximum count and find sum as
number of occurrence * value.

O(n) time , O(n) space

hope it helps

another solution for the problem. O(nlgn) time, O(1) space

use four variable curMax,curVal, max, val.
sort the arry.
curVal = A[0];
curMax = 1;
for (i=1;i<n;i++) {
if (A[i] == curVal)
curMax++;
else {
if (curMax > max) {
max = curMax;
val = curVal;
}
curMax = 1;
curVal = A[i];
}

}

if (curMax > max) {
max = curMax;
val = curVal;
}

return max*val;

Hi,
What is the team that you interviewed for? Is it AWS?

if the highest element is not significantly very large then this solution will work in O(L).L is largest element in the array.
declare an array of the size of L and keep incrementing Arr[i] if i is found. find the max element in Arr. the ans will be "max element * arr[max]"

haven't tested out the code, but this should work.

my $biggest = 0;
my %hash = ();
foreach my $num (@A) {
if ( $hash{$num} ) {
$hash{$num}++;
} else {
$hash{$num} = 1;
}
if ($hash{$num} > $biggest) {
$biggest = $num;
}
}

oh, forgot to tally the highest guy... here's the full code:

<pre>
my $biggest = 0;
my %hash = ();
foreach my $num (@A) {
if ( $hash{$num} ) {
$hash{$num}++;
} else {
$hash{$num} = 1;
}
if ($hash{$num} > $biggest) {
$biggest = $num;
}
}

return $biggest * $hash{$biggest};
</pre>

also, this would take O(n) time, as it only needs iterate through the array once...

cristo, your solution finds the sum but it does that in O(n) + O(n) = O(n)
once for going through the list putting the numbers in the hash table and the second one for going through the hash to find the number that occurs maximum number of times, right?
One Question:
What if we have a scenario like this:
2,3,4,5,6,4,6,7,
what is the output in this case?
ans = 4+4 or 6+6 or 4+4+6+6 ???

I think nickNack has a point.
guys whats the answer for his Question ?