Data Structures and Algorithms are at the base of almost every application we code, every project we create. Interviews for developers involve DSA as it helps test logic and problem-solving skills of the candidate. In recent years, there has been an enormous growth in the number of competitive programming websites and courses provided in DSA. Before we dive into understanding the roadmap, let’s learn what exactly DSA is and why is it important.
WHAT IS DATA STRUCTURES AND ALGORITHMS?
Imagine having sequins of different colours mixed after a long sewing session. You need to organize them based on colours so that you don’t face any difficulty in your next sewing session. These containers can be thought of as data structures where different kinds of sequins (data) are stored based on predefined criteria to ease solving problems.
A data structure is a named location where data and information are stored and organized based on the associated operations in order to increase the efficiency of programming. Algorithms consist of ordered steps to solve a particular problem or achieve a goal. Learning data structures and their algorithms is essential to create clean and optimized code.
ROADMAP TO LEARNING DATA STRUCTURES AND ALGORITHMS
Let’s learn the steps to acing DSA in detail.
CHOOSING A LANGUAGE
The choice of a programming language solely depends on your priorities. Most people choose either C, C++, Python or Java. Each of them have their fair share of pros and cons. The following 5 factors can help you determine which programming language will suit your needs the best:
- Purpose of Learning — Why do you want to learn DSA? Is it for competitive programming, creating projects or cracking interviews?
- Career Goals — Are you aiming to learn DSA for a particular company’s interview? Talk to the employees and get to know what language is preferred there and which will help you score better.
- Ease and Comfortability — You might have been programming for long using one language. Being comfortable and knowing the syntax at the back of your hand might make this a better option. If you think you can code easily and efficiently using this language, go for it as long as other factors go well with it.
- Usage — This is an important factor to take care of. Determine how commonly a language is used. Usually, people prefer C, C++, Java and Python for DSA. There are other languages too, and there is no harm in using them. However, avoid using languages that are no longer in use.
- High Level or Low Level — The choice of the level of language is based on your application.
GETTING STARTED WITH THE BASICS
Whichever language that you select, you need to be thorough with the syntax and know the data structures that the language provides. There are several primitive and non-primitive data structures that you should be aware of and learn how to code them.
Learning and mastering these isn’t as tough as it seems to be. You need to strengthen your logic and not mug up the code as it is. Follow the 3 steps to be stronger at your fundamentals:
- Visualize by drawing
- Understand and Code
Often people think drawing and paper-pen practice as a waste of time but when you learn data structures, this tends to be the best way to strengthen logic. You might have to spend a lot of time in solving problems during the first few days. However, it will seem much easier once you get used to solving similar problems.
One of the most common applications of data structures is Search and Sort algorithms. These come in handy not only in programming but even in day-to-day life. The most commonly used of these are:
- Binary Search
- Search an element in a sorted and rotated array
- Bubble Sort
- Selection Sort
- Insertion Sort
- Merge Sort
- Heap Sort (Binary Heap)
- Quick Sort
- Topological Sort
ALGORITHMS YOU SHOULD KNOW AND MASTER
- DFS and BFS Traversals
- Dijkstra’s Algorithm for Shortest Path
- Prim’s and Kruskal’s For Minimum Spanning Tree
- 0–1 Knapsack Problem
- Subset Sum Problem
- Longest Common Subsequence
- Longest Increasing Subsequence
- Modular Exponentiation
- Sum of Bit Differences among All Pairs
MAKING CODE EFFICIENT
Every problem can be solved in various ways. So how do we analyze and select the best solution to a problem? Here is where time and space complexity plays an important role. The time complexity of an algorithm determines the amount of time taken by an algorithm to run. Similarly, the Space complexity of an algorithm specifies the amount of space or memory taken by an algorithm to run.
Understanding the Big-O Notation helps understand us this quantitative measure in a much better way. Here are a few O notations to understand time complexity better. Imagine a class of n students and give a coin to one person randomly. The task is to find who has the coin.
- O(1) — It has been found that the coin is with one among 8 students in the classroom. Going and asking individually will consist of 8 questions. Since the number is a constant, the time complexity is O(1).
- O(n) — To find who among the entire class of n students has the coin, going and asking them individually is O(n).
- O(n.logn) — Divide the class into two groups, then ask: “Is it on the left side, or the right side of the classroom?” Then divide it into two and ask again, and so on. Repeat the process till you are left with one student who has the coin. This is what you mean by O(log n).
- O(n²) — You go and ask the first person of the class, if they have the coin and if they know who among the others have a coin. This is what we call O(n²).
Each assignment statement, return statement is counted as 1 unit. Find the cost of each statement, the repetition and then find a total number of units. In the below example, 4n+4 = O(n).
The following table consists of the complexities of the common data structures and algorithms.
The precedence of time complexity is as follows:
RESOURCES TO BEGIN WITH
I have compiled some presentations and codes in DSA that can help you get a quick start on your DSA journey and give you an edge while learning the fundamentals.
- Introduction: Arrays, Structures, Pointers, Recursion
- Linked Lists
- Stacks and Queues
- Sorting Techniques
- Search, Hash and Store
GITHUB REPOSITORY WITH COMMON DSA CODES: Click here
Here are some external author documents that can be of help:
NOTES ON ALL DSA: Click here
YOUTUBE TUTORIALS: Click here
GUIDES FOR REFERENCE:
DSA IN EVERYDAY LIFE
The first and foremost question that we ask before learning something new — Will it even help us in everyday life? Concepts used in DSA does help you in various everyday tasks as shown below.
TIPS TO ACCELERATE YOUR JOURNEY IN DSA
- Understand the fundamentals of the language that you are programming in. Learn beyond the theory by implementing all concepts in different ways.
- Understand the depth of time and space complexity. Code and test.
- Focus on strengthening logic instead of studying existing codes. A better logic will help you solve more unseen questions.
- Improve problem-solving skills not only specific to programming. It changes the way you think and can help you gain more exposure to larger problems.
- Practice coding on sites like Leetcode, GeeksForGeeks, CodeChef, HackerRank, HackerEarth, CodeForces, etc. While practising, ensure that you solve at different difficulty levels. Do not stick to a particular level and solve all from that only. This will reduce your exposure to higher difficulty questions.
- Keep calm and believe in yourself. No question is unsolvable.
Hope this helps you along your journey. Do comment about how it helped you. Feel free to connect with me on Twitter.