This question is derived from an interview question that I got for a job I was declined. I have asked for code review for my solution at the dedicated Stack Exchange site (https://codereview.stackexchange.com/q/51842/43237). But I hope this question is sufficiently rephrased and asked with a different motivation not to be a duplicate of the other question.
Consider the following scenario:
You should store player scores in the server back end of a game. The server is written in Java.
Every score should be registered, that is, one player may have any number of scores for any number of levels.
A high score list should be produced with the fifteen top scores for a given level, but only one score per user (to the effect that even if player X has the two highest scores for level Y, only the first position is counted and player Z has the second place).
No information should be persisted and only Java 1.7+ standard libraries should be used. No third party libraries or frameworks are acceptable.
With the number of players as the primary factor, what would be the best data structure in terms of scalability and concurrency?
How would you access the structure to register a single score given a level and a player id?
How would you access the structure to compile the high score list?
Best Answer
This might be a trick question, since it's implying that you should be able to represent the scores for every single level for every single player in a single data structure. While that may be true in general, we're talking about a game with many many players. Therefore, trying to hold everything in memory might work initially, but it's not reasonable to assume it would scale, and since scalability is important here, you should flat out tell your interviewer that a java data structure of any form could not reasonably be thought to hold all the information required.
What comes to mind is a database for such things, since it is both scalable as well as completely supporting concurrency, both of which are requirements in this case. If the interviewer wants to go into details in that regard you can, but I think the key point here is that you wouldn't try to stuff everything into the server's memory.
However on that point, you should probably add that it would be also inefficient to have to load all scores after each level in order to see if you've got a spot on the top scores list. Therefore to that effect, I do think keeping the top scores for each level is a reasonable compromise for performance. In terms of memory, top 10 slots X 100 levels is 1000 slots, perfectly reasonable amount of space and more importantly, it does not grow.
I would represent this using a
Map<int, SortedMap<long, Player>>. The outer map is used to store a map for each level (no need searching in other levels other than the one I've just beaten). It is also irrelevant what type the Map is, since it just has to find the given level. The innerSortedMapstores the score as the key and the associatedPlayerclass which got that score. In this case it is relevant that it is aSortedMap, since you may likely want to access them sequentially based on score.When a player finishes a level, you can do a quick check in memory to see if the player has made it to the top score list for that given level without making an explicit fetch to the database each time. If so, in a synchronized action, you should insert the player into the
SortedMapfor that level (removing the worst score afterwards) and then update the database. It must be synchronized in order to guarantee that it is also consistent with the database and consistent with the multiple requests that will be done.Does that answer your question?