DEV Community: Alberto González Rosales

A Tale of Interviews: A Collaborative Approach to Problem-Solving

Alberto González Rosales — Fri, 14 Apr 2023 07:01:20 +0000

No matter how experienced a developer you are, being interviewed for a new job is always stressful. I can tell from experience. In my case, I have only been working professionally as a Software Developer for two and a half years, and I've had to face the process of interviews five times already.

I have seen people focus too much on specific algorithmic problems, or training in online platforms specialized in interview challenges. But there is another side of the interviews which I think is as important, and people pay less attention to it.

So, if you are interested in my opinion on how people should focus their training for interviews, grab a cup of coffee and seat comfortably.

It's going to be a long ride! Python examples included!

Do Algorithms and Data Structures Matter?

The short answer is Yes.

Knowing about Data Structures and Algorithms will often help you get a job. Also, the benefits of having a solid algorithmic background include the capacity of making better decisions when faced with a challenging problem.

In real life, algorithmic problems won't appear like the academic exercises' statements. The more trained you are the most likely you are to be able to recognize an application of a Balanced Binary Tree or a Shortest Path algorithm in disguise.

With this in mind, I would recommend not training Data Structures and Algorithms solely for the interviews that you want to excel at. The design of algorithms and the use of the right data structures are topics beautiful enough to be studied just for the pleasure of knowing.

The scope of an interview is very limited. Instead, focus on the problem-solving part of the issue. Try to understand how to use an algorithm (or variations of it) for similar tasks. Study all the variants, and learn to recognize them in different situations. This will help you face new tasks with an open mind.

Don't memorize solutions. It won't take you anywhere. It is very easy for an experienced developer to ask the right questions that will put you on display if you only train for very specific topics.

Take a problem and try to solve it using different methods. Try to solve harder problems every time. Get out of your comfort zone.

It will pay off.

Focus on a Collaborative Approach

Most people train for their interviews on websites like Leetcode. There is no problem with that. These websites are good for training your problem-solving skills.

I have been participating in Competitive Programming contests for the last eight years at least, and I have always benefited from these online resources.

But here is one thing that is hard to understand for most software engineers wanting to perform well in an interview. They don't train the most important aspect of software development: Collaboration.

Usually, when you are faced with a problem in an online platform, it comes with some constraints on the maximum values for some input and maybe some time and memory limits for you to adjust your solutions to be more or less efficient. But this is not how it will be in real life.

It is not obvious how to map these constraints to real-life scenarios. They usually come in the form of very specific requests from the clients, or very specific characteristics from the team.

In a real project, the team will collaborate to determine what these constraints will be. You have to analyze your use cases, the time you have for the task, who is the final user, how many people will be working on it, and so on...

After a series of discussions, you will reach a consensus and finally start implementing a solution that suits your needs. And this solution doesn't even have to be the more efficient in some cases, but the fastest to implement, for example.

This is what interviewers want to see from candidates during the interviews as well.

You don't jump straight to implementing the best solution you know for the problem you are facing. Instead, you should use your interviewers as a valuable resource, treat them as if they were your teammates (in the end, you want them to be), and ask questions about how the team prefers the solution for the problem to be implemented.

This will lead to a very fruitful discussion where you can showcase your coding abilities and your collaborative ones. You could start proposing simple solutions and walk your interviewers through the process of how the solution can be improved using the best Aces under your sleeve.

As a final note on online training, I would recommend doing individual and team training. Use websites such as Codeforces or AtCoder, which have a huge set of interesting (and challenging) problems, and try to compete against yourself every day.

Don't focus on your rating. I have done that before, and it only holds you back.

Mock Interview

If you reached this point in the article, I would like to propose a little exercise. Let's have a mock interview where I will act as the interviewer. I will tell you how I think the candidate (you) should answer every task.

Of course, we will focus only on the programming challenge part. Other aspects of interviews, such as talking about previous experiences, are also important, but we will try to cover that in another article.

So, if you feel ready enough, let's go!

The Initial Problem

Let's start with the task that you will be solving. Keep in mind that if you and I are ever in this situation, I won't be using this same example, but of course, I will be using the same methodology 😉.

The statement of the problem is the following:

"Given an integer number X, find out if it is a prime number."

You might be tempted to go for the best solution you know to solve this problem. This approach, as I explained before, I think it is wrong.

Instead, what I would like to know are the different approaches to solving this problem. Also, I would be glad if you ask about the requirements for this task. Something like:

Should we aim for performance or to solve it faster?
Should we make a solution that is easy to understand for other developers?

Usually, some aspects to consider when creating the first solution for a problem are:

Easy vs Hard: Should we make an easy-to-implement solution even if it is not perfect, or should we go for a more robust solution that will be difficult to implement?
Naive vs Efficient: Should we deliver a working, naive solution first and then a more efficient one, or should we go straight to efficient?

Evaluate what your team wants to optimize for. Reach a consensus, and implement the agreed solution.

In my case, I would be glad if you would propose the easiest, fastest-to-implement, correct solution that you can think of and then guide me through the process of how to improve that solution. An example of a very good initial solution to this problem is something like the following:

# naive.py

def is_prime(x: int) -> bool:
    if x in [0, 1]:
        return False
    for i in range(2, x):
        if x % i == 0:
            return False
    return True

As we can see, this function is correct. Since a prime number is an integer only divisible by the number 1 and itself, it makes sense to iterate from 2 to x - 1 looking for a divisor of x. If we find one, we can immediately return False. Otherwise, we return True. As edge cases, the numbers 0 and 1 are not prime by definition.

This is a good starting point!

Now, before diving into optimizing this method, you can discuss the style of the code. Is it Pythonic enough? Do we care about it? Is it readable?

All these questions might not seem important at first but, since we work as a team, they do matter. Having a coding style is important because it makes it easier for every team member to understand each other's code, and it will speed up reviews and refactorings. Also, the code is more often read than written, so readability counts!

You might be tempted to show off your Python skills and rewrite the previous function as follows:

# pythonic_naive.py

def is_prime(x: int) -> bool:
    return False if x in {0, 1} else all(x % i != 0 for i in range(2, x))

I think this is a good, pythonic way to write this function. But, since the team is the most important thing here, this change should be discussed.

It might be the case that some team members are not so skilled in Python. Maybe, in this case, we should optimize for readability instead and keep the function as we first wrote it.

A more interesting addition, before getting into performance, would be adding docstrings to the function. As a said before, this code is most likely to be read by your team members in the future. It is important then, to make it easier for them (and your future self) to understand what this function is doing.

Maybe changing the function to something like the following will add more value:

# naive.py

def is_prime(x: int) -> bool:
    """This function takes an integer `x` as
    argument and checks whether is prime or not.

    Args:
        x (int): The integer number to test for primality.

    Returns:
        bool: True if the number `x` is prime, False otherwise.
    """
    if x in [0, 1]:
        return False
    for i in range(2, x):
        if x % i == 0:
            return False
    return True

First Optimization

Until this point, we have an initial solution that works. We have discussed important topics such as code styling, readability, and documentation for developers. These are all important things to consider when working as a team.

But we still haven't talked about the performance of the solution! So, it's probably time for it.

At this moment, if you would not bring up that this function can be implemented so it runs much faster, I would do it. And now is when you showcase all that algorithmic knowledge inside you!

The previous solution has a time complexity of O(x), where x is the input integer the function takes as an argument. This can be optimized to O(sqrt(x)) with the following code:

# sqrt.py

import math

def is_prime(x: int) -> bool:
    if x in [0, 1]:
        return False
    for i in range(2, int(math.sqrt(x)) + 1):
        if x % i == 0:
            return False
    return True

Or even like this, without importing the math library:

# sqrt.py

def is_prime(x: int) -> bool:
    if x in [0, 1]:
        return False
    i = 2
    while i**2 <= x:
        if x % i == 0:
            return False
        i += 1
    return True

I would be ok with either alternative.

I omitted the docstrings in the previous implementation for the sake of making the actual code changes clearer. But, it would be great to include the time complexity of the function in the documentation for developers. The more information you can give about your code, the better it will be for your team members and yourself.

You are doing great so far. Let's continue!

The Second Problem

So far, I was able to evaluate that you have the necessary collaborative skills to take on easy tasks with the team. Now it's time to complicate things a little.

This is the statement of the second problem I would propose:

"Given two integer numbers L and R, count how many prime integers are in the interval [L, R]."

Once again, I would recommend discussing what are the priorities set by the team regarding this task. Start simple and walk through the process of improving an initial solution. Emphasize that premature optimization is not a good practice.

Also, discuss the possibility to use the solution that you implemented on the previous task to solve this one. It makes sense that if we have a function that tells whether an integer is a prime number or not we can use it for every number in a range.

And this is something that you will have to do in real life. Usually, when a new task shows up, the team should look into the maintained projects to see what can be reused to speed up the implementation process. If you don't do this, you might end up coding duplicated functionalities.

That being said, a good initial solution for this task could be something like this:

# range_primes.py

from sqrt import is_prime

def count_primes(l: int, r: int) -> int:
    primes = 0
    for i in range(l, r + 1):
        if is_prime(i):
            primes += 1
    return primes

This is perfectly fine, and you have shown that you can reuse previous functionality to build new ones. As in the first example, you might be tempted to show off your Python skills and write this function like this:

# range_primes.py

from sqrt import is_prime

def count_primes(l: int, r: int) -> int:
    return sum(bool(is_prime(i)) for i in range(l, r + 1))

I recommend not going for this Pythonic implementation as your first option. Leave it for discussion, evaluate the readability of the code, and maybe analyze the differences in performance. Don't forget the docstrings!

The next section is when things get interesting. Keep reading. We are on the final step!

The Hardest Problem

Remember when I said previously that the constraints present in competitive programming websites are hard to map to real-life requirements?

Here is how I would present a difficult challenge for you to determine those constraints and implement the best solution that you can:

"Suppose a client wants us to provide the functionality of calculating prime numbers in a range as a service. They want the focus to be on performance because they plan to use this service very often. How would you implement it?"

If you have been practicing your algorithmic skills for interviews, you have probably solved problems similar to this one a few times. The main difference here is the change in context.

Instead of giving you precise instructions, numeric constraints, and input or output formats, I gave you a broader description of the task. And my goal here is the same as before: get you to interact with me as if we were teammates figuring out how to solve this problem from the little information we know.

Hopefully, after exchanging a few questions and answers, we can translate the previous, more ambiguous statement into something much more familiar:

"Given a set of queries of the form [L, R], answer, for each query, how many integer numbers inside that range are prime."

And this makes sense because the client wanted to use this service very often, as stated in the description.

We want to focus on performance. That should be our main concern when implementing the solution. But still, the best way to get to an optimal solution is to start with a simple one, analyze if we meet our performance requirements, and keep improving gradually. Let's see the entire example!

We could start by using the solution we implemented in the previous step. Is it good enough?

Let's assume that the maximum range of numbers we will have as an argument to our function is [1, 10^6]. Also, realistically, let's assume that the number of queries our service will answer per minute is around 10^5.

Our previous solution has a time complexity of O(sqrt(n)) to determine if a number is a prime. If we were to do that for every number in the range, the complexity goes up to O(n * sqrt(n)). On top of that, if we do that for every query, we will end up with an even higher time complexity of O(q * n * sqrt(n)).

Substitute the previous variables with the highest possible values they can have, and you will get that this solution will take around 10^14 operations to answer all the queries. Assuming that a computer can perform around 10^8 elementary operations per second, it will take approximately 10^6 seconds to complete all of them.

Note: Convert 10^6 seconds to days. You will be amazed 🤯.

This solution is unfeasible if the goal is to prioritize the performance of our solution. Let's see how we can improve it.

At this point, what I would expect is for you to take out the best of the training that you've had on all those online platforms, and show me an impressive solution. This is the time to showcase all your analytical and algorithmic skills.

But only now, because I know that you are a team player.

The Final Solution

Since this is a mock interview, I am very interested in knowing your approach to solving this last problem efficiently. Let me know in the comments how you would implement the solution or share your code on GitHub, don't be shy.

I guarantee you one thing: if you can make it to this point in real interviews, probably it won't matter too much that you don't know the optimal solution to this problem. It doesn't mean that you shouldn't try your best to solve it, but rest assured that you have done a very good job already.

That's it! Now I want to see your code!

Last Words

In this article, I tried to summarize some of the aspects I consider to be the most important in coding interviews. I made special emphasis on the collaborative part because I think most people underestimate how important this skill is. It is a must, especially if you want to work on a team with other developers.

I tried to guide you through a mock interview where I explained the thought process I would follow when faced with a standard coding task in an interview. I hope this exercise was useful and that it can help you in your next interview (as a candidate or as an interviewer).

Share your thoughts on this mock interview in the comments, and let's start a fruitful discussion.

See you soon! 👋

Sources

Code examples used in the article can be found here.
Hint for the last problem: implementation of the Sieve of Eratosthenes algorithm.

👋 Hello, I'm Alberto, Software Developer at doWhile, Competitive Programmer, Teacher, and Fitness Enthusiast.

🧡 If you liked this article, consider sharing it.

🔗 All links | Twitter | LinkedIn

A Tale of History: A Family Essay about AI Drama

Alberto González Rosales — Tue, 04 Apr 2023 08:00:39 +0000

The emergence of new tools based on artificial intelligence is raising concerns among an increasing number of people. Many wonder how much their already precarious jobs will last, which professions will disappear, and which areas of the economy will be most vulnerable to these new invaders.

And we should indeed be concerned, but to what extent?

Throughout our existence, we have constantly faced dilemmas like this. Just think of how Gutenberg's printing press took the 15th century by storm. Some predicted the loss of collective memory, as everything was now written on paper, and no one would remember anything to pass on to the next generations.

But what happened?

Indeed, minstrels gradually faded away, and by the early 16th century, they practically did not exist. But in their place, other trades and businesses related to printing emerged, which absorbed much of the surplus labor force.

Also, the number of people learning to read increased substantially, and the collective knowledge was put on much more permanent support than the human brain.

A similar phenomenon was the industrial revolution that occurred in 18th-century England. It brought changes in the economic and social structure, causing a massive exodus of rural workers to large cities, with the consequent precariousness of their living conditions.

However, we moved from a stagnant economy based on subsistence agriculture, artisanal production, and limited trade to a more dynamic one that guaranteed sustained growth. Just like with the printing press, jobs disappeared, but others emerged and absorbed the surplus labor force created in the process.

For much of the 20th century, especially after the disastrous wars in that humanity was involved, we saw an accelerated growth of these phenomena, now associated with computing. It is no secret that it has rapidly and unstoppably penetrated all spheres of society.

For years, the images of Chaplin's "Modern Times" became history in many factories as employees were replaced by automated robots that tirelessly performed the most tedious and dangerous tasks in the production sector.

Undoubtedly, it is a process not exempt from pain, where many people have had to reinvent themselves to move forward. Ancestral family traditions have disappeared, those where children learned their parents' trade and continued it from generation to generation.

Still, humanity has been able to overcome this process and benefit from the surplus production resulting from it.

Today, when the threshold of the future is the morning of the next day, where we need to be faster, more accurate, and more timely, AIs appear, and panic begins, as if collective memory had been lost after Gutenberg's printing press. New tools present new challenges, which we must resolve with everyone's effort.

Let us stop to analyze just one of the benefits:

One benefit of these tools is the possibility of freeing up a large number of qualified personnel and channeling them into areas where humanity has made little progress, such as combating diseases and researching the cosmos or the brain.

An important, albeit distant question, is how we will face the long-time anticipated destruction of the solar system when our sun ceases to exist. How much of the qualified labor force will be necessary to solve this crucial problem?

How many resources will be needed to implement possible solutions?

I leave you with those thoughts in mind. Let me know what you think about this topic, and let's start a fruitful discussion.

See you soon 👋

👋 Hello, I'm Alberto, Software Developer at doWhile, Competitive Programmer, Teacher, and Fitness Enthusiast.

🧡 If you liked this article, consider sharing it.

🔗 All links | Twitter | LinkedIn

A Tale of Algorithms: Edit Distance in Web Development

Alberto González Rosales — Tue, 28 Mar 2023 13:42:18 +0000

Two years ago, I was working on a delivery app. Our client wanted to create a system that could manage users ordering products, and service providers would register on the app to sell their products. Sounds easy, right?

In this article, I will tell you the story of how I got to implement a cool Dynamic Programming algorithm to satisfy the requirements of a not so experienced Project Manager. Keep reading until the end; I assure you it will be educational and fun.

Let's go!

Some Context

My role on the project was to create the API that would serve the web and mobile apps. We decided to go with Python, using Django Rest Framework for the backend side.

We were a fairly new team with little experience in the Software Development industry. But somehow we managed to understand each other well and to collaborate to keep the project moving forward.

As you can imagine, there are several parts involved in the software development process. In our case, these parts were:

A Back-end Team (where I was)
A Front-end Team (responsible for the web apps mainly)
A Mobile Team (responsible for the mobile apps)
A DevOps team (responsible for... well, you know, DevOps stuff 😅)

Whenever you are part of a team involving that many members, there is usually a person (or persons) that should keep track of the progress the team is making, should coordinate all the parts so that everyone knows what it's doing, and should decide on the next steps of the development process. That way, the developers can focus on what they do best: coding.

In our case, we had a so-called Project Manager in charge of all the previous and more. But, as you will see in a minute, it was not always so accurate in making the right decisions.

Enter the Browser

One day we had a request from our Project Manager to add a browser feature to the mobile apps. This seems like a good idea, right? The user would log in to the app and could search for something on the Home screen to speed up the process of ordering products.

My initial thought was: "We probably want a browser feature that can match somehow the name of the service providers". This seemed like the most obvious initial approach because then you could provide the user with a list of the most probable providers it was looking for, giving it the option to select the one that suits its necessities the most.

Still, I had to ask for some specifications so I could have a better understanding of how this new feature was conceived to be used. Then, the moment I asked the obvious question: "How will this be used? Should it match the names of the service providers?", I got the most unexpected answer.

"Yes! But not only that. It should also match the names of the brands, products, product categories, etc... Everything that we can match, it should!

Also, of course, the match doesn't have to be exact. Maybe the user can have some typos and miss a letter or two... We should be able to take that into account."

So, in my mind, it was clear that our Project Manager wanted to have a very specific browser feature (we only cared about its use in the app) that behaved the most similarly to the Google browser. Nice!

Dynamic Programming to the Rescue

When I was tasked with this browser feature I knew that I had to come up with a solution that solved the problem but that was not too overkilled also. Fortunately, I have some background in Data Structures and Algorithms and I could quickly find a solution that was good enough for us.

I have always struggled to find good applications of the algorithms I know in real-life scenarios. That is why I try to think of different approaches to the problems I face every day, hoping that someday it will allow me to implement and deploy some cool algorithms to production.

In this specific case, the algorithm that solved our problem was Edit Distance. This algorithm receives two strings as arguments and returns an integer value that represents the minimum amount of "operations" that you should perform on one of the strings to make both of them equal. The operations allowed are:

Insertion of a single symbol.
Deletion of a single symbol.
Substitution of a single symbol x for a symbol y.

As I see it, this algorithm returns a number that shows you how "close" two words are to each other. Which seems like a good ad-hoc approach to our brand-new browser.

Imagine that we want to know how many operations we need to convert the string kitten to sitting. The algorithm will return 3:

k itten s itten (substitute s for k)
sitt e n sitt i n (substitute i for e)
sittin sittin g (insert g at the end)

Do you see how to use this algorithm in our specific case? Keep reading so you find out how we put all this together.

Levenshtein goes to Production

With all the theoretical knowledge sorted out, the only thing missing was how to include the algorithm inside the application in a way that solved our initial requirements. Let's analyze a simplified version of the problem we were facing:

Suppose the user is only allowed to enter one word in the browser. How to match products, categories, brands, service providers, etc... with that word? Remember that the match doesn't have to be exact.

First of all, the easiest part is to get the input word from the user. Let's assume we already have that and that we called it query.

After that, we needed a candidate list of words to match our query. Fortunately, the corresponding entities in our database all had a name attribute that we could use for that purpose. So, we just had to collect every name from our Product, ProductCategory, ServiceProvider, and Brand entities.

With all these names collected, we could run the Edit Distance algorithm with our query word and the names. Then, we could sort the results from lowest to highest. This means that we would be recommending to the user a list of results starting from the ones that were more similar to the word that was entered in the browser.

A sample code would be something like this:

from utils import edit_distance

results = []
for entity in entities_collected:
    results.append((edit_distance(query, entity.name), entity))
results.sort(key=lambda x: x[0])

This worked pretty well for being an ad-hoc solution that came out of thin air. The only thing we had to adjust was the fact that, sometimes, the results we were showing differed too much from the original word entered as the query.

For example, usually, after the 10th word the value resulting from the Edit Distance algorithm was too high that even if it wasn't the 10th but the 1st result it would have made no sense to show it as a "match". To deal with this issue we introduced the concept of threshold to our algorithm.

This threshold would allow us to discard results whose edit distance to the query word was higher than a specified value. After a few tries tunning the threshold value and analyzing how it behaved with the data in our database, we decided on one and we were ready to test this feature in our staging cluster.

After that, we shipped it for production. Succesfully!

As a note, the process of tunning this threshold parameter was surprisingly educational for me. We started doing it completely wrong by setting actual numeric values in the code. But we ended up with a solution that used advanced Object-Oriented Programming concepts such as the Singleton Pattern.

I plan to create an article talking about this, so stay tuned!

Conclusions

I hope this story was inspiring enough for people that, like me, find beauty in algorithms.

I showed you how I and my team managed to quickly develop a solution that completely suited all our needs. And it all started with some very generic requirements that we had to satisfy somehow.

Sometimes, we get the most creative when faced with the most difficult tasks. So, my advice to you is: don't miss the chance to step up in front of a challenging situation. It will build up your trust, it will allow you to take out the best of yourself.

See you soon!

👋 Hello, I'm Alberto, Software Developer at doWhile, Competitive Programmer, Teacher, and Fitness Enthusiast.

🧡 If you liked this article, consider sharing it.

🔗 All links | Twitter | LinkedIn

A Tale of Debugging: The Competitive Programmer Approach (Part II)

Alberto González Rosales — Sun, 19 Mar 2023 19:34:37 +0000

A month ago, I wrote about how competitive programmers debug their solutions during competitions by taking advantage of randomization and the computing power in the devices we use daily. That article was selected as one of the winners of the DebuggingFeb Writeathon and got a lot of visibility from the Hashnode community.

The feedback from some of the readers was the best thing that came along with all the visibility. Those readers are what I like to call Active , those who don't stop at the end of the article but instead keep asking questions and suggesting improvements.

One of the more frequent requests was if I could try to make this debugging mechanism more similar to a tool that could be used easily in our everyday coding tasks.

This article is about my proposal for you who keep pushing the limits of knowledge by asking the right questions and giving the proper suggestions.

If you haven't read the article that motivated this one yet, I recommend you to read it here. After you get familiar with the topic we will discuss, please dive into the next section and read through the whole article.

Let's go!

Stress Testing

While I refrained from naming this technique in the first article, it has a proper name in the software developer community. That name is Stress Testing.

According to Wikipedia, Stress Testing can be defined as:

Stress testing is a software testing activity that determines the robustness of software by testing beyond the limits of normal operation. Stress testing is particularly important for "mission critical" software, but is used for all types of software. Stress tests commonly put a greater emphasis on robustness, availability, and error handling under a heavy load, than on what would be considered correct behavior under normal circumstances.

Even though this definition is more suitable for real-life software development situations, it can be extrapolated to our use case. Especially because of the " under a heavy load" part.

I recall that the main advantage of this approach to test solutions is the capacity to generate thousands of test cases and run them in seconds. If that isn't a heavy load, then what is?

The approach of generating thousands of small sample cases to test one solution is not only used by competitive programmers when they try to find bugs during competitions. The problem-setters also use it when they want to determine if a proposed solution for a problem is indeed correct.

I have been on both sides, and I can tell that the benefits are remarkable. The speed at which you can find counter-tests to your solutions increases at least by a factor of 10. This allows you to spend less time debugging solution proposals and more time on important things.

The Sample Problem

Let's recall the problem we solved last time. The statement was the following:

"Given a sorted array of integers, and an integer x, find the first index of the array containing the number x or return -1 in case the number doesn't appear on the array".

We can solve this problem with a naive solution that iterates through the list from left to right and stops as soon as it finds an element equal to x. If it reaches the end of the list without finding the element we are looking for, it returns the value -1.

A possible implementation in python is the following:

# solutions/naive.py

def naive(a, x):
    return next((i for i in range(len(a)) if a[i] == x), -1)

if __name__ == " __main__":
    num_list = list(map(int, input().split()))
    x = int(input())
    print(naive(num_list, x))

This solution, even though it's correct, is not fast enough. It is performing a linear search through the entire list, which results in a time complexity of O(n), which is good enough, but we can do better.

To improve our solution, we should notice that we are not taking advantage of the fact that our input list is sorted. This means that we can make use of the binary search algorithm to look for the number x.

Our improved solution would be something like this:

# solutions/solution.py

def solution(a, x):
    l = 0
    r = len(a) - 1
    while l <= r:
        m = (l + r) // 2
        if a[m] == x:
            return m

        if a[m] < x:
            l = m + 1
        else:
            r = m - 1
    return -1

if __name__ == " __main__":
    num_list = list(map(int, input().split()))
    x = int(input())
    print(solution(num_list, x))

By using binary search, we have reduced the time complexity of our solution to O(n log n). But unfortunately, this solution has a bug.

How to find it, then? We could spend hours trying to generate manual test cases to check where is that our solution fails.

Well, here is where we benefit from generating randomized cases. And here is my new proposal to do so.

Stress Tester Tool

Let's create a new project with the following structure:

stress_tester
|-- generators
|---|-- random_generator.py
|-- solutions
|---|-- naive.py
|---|-- solution.py
|-- test_cases

As you can see, it contains a "generators" folder with the generator files. In our case, we will just use a random generator, but sometimes more specific generators are necessary.

It also contains a "solutions" folder that will store our naive solution for the problem and the solution we want to test.

Lastly, we created a "test_cases" folder that will store all the test cases we generate to inspect them whenever we find a difference in the output of our solutions.

The generator we are going to use for this example is this one:

# generators/random_generator.py

import random

def generate_input():
    n = random.randint(1, 10)
    a = [random.randint(1, 10) for _ in range(n)]
    a.sort()
    x = a[random.randint(0, n - 1)]
    return a, x

if __name__ == " __main__":
    a, x = generate_input()
    print(" ".join([str(elem) for elem in a]))
    print(x)

Ideally, what we want is to generate random test cases, supply them (one at a time) to both our solutions, and stop when the outputs returned to a given input are different. Then, we can examine the test case that makes our solution fail and start fixing our bugs.

Let's automate this process!

Automating with a shell script

Shell scripting seems to be the go-to option here. This is used widely in tasks related to automation in areas such as Operative Systems and Networking. In our case, we will be using it to link existing programs together.

The fact is that the output generated by our random_generator program should be supplied as the input to both our naive and solution programs. Once again, the outputs of these two programs should be supplied as input to some other program that tells whether they are different or not.

The good thing is that a simple shell script can help us achieve all that without much effort.

Let's create a file in the root of the project and call it check.sh. The content of the file should be this:

# check.sh

# Number of test cases
TEST_CASES=100

# Commands to execute python scripts
RUN_GENERATOR="python3 ./generators/random_generator.py"
RUN_SOLUTION="python3 ./solutions/solution.py"
RUN_NAIVE="python3 ./solutions/naive.py"

# Test directory
TEST_CASES_DIRECTORY="./test_cases"

# Console Colors
RESET_COLOR="\x1b[0m"
OK_COLOR="\x1b[32m"
WA_COLOR="\x1b[31m"

echo "Starting stress testing with $TEST_CASES test case(s)..."

mkdir -p "$TEST_CASES_DIRECTORY" # Create directory to store test cases
for i in `seq -f "%0${#TEST_CASES}g" 1 $TEST_CASES`
do
    INPUT="$TEST_CASES_DIRECTORY/input-$i.in"

    eval "$RUN_GENERATOR" > "$INPUT" # Generate a test case
    DIFF=$(diff -w <(eval "$RUN_SOLUTION" < "$INPUT") <(eval "$RUN_NAIVE" < "$INPUT")) # Evaluate the test case in both solutions and get their output differences
    if ["$DIFF" == ""] ; then # Same output
        echo -e " Test case $i: ${OK_COLOR}OK!${RESET_COLOR}"
    else # Different output
        echo -e " Test case $i: ${WA_COLOR}Wrong Answer!${RESET_COLOR}"
        break
    fi
done

Let's explain what's happening in this code:

We define necessary variables such as the number of test cases we are going to run, the commands to execute our generator and solution python scripts, and the colors to display in the console.
We iterate from 1 to the number of cases we defined. Each time, we call the generator script and redirect the output to a file using the > operator.
Then, we supply this file as input to both solutions using the < operator and check for differences using the diff command.
If no differences are found, we print OK! to the console and proceed to the next test case. Otherwise, we print Wrong Answer! and stop the script.

To execute this script, we need to type the following command in our console when we are at the root of our project:

./check.sh

An output similar to this should appear on your console after executing the command:

In my case, it detected a difference in the outputs on case number 11. Now I have to go and analyze that case and try to fix the bugs in my code. This will be much easier now that I know of a case where my solution fails.

When we finish fixing our buggy solution, we can run the script again to check if it passes all the test cases. Hopefully, you will get a result similar to this one:

Otherwise, fix your solution again until you do. Now you will have a new test case to analyze.

Automating with a python script

Even though we have a solution that uses a shell script to automate the checking process, it still has some implementation details that I don't like. The most important for me is that the variables we use are fixed in the code.

Let's say, for example, that we want to change the directory where our solutions are or where we store the test cases. We would have to go to the script and change the value of those variables by hand.

While looking for a better solution, I figured it would be better if the values of the variables we need to make our script work could be passed as arguments through the CLI. Since I don't know much about the shell scripting language, I decided to create an alternative using python.

We are going to create a check.py file at the root of our project. This file will contain a similar logic to the one in our shell script, but it will also include parsing arguments from the CLI.

To parse arguments from the CLI in python, I usually go for the argparse library. It is simple enough, and the documentation is excellent. It will help you create applications that receive arguments from the console instantly.

Let's see an example of how a function that parses the arguments we need will look like:

# check.py

def parse_args():
    parser = argparse.ArgumentParser()
    parser.add_argument("--test-cases", type=int, required=True)
    parser.add_argument("--generator-path", required=True)
    parser.add_argument("--solution-path", required=True)
    parser.add_argument("--naive-path", required=True)
    parser.add_argument("--tests-path", required=True)
    return parser.parse_args()

As you can see, for our script to work, we need to specify the values for the following variables:

test-cases: The number of test cases to execute.
generator-path: The path to the generator file.
solution-path: The path to the solution file.
naive-path: The path to the naive solution file.
tests-path: Directory to store the test cases.

After all our variables have been parsed, we need to call the function that will execute the same workflow that the shell script does. To achieve this behavior from a python script, I used the subprocess library, which allows the execution of commands in the console and redirects inputs and outputs. For the colors, I used the colorama library.

Here is an example of how this function could look like:

# check.py

def check(
    test_cases: int,
    generator_path: str,
    solution_path: str,
    naive_path: str,
    tests_path: str,
) -> bool:
    print(f"Starting stress testing with {test_cases} test case(s)...")
    for i in range(1, test_cases + 1):
        # Generate random test case
        with open(f"{tests_path}/input-{i}.in", "w", encoding="utf-8") as test_case:
            subprocess.run(["python3", generator_path], stdout=test_case)

        # Open test case input file
        with open(f"{tests_path}/input-{i}.in", "r", encoding="utf-8") as test_case:
            # Run solution and store the output in a file
            with open(f"{tests_path}/solution-{i}.out", "w", encoding="utf-8") as solution_file:
                test_case.seek(0)
                subprocess.run(["python3", solution_path], stdin=test_case, stdout=solution_file)

            # Run naive solution and store the output in a file
            with open(f"{tests_path}/naive-{i}.out", "w", encoding="utf-8") as naive_file:
                test_case.seek(0)
                subprocess.run(["python3", naive_path], stdin=test_case, stdout=naive_file)

            # Check for differences in both output files
            output = subprocess.run(
                ["diff", f"{tests_path}/solution-{i}.out", f"{tests_path}/naive-{i}.out"], stdout=subprocess.PIPE
            )

            # Return code different from 0 means that the outputs differ
            if output.returncode == 0:
                print(f" Test case {i}: {Fore.GREEN}OK!{Fore.WHITE}")
            else:
                print(f" Test case {i}: {Fore.RED}Wrong Answer!{Fore.WHITE}")
                return False
    return True

And our main function would look like this:

# check.py

def _main():
    args = parse_args()
    check(
        args.test_cases,
        args.generator_path,
        args.solution_path,
        args.naive_path,
        args.tests_path,
    )

if __name__ == " __main__":
    _main()

To execute this script, it is necessary to run the following command at the root of the project:

python3 check.py --test-cases 100 --generator-path ./generators/random_generator.py --solution-path ./solutions/solution.py --naive-path ./solutions/naive.py --tests-path ./test_cases

As you can see, now it is possible to modify the values of the parameters from the CLI without having to affect the code. For example, we could increase the number of test cases we want to run to 1000.

After we run this command, we get the following output in our console:

Now, it failed test case number 7. After inspecting the test case and fixing our solution, we should get something like this:

Conclusions

In this article, we have learned how to create an automated tool to stress-test our solutions against randomly-generated test cases. We automated the process using a shell script and then we made a python version making use of libraries such as argparse and subprocess.

To be able to find counter-tests to your solutions is a crucial aspect of software development. Even though this is an educational, simple example, it has multiple similarities to cases of real life. Try this out, and let me know your thoughts about it!

Also, I would like to keep improving this tool a little, but I don't have much time to do it alone. It would be great to have some contributors to the GitHub repo where I keep the code used in this article. I started writing some possible improvements. Reach out to me if you want to collaborate on this.

See you soon!

Sources

Code examples used in this article can be found here.
Stress Testing (Wikipedia): Article from Wikipedia about stress testing in software.
How to test your solution in Competitive Programming by Kamil Debowski: Youtube video explaining some of the topics discussed, with code examples in C++.

👋 Hello, I'm Alberto, Software Developer at doWhile, Competitive Programmer, Teacher, and Fitness Enthusiast.

🧡 If you liked this article, consider sharing it.

🔗 All links | Twitter | LinkedIn

A Tale of Refactoring: Dealing with Multiple Conditional Statements the Python Way

Alberto González Rosales — Sat, 04 Mar 2023 12:01:38 +0000

Are you tired of dealing with messy and hard-to-maintain code filled with multiple conditional statements in Python?

Learn how to improve your code's readability, maintainability, and testability by exploring different techniques for refactoring code with multiple conditional statements.

From extracting functionalities into methods to using object-oriented programming and the Visitor pattern, this tutorial will guide you step by step through the process.

Say goodbye to the headache of long chains of conditional statements and hello to a more efficient and effective coding experience.

Let's go!

Initial Codebase

Let's say we are writing python code to generate an HTML page. There are different types of components on the page. Those types are common, href, span, and div.

For some reason, the code we use for generating every type of element is a bit different, so we come up with a solution like the following:

# main.py

if component_type == "common":
    # Generate common component
    ...
    ...
    ...
elif component_type == "href":
    # Generate href component
    ...
    ...
    ...
elif component_type == "span":
    # Generate span component
    ...
    ...
    ...
elif component_type == "div":
    # Generate div component
    ...
    ...
    ...

Note : We have omitted the implementation details for generating the specific components in the code because it is not relevant to the purposes of this tutorial.

What's wrong with this approach?

In the first place, since we have multiple cases to handle and the implementation for each can keep growing, we would end up with a huge codebase that will be harder to read and maintain later.

Let's start refactoring!

Step 1: Extracting Methods

A reasonable way to improve this code is by extracting some of it into different methods, making the solution more modular.

We start by creating a different method to handle every specific component. This will allow us to locate the code that handles specific component types more easily. A possible implementation could be the following:

# html_generator.py

def generate_common_component():
    # Generate common component
    ...
    ...
    ...

def generate_href_component():
    # Generate href component
    ...
    ...
    ...

def generate_span_component():
    # Generate span component
    ...
    ...
    ...

def generate_div_component():
    # Generate div component
    ...
    ...
    ...

This will allow us to change our main code to something like the following:

# main.py

from html_generator import (
    generate_common_component,
    generate_href_component,
    generate_span_component,
    generate_div_component
)

if component_type == "common":
    generate_common_component()
elif component_type == "href":
    generate_href_component()
elif component_type == "span":
    generate_span_component()
elif component_type == "div":
    generate_div_component()

The benefits of this refactoring are clear. The code automatically becomes more:

Readable
Maintainable
Testable

But we still have some issues to solve. The more obvious of them is that even if we extracted the logical parts that deal with specific types of components, we are still in danger of having our main code grow, making it harder to read, test and maintain again.

This will happen if we want to generate new types of components in our code. With the current solution, we would have to keep adding additional elif statements, resulting in the same problems we were trying to solve in the first place.

Still, it is a good starting point. Let's keep improving it!

Step 2: Dictionary Dispatch

As we have seen, extracting most of our code into methods doesn't solve the issues that the long chain of if-elif causes. The question is, how to get rid of them in a way that ensures our code is still correct and improves readability, maintainability, and testability as well?

The answer to that is the Dictionary Dispatch pattern, which will allow executing methods depending on the values of variables without using conditional statements.

We start by creating a dictionary whose keys are the possible values that our variable used in the conditional statements can have:

# main.py

from html_generator import (
    generate_common_component,
    generate_href_component,
    generate_span_component,
    generate_div_component
)

generator_functions = {
    "common": generate_common_component,
    "href": generate_href_component,
    "span": generate_span_component,
    "div": generate_div_component,
}

By doing this, we can replace our conditional statements with the following code:

# main.py

generator_functions[component_type]()

Which will still call a function to generate the component we want depending on the value of a variable. Only this time, we are sure this code won't grow any longer.

Now, if we want to add a new component to generate, we would only need to implement the logic for it in a different method and add the corresponding key-value pair to our dictionary.

Let's see an alternative if we want to make this solution more robust.

Step 3: The Visitor Pattern

As a last step of refactoring, we will see an alternative using object-oriented programming: The Visitor Pattern.

We will start by creating a class that handles the writing of HTML components. This class will have the methods for writing every specific component but also a more general method that decides which of these specific methods to invoke depending on the component type.

# html_generator.py

class HTMLGenerator:
    @staticmethod
    def generate_component(self, component_type: str):
        writer_method = getattr(
            self, f"_generate_{component_type}_component", "generate_common_component"
        )
        writer_method()

    def _generate_common_component():
        ...
        ...
        ...

    def _generate_href_component():
        ...
        ...
        ...

    def _generate_span_component():
        ...
        ...
        ...

    def _generate_div_component():
        ...
        ...
        ...

What the generate_component method does is try to match any method with the pattern _generate_<component_type>_component, and invoke it to generate the component type passed as an argument. In case there is no method matching the pattern, we take the _generate_common_component by default.

Now, our main code will look like this:

# main.py

from html_writer import HTMLGenerator

HTMLGenerator.generate_component(component_type)

Like with the Dictionary Dispatch approach, if we want to add a new component type we would only need to implement the corresponding method in the HTMLGenerator class.

Conclusions

In this tutorial, we have seen different techniques for refactoring code with multiple conditional statements.

We started by extracting functionalities into methods and applying the Dictionary Dispatch pattern. Lastly, we made our solution more robust by using object-oriented programming and the Visitor pattern.

All of these refactoring techniques allow for improved readability, maintainability, and testability of our code. Also, in our specific case, it allows the easy addition of new components.

This specific example might not be the exact case of use that you are dealing with, but if you see yourself struggling with a long chain of conditional statements try to apply the approaches explained here. It will be somehow similar to the problem you are facing.

This is the first article in a series about improving code step by step. If you would like me to take a look at specific examples you have, leave them in the comment section and I will try to create a tutorial like this one for the most interesting ones.

See you soon!

👋 Hello, I'm Alberto, Software Developer at doWhile, Competitive Programmer, Teacher, and Fitness Enthusiast.

🧡 If you liked this article, consider sharing it.

🔗 All links | Twitter | LinkedIn

A Tale of Debugging: The Competitive Programmer Approach

Alberto González Rosales — Sun, 19 Feb 2023 18:22:08 +0000

Coming from a five-year Competitive Programming journey, I have faced the process of debugging on numerous occasions. In this article, I will try to describe how the debugging method works in such environments, instead of depicting it in the regular software development activities we do every day.

But why? You might ask.

The reason is that, because of the short time limit set in these competitions, the participants have to come up with creative ideas to solve all the issues they face. There is no tomorrow for them. It is either "crack or go home". And sometimes, these ideas can be extrapolated to the so-called "real world" software development.

Without further ado, let's see what I'm talking about!

Some Context

Competitive Programming contests are a type of competition in which a set of problems is presented to every contestant. The idea is for them to solve the maximum number of problems they can within the time limit set for the contest, which is usually around two to five hours.

Every problem specifies the format of the input, and it expects some output in response. For example, we could have a problem stating that you need to find the sum of the numbers in a list. In this case, the input would be a list of numbers, and the output would be a single number.

Usually, these competitions take place on automated platforms that can receive solutions for every problem and evaluate those solutions against an entire dataset hidden from the competitors. If a solution returns the expected value for every dataset, it is said to be "Accepted", otherwise it is "Rejected".

As can be noticed, being accurate in the solutions is an important skill for every participant, but also being fast. Finding the right balance between correctness and speed is what makes a competitor rise to the top of the standings with more problems solved than its rivals.

Not so far from "real life", isn't it?

It is common to see software companies fighting each other to see which one is the fastest to achieve certain goals or which one gives better results when looking at some particular topic. The balance between doing something right and doing it fast is always an aspect to focus on when working in software development.

And here is where debugging shows up as a key factor, because:

It ensures correctness once the "bugs" have been dealt with.
It can affect speed because the process of finding errors takes too long.

Let's see the actual situation that happens during competitive programming contests, then!

The "Bug" strikes back

A common case where "bugs" might show up when participating in programming contests is when performance is a defining factor in the solution of a problem. That is, not only the output being correct is taken into account but how much time your solution takes to return that output for the entire dataset.

The following case is the most common one:

We read a problem, we know a solution that solves that problem correctly but, unfortunately, it won't be fast enough. No worries, we gave the problem some thinking and we came up with a solution that is also correct, but this time it will fit in the time limit set for the problem.

We rush into coding our solution, tested it a little with some manual test cases, submit it, and... end up receiving a "Rejected" verdict. Which means our solution returned the wrong output for some input.

What to do in this case?

The approach that most of the competitors take is to keep testing their solutions against some hand-crafted test cases they come up with. They try to look for edge cases where the solution might return the wrong output, but this is not always easy to do.

The frustration of seeing your program return the correct output for every input you give but knowing there is some hidden test case in which your solution fails can lead to stop trying a problem that you are almost certain you know the solution of. This will, of course, impact your performance in the competition because you invested time in a problem you will not end up solving.

So, when the debugging process is taking too long, it is a good alternative to go for the "have the computer find the bugs for you" approach.

Let's see how this works!

Debug Smart, not More

First of all, of course, the computer won't find the bugs for you. The bugs are your own and you will be responsible for finding them. But, what the computer can do is help you generate enough data in a short time to make you find where your solution fails.

Remember that solution we talked about that would give the correct output but wasn't fast enough? Now it's time to make use of it.

Usually, this solution will be easier to code, and less prone to have bugs in it. Let's say we can rely on it because we know we are skilled enough to solve any problem using a no-brainer approach.

Do you recall the previous debugging process?

Generate hand-crafted input.
Run your solution with that input.
Manually check if the output returned is correct.
If it is not correct, you have a test case to debug thoroughly. Otherwise, repeat step 1.

This is highly inefficient for a person to do. Especially steps 1 and 3.

What we can do to speed up this process is to change the checks that we do in step 3 to automatic instead of manual. And the easiest way to do it is by comparing the outputs returned by both of our solutions (the no-brainer and the buggy ) given the same input.

If we coded our no-brainer solution right (which we are skilled enough to do, of course) then we can assure that the moment the outputs differ, we have found a test case that is worth having a deeper look into.

Ok. But what about step 1?

The process of generating test cases can be difficult, especially if what we are trying to do is to find one that makes our solution return the wrong output. I mean, if we were able to do that easily then we would have fixed our solution already 😅.

Fortunately, the solution for this issue is to rely on randomness. Yes, as you hear it! Randomness provides a spectacular way of generating non-biased input and it works surprisingly well and fast in most cases. We can replace our hand-crafted process of creating test cases with an automated, easy-to-code, random process that will do the work for us.

Now, the debugging process will be:

Generate random input.
Run both solutions with that input.
Check if the outputs differ.
If they do, you have a test case to debug thoroughly. Otherwise, repeat step 1.

The difference between both approaches is that the second one can be fully automated, and we will see how to do it next.

Automated Debug Mode

Let's automate our debugging process, then!

We will start with this template code in Python, which we will be filling up with the proper code to help us achieve our goals.

def no_brainer():
    pass

def solution():
    pass

def generate_input():
    pass

def debug():
    pass

if __name__ == " __main__":
    debug()

The purpose of this implementation is to have the debug function generate a new test case by using the generate_input function, and supply it to our solution and our no_brainer solution while the results are the same. The moment the results differ, we can stop generating new test cases and analyze the one that makes our solution fail.

A real example

Let's make it more interesting by solving a classic algorithmic problem:

"Given a sorted array of integers, and an integer x, find the first index of the array containing the number x or return -1 in case the number doesn't appear on the array".

Now, because we are smart, we know how to solve this problem by using a linear search over the array. The implementation in Python could be something like this:

def no_brainer(a, x):
    for i in range(len(a)):
        if a[i] == x:
            return i
    return -1

This is our no-brainer solution. Just a plain for-loop until we find the element we are looking for. The moment we find it, we return the index in which the element is. And, in case we don't find it, we return -1, as requested in the problem statement.

Let's assume this solution is not fast enough. Maybe it is because the size of the array is too big and, in the worst case, our solution will end up iterating through all the elements just to find out that the number we were looking for is not present in the array at all.

But, since the array is sorted maybe we can use the Binary Search algorithm, which will indeed speed up the search process. That sounds like a good idea, right? Let's try it!

def solution(a, x):
    l = 0
    r = len(a) - 1
    while l <= r:
        m = (l + r) // 2
        if a[m] == x:
            return m
        elif a[m] < x:
            l = m + 1
        else:
            r = m - 1
    return -1

The code above tries to find the number x in the array, and it also returns -1 in case it doesn't find it. Now, it doesn't perform a linear search so we are not expecting it to time out but for some reason, when we submit it for review, we receive a "Rejected" verdict.

As we said before, we will not rush into manual debugging. Instead, let's start by creating a random generator to supply input to both our solutions, hoping we will find the bug soon. Our generating function could be something like this:

import random

def generate_input():
    n = random.randint(1, 10)
    a = [random.randint(1, 10) for _ in range(n)]
    a.sort()
    x = a[random.randint(0, n - 1)]
    return a, x

We are generating arrays with sizes at most 10, which is a manageable number of elements. We are also making sure the elements are sorted, and we are taking the number x as one of the numbers present in the array.

What we are missing now is just putting all the pieces together, like this:

def debug():
    test_cases = 10000
    for _ in range(test_cases):
        a, x = generate_input()
        no_brainer_output = no_brainer(a, x)
        solution_output = solution(a, x)
        if no_brainer_output != solution_output:
            print("Test Case:")
            print(a, x)
            print("Solution Output:", solution_output)
            print("No-Brainer Output:", no_brainer_output)
            exit()
    print("All test cases passed succesfully")

By having a glance at the code we can see the benefits of having this as part of our debugging process.

Notice that we have set a limit of 10000 test cases. That amount is not realistic for a single person to generate, and it sure seems like a sufficiently large number that might ensure we will find a test case where our solutions differ.

On the other hand, once we have fixed our solution, we can run these 10000 cases again looking for new bugs. The moment all the outputs are the same we would have a stronger belief about the correctness of our algorithm after passing that high number of tests.

This is the complete version of the implementation, in case you want to see the whole picture:

import random

def no_brainer(a, x):
    for i in range(len(a)):
        if a[i] == x:
            return i
    return -1

def solution(a, x):
    l = 0
    r = len(a) - 1
    while l <= r:
        m = (l + r) // 2
        if a[m] == x:
            return m
        elif a[m] < x:
            l = m + 1
        else:
            r = m - 1
    return -1

def generate_input():
    n = random.randint(1, 10)
    a = [random.randint(1, 10) for _ in range(n)]
    a.sort()
    x = a[random.randint(0, n - 1)]
    return a, x

def debug():
    test_cases = 10000
    for _ in range(test_cases):
        a, x = generate_input()
        no_brainer_output = no_brainer(a, x)
        solution_output = solution(a, x)
        if no_brainer_output != solution_output:
            print("Test Case:")
            print(a, x)
            print("Solution Output:", solution_output)
            print("No-Brainer Output:", no_brainer_output)
            exit()
    print("All test cases passed succesfully")

if __name__ == " __main__":
    debug()

After we run this script, we will get a result like the following:

In this case, the input consists of the array [4, 4, 4, 5, 10] and the number 4. This means we need to find the first index where the number 4 appears in the array.

As can be seen, our solution using binary search returns the value 2, which is an index where the number 4 is present, but it is not the first one. On the other hand, our no-brainer solution returns the value 0, which is the first index whose value is equal to 4.

And, just like that, in a matter of seconds, we have generated a test case that shows that our solution fails. Now we can proceed to analyze it thoroughly and fix our code.

Note : As an exercise for the reader, I will skip the part where I explain what is wrong with the implementation above. If you realize what the issue is, leave it in the comments so we can start a discussion and keep learning as a community.

A possible fix to our implementation is the following:

def solution(a, x):
    l = 0
    r = len(a) - 1
    pos = -1
    while l <= r:
        m = (l + r) // 2
        if a[m] >= x:
            pos = m
            r = m - 1
        else:
            l = m + 1

    return pos

Let's see that when we run the script, now that we have modified our solution, we get the gratifying result:

Which will give us the courage to submit our implementation again.

Conclusions

In this article, we have seen an effective approach for generating test cases to stress-test our solutions. We have automated the process of crafting each case and checking for correctness, making it less time-consuming to find bugs in the code.

The approach seen here is one of the most effective ones used in Competitive Programming, but it sure can be extrapolated to use cases in "real world" software development. It also shows how you can take advantage of the computing power present in the devices we use every day to speed up the debugging process and deliver features that have been tested thoroughly while still being able to beat your deadlines.

During my Competitive Programming journey through college, I implemented this type of debugging not only in individual competitions but in team contests as well. As a result of that, my teammates and I gained speed when competing and were able to achieve amazing results.

We all agree that this method of debugging played an important role in our achievements as competitive programmers. We went all the way from programming enthusiasts to ICPC World Finalists by making sure that we were the most productive that we could during the limited time we had in every contest. And I assure you: there is no contest without debugging.

I recommend you give it a try. Let me know your results!

👋 Hello, I'm Alberto, Software Developer at doWhile, Competitive Programmer, Teacher, and Fitness Enthusiast.

🧡 If you liked this article, consider sharing it.

🔗 All links | Twitter | LinkedIn

A Tale of Teamwork: Ensuring Quality in Software Development

Alberto González Rosales — Sat, 11 Feb 2023 21:23:13 +0000

Since I started doing software for a living, I have been part of different teams. As you can imagine, different teams mean different ways of working. But they all had one thing in common: and that is the fact that at some point throughout the development of a product, it was time to ship for production.

So, how to ensure the quality of that final product?

Most people think that after a long time of development, then you should spend time reviewing and fixing errors. I don't disagree with having a test plan that helps you find some use cases not being covered, or maybe some last-hour unexpected behaviors.

But to ensure the highest quality throughout the process, it is necessary to have a good code review system involving automatic tools and effort on the part of every team member.

Let's see how!

Unit Testing

Having unit tests for every feature is one of the most beneficial approaches a software development team can take. Doing this ensures that the new features are properly working before merging into the main branches of your product.

Not only that! It also ensures that all the previous features are still working properly. Which is exactly what your product needs. In the ideal case, the new feature needs to add value to the product without compromising all the work that was done previously.

This is easier to ensure when unit testing is implemented.

A good and natural way to start with unit testing is to take the test-driven development approach:

Write tests for the new feature. They should fail until the feature is properly implemented.
Implement the new feature. The tests should pass once the feature is implemented correctly.
Refactor your code. This way you take care of putting all the pieces in the right place without making the tests fail again.

This approach takes extra effort in the beginning because it is hard to start a new feature by writing the tests for it. But the great benefit of it is that it makes the developer think about all the aspects of the feature before diving right into coding. This might seem obvious, but not everyone does it.

Once the feature is implemented and all the tests pass, the developer can request a deeper review from the team members. But now your team can rest assured that your changes are more likely to work as expected and that all the previous work done has not been affected.

Additional checks

What I call "additional checks" here are mainly necessary checks that need to be run in the codebase and are not related to the functionality itself. These kinds of checks usually help to standardize the way the team does certain things during the development process.

Let's see two examples that I use in my everyday work.

Code styling

Code styling is, in my opinion, one of the more underestimated aspects of software development. The fact that several developers are going to be working on the same project, making changes to the same codebase, each of them with their coding style, can make a project look like a mess after a sufficiently large amount of changes.

Over time, it will become harder for new developers to understand the code that was written by others before them. And this will certainly act as a drawback when adding new features or debugging.

What to do, then?

Usually, there is a standard way of coding for every language. The developers of the languages work hard in creating these standards because they understand the flaws of a poor coding style. And some tools called linters can be run in a project to detect when the code doesn't comply with certain rules defined by the standards.

Make these linters run as part of the automated processes of code checking. It will return the list of faults that are present in the project and the developer can go and fix them. Usually doesn't take much time to fix these suggestions manually, but my recommendation is to use a code formatter that makes that work for you.

Once the code complies with all the coding style guidelines, your team can proceed to make manual reviews on a very much more familiar code this time.

Spell checks

Spell checking is as important for a team as a very thorough code review. The fact that many teams nowadays have members from multiple countries has made it a standard of having a primary language of communication inside every team.

This goes from the language they speak to communicate ideas and have discussions, to the names they set for variables in the code. Also, writing documentation is part of the daily work of software developers, and this documentation is usually written in the same agreed language.

Having an automated process for spell-checking can reduce the number of typos that the team has on their daily tasks. This will lead to a higher understanding of the overall code and documentation written and will make easier the process of explaining details to the developers from other teams or even people that has nothing to do with the software development industry.

Reviewers

Once all the automated tests and checks pass it is time for manual reviews. This means that the feature will be read by other team members apart from the one making the feature. If they consider something needs to be changed, then changes are requested. Otherwise, they approve the feature.

For the feature to be merged, all the reviewers need to approve it. As long as one of them requests changes, the feature should not be merged.

Of course, this can lead to a discussion between the team members, analyzing if the requested changes are needed or if the current implementation is good enough. Don't be afraid of these discussions, they will only make your team closer and everyone will learn a lot in the process.

In my experience, having two reviewers approve a feature is usually good enough. But in any case, the reviewers should be active. This means that they not only should read the code but run it, test it, ask questions, and understand everything that has been put for review.

If these criteria are met, then your team is good to go and your product will almost certainly have a new feature that adds value while keeping everything else working properly.

Conclusions

We have seen some methods to ensure the quality of a product throughout the entire process of development. From unit testing to manual reviews, checking for code style and spelling mistakes.

Taking care of these details for every new feature has proven to be effective in all the teams I have been a part of, and it continues to be. Ensuring good testing and reviewing practices more often than not will make your products more reliable and easier to maintain.

In the beginning, some of these practices might seem like a waste of time, since they can delay the process of shipping new features for production. Nevertheless, using them will make the team more comfortable every time and the development times will start to decrease again. Only that this time you will be a much better team: one that delivers fast and safely.

👋 Hello, I'm Alberto, Software Developer at doWhile, Competitive Programmer, Teacher, and Fitness Enthusiast.

🧡 If you liked this article, consider sharing it.

🔗 All links | Twitter | LinkedIn

A Realistic Look at Python Interfaces: Part II

Alberto González Rosales — Fri, 27 Jan 2023 13:26:42 +0000

Prerequisites

Before reading this article, you should be familiar with the topics exposed in Part I. Be sure to read and understand the problem described there and the flaws of the initial solution proposed.

Also, try to think about an alternative solution before reading this article. That way you will be able to compare and see what the differences are between the one it's going to be discussed in this article and the one you were able to create on your own.

Share your solution, even if it is not completely accurate. I can guarantee you, there is almost always some flaw in some solution because they are almost always created to solve a particular problem. So, don't be hesitant about sharing yours. That way we all learn more!

After that, dive into this article to find out about better solutions using interfaces in Python.

Initial solution

Right now we have a solution that solves the problem we were asked to solve, but it still has some design issues. The main issue we face is that it is impossible to add a new visitor entity without modifying the Research Center class.

This coupling in the classes can lead to introducing bugs because we are adding code in more places than we should when trying to create a new visitor class. Let's see how we can solve this issue!

Interfaces

To create a better solution to this problem, we are going to use an important concept of object-oriented programming called interfaces.

In programming, an interface is a set of rules or guidelines for a class or object to follow. It defines a contract for the class or object, outlining the methods and properties that must be implemented.

An interface does not provide an implementation for the methods or properties, but instead, it defines a blueprint for classes or objects to follow. It is commonly used to provide a common set of methods for different classes or objects to implement, which can then be used interchangeably.

In Python, interfaces are not a built-in feature like in some other programming languages such as Java or C#. However, you can use abstract base classes (ABCs) to achieve a similar effect.

An abstract base class is a class that cannot be instantiated and is used as a base class for one or more derived classes. Classes that derive from an ABC are required to implement certain methods or properties defined by the ABC.

Note : If you want to have a look at another example of using abstract classes in Python feel free to check this article to see how they can be used to implement different sorting methods.

Using interfaces

So, how can we use the power of interfaces to tackle this problem differently?

First, we must go to the root of our problems. That is the fact that we are letting all the responsibility for checking the access to our Research Center class. What if the visitor classes could verify somehow that they have access to a specific research center? This way, adding a new visitor class could prevent us from adding more code to the Research Center class, leading to a more maintainable, less error-prone, code.

To achieve this using Python we need to create an interface that represents what a visitor is. Essentially, a visitor instance needs to be able to check if it can access a specific research center. Therefore, it needs to have a method that allows performing this check for all concrete instances inheriting from it.

An example of our Visitor interface is the following:

from abc import ABC, abstractmethod

class IVisitor(ABC):
    @abstractmethod
    def can_access(self, visitors):
        """Returns whether or not a visitor is on the list of authorized visitors.
        Args:
            visitors (List[Self]): Authorized visitors list.
        Returns:
            bool: `True` if the given visitor is on the list of authorized visitors. `False` otherwise.
        """

As you can see, this class only contains a method can_access that will verify if this visitor belongs to a list of visitors.

Note : The code above names the class representing the interface IVisitor. This capital I at the beginning of the name is a convention for naming interfaces in languages such as Java or C# , but not in Python. We are just trying to emphasize the fact that this class represents an interface, but it might as well have been called Visitor without any problem.

The Research Center Class

The main advantage of this approach is that we won't have to modify the Research Class once a new visitor type is added. But still, we need to make some modifications to our previous implementation of this class to make it comply with this new way of checking the access of visitors.

Let's see how it would look:

class ResearchCenter:

    def __init__ (self):
        self.allowed_visitors = []

    def add_visitor(self, visitor: IVisitor):
        self.allowed_visitors.append(visitor)

    def verify_access(self, visitor: IVisitor):
        return visitor.can_access(self.allowed_visitors)

This new implementation is a lot better than our previous one. Let's see why:

We don't need a new list to store the allowed visitors of each particular type. We replaced our allowed_persons and allowed_vehicles lists with the allowed_visitors lists that don't care about the type of visitor but the fact that they are visitor instances instead.
We don't need a new method to add visitors for every particular visitor type. We have replaced our add_person and add_vehicle methods with a more general-purpose add_visitor method that adds a new visitor without caring about the specific type.
We don't need a new method for verifying the access for every particular visitor type either. Since the responsibility for verifying access now lies in our visitor classes, we can get rid of our previous verify_person_access and verify_vehicle_access methods, and replace them with a more generic one called verify_access. This new method will receive a visitor as an argument and have that visitor check if it can access the list of visitors stored in the research center.

Do you see now how we won't need to add any more code to this class whenever a new visitor class is added?

Modifying our previous concrete visitor classes

With our interface representing visitors and the modified Research Center class, what we are missing now is modifying our concrete visitor classes so they can handle their mechanism for verifying access to some research centers. This is the more important part of this solution since it will be what we would have to code whenever a new visitor class needs to be added.

Previously, the visitor classes were only storing information in the form of attributes, but now they will be needed to have some "behavior" too. They will be responsible for defining their way of checking if they belong to the visitor list of some research center. Let's see a possible solution:

class Person(IVisitor):

    def __init__ (self, id: str, name: str):
        self.id = id
        self.name = name

    def __str__ (self) -> str:
        return self.id

    def can_access(self, visitors: List[IVisitor]):
        for visitor in visitors:
            if isinstance(visitor, Person) and visitor.id == self.id:
                return True
        return False

class VehicleType(Enum):

    AUTO = 1
    TRUCK = 2
    BUS = 3

class Vehicle(IVisitor):

    def __init__ (self, license_plate: str, vehicle_type: VehicleType):
        self.license_plate = license_plate
        self.vehicle_type = vehicle_type

    def __str__ (self) -> str:
        return self.license_plate

    def can_access(self, visitors: List[IVisitor]):
        for visitor in visitors:
            if (
                isinstance(visitor, Vehicle)
                and visitor.license_plate == self.license_plate
            ):
                return True
        return False

Let's explain this code a little:

Both our visitor classes ( Person and Vehicle ) now inherit from the IVisitor class that defines our interface for visitors.
Because of this, they need to have a concrete implementation of the can_access method. If any of these classes would not implement it, we would receive an error when trying to instantiate it.
Since the visitor classes are now responsible for checking if they belong (or not) to a list of visitors, they are defining a way to be identified in a collection of visitors. In the case of the Person class, we are assuming they can be identified by the attribute id , and in the case of the Vehicle class, they are identified by the license_plate attribute.
There is an important difference between this solution and the previous one when iterating the list of visitors checking for access. And that's the fact that previously we always knew that we were checking for a visitor of some type on a list of visitors of the same type. But now, since the list of visitors can be of any type, we need to be sure that we are checking against the same type that our class has. That is what we achieve when using the isinstance method provided by Python.

With all these pieces in order, we now have a much better mechanism to handle access verification at the research centers. Let's see how easy it is now to add a new visitor type.

Adding a new Visitor Class

We are trying to create a better solution than the one exposed here precisely because of the flaws this solution had when adding new visitor classes. To illustrate how we have solved those issues with this new solution, let's add an Animal class to this scenario.

Let's assume the animals only have a name and an id attribute, and that this id is unique for every animal. A possible implementation in Python would be the following:

class Animal(IVisitor):

    def __init__ (self, id: str, name: str):
        self.id = id
        self.name = name

    def __str__ (self) -> str:
        return self.id

    def can_access(self, visitors: List[IVisitor]):
        for visitor in visitors:
            if isinstance(visitor, Animal) and visitor.id == self.id:
                return True
        return False

And that's it! As easy as creating a new class and implementing the can_access method. In this particular case, it looks very similar to the implementation of the Person class because we are also using an id attribute to identify the animals.

The identification can be addressed in whatever way we define, for a specific class. Let's say, for example, that we could have also checked for the name of the animals, in case we were guaranteed that the names were unique for every animal.

Conclusions

In this article, we have learned how to use interfaces in Python to solve problems very similar to what we could encounter in real-life scenarios. We learned how to address all the issues presented in Part I of this series of articles.

With this new solution, we got rid of having to add extra code to the Research Center class whenever we wanted to include a new visitor class in our project. We refactor our code to make it much more maintainable by using interfaces and letting the responsibility for checking access to the visitor classes instead of leaving all the responsibility to the overloaded Research Center class.

We saw how we could add a new visitor class easily now. Just define whatever attributes you need to identify it, and make a concrete implementation of the can_access method.

If you want to check a more complete version of the code examples shown in this article you can do it here. Be sure you understand it and don't be hesitant about modifying it and running it on your local computer. Also, ask any questions regarding this implementation. I will be happy to help you, and very grateful for your feedback.

If you enjoy this article, please show your support by reacting, commenting, or just spending a few minutes thinking about the topics exposed here. Don't be a passive reader, think about what you read and share your thoughts. See you soon!

Also, if you want (or have a friend that wants) to learn about programming in Python in the Spanish language, you might be interested in the other project I'm glad to be a part of:

CodeXL Academy blog: A blog with Python content only in Spanish. Sometimes we publish translations of the articles published here for our English-speaking audience.
CodeXL Academy official website: Learn about everything we have to offer you.
Free newsletter: Receive updates every week about what's happening in the world of Python and our Academy.
Free and Paid courses: Discover our teaching materials in Spanish.

👋 Hello, I'm Alberto, Software Developer at doWhile, Competitive Programmer, Teacher, and Fitness Enthusiast.

🧡 If you liked this article, consider sharing it.

🔗 All links | Twitter | LinkedIn

A Realistic Look at Python Interfaces: Part I

Alberto González Rosales — Sun, 15 Jan 2023 21:25:49 +0000

In this series of articles, we are going to be talking about interfaces in Python. Interfaces are a powerful resource to use in several real-life scenarios.

Because of that, we are going to approach learning them by using an example that is very likely to occur in real life. Even if this exact case does not happen exactly as we will show, it is easy to find similar cases and use similar solutions to the ones we are going to be talking about.

So, let's dive in!

Real-Life Problem and Motivation

Suppose there is a Research Center that is conducting some important experiments. This Research Center would like to verify the access to its facilities. For that reason, it has a list of visitors authorized to enter. These visitors can be persons or vehicles. For the persons, it is only needed to store their identity number and name. And for the vehicles , it is only needed to store their plate number and the type of vehicle (car, bus, or truck). We are asked to implement an access verification mechanism for the Research Center.

As we can see, this scenario is likely to happen in real life. Many institutions need to keep track of the visitors they have to their facilities, and need to be able to tell if a certain person or vehicle is allowed to enter it or not.

Let's see how we can make an initial solution to this problem using object-oriented programming in Python.

First Approach

We need to start by creating a way to represent all the elements involved in this problem. On the one hand, we have persons and vehicles , and on the other hand, we have the research center. The first ones are the visitors, and the latter is the entity responsible for handling the access verifications.

Let's create our first solution.

The Person Class

To represent a Person we will create a class that contains two attributes:

An id attribute, which is of type string. This attribute is unique for every person.
A name attribute, also a string.

A possible implementation in Python would be like this:

class Person:

    def __init__ (self, id: str, name: str):
        self.id = id
        self.name = name

    def __str__ (self) -> str:
        return self.id

This is a simple class, just for representational purposes. Because of that, it does not have any methods except for the special __str__ to give a more human-readable representative string as its identifier.

The Vehicle Class

Similar to the above example, to represent a Vehicle we will also create a class with two attributes:

A license plate attribute, which is of type string and it is unique for every vehicle.
A vehicle type attribute, which will be an enum type, since we only have three possible choices: car, bus, or truck.

An example of this class would be the following:

from enum import Enum

class VehicleType(Enum):

    AUTO = 1
    TRUCK = 2
    BUS = 3

class Vehicle:

    def __init__ (self, license_plate: str, vehicle_type: VehicleType):
        self.license_plate = license_plate
        self.vehicle_type = vehicle_type

    def __str__ (self) -> str:
        return self.license_plate

Once again, since this class is just for representational purposes, it will not have any methods except the __str__ method, which we can use to easily identify our vehicle instances.

The Research Center Class

Now that we know what our visitor classes look like, it is time for us to figure out a way to handle access verifications properly. For this reason, we are going to create a third class: the Research Center.

This class needs to have the capacity of checking if a person or vehicle can access it. Let's see one way to achieve this.

Let's create a Research Center class that will consist of the following:

An allowed_persons attribute, which will be a list of persons , as defined above. This list will contain all the persons allowed to enter the research center.
An allowed_vehicles attribute, which will be a list of vehicles , as defined above. Similar to the allowed_persons list, this one will contain all the vehicles allowed to enter the research center.
An add_person method. This will add a new person to the list of allowed persons.
An add_vehicle method. This will add a new vehicle to the list of allowed vehicles.
A verify_person_access method. This one will check if a particular person can access the research center.
A verify_vehicle_access method. This one will check if a particular vehicle can access the research center.

As we can see, this class is more complex than the person or vehicle classes. It contains attributes as well as methods to handle the addition of new visitors and check the access of a particular visitor as well. An example of this class in Python would be like this:

class ResearchCenter:

    def __init__ (self):
        self.allowed_persons = []
        self.allowed_vehicles = []

    def add_person(self, person: Person):
        self.allowed_persons.append(person)

    def add_vehicle(self, vehicle: Vehicle):
        self.allowed_vehicles.append(vehicle)

    def verify_person_access(self, person: Person) -> bool:
        for registered_person in self.allowed_persons:
            if registered_person.id == person.id:
                return True
        return False

    def verify_vehicle_access(self, vehicle: Vehicle) -> bool:
        for registered_vehicle in self.allowed_vehicles:
            if registered_vehicle.license_plate == vehicle.license_plate:
                return True
        return False

We should notice how the verify_person_access method iterates through the list of allowed persons and checks if any of them shares the same id as the person being checked. Similarly, the verify_vehicle_access does the same for the allowed vehicles, and checks against the license_plate attribute.

Remember that we are assuming that these attributes are unique, so they are a correct way of uniquely identifying either persons or vehicles.

Flaws of our First Approach

The solution above seems to handle this particular problem very well. It sure can add new persons or vehicles and check for the access of some particular visitor by comparing their identifying attributes against the allowed persons or vehicles, depending on the case. So, what is wrong with this approach?

Well, let's imagine that the research center suddenly realized that it has not been tracking the animals they use for regular experiments. They would like to have a mechanism that allows them to check if some specific animal is part of the list of allowed animals. How would we modify our solution so that it can handle this new type of visitor?

A natural answer would be to create an Animal class, with some id attribute, and add the corresponding allowed_animals list and the add_animal and verify_animal_access methods to our Research Center class. This way we handle the case of animals.

But, what if they are also not keeping track of drones or robots , or any other entity they consider should be verified for access?

We would have to add the corresponding classes to represent these new entities and also add methods and properties to the Research Center class to handle the tracking and access checks.

These constant changes in the Research Center class could lead to introducing errors in our program. And this happens because we are letting all the responsibility for checking the access to the "almighty" Research Center class.

Conclusions

So far we have seen how to approach a real-life problem using object-oriented programming. We have seen how to create classes and use them together to create a correct solution which still has some design issues.

So, how can we address these issues? That will be the subject of the Part II of this series of articles. In the meantime, feel free to reach me and tell me about how would you solve this problem using object-oriented programming. A little hint is on the title of this article itself!

If you want to check a more complete version of the code examples shown in this article you can do it here.

👋 Hello, I'm Alberto, Software Developer at doWhile, Competitive Programmer, Teacher, and Fitness Enthusiast.

🧡 If you liked this article, consider sharing it.

🔗 All links | Twitter | LinkedIn

My Journey as a Computer Scientist in 2022 - Dev Retro 2022

Alberto González Rosales — Wed, 04 Jan 2023 20:20:51 +0000

When 2022 started I decided that I would seize it and that it would be the best year so far in terms of learning about new topics and opportunities that I would not let pass by. This is what I accomplished by trying as hard as ever in any period consisting of 365 days in my life.

I'm writing this right now with the hope that it serves as a motivation for those of you who want to take out the best of yourselves. And, long story short, the secret for it is no secret at all: just try every day to be better than the day before.

With that being said, here we go!

Software Developer

When it comes to the software developer in me, I think this year I indulged myself a lot. I tried to learn all I could from all the teams that I was working with at the moment, and the fact that I get to work in such different environments allowed me to get a better understanding of several areas of software development that I was not familiar with at the moment.

A non-exhaustive list of the roles that I have been involved in is:

Being a Back-End Developer in several types of projects such as e-commerce websites, booking services, and accessibility tools. These kinds of tasks allowed me to get deeper in my knowledge of frameworks such as Django and Node.js. These both are highly recommended if you want to get started in Back-End development.
Being a " Front-End Developer". And yes, here I use quotes :). And the reason is that even if I did have some experience doing some Front-End development I did not enjoy the tasks very much and I always ended up doing the easiest tasks that my team could give me. But still, I was able to collaborate on some landing pages here, some widgets there, etc... I don't regret the time I spent doing these jobs. It helped me a lot in deciding that these were not skills that I wanted to have at the moment and that I should be focusing on something that I enjoy more. And that is what I did! Even though, I have to say that React is a good library if you want to start with Front-End development.
Being an Automation Engineer. I don't know if this is the appropriate name for this role, but my tasks were mostly related to creating automated tests that tried some functionality on websites. This was an exciting role! I learned a lot about the theory behind testing and why it is such an important part of software development. Although I was mostly doing end-to-end testing this opened the path to other types of testing such as unit testing and integration testing. And, right now, testing is one of the topics that I'm more passionate about. My recommendation, if you want to get started with end-to-end testing, would be to use Cypress. It is a very powerful library that will allow you to take your tests to the next level.
Being a CI/CD Engineer. As before, I don't know if this is the name of the role, but that doesn't matter. The reason why I call it this way is that I get to work closely on creating deployment pipelines for other people's projects. It is a role where I have to keep myself up-to-date with Python and Ansible.

Data Scientist

This year was also when I took my first steps as a Data Scientist. I enjoy this area of Computer Science and I would like to do more of that shortly.

I started by taking most of the courses offered by Kaggle and some of the things I learned there allowed me to make actual progress in some real-life scenarios manipulating and interpreting geospatial data. I increased greatly my knowledge of libraries like GeoPandas and I started to use Jupyter Notebooks much more.

I would recommend everyone with an interest in programming to try and do some Data Science. There is a lot of value in the data and you can make a real impact on the world if you take the time to learn to interpret data correctly.

ICPC Problem setter

Being a former competitive programmer I find myself now on the side where I can collaborate creating good contests for the current competitors. This year was no exception.

I'm glad that I had the chance to collaborate with a group of wonderful people creating the problem set for The 2021 ICPC Caribbean Finals (Qualifier). This was a good way to keep my knowledge about algorithms and data structures fresh. Also, it allowed me to train my writing and code-reviewing skills, since we had to create statements in several languages and provide solutions for problems using several languages also (only this time I mean programming languages :)).

For those of you who don't know what Competitive Programming is, I would recommend it if you are looking for some algorithmic challenges. You can check about the World Finals held this year here.

Teacher

Last, but not least. This year I had the chance to teach courses about Data Structures and Algorithms and Introduction to Programming in Python. The first one was for students of Computer Science and the second was for high school students pursuing a major degree in Chemistry.

I would say that the teaching experience is one of the more gratifying I had this year. It pays off when you see your students improving after every lesson. And it comforts me that I might have been able to teach something useful to someone.

Also, because of my passion for teaching and spreading knowledge, this year I decided to start writing on a blog about topics that I found interesting. You can check it out here. Keep tuned for more articles in the future and don't be hesitant about giving some feedback. It will be much appreciated.

On top of that, I created this open-source repo Data Structures and Algorithms in Python. It was supposed to be a way for me to learn more about Python, but now we are trying to create a community to spread knowledge about Algorithms , Data Structures , Testing , Object-Oriented Programming , and Python. You are welcome to collaborate!

Conclusions

I have to say that for me it was one of the greatest years I've had in terms of personal growth. When I look back it seems like I've walked a long road. But it has only been the effort put on every day to become a bit better than I was the day before.

One last thing to consider though:

I was able to make this journey because I did not take it alone. The people that support you every day, your teammates, your loved ones... Your merits are theirs also in a great part. So, don't forget to thank them.

And that's it. When writing this I came across the idea that, to achieve many of the goals related to Computer Science, Software Development, etc... I had to change a set of habits in some aspects of my life. Maybe I will write about it shortly, so stay tuned if you want to know my experience about how some external factors can influence your ability to learn and achieve goals if you are a programmer.

Also, you might have noticed that I did not go too deep into details when listing some of my working experiences. In case you want to have a much more in-depth conversation about some particular topic (framework, library, work experience, or anything related) you can leave a comment or reach me directly. Maybe it will lead to some interesting debates. I sure hope so!

👋 Hello, I'm Alberto, Software Developer at doWhile, Competitive Programmer, Teacher, and Fitness Enthusiast.

🧡 If you liked this article, consider sharing it.

🔗 All links | Twitter | LinkedIn

Abstract Classes, Inheritance, and Sorting Algorithms in Python

Alberto González Rosales — Sun, 01 Jan 2023 21:34:38 +0000

Recently I found myself revisiting my knowledge of data structures and algorithms. I was also trying to improve my skills in Python, so I decided to give it a try at implementing some sorting algorithms from scratch. Here is how I did it.

Sorting Algorithms

First of all, we need to define what a sorting algorithm is. For me, it is a way to "sort" a set of items (integers, strings, objects...) according to some comparison criteria.

For example, we could sort an array of integers from lowest to highest. In this case, the integers are our set of items, and the "lowest to highest" sentence tells us that the comparison criteria demand that smaller integers should come first once the items are sorted.

Notice that right now we are not making emphasis on what exact algorithm we are going to use to sort the items but on the prerequisites of a sorting algorithm.

Abstract Classes

Now that we have somehow defined what a sorting algorithm is, we can try to express this kind of "behavior" by using a class. Since we don't care at the moment about the specific implementation of the sorting algorithm, we can start by defining its "interface" by using an abstract class.

We can think of abstract classes as a template definition of methods and variables of a class. At least one of the methods of an abstract class also needs to be "abstract", which means that it is not needed to provide a specific implementation.

Abstract classes cannot be instantiated, but they can be subclassed. As a result, subclasses need to implement the "abstract" methods.

Returning to our case of use, an abstract class representing our Sort "interface" could have the following attributes and methods:

The attribute items represent the items to be sorted.
The attribute comp_func represents how to compare two elements in the items collection.
The sort method returns the sorted version of the items collection when sorted using the comp_func criteria.

This "sort" method is only responsible for returning the sorted items, but it does not care about the "how". To handle this, we need to add an extra method:

A _sort method. We will not implement this abstract method in the abstract class but in the subclasses. This way we can have a "Bubble Sort" implementation as well as a "Merge Sort" implementation. We can have any sorting method that we want!

A possible implementation using Python would be like this:

"""Module with the base implementation of a Sort class."""

from abc import ABC, abstractmethod

class Sort(ABC):
    """Base class for sorting."""

    def __init__ (self, func, items):
        self._comp_func = func
        self._items = items

    def sort(self):
        """Returns the sorted version of the elements contained
        in the `_items` property.
        Returns:
            List: The sorted elements.
        """
        return self._sort(self._items)

    @abstractmethod
    def _sort(self, items):
        pass

Inheritance

Now is the time when we need to care about what specific sorting algorithm we are going to use. Let's see how we can make use of inheritance to implement two of the classic sorting algorithms out there: "Bubble Sort" and "Merge Sort".

For the "Bubble Sort" algorithm, a simple implementation would look something like this:

"""Module with the implementation of the BubbleSort algorithm."""

from .sort import Sort

class BubbleSort(Sort):
    """Class that represents a BubbleSort implementation."""

    def _sort(self, items):
        size = len(items)
        swapped = True
        while swapped:
            swapped = False
            for i in range(1, size):
                if not self._comp_func(items[i - 1], items[i]):
                    items[i - 1], items[i] = items[i], items[i - 1]
                    swapped = True
            size -= 1
        return items

Things to notice here:

We are creating the "BubbleSort" class as a subclass of the "Sort" class.
We don't need to redefine the __init__ and sort methods. These are inherited from the "Sort" class.
We redefine the _sort method to make a classic O(n^2) implementation of the "Bubble Sort" algorithm.
We are making use of the _comp_func attribute set in the __init__ method of the "Sort" class.

For the "Merge Sort" implementation we can do the following:

"""Module with the implementation of the MergeSort algorithm."""

from .sort import Sort

class MergeSort(Sort):
    """Class that represents a MergeSort implementation."""

    def _sort(self, items):
        if len(items) <= 1:
            return items

        left = items[0 : len(items) // 2]
        right = items[len(items) // 2 : len(items)]

        left = self._sort(left)
        right = self._sort(right)

        sorted_items = self._merge(left, right)
        return sorted_items

    def _merge(self, left, right):
        merged = []
        left_idx = 0
        right_idx = 0

        while left_idx < len(left) and right_idx < len(right):
            if self._comp_func(left[left_idx], right[right_idx]):
                merged.append(left[left_idx])
                left_idx += 1
            else:
                merged.append(right[right_idx])
                right_idx += 1

        while left_idx < len(left):
            merged.append(left[left_idx])
            left_idx += 1

        while right_idx < len(right):
            merged.append(right[right_idx])
            right_idx += 1

        return merged

Things to notice here:

Same elements as above. The only difference is that in this case the running time of the algorithm is O(n log n).
We are implementing a _merge method even if it is not enforced by the "Sort" class. This is ok, we need to implement the "abstract" methods but that doesn't mean we cannot create new methods.

Following this pattern, we can create more sorting algorithm implementations such as "Heap Sort" and "Insertion Sort".

Next Steps

I will be looking into creating unit tests for these implementations in the future. Maybe by taking advantage of Object-Oriented Programming and some concepts such as parametrization it is possible to create reliable and maintainable tests.

If you would like to take a closer look at these implementations you can do it here:

Sorting Implementations

If you want to take a look at the current status of the unit tests I'm creating you can do it here:

Unit tests for Sorting Implementations

Also, if you want to contribute to this open-source project to learn about Data Structures, Algorithms, and Python, you can check it out here:

Data Structures and Algorithms in Python

We are waiting for your contributions. Any help will be appreciated.

👋 Hello, I'm Alberto, Software Developer at doWhile, Competitive Programmer, Teacher, and Fitness Enthusiast.

🧡 If you liked this article, consider sharing it.

🔗 All links | Twitter | LinkedIn