I’d classify this more of a rant than an informative post. We’ve all been stuck on an algorithm question before and we’ve all experienced the joy & satisfaction that a sudden flash of insight leads us to the solution. Some times we succeed, some times inspiration fails to arrive in a timely manner and we have to look at the analysis. This question was the latter. For those who are curious, this is the Google Kickstart 2019 A round ‘Parcels’ question.
I shan’t go in to the specifics, if you’re interested, you can check out the question here. My first instinct did not work as I tried placing the new centers at the furthest points, or if there were more than 1, I’d try placing them at the middle of them. Then after some drawing on a paper, I realised that I have to find the intersections of the furthest points but generating a possibility area for each point will take linear time, and doing this for all furthest points will take quadratic (linear*linear). At this I gave up and looked at the analysis. I was expecting optimisation by rearranging calculations and pruning some possible candidates, but I got a math lesson. To solve the question in linear time, you had to rearrange the equation which contains absolute values and to obtain the minimum and maximum of some parameters. I have not worked with equations containing absolute values since lower secondary! It took me 4 days to understand and work out the math. During which, I found out why L1 and L2 norm graphs look the way they do and relearned how to work with absolute value equations.
In order to solve the question, you had to implement BFS, work out the Math, implement binary search, each of which could be a whole coding question by itself! Man, these questions are brutal! Working out the answer (when given the answer) was tough, it made me doubt myself in so many ways but ultimately I’m glad for it.
I’ve yet to come up with my first post about ML, maybe I should start where most good teachers do, at the introduction…
