Coming from the background of Competitive Programming and Software Development, I have compiled a list of algorithms and data structures that every programmer should know about. We will see what they do and where they are used with simple examples. This list is prepared to keep in mind their use in competitive programming and current development practices.
Here are the Top 7 algorithms and data structures to know:
- Sort Algorithms
- Sorting by price, popularity, etc. in e-commerce websites
- Sorting by score in HackerEarth contest leaderboard
- Search Algorithms
- Searching for a song in a sorted list
- Git debugging via git bisect
- Used by search engines for web-crawling
- Used in AI to build bots
- Finding shortest paths on maps
- Hashing
- Routers use IP address → Path mapping
- Checking for duplicates efficiently
- Dynamic Programming
- Used in many DP algorithms
- Real-world example: Duckworth-Lewis method in cricket
- Exponentiation by Squaring
- Used in RSA encryption
- String Matching and Parsing
- KMP Algorithm is used for matching substrings
- Regular expressions for validation and parsing input
- Primality Testing Algorithms
- Sieve of Eratosthenes – for finding primes in a range
- Trial Division up to sqrt(n) – when memory is limited
- Fermat and Miller-Rabin Tests – probabilistic checks
- Used in encryption (e.g., RSA)
- Hashing algorithms
Sorting is the most heavily studied concept in Computer Science. Idea is to arrange the items of a list in a specific order. Though every major programming language has built-in sorting libraries, it comes in handy if you know how they work. Depending on the requirement, you may want to use any of these.
More importantly, you should know when and where to use them.
Binary Search is used to perform a very efficient search on sorted datasets. The time complexity is O(log N). The idea is to repeatedly divide in half the portion of the list that could contain the item until we narrow it down to one possible item.
Depth/Breadth First Search are also commonly used in tree/graph data structures.
Hashing is the most widely used technique to find appropriate data by key or ID. The data structure is referred to as a Hash-Map or Hash-Table or Dictionary.
Dynamic Programming (DP) solves problems by breaking them into simpler subproblems and storing their results to save time.
This analogy explains DP like a 4-year-old could understand it.
Instead of looping N times, Exponentiation by Squaring calculates powers in O(log N). This method is commonly known as Binary Exponentiation.
Pattern matching and validation are widely used tasks. For example:
To test whether a number is prime, we use:
Applications:
We'll discuss some advanced algorithms every competitive programmer should know in the next post. Meanwhile, master the above or comment what you think every beginner-intermediate programmer should know.
Till next time. Evíva!
