Exploring two common ways to make applications more efficient
Throughout a software developer’s career, there are some recurring to-solve problems, such as counting, stating if a condition is met or not, choosing the best data structure to suit a particular situation, and so on.
One of the most common misbeliefs is marking a problem as solved when its compilation ends successfully. When a project, an application, a framework, or a library builds correctly is a major milestone, no matter what.
Nevertheless, working software isn’t always the ending point, mostly regarding handling its efficiency.
Until a not-so-long time ago, I could consider all the software I built as done when they properly worked, after testing and debugging. But just recently, I realized how the time a program spends to be executed is a key aspect of the overall software base.
To maximize software’s efficiency, copious common patterns are designed to boost its soundness and enhance the developer’s skills.
Let’s look at theafm.
For a software developer, problem solving is a never-ending skill to sharpen.
It’s a multidisciplinary compound, made not just of coding skills but also math and logic. And most important, it’s not closely related to Computer Science, but it can perfectly fit several aspects of our ordinary lives.
In a few words, we could state that problem solving refers to adopting some methodologies that, alongside the current tools and abilities we own, can make us realize different objectives.
It suits many tasks, for instance, repairing a computer, solving a math equation, and playing chess.
When it comes to computer science, two common solving patterns are massively involved in problem resolution. And, as if it wasn’t enough, they are also patterns that are largely required by interviews in the IT field.
More specifically, they are the “Two Pointers pattern” and “Frequency counter pattern.”
Without further ado, let’s jump into discovering them.
You’ve been asked to reverse a string. Normally, someone should use up to two nested loops to achieve that. That would perfectly work, though the software time complexity would skyrocket up to O(n²), quadratic complexity.
Luckily, there’s an effective workaround to prevent this through the Two Pointers pattern.
The basic idea follows:
- Use two different indexes through one loop. The first one starts from the beginning of the string, and the second one, from the last item.
- While the second index is greater than the first one, I can go further by swapping the internal characters.
Through this pattern, you’ll be able to reduce the time complexity from
O(n²) up to
O(nlogn). The following snippet showcases this pattern through the C++ language.
How many times have you grappled with counting something inside an ADT? Many, I suppose.
Likewise to the past pattern, the Frequency Counter one allows you to reduce access to nested loops by creating a map.
If you don’t know, a map, similar to a dictionary or an associative array, is a data structure made by pairs of key-> value.
For example, If we have to deal with checking if all the items stored in an array are also contained in another one, one of the most adopted solutions is to approach through two nested loops and output true or false, accordingly to the research.
However, by introducing a map, we can drastically reduce the time complexity up to
Let’s see how to implement it.
We’ve reviewed two of the most common coding pattern to increase the quality and efficiency of the software we’re building.
To sum up, remember that sometimes… less is more, especially when it comes to code.
Thank you very much for reading.
Want to Connect?If you want to reach me to discuss a project or simply chat, here’s my GitHub link.