Classes of complexity
Classes of complexity
Classes of time complexity to classify algorithms. Plus strategies used by load balancers to redirect the traffic.
Hi Friends,
Welcome to the 23th issue of the Polymathic Engineer newsletter.
Today we will talk about:
Load balancers traffic redirection strategies
Classes of time complexities
Coding challenge
Interesting tweets
Load Balancing strategies
Load balancers are servers sitting between a set of clients and a set of servers. They act as reverse proxies, redirecting and distributing the requests to the servers.
Here are 7 strategies used to distribute the requests:
Random redirection: The Load Balancer redirects the traffic to the servers following a random order. This strategy could have problems because a server can get overloaded by chance.
Round Robin: The Load Balancer evenly redirects the traffic to the servers following a particular circular order. This strategy is easy to implement and a good starting point in many cases.
Weighted Round Robin: This strategy is a variant of the Round Robin, where each server receives many requests according to weight. This approach is helpful if some servers are more powerful than others.
Sticky Round Robin: This is an improvement of the Round Robin, where all the requests from a client go always to the same server.
Performances based: The Load Balancer performs healthy checks on the servers to get statistics. It then uses these data to stop redirecting requests to overloaded servers and redirect more traffic to servers performing well.
IP based: The Load Balancer calculates a hash of the client's IP address and uses this value to redirect the traffic. In this way, it redirects the requests of a given client always to the same server. This approach can be helpful if the server caches the request results.
Path based: The Load Balancer distributes requests according to their URL.
So the service requests are always redirected to the same servers. This approach separates the services making the deployment easier and isolating them in case of failures.
No strategy is intrinsically better. Each strategy has pros and cons, and you should adopt the best approach fitting your use case. Without precise requirements, Round Robin is always a good strategy.
It can also make sense to have multiple layers of load balancers adopting different strategies. For example, the 1st layer could use the hash approach to redirect traffic to the 2nd layer. The 2nd layer could then use Round Robin to redirect traffic to the servers.
If you are interested in reading more about load balancers, you can read this blog post I wrote time ago on my personal website.
Time complexity classes
The Big O notation groups algorithms into a set of classes, such that all the members of a class are equivalent in terms of running time.
The running time is described by a numerical function dependent on the size of the inputs.
The good news is that only 8 classes can occur during the analysis:
Constant: O(1) The running time of the algorithm is independent from the size of the input. Example: function adding two numbers.
Logarithmic: O(logn)
The algorithm halves the size of the input at each step.
Example: binary search reduces the solution space is reduced by half after every step.
Linear: O(n)
The algorithm looks at each input item a costant number of times.
Example: a function computing the biggest or smallest item of an array.
Superlinear: O(nlogn)
The algorithm performs the following operations at each step:
- split the input in two halves
- execute a linear scan of the input
Example: sorting algorithms like Quicksort and Mergesort.
Quadratic: O(n^2)
The algorithm looks at most or all pairs of input items.
Example: less optimal sorting algorithms such as insertion and selection sort.
Cubic: O(n^3)
The algorithm checks all triples of items in an array.
Example: some dynamic programming algorithms.
Exponential: O(c^n) for a constant c > 1
The algorithm uses a recursive function having a branching factor of c.
Example: a function enumerating all subsets of n items is O(2^n).
Factorial: O(n!)
The algorithm generates all permutations or orderings of the input items.
Code challenge
The coding challenge for this week is Maximum Number of Vowels in a Substring of Given Length.
The problem takes a string as input and asks to find the maximum number of vowel letters in any substring with length k.
The brute force approach would be:
- iterate all the possible substrings of length k
- check the max number of vowels in it
The problem of this approach is that there is a lot of repeated work.
A better approach requires a sliding window:
- keep a window of size k
- update the number of vowels in the window as it moves through the string
Here is a possible implementation:
The time complexity is O(N) to move the windows through the string, while the space complexity is O(1). There is an easy possible optimization that doesn’t affect the overall time complexity. If vowelsInSubstring is equal to k, it’s possible to safely break from the main for loop, as that would be the maximum number of vowels possible.
Interesting Tweets
I remember well that factory worker mentality about software engineering. That culture was so deeply rooted, especially in more traditional companies. Hard to enjoy being a software engineer in that context.
If both parents work and live far from the family, it's hard to completely avoid childcare. But expenses should never be a blocker for having kids, especially considering how much they give back to you. Probably the best investment you can do in life.
Deadlines give that adrenaline and pressure that help to complete a task faster. I'm not too fond of deadlines, but I must admit that they're essential occasionally. The problems arise when they come too frequently.
