Enhancing Software Engineering Skills through Algorithms and Data Structures Mastery with Michael Ayomide Johnson at Techstrong Con 2024

Um, hello everyone. Uh, welcome to this session. Uh, we would be, uh, talking about the importance of, uh, algorithm and data structures and how it's answers your software engineering skills.

Um, we'll take a look at some commonly used algorithm and data structures, sample real world, uh, applications of them, and also touch on how, uh, you might want to use AI to your advantage on your journey to proficiency. Now, before we go into the presentation, uh, lemme state that algorithm and structures, uh, uh, is a very, uh, vast subject and will require a lot more than, uh, just a 30 minutes presentation to become proficient. But my aim is to show you why I believe that, um, it's important to master the skills.

Uh, but first, uh, let me, uh, introduce myself. Uh, my name is Michael and I'm a software engineer with over a decade of experience. Um, during this period, I've had the privilege to, you know, work with, uh, a number of leading companies in the sector, including, uh, meta at the end and wise.

Uh, and I've also had the privilege to contribute to a number of, uh, large scale distributed, uh, system projects. So, uh, why is it important to, to become proficient in, uh, algorithm and data structures? Of course, there are a lot of reasons, but I just thought to note, uh, four of them down here.

Uh, one is, uh, to build, you know, scalable solutions. Uh, you know, technology has become, uh, part of our daily life, and it dominates a lot of industries than, uh, it w it was a few years ago, for example, um, uh, an automobile company today could qualify to be called a tech company, simply because tech is really embedded into, uh, a lot of cars that we drive these days. You know, talking about self-driving cars.

Uh, computers no longer just execute instructions that we give them, but using modern technologies like say machine learning, computer vision, lms, you know, artificial intelligence, uh, and many more, um, computers process large data, and they're making, uh, their own decisions. So I believe now more than ever, uh, it's, uh, you know, it's important to pose the skills to build scalable solutions. Uh, secondly is that, uh, efficient algorithms actually facilitate faster innovation.

You know, um, without efficient algorithms, uh, certain problems will take longer time to, to solve. Um, for example, uh, we're seeing a lot more use of technology in the, you know, in the healthcare sector. Uh, some scientific ex experiments, uh, can be carried out these days using, you know, simulation software.

And this helps reduce experimentation time. Next is that, uh, application adoption time is reducing. Um, you know, years ago, it took some of the most, uh, some of the most popular applications that we see today, uh, over three years to gain, say millions of, uh, customer base.

But over the years, this number has been reducing. Uh, it has been on a decline, and we see with the adoption of Chad GPT, uh, which took, uh, about five days, uh, you know, less than a week to, to reach, uh, a million, uh, users. I mean, with that kind of adoption, uh, it's obvious that building for scale, um, is important from the, you know, from the onsets.

Uh, this is not to say that every application that you build, uh, will reach a million users, uh, and maybe not in the first week, but just to point out that the potential is there because, um, there are a lot more people using technology, uh, as the days go by. Last, but not the least, um, you know, improving, uh, your skills in so, uh, in algorithm mandated structures actually helps you to secure, uh, maybe your dream job at some reputable companies. And I can personally, uh, attest to discuss, um, yeah, with discus, I've been able to say, receive, uh, multiple offers from top tech, uh, companies.

All right. That's, uh, that said, uh, let's quickly, um, cover some of the common terminologies that we'll be talking about in, in this presentation. Uh, number one is algorithm, which I've mentioned a number of times.

Uh, and it's simply, uh, a series of steps that you take to address a problem. You know, this could be as simple as instructions, uh, for preparing your meal or as complex as processing, uh, or crawling the web and, you know, indexing information from the web, um, and then data structures as, uh, a way that we organize and store this data, uh, in the computer so that we can access them and modify them. Lastly, time and space complexity, which is something I believe is very important to grasp.

Um, if you want to improve your skills, as you know, a software engineer, you need to know how much time your, uh, how much time your program requires to perform an operation, and how much space it also uses, you know, so time and space complexity is the measure of, you know, the amount of time or space or memory that, uh, your algorithm requires to run. Uh, with respect to input size, and we'll talk a little bit more about what I mean by respect to input size, uh, on, on the next slide. Um, and the time and space complexity of algorithm is, you know, generally classified, um, or expressed by the big O notation.

Um, here I've listed some of the common big O notations we have, uh, o of one, which is constant o of login, which is logarithmic. O of N is linear. O of n login is linear, rhythmic, and o of n square is quadr again, um, we will talk a little bit more on the next slide, but just to point out that the, um, legal not, uh, notation of complexities is a very, uh, huge topic and outside the scope of this con, uh, you know, this presentation, but I believe the knowledge of it is vital to distinguish between optimal solutions and, you know, suboptimal, uh, algorithms.

Um, so here is, uh, a table where I try to show how, uh, algorithms with different complexities might, you know, perform, uh, given different input sizes. On the left, uh, I have the input sizes ranging from 10 inputs to, uh, I believe this was 1 trillion inputs, um, as a size. And then going from, uh, left to right, uh, algorithms with different, um, different type complexities.

For algorithms, we have the constant linear, uh, logarithmic, linear, linear, rhythmic, and quadratic. And from top to bottom, it shows how many operation each time complexity or each complexity required to execute, uh, in order to fully perform the operation. That's, uh, you require to perform.

Uh, just to give quick, uh, uh, examples of this, for example, we can see that if it takes a constant algorithm, uh, one operation, uh, to solve a problem with an input size of 10, it'll still take its one operation to solve a problem with an input size of 1 trillion. Um, for Lmic, we have ranging from four operations for 10 impute size to 40 operations for, um, a trillion input sites. But on the other end of it, we have quadratic, which goes from a hundred for 10 epi sites to, I think I had to Google this, which is some septillion, uh, you know, uh, which is something that's probably outside, um, acceptable, uh, number of operations.

Uh, and using maybe an example, say you are looking for a book on a bookshelf. If you use a constant time algorithm, whether there are 10 books on the bookshelf or there are 1 trillion books on the bookshelf, it takes just one check to find that book. Uh, and if you use logarithmic, uh, search, uh, for 10 books, it takes four checks.

Uh, we'll see, uh, that, uh, in a later section where we talk a little bit about binary research. Um, and if you're looking for, uh, a book and you have a trillion books, it takes just 40 checks. So we can see that formic algorithm, the difference between 10 books and 1 trillion books is just additional 36 operations, which is, you know, still quite acceptable.

But, um, if you go on linear search, it might take a trillion checks to find a book in a bookshelf that contains a trillion, uh, books. Um, uh, I hope that's, you know, clarifies a bit on, uh, complexity. But let's take quick looks at some, uh, data structures and common operations that are performed on them.

Uh, the reason I want to talk about operations performed on data structures is because personally, um, and I think this would apply to a lot of software engineers also, uh, how I decide what data structure to use, uh, depends on the, um, you know, the operations that I want to perform. So these are some common operations you wanna insert into your data structure, retrieve from it, remove and search. So we will talk about three basic data structures, uh, arrays, link list, and ash tables.

Um, and we will break them down into how they perform for those, uh, four operations, uh, mentioned in previous slide. So for arrays, um, uh, starting with the insertion operation, inserting at the end of an array is a constant time operation. You know, um, uh, however, in insert anywhere else, say at the beginning or in the middle, uh, is in worst case, linear time operation.

And the reason for this is, if you need to insert at the beginning of the array, you have to shift every, uh, item that is already in the array. You know, one step, uh, forward bef to make room for the new entry. Uh, and, uh, so that makes, uh, inserting in the middle or the beginning linear, uh, on the retrieval operation, it's constant because arrays are index based, as you can see here.

So if I need to get an element or an item, I could easily say, give me the item in, uh, index two, and it goes straight to index two, the position to get the item from me. Uh, removal is similar to insertion for arrays, um, as, uh, in, uh, removing from the front or the middle would take linear time operation, because when you remove, you need to shift items again, backward. Uh, but removing from the end is, uh, constant search is, um, that, you know, two or multiple, um, ranges of time complexity, uh, depending on whether the array is sorted or not, if it's sorted, you could use, uh, a binary search to search, and that would take logarithmic time.

If it's not, um, it might take linear time to search, um, which is, uh, or event. So when or how do I decide, uh, to use array? Um, as I can see from here, the most optimized, uh, operation is to retrieve from the array when you know the position of, you know, what you're trying to get.

So, um, when I have operations that require random access, uh, meaning the access to the items is not in a specific order, it could, I could get from index two and then get from index zero, get from index four, uh, I would prefer arrays because it allows me, um, perform the operation in constant time. Next is link list. Uh, also stores a list of items, uh, like an array, but uses a different concepts, uh, uh, with nodes and pointers to next or previous, uh, nodes, uh, depending on if it's a single good single link list or a single link list or w link list.

Uh, the insertion operation for link list is constant when you insert in the front and at the end. Um, however, if you, uh, insert in the middle, uh, it's linear because it needs to loop through to find, uh, the position where you want to insert and then perform the insertion operation. Um, you can typically use a different, uh, uh, data structure, which is assets that we'll talk about next to optimize in inserting the middle of a link list, um, to make it more constant.

But, uh, by default in, insert the middle of a link list without any optimization is, um, linear operation. And similarly, same thing applies for removal, removing from the beginning and the end is constant. But, you know, uh, in the middle it's linear to search from a link list, regardless of whether the items are sorted or not.

Um, it takes, uh, linear time, and that's because, um, you can't perform binary research, uh, typically on a link list. So you have to move from one node to the other to search. So when would I decide to use a link list?

Um, the most optimized operation here is inserting and deleting from the beginning. Uh, and like I said, if you combined with say, hatchable, maybe inserting and deleting from many position would, uh, be optimized to constant. So I typically think about using clease if I need to, um, build something that has a lot of in insertion and deletion, uh, from the list.

Um, for example, uh, think about the queue where we insert at the back of the queue, and then we remove from the front of the queue or a stack. Um, these are good use cases of, uh, linked lists. It's also used in cases like where you're building, uh, a list recently used cache, for example, where, um, items are put, um, either at the beginning or the end, depending on implementation, and you remove from the other side when you need to eve.

So, uh, last basic data structure, uh, is ash. And this, depending on the implementation, um, is relatively optimized for all four operations. Um, and I know you might be asking yourself, since ash tables are optimized for all of these operations, why not use them all the time?

And yeah, that would be a valid, um, uh, thought process. However, um, there are limitations to, um, what situations, uh, hash tables would be suitable. Uh, for, for example, uh, for use cases where the order of insertion is important, hash tables would not be appropriate because it does not guarantee that you read, uh, items in the order that they were entered.

Um, and also, um, if you need to sort items, um, ash tables typically do not support certain, so when would I use an ash table? Um, I would use a ash table. Typically, when you require a key value pair, um, data to store, for example, in a dictionary, you have a word, and the value is the definition of that word.

That's the key value pair. Or for example, in some Mongo real world, um, applications, A DNS that transforms the web, URL into, um, IP addresses, uh, would, and vice versa would use, you know, um, a key value, uh, pair actionable to store. Uh, this information where the keys, the, you know, web BRL and the value is say, a list of ips for the URL.

Uh, also, ash are commonly used in caching systems, you know, like main cache. Um, there are a number of advanced, uh, data structures that, uh, you know, we could talk about. But I, you know, narrowed down to some of these three that I think I've personally seen used a lot, uh, EAPs tries and graphs.

And, um, instead of focusing more on the time complexity to avoid reputation, I would just, you know, focus more on the use cases of this, uh, advanced data structure. Um, starting with ips, ips are generally efficient for storing data that are required to be sorted in a certain way. You know, uh, the two, uh, most popular types of, uh, ips that you find out there is mean IPE and max e.

And, uh, you use this when you wanna store, when you want to, uh, quickly or efficiently retrieve, uh, say minimum, uh, item in a list, or the maximum item in a least dependent type of e, uh, implemented and some real life, uh, cases. Uh, uh, Netflix trying to show you the top 10 movies that are watched in a region or maybe, uh, CPU scheduling system, trying to get what's the next, uh, task to schedule based on certain priority, you know? So, uh, ips, uh, useful for this because of the, uh, time complexity.

Um, it's, you know, constant time to retrieve the next smallest or the next biggest, um, item on the list tries, um, is something that we all would've come across in one way or the other, uh, in our everyday life, uh, even if we might have not noticed it. Uh, if you've, you know, typed a message on your smartphone or you've set on Google, you've centralized in action because they're commonly used for auto completion. Um, and suggestion, uh, features, you know, so when you start to type, uh, a query on Google, or you start type a message on, you know, your phone and you see suggestions to complete, uh, most likely the application is using some variation of the try data structure.

Um, and also spellcheckers, uh, that now being used in applications like, uh, Google Doc, um, also use, uh, some, you know, variation of trials to implement, uh, this pair checkin Last, uh, but not least, uh, is graphs. Uh, here I've augmented the complexity of the operations because for graphs, depending on the implementation, um, the complexities, you know, the different, uh, complexities for this. And there are a number of different operations that you, uh, perform on graphs also.

Um, there are a number of real world applications for graph, uh, some obvious and some ed, uh, the obvious ones that we know that we use every day, say your map application on your phone, uh, social network, uh, you know, you as a node connected to your friend and your friend's friend, and the old web is a giant, uh, graph on so on. While some less, uh, obvious use cases, uh, say phone editing apps, uh, imagine that every pixel on the phone is a node. Um, and while trying to say, remove a background, the app tries to detect connected nodes to remove background.

And this is a lot more complicated or complex than, uh, what I've said. But, uh, the fundamental concepts, uh, used for that, um, has to do with graph. Um, before I close, um, close up the data structure section, I thought to share, uh, this quote by Linox stove out the creator of Linux.

And the highlighted part says, bad programmers worry about the code. Good programmers worry about the data structures and their relationships. Uh, this goes a long way to emphasize the importance of, um, uh, data structures for software engineers.

So, um, let's take a quick look at some, uh, common algorithms that we need to be familiar with. Again, there are so many algorithms, uh, out there, uh, but I just thought to list some of the common ones that you start to learn as a software engineer trying to be proficient with, uh, algorithm and digital structures, you know, uh, also the time and space complexity of this, uh, available publicly online. So, uh, I would omit that part here also.

Um, but one thing I would like to focus on here, like as I mentioned in previous, uh, section, is what's important is how I decide, uh, what's the right tool to use, what right data structure to use or the right algorithm to use. So here, for example, for sorting algorithm, um, if I have a constraint of memories here, I wanna sort a list of items where I have memory constraints. I would rather prioritize some in place algorithms like, uh, quick sorts rather than merge sorts, um, because I don't want extra spaces to be used, but if I want a stable algorithm, I would opt for, um, merge sorts, um, as opposed to, you know, quick sorts.

Uh, I've talked a bit about linear search and binary search in previous, um, uh, sections. So just go straight to graph algorithms. Uh, union find algorithm is actually a very, you know, useful algorithm.

It's quite widely used, uh, in a real life scenario. Uh, for example, uh, if you want to check on LinkedIn, if I'm connected to, uh, say some popular artist in some way, uh, either directly or through my connections, uh, you know, find algorithm is suitable for solving that problem in network security. If you build a private network and, uh, every time you want to check if one of your servers, um, has, uh, created a connection to the public internet, uh, net, um, uh, union find is suitable to, to, you know, solve that outside network security generally, uh, if you're asked to build a prototype for a new airport, for example, um, and you need to check if there is an unwanted connection between the secure area, say the, um, the boarding area and the general area says, uh, to prevent people from unwanted access to, uh, or unauthorized access to those areas.

Uh, union, union find algorithm could be used, you know, in, in such situation. And there's so many other, um, use cases for union find algorithm. Uh, but jumping into the last two, dextra and ETA algorithm are algorithms that are important for, um, finding shortest parts to, you know, on a graph.

And some of our MAP applications used it, and they're interesting algorithms to actually, uh, learn. Now, finally, I'll be talking about the path to proficiency. Um, re and I would be using personal experience to, you know, share this.

Uh, what I did, um, on my way to learn or become proficient with our grading mandated structures is I started by using educational platforms like Coursera, you know, Udacity and the likes to, um, take courses on these different data structures and the algorithms. Um, and the, one of my favorites is a two part course, uh, offered on Coursera, uh, by Princeton. Um, I think it was a professor called the Robot Cedgwick.

Um, uh, it's called algorithm. I think they're part one and part two. Um, this focuses most of the examples are in Java, but the, I, the overall concept is actually useful, uh, regardless of the language.

Um, and yeah, I, I find it very, uh, useful. So, um, first I took courses, like I mentioned, and then taking the course actually helps you get familiar with, you know, the, uh, algorithms and the data structures. But, uh, in order to exercise the brain to be able to identify the right algorithm or data structure to use when solving a problem, you need to, you know, uh, practice and participate in, uh, coding challenges or just personal coding on lead code, uh, and or similar platforms.

Uh, this is gonna help you get more familiar with seeing questions or problems and being able to attribute it to the right data structure, uh, algorithm to use. Um, and lastly, uh, something I wish that existed, uh, years ago when I started learning algorithm and data structure was generative ai, but I mean, it's not too late, and I'm starting to even AURs, uh, the power of AI to analyze my code and, you know, suggest possible optimizations with, you know, explanation as to maybe why the newer suggestion is even better. Uh, and of course that would be in terms of, say, the time complexity or the space complexity.

Um, and just to, you know, close this part, um, uh, I thought to mention that, you know, ai, the capability of AI is growing really rapidly, and I, I foresee that in the nearest future, um, code completion tools on ID is, like you say, intelligent would not just help us to, you know, write code faster, true suggestions, but would also help us write code better, you know, by, uh, suggesting optimized, uh, versions of, um, our functions. You know, I mean, that's my personal opinion because, uh, from the capabilities of ai right now, we're getting, you know, to that point, just to recap, um, uh, all of the things that we've talked about, um, started by talking about the importance of, uh, algorithm and data structures. And then we looked at how different algorithms perform given different, uh, impute sizes.

Uh, we touched on some of the common data structures and algorithms and, you know, the operations that you perform on them. Um, and finally, uh, the steps to actually becoming proficient. Um, and I'm, you know, hoping that you take these steps, um, judiciously on your way to proficiency.

Um, I'd like to close, uh, you know, this presentation by reminding us that this journey, uh, you know, to master the skill is a marathon and not a sprint. Uh, it's going to involve relearning some topics over and over again. You need to be patient with yourself.

You need to take breaks when needed, um, keep practicing and eventually all of the pieces will start to come together. Um, I hope this has been helpful for you. And, uh, I wanna say thank you for listening.