Kattis is a programming problem archive. Problems are categorised into easy, medium, and hard. In this repo you'll find all of the kata's I've completed using Java. You can find my kattis account here alex redfearn.
| Kata | Difficulty | Problem Report | Accepted |
|---|---|---|---|
| Jumbo Javelin | Easy | Jumbo Javelin | ✅ |
| Carrots | Easy | Carrots | ✅ |
| Coldputer Science | Easy | Coldputer Science | ✅ |
| Birthday Memorization | Easy | Birthday Memorization | ✅ |
| Compact Disc | Medium | Compact Disc | ✅ |
| Teque | Medium | Teque | ✅ |
Super easy, the first kata I solved, was just a simple loop and concatenation.
Super easy but not a very fun one.
Loop to count negative numbers, kinda fun.
A slightly more involved easy one. The task was to store friend's birthdays in a calendar. I used a map for this, birthday as the key. If two friends had the same birthday then the friend rating was used to decide which birthday to store. I had fun writing two simple functional interfaces that implement Comparator and could be passed to a lambda expression e.g. stream().sorted(Comparator).
The first time I learnt that java.util.Scanner is too slow for io operations, started using java.io.BufferedReader. The challenge was to output the number of duplicate values in two lists. Extracted the two sequences into two sets and then used java.util.set.retainAll().
Tough challenge but really enjoyable, learnt a lot. Create a triple-ended queue, like a deque but with add middle, with a performance constraint. Started by using one List, on add middle, split the list, add the value, join them back together again. Too slow! Next approach, use two Deques. On add middle, add the value to the start of the second Deque. Quicker but still too slow! The Deque type in Java has no get(index) method?! You have to traverse the list. Two Lists instead then so I could use List.get(index), still too slow! Lookup in a List is significantly slower than lookup in a Map. Modified my approach to use two Maps, and tracked the head and tail of each Map so I could add to the front and back. This solution was accepted with 0.62 seconds to spare.
After brushing up on data structures... Lists suffer from a major drawback, removing/inserting elements from/to the middle is expensive as the list must be traversed and items moved back. Maps are obviously quicker because they're unordered. The best structure to use probably would have been a linked list which solves the problem of operations on the middle elements. Each element stores a reference to the element in front and behind. Only the surrounding elements would need to be updated.