x0040h
BAN USERYou can sum numbers locally then we have 2 options:
1 - correctness should be as high as possible. In this case we send full sum to some aggregate server which can sum all sums and then divide it to 10k* 1billion
2 - we can divide sum locally and send meaning then on aggregate server when we just power it by 1 bill sum with other sums and divide to 10k* 1billion
From example above:
Machine 1: 2, 3, 4, 5, 6. Sum is 20
Machine 2: 6, 6, 6, 6, 6. Sum is 30
Then Machine 1 receives 30 and 50 / 10 = 5
Here sum is a map operation and sum of sums is reduce operation
You probably can get number type overflow, but create an custom type to store value in few buckets is efficient enough and transfer between node will not take a long time.
Don't see any note about extra collection so it is reasonable to use map. Key search is amortised O(1). Also it reasonable to use custom counter class to prevent active memory allocations and reset it after any word we test.
using System.Collections.Generic;
namespace Appl{
internal class Counter {
int _base = 0;
int _current;
public void Add(){
_base++;
_current = _base;
}
public bool Use() {
return (--_current) >= 0;
}
public void Reset(){
_current = _base;
}
}
class WordRutine{
static string GetBiggestWord(string[] words, char[] chars){
var map = new Dictionary<char,Counter> (chars.Length);
foreach (var c in chars) {
if (!map.ContainsKey (c))
map.Add (c, new Counter ());
map[c].Add ();
}
int largestIndex = -1;
int largestLength = 0;
for (int i = 0; i < words.Length; i++) {
var word = words[i];
if (word.Length < largestLength)
continue;
if (word.Length > chars.Length)
continue;
if (CanBeCreated (map, word)) {
largestIndex = i;
largestLength = word.Length;
}
foreach (var pair in map) {
pair.Value.Reset ();
}
}
if (largestIndex > 0)
return words [largestIndex];
return null;
}
static bool CanBeCreated(Dictionary<char,Counter> map, string word){
foreach(var c in word){
if(!map[c].Use()) return false;
}
return true;
}
}
}
Suffix sort (count sort, LSD sort)
C# implementation.
Complexity: space O(n) and time O(L*n) where L - length of string.
- x0040h September 15, 2014