I know the stress of preparing for technical interviews at companies like FAANG. That's why I'm kicking off a new series to demystify the most critical coding interview concepts.
First up: Binary Search.
It seems simple, but its variations are where most candidates stumble. In this first post, I break down the algorithm, reveal the hidden patterns in its complex variants, and walk you through structured approaches to solve related problems efficiently.
In this post, I will explain in detail how I used the builder design pattern together with the bit mask field technique to reduce complexity. As a result, I decreased the cyclomatic complexity from 24 to 0 and reduced development time from hours to minutes.
The rest of this post is organized as follows sections:
- The problem explains the problem I was solving.
- Creating the bit mask field presents a solution to the problem.
- Cyclomatic Complexity discusses cyclomatic complexity and calculates this metric for the solution presented in the section above.
- Builder design pattern explains the builder design pattern and describes the refactoring process that removed complexity.
- Conclusion summarizes this post.
- References provides references related to the topics discussed here.
All the examples shown here are in C++.
Hi @linguae, The video in the post, originally presented by Barbara Liskov, is a very interesting resource on this topic.
Let me know if your students want to discuss this in more detail, and please share their ideas!
In software development, organizing our codebase in a way that is easy to maintain is always a good practice, and this idea is not new. Actually, I think this started in 1968 when the term software crisis was coined. Since then, we have developed many principles to help us achieve this goal. One person who has made many contributions to this field is Barbara Liskov. She is very famous for the Liskov Substitution Principle (LSP), but she also invented the Abstract Data Type(ADT), which is the core concept of classes and object-oriented programming. Here, I want to discuss composition compared to inheritance and how understanding the Liskov Substitution Principle can help you develop better software.
I described how I improved an ETL process to be more than 4x faster using the same resources. While the old architecture used Python threads, the new one used task queue architecture to be more reliable and scalable. So, I will explain how we can improve a legacy code and speed it up by only modifying the architecture to run the code.
I mean, only the threaded version, which is expected. For tons of cases Python without the GIL is not just slower, but significantly slower; "somewhere from 30-50%" according to one of the people working on this: https://news.ycombinator.com/item?id=40949628
All of this is why the GIL wasn't removed 20 years ago. There are real trade-offs here.
Thanks for the link, that's an interesting read. Actually the referenced PyMutex is a good old pthread_mutex_t, the same you'd use in C or C++. But I shouldn't have written so surely. Although uncontested locks are very fast, if the loop is tight enough, adding locks will be significant.
However, PEP 703 specifically points out that performance-critical container operations (__getitem__/iteration) avoid locking, so I'm still highly skeptical that those locks are the cause of the 30-50%.
The pthread_mutex_t is focused on compatibility at any cost. So while you're right that the C++ stdlib chooses this too, it's not actually a good choice for performance.
But I think you're right be sceptical that somehow this is to blame for the Python perf leak.
One of the things this spends some time on that was already obsolete in 2011 is using a pool of locks. In 1994 locks are a limited OS resource, Python can't afford to sprinkle millions of them in the codebase. But long before 2011 Linux had the futex, so locks only need to be aligned 32-bit integers. In 2012 Windows gets a similar feature but it can do bytes instead of 32-bit integers if you want.
If a Linux process wants a million locks that's fine, that's just 4MB of RAM now.
