Let’s imagine that you want to record the website visits onto a database. The information to record is pretty simple,
Metadata of the record: <IP Address, User Agent, Location, Country>
Example record: <18.104.22.168, Mac/Chrome, California, US>
All databases come up with read/write limits. Let’s assume that the database we are going to use comes with write limit of 200 TPS.
Solving the problem:
Starting off with a simple solution without any distributed system bells and whistles. Focusing on the core architecture, we would like to have something that would prevent us from overwhelming the database with too many requests. …
Today we are going to look at the explore the technique called Binary Search. Binary Search is a technique that works on sorted arrays, when the numbers are sorted you can make certain decisions which help optimize the algorithm a lot.
Suppose the problem statement is to find the number ‘9’ if it exists in the array or not, then we just walk through the elements one by one and check if it exists and return the index when you find it. A basic for loop would be suffice to get the job done for this one. …
Having the basic understanding of Recursion is necessary before jumping onto Memoization technique used in algorithms, please take a look at the following problem and solve the problem by drawing out the recursion tree.
You are climbing a stair case. It takes n steps to reach to the top. Each time you can either climb 1 or 2 step(s). In how many distinct ways you can climb to the top?
The problem statement is the same in the linked post, but this time we are going to add the optimization.
I have went ahead and completed the recursion tree from the last problem, I have highlighted the parts where the calculation is repeated. The observation to make here is once we are at a certain stair #, there are only so many distinct ways of getting to the top. …
We are going to talk about how to intuitively think about recursion.
You are climbing a staircase. It takes n steps to reach to the top. Each time you can either climb 1 or 2 step(s). In how many distinct ways you can climb to the top?
This problem is a typical model for recursion. To easily visualize how you can solve this problem assume that you are on the top position already, A friend of yours is going to climb up the stairs.
As you started observing this you would have probably identified the pattern, your friend can make the decision of taking either 1 step or 2 steps from the current position. Assume your friend is in Stair #X and if he/she decides to take 1 step from there that will be one distinct route and if he/she decides to take 2 steps from there that will be another distinct route. The problem states asks us to account for all the routes and thus we should basically do this at every step. …