So I was recently introduced to the service Codility which provides programming challenges for people looking for a job in the industry. I’m not looking for a job, but I do like interesting programming challenges, so I thought I’d try it out.
Apparently, once a month they release a new algorithmic problem to solve and test your solution for correctness and good time complexity. You can get a “silver” award if your program is correct and a “gold” award if it also has good time complexity. They give you a time limit of 2 hours, but I’ve figured out first hand that you can simply retake the test as many times as you like.
After three tries I got my shiny gold medal. My first attempt was almost completely correct if it wasn’t for a very small edge case that they specified in the problem. I only had to change one line of code to make it correct.
Anyway, in short the problem statement is to find the number of ranges within an array where the Max(range) - Min(range) <= K.
I’m not sure If I’m allowed to post my solution online - so I’m sorry if this is bad form…
So apparently this code was good enough to get a gold sticker, but I don’t think it’s actually O(n) time complexity. In the worst case I could create a multiset of size n. Since erasing a single value takes O(logn) time, then erasing them all one by one should take O(nlogn). But since sets and maps are so awesome, maybe they don’t always have a good way of judging the time complexity.
Either way, it was a pretty fun challenge and I’d like to complete more of them. They appear to have a whole set of training challenges at codility.com/demo/train/.- Isaiah Hines