あなたは Zynga で働いており、さまざまなゲームで現在アクティブなプレーヤーの数を数えたいと考えています。Web サーバーはさまざまなゲームからの ping を処理し、各ユーザーは一意の GUID を持っています。一度に 1 つのゲームのアクティブ ユーザー数を照会できる必要があります。アクティブなユーザーは、直前に ping を受信したユーザーです。
ログ行は Web サーバーに継続的に入ってきます。
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();
}
};