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?

  • 1
    Sharing your research helps everyone. Tell us what you've tried and why it didn’t meet your needs. This demonstrates that you’ve taken the time to try to help yourself, it saves us from reiterating obvious answers, and most of all it helps you get a more specific and relevant answer. Also see How to Ask – gnat May 28 '14 at 7:39
  • 2
    @zrvan It would be best if you linked to the question you posted on Code Review. – George Howarth May 28 '14 at 8:20
  • "store scores" yet "no information should be persisted" is clearly contradictory requirements. No further analysis needed until that is clarified by the customer. – jwenting May 28 '14 at 10:14
  • @jwenting Persisting information means to preserve state in order to potentially outlive the process that originally created the state. So technically, it's not contradicting. – George Howarth May 28 '14 at 10:41
  • 2
    You might wish to read Why do interview questions make poor Programmers.SE questions? – user40980 May 28 '14 at 13:53

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 inner SortedMap stores the score as the key and the associated Player class which got that score. In this case it is relevant that it is a SortedMap, 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 SortedMap for 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?

  • 1
    The "No information should be persisted " requirement rules out databases. – user281377 May 28 '14 at 8:53
  • @user281377 There are ways you can use databases to achieve the same effect with the guarantee that once the connection closes, all data inserted will be removed. It seems silly to insist everything should be held in memory, and even databases which temporarily hold data do not attempt to keep it in memory. If the interviewer is obtuse and insists not to use databases for the sake of the exercise, it is an impractical exercise. We might as well ask a programmer to write to an excel sheet without the use of loops inside the program. – Neil May 28 '14 at 9:06
  • Wouldn't a Map<int, SortedMap<long, Player>> create issues where 2 players have the same score, on the same level? Won't updating the information for the 2nd player erase the information about the first one (since the inner map key is score value) ? – Shivan Dragon Mar 3 '16 at 14:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.