I've began reading The Algorithm Design Manual by Steven Skiena as means of preparing for technical interviews. I will admit, I am not a fan of them but it's a non-arguable process you will eventually have to go through if you plan to work as a software engineer. From the places I've worked at, only one has required I take a technical interview, however, the most difficult task of taking these interviews is knowing what to study and how. I disagree with the notion of sitting infront of a computer doing leetcode 24/7 until you land a job at some tech/non-tech comapny doing tech work. While solving problems on the platform does require skill and the ability to know fundamental concepts in data structures and algorithms, it merely rewards recognizing a series of patterns and question styles. One can argue this is the same for many real-world tasks:
You encounter a problem
-> You recognize it from somewhere else or someone else has faced it
-> You see what they did, how they solved it (recognize)
-> You try the same thing out (pattern)
But of course, then there's:
You encounter a problem
-> You recognize it from somewhere else or someone else has faced it
-> You see what they did, how they solved it (recognize)
-> You try the same thing out (pattern)
-> it fails
-> it fails??
-> uhhh...
Leetcode doesn't really transfer all that well when the work you are doing is unique, which more often than not it is, so what then? I don't agree with rewarding pattern recognition and memorization. It is good, I don't disagree with that, but it is much better when you can disect a problem and suggest solutions using the tools at hand you normally have if you were in that scenario. Memorization and recognition is only a factor of tackling real-world problems. But, I digress. It's unlikely to change, so let's ride the interview-train.
Most of my work in this, and consecutive, solutions and explanations are going to be from Skiena's book. I can't say I know all of this myself well enough to write a full series on it, so I am going to be reading from many sources and doing my best to explain them here. I'll also make attempts at providing code and maybe even some visualization (if I have the time).
Insertion sort: what is it? It's a comparison-based sorting algorithm that build up to a sorted array by taking each element, one at a time, and comparing it to the item on the left (or right, depending on how you're applying it), on some criteria. For example, suppose we wanted to sort the list below from lowest to highest using insertion sort:
If we started at 1, well there's nothing to the left, so we move up to the next item. Because we're going from lowest to highest, \( 1 < 2 \), so nothing happens again, and we move to 10. Again, \( 2 < 10 \), and we keep going. Now comes 4: \( 10 > 4 \), so we move 4 into 10's position and 10 into 4's.
Because the last index we checked was at 4, the next item to check is 6. Since \( 10 > 6 \), we do the same and keep going until we finish with the last element.
Once we finish checking all the elements in the list, we're able to see that it's now sorted.
Of course, there will be cases where you don't just have to move an item to the left only once, i.e., you have to keep moving them until said criteria fits. If the list was [2, 3, 4, 5, 1], when we got to 1, we'd have to move 1 all the way to the start, which is where the criteria fits.