Challenge: Prime access list
Today I have for you this exercise that I already presented in the Functional Kotlin book and online course, but that captures the core idea of the Effective Kotlin book Item 55: Consider associating elements to a map. It is especially an important exercise for backend development, where I found this optimization useful in many services, but it has its applications in frontend development as well. So without further ado, here is the exercise in its original form:
Associating elements to a map can be an important performance optimization. Finding an element by key in a map is a lot faster than iterating over a list and comparing each element to the searched value. To see the differentce, implement methods of the
trueif the user is on the allowlist (entry with this user id has
trueif the user is on the denylist (entry with this user id has
Implement two kinds of solutions:
- iterating over entries to find the searched user id,
- associating entries to a map by user id in the class body, and in methods finding the entry by user id.
For each of those solutions, check its efficiency using the main function I defined in the playground below:
Beware! Such measurements are not precise. They are only to show the difference between the two solutions. For precise measurements, you should use a benchmarking library, like JMH.
Starting code and the code to measure implementation performance can be also found in the kotlin-exercises project on GitHub in the file
effective/collections/PrimeAccess.kt. You can clone this project and solve this exercise locally.
I decided I wouldn't feel good showing you the solution. It can be found at the end of the book Functional Kotlin, and in the course Functional Kotlin, but here it would be just too easy to see it and copy it. I want you to try to solve it yourself. If you have any questions, feel free to ask them in the comments below. You can also send a Tweet to me @marcinmoskala. I will be happy to help you. If you managed to solve this exercise, feel free to share it with others. I will be happy to see your solutions. Good luck and have fun!
Know that this optimization can also be applied on other cases. Even in a local code, if you need to find if a list includes elements, it might be worth to transform it into
Set, and if you need to find what a key is associated with, it might be worth to transform it into