An Algorithmic Journey
Today is the first day of a journey I wanted to share. Now I know it sounds slightly dramatic, but it’s because I might just slightly be dreading it. So to help me get through it, I thought it was worth documenting. I have just finished a 6-months remote bootcamp, specialising in React and ending on a month-long group project. Everything has been going great, by which of course I mean difficult but rewarding, I’ve learned a lot, BUT - I do not master algorithmia at all. My logic is one of someone with a literary background - not to demean anyone but, well. Reading philosophy has brought me some structure I guess. But I want to train and get better at solving problems. I own “Cracking the Coding Interview” by Gayle Laakmann, which I hope to rely on a lot during this journey. So, whether you’re in the same case as I am, or you’re just curious, or lost, welcome.
Started reading Gayle’s book and feeling a sense of discouragement as my brain is slowly turning into egg wash. Maybe the fact that I’m reading in English - not my mother tongue - is adding unnecessary difficulty? Or the fact that she’s mentioning Google and Amazon interviewing processes and that, uh, I don’t have such goals? Oh well. I then decide to dig into the basic concepts of algorithmia by watching some french youtube videos and find out this cool guy. I understand that : space and time are core concepts in finding the best possible way to find a solution to a problem. In coding, we measure the performance of our code by counting the number of operations running in our programme. O(n).
Let’s imagine I have a list of numbers I want to reorganise in an ascending order. What would be the best way to do that? Here is what I gathered from this video. Bubble sort : this solution would be to evaluate two numbers every time and compare them to each other. I compare the first pair of numbers and I only keep the smallest one. The program ends when there is no more switching. Even someone who doesn’t have a great logic would get that, even though it’s probably tidy, this solution is not the most efficient. Merge sort: Let’s split the list into two segments of equal size. The beauty of this (yes, I am starting to see beauty in this) is that I’m going to call that same function that split the list again, until I am left with lists of one item. At this point, I can merge the two halves to get my ordered list. This type of algo apparently belongs to the “divide and conquer” category. Now if we’re talking politics, I’m going to take a strong stance by stating I disagree with the morality behind that slogan. Now politics aside - recursion is amazing.
Every problem involves multiple ways to approach it. My immediate problem, after Problem 3, has been focus. I watched this video which I thought was useful but then started wondering, should I not follow a more rigorous path on my journey? Should I remain careful not to end up watching 100 videos of robots playing with balls? It was time to say hi to Gayle again. And she provided me with an answer! So according to her, the absolute knowledge required for anyone willing to master algorithms can be summed up in that list: breadth-first search, depth-first search, binary search, merge sort, quick sort. But before diving into that list, she specifically asks the readers to also have a strong understanding of data structure, especially hash tables. I will not immediately document the research I have been doing on hash tables to focus first on the different core algorithms.
I must admit the name scared me. But after doing some research in French, I got less scared. Dare I say that for once, the French name is more eloquent and straightforward than the English one? Anyway. From what I gathered, you need to think of this algorithm like you would think of Google Maps: what is the shortest distance that will lead me from one point to another? So let’s say we have a network represented by nodes, and each node is linked to another by a straight line that represents a distance. We have a source node and a destination node. So how do we do this? Well, we’ll first have a look at all the nodes directly linked to our source node. Then we’ll pick the one that has the smallest distance. We repeat the same thing but this time, we exclude the node/nodes that have already been evaluated. And that’s it!
Repeat the same setting as the previous problem. Instead of jumping from one node to another by evaluating all the neighbour nodes, the goal is to go the furthest away - where there is higher depth in the tree. Each time you go through a node, you cross it off your list. If at some point in the journey you get stuck, you go back one step and try to find a node you haven’t traversed (is that even English?). And if it doesn’t work - well, go back one step again. Be mindful though because you might create an infinite loop. I may only have a 6 months development experience - I know how those can be horrible. Last month, I used a React hook in a place I shouldn't have (*activate guilt*) and created an infinite call to an API. I felt really guilty towards my browser and wondered if it was at all possible for me to find it deceased the next morning (gladly, it survived or rather, resurrected).
I stumbled on this video that is coincidentally narrated by Gayle. I notice I call her Gayle as if she were a close friend - another consequence of lockdown that had previously led me to talk about Adriene from Yoga With Adriene as if we were BFFs (I do spend an hour of my day with her). So, binary search. Let’s say we have an ordered list of items and we want to find one specific item within that list. We could go through each item of the list until we find the right one - that would be a linear approach, but that’s not ideal. So instead, we’ll split the list into two, and see whether the item we’re looking for is located on the left side of the half, or on the right. And we repeat, until we narrow it down. Voilà.
We want to sort an array. We’ll pick a pivot which is an item in the middle of our array, and start performing operations: we want items to the pivot’s left to be smaller, and items to the pivot’s right to be larger. How do we do this: we put the pivot at the end of the array, to get it out. We’ll pick two items on each iteration. One that will be the first item starting from the left that is larger than the pivot, and one that will be the first item starting from the right smaller than the pivot. And we swap, and repeat, and swap. When we can’t swap anymore, we take care of each side of the pivot to sort items out again...by calling the same function. Recursion - again.
I should have started with this : Tom Scott makes brilliant videos about algorithms and manages to make things simple. I would definitely recommend watching. I realised that as for every subject, there is a culture underneath it, which is basically a storage of geeky jokes. Understanding those gives the same amount of satisfaction as would being a small elephant joining a new tribe - or just simply someone living with constant FOMO. A person called hang kikuta wrote “I usually clean my room with bogosort" and another person called Klappspaten said “I recently read a paper on a new linear sorting algorithm: It's called Stalin-Sort. It achieves this by simply eliminating any element that isn't in order.” Am I now part of something new??
Answer is yes. Step 1: Listen to the problem. Pay attention to all the details. Step 2: Example. Debug your example and ask yourself ‘is it big enough?’ (most of the time examples are too small), ‘is there any way it’s a special case?’. Try to make a drawing of your example. Step 3: Brute force. Come up with one ASAP. State a naive algorithm and optimize from there. But don’t code just yet! Step 4: Optimize. Step 5: Walk through. Make sure you understand every detail before you start coding. Step 6: Implement. Modularize. Refactor. Error check. Good variable names. Step 7: Test.
Following Gayle’s book, I started to read the “Interview Questions” part. Pages filled with problems - not the most welcoming place. I focused on the “URLify” challenge: write a function that, given a string, replaces all spaces with the characters ‘%20’. Naively - very naively - I thought I had picked a fairly easy one. I had the flowchart beside me, but it didn’t feel particularly useful. Why? - I don’t know how to organise my ideas efficiently in this process. - I don’t have enough knowledge in the language I’m trying to solve this in. Or rather, I have big gaps in my knowledge of what a programming language can do. Therefore, this is even more useful than I thought it would be. So after trying to solve that problem for some -way too-long- time, I found this resolution that I copied in a fiddle and tried to comment. There are two scans in this approach: the first one determines the amount of spaces the “urlified” string will need to have, and the second will edit the string so as to either add the ‘%20’ or just copy the current letter.
.png)
.png)
What I learnt from this problem: • to manipulate strings try to transform them into array • the split method in JS • a common approach in string manipulation is to start by the end and to work backwards
I randomly tried to go back on Codewars. The first problem I got seemed fairly easy (should I be more vigilant towards myself? Turn on an internal alarm every time something looks easy?). Anyway, it looked quite similar to fizzbuzz; so the question was, if it looks easy, then can I find a better way to implement it? Following Gayle’s advice again, I tried to • rewrite the problem to make sure I went through every case. What is the expected output?
.png)
• write a brute-force algorithm. Chained 'if/else'. Something super ugly, but something that works.
.png)
• after the brute-force one has been tested, find a way to make it look more elegant. Refactoring.
.png)
• and eventually, using a switch case for more readability.
.png)
So after solving this, my confidence has improved. I mean, I know there are multiple ways to make this more concise and probably more elegant, but also a hundred ways to make it unreadable by trying to synthesize it until it's full of i's and el's. So for now I'll stick to that. Feel like I'm slowly starting to understand the methodology I need to adopt.
More Codewars.
.png)
.png)
.png)
So at this point, it feels like all I’m doing is CODEWARS. I wake up kata, I sleep kata, and it’s merely all I think about all day. There is something dangerously addictive about it. Like, at some point, I wish I wanted to do something else, but no, I’ll spend way too much time trying to solve a problem. The good thing is - my logic has improved. I am quicker and my brain seems to be formatted more into an automatic problem-solving way of doing things. I thought I should share this article giving some good insight and methodology on how to become a codewar god. Combining Gayle’s way of doing things with Alice Cheung’s advice, it does feel like there is a successful recipe to get a grip on algorithms.
