Работите за Zynga и искате да преброите броя на текущо активните играчи за различни игри. Вашият уеб сървър обработва ping от много различни игри и всеки потребител има уникален GUID. Трябва да можете да заявявате брой активни потребители за една игра наведнъж. Активните потребители са тези, които са получили ping в последната минута.
Редовете на регистрационния файл влизат непрекъснато в уеб сървър:
10.1.12.13 - - "http://zynga.com/ping?guid=<guid>&game=<gameID>" -
Кой е най-бързият/лесният начин за преброяване на активните потребители? Моля, предложете 45 минути отговор с някакъв код.
Моята версия
// web server interface, every time ping comes in count() will be called
// void count(String gameId, String guid)
// int getNumberActivePlayers(String gameId)
struct Record{
String gameID;
String guid;
};
class PingStorage{
private:
max_heap<long, Record> storage;
public:
// O(log(n))
// n = total number of elements in storage
void count(String gameId, String guid){
long currentTimeStamp = getUnixTimeStamp();
Record rec ;
rec.gameId = gameId;
rec.guid = guid;
storage.add(currentTimeStamp, rec);
}
//N = numner of records in last ,minutes in storage
//O(N)
int getNumberActivePlayers(String gameId){
map<String, Set<string> > game2user;
long tillTimeStamp = getUnixTimeStampNow() - 60;
while(true){
pair<long, Record> rec = storage.getMax(); //O(1)
if(rec.first <= tillTimeStamp) break;
Set<String> temp = game2user[rec.gameid]; //O(1)
temp.add(rec.userid); //O(log(N)) - O(1)
}
return game2user[gameID].size();
}
};
