fork download 
  1. #include <iostream>
  2. #include <unordered_map>
  3. #include <vector>
  4. #include <list>
  5. #include <algorithm>
  6. #include <queue>
  7. using namespace std;
  8.  
  9. /*
  10. Write a game leader board. Record user id and game score. Return top n players.
  11. */
  12.  
  13. struct UserWithScore {
  14. 	string user_id;
  15. 	int score;
  16. 	UserWithScore(string user_id_, int score_): user_id(user_id_), score(score_) {}
  17. };
  18.  
  19. struct Compare {
  20. 	bool operator()(UserWithScore a, UserWithScore b) {
  21. 		return a.score > b.score;
  22. 	}
  23. };
  24.  
  25. class GameLeaderBoard {
  26. public:
  27. 	unordered_map<string,int> ht;
  28.  
  29. 	void add_score(string user_id, int game_score) {
  30. 		auto it = ht.find(user_id);
  31. 		if (it == ht.end()) {
  32. 			ht.insert(make_pair(user_id, game_score));
  33. 		} else {
  34. 			if (game_score > it->second) {
  35. 				it->second = game_score;
  36. 			}
  37. 		}
  38. 	}
  39.  
  40. 	vector<UserWithScore> get_top_n(int n) {
  41. 		vector<UserWithScore> out;
  42.  
  43. 		priority_queue<UserWithScore, std::vector<UserWithScore>, Compare> min_heap;
  44.  
  45. 		for (auto e : ht) {
  46. 			if (min_heap.size() < n) {
  47. 				min_heap.push(UserWithScore(e.first, e.second));
  48. 			} else {
  49. 				auto it = min_heap.top();
  50. 				if (it.score < e.second) {
  51. 					min_heap.pop();
  52. 					min_heap.push(UserWithScore(e.first, e.second));
  53. 				}
  54. 			}
  55. 		}
  56.  
  57. 		while (!min_heap.empty()) {
  58. 			auto n = min_heap.top();
  59. 			min_heap.pop();
  60. 			out.push_back(n);
  61. 		}
  62.  
  63. 		return out;
  64. 	}
  65. };
  66.  
  67. void print(vector<UserWithScore> top_n) {
  68. 	for (int i = 0; i < top_n.size(); i++) {
  69. 		cout << "user: " << top_n[i].user_id << ", score: " << top_n[i].score << endl;
  70. 	}
  71. 	cout << '\n';
  72. }
  73.  
  74. int main() {
  75. 	// your code goes here
  76.  
  77. 	GameLeaderBoard g1;
  78. 	g1.add_score("gerald", 10);
  79. 	g1.add_score("tushar", 20);
  80. 	g1.add_score("gaurav", 15);
  81. 	g1.add_score("vishal", 3);
  82. 	print(g1.get_top_n(3));
  83.  
  84. 	g1.add_score("gerald", 30);
  85. 	print(g1.get_top_n(3));
  86.  
  87. 	return 0;
  88. }
Success #stdin #stdout 0.01s 5452KB
comments (?)
stdin 
Standard input is empty
stdout 
user: gerald, score: 10
user: gaurav, score: 15
user: tushar, score: 20

user: gaurav, score: 15
user: tushar, score: 20
user: gerald, score: 30
https://ideone.com/cwatUR
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!