Unlocking the Hidden Patterns: The Wonders of Binomial Coefficients and Pascal's Triangle

Understanding the Binomial Coefficient:

        Imagine you have a group of 5 friends (let's name them A, B, C, D, and E), and you want to select 3 of them to form a team for a game. The binomial coefficient $\left(\genfrac{}{}{0px}{}{5}{3}\right)$ tells you how many different teams of 3 you can form from the 5 friends.

Breaking Down the Formula:

The formula for the binomial coefficient is $\left(\genfrac{}{}{0px}{}{�}{�}\right)=\frac{�!}{�!(�-�)!}$. Let's break it down using our example where $�=5$ and $�=3$:

1. 1. Factorials: The "!" symbol stands for factorial. For any positive integer $�$, $�!$ (x factorial) is the product of all positive integers up to $�$. For example, $5!=5\times 4\times 3\times 2\times 1=120$.

2. 2. Applying the Formula: To find $\left(\genfrac{}{}{0px}{}{5}{3}\right)$, we plug our numbers into the formula:

   $\left(\genfrac{}{}{0px}{}{5}{3}\right)=\frac{5!}{3!(5-3)!}=\frac{5!}{3!2!}$

   Calculating each factorial:

   
   
   • $5!=120$
   • $3!=6$
   • $2!=2$

   So, $\left(\genfrac{}{}{0px}{}{5}{3}\right)=\frac{120}{6\times 2}=\frac{120}{12}=10$.
   

   This means there are 10 different ways to choose 3 friends out of 5.

3. Why Does the Formula Work?

4. 
   

5. 1. Starting with Permutations: Initially, if we were to line up 3 of your friends out of 5, not just choose them, we'd have to consider the permutations (different arrangements). For the first friend, you have 5 choices, for the second, you have 4 (since one friend is already chosen), and for the third, 3 choices left. So, for permutations, you multiply these:

1. $5\times 4\times 3=60$.

2. 2. Adjusting for Order Not Mattering: The 60 permutations include different orders of the same 3 friends (like ABC, ACB, BAC...). But in our case, the order doesn't matter; ABC is the same team as BAC. Each group of 3 friends can be arranged in $3!=6$ ways (3 options for the first position, 2 for the second, and 1 for the last), so we've counted each group 6 times in our 60 permutations.

3. 
   

4. 3. Getting to Combinations: To correct for this and count each unique group once, we divide the number of permutations by the number of ways to arrange 3 friends:

5. $\frac{60}{6}=10$. This matches our calculation using the binomial coefficient formula, showing that there are 10 unique ways to choose 3 friends out of 5.

6. Conclusion:

             The binomial coefficient formula $\left(\genfrac{}{}{0px}{}{�}{�}\right)$ gives us a way to calculate the number of unique groups (combinations) of $�$ items we can choose from a larger set of $�$ items, without caring about the order of selection. It corrects for the overcounting of arrangements (permutations) by dividing by the factorial of the group size $�!$, ensuring each unique group is only counted once.

Now lets gets into the most interesting part. The pascals triangle and creating it with Binomial Coefficients.     

 

First lets start with writing a small program to print pascals matrix to the nth row.

Idea behind this program is pretty simple List<List>  basically represents Column<Rows> or a matrix.  

  Each rows first and last value will be one that we hard code. Then iterate over numRows and construct each rows. One small thing to notice here is the inner for loop it has to run from 1 to < less than rowNum. Basically it runs 1, 2, 3 times from the 2nd  row. So basically rowNum-1 times it runs, basically skipping for first two rows.

    Lets move forward to  to understand the relation between binomial coefficient and the pascals triangle. If you look closely you can find something really interesting. Below is the representation of of pascals triangle 

If you did not catch this yet see the below which will unlock the hidden pattern of the relation between binomial coefficient and pascals triangle

with this we now understood the relation between pascals triangle and binomial coefficient. Great now for a very dumb person like me can easily understand what Striver is saying in his video. Now the below program makes a lot of sense. Check the below program which will show you how to calculate the value in a particular position of the pascals triangle.

If you reached this far of the blog then great you are upto something special in your life. Stay tuned for the next blog

Designing a Browser History Feature

Objective

The goal is to create a class capable of handling browser history operations efficiently. This includes:

• Initializing the browser with a specified homepage.
• Navigating to new URLs (visiting pages).
• Enabling backward and forward navigation through the history.

Key Components

• Constructor: Initializes the browser with a homepage.
• Visit(URL): Navigates to a new URL and updates the current position in the history.
• Back(steps): Moves back a specified number of steps in history and returns the current URL.
• Forward(steps): Moves forward a specified number of steps in history and returns the current URL.

Implementation

We will use a doubly linked list to manage the history of visited URLs, allowing for efficient navigation both backward and forward.

class BrowserHistory {
    class Node {
        String url;
        Node prev, next;

        public Node(String url) {
            this.url = url;
        }
    }

    private Node current;

    public BrowserHistory(String homepage) {
        current = new Node(homepage);
    }

    public void visit(String url) {
        Node newNode = new Node(url);
        current.next = newNode;
        newNode.prev = current;
        current = newNode; // Move forward to the new page
    }

    public String back(int steps) {
        while (current.prev != null && steps-- > 0) {
            current = current.prev;
        }
        return current.url;
    }

    public String forward(int steps) {
        while (current.next != null && steps-- > 0) {
            current = current.next;
        }
        return current.url;
    }
}

Example Usage

BrowserHistory browserHistory = new BrowserHistory("takeuforward.org");
browserHistory.visit("google.com"); // User visits 'google.com'.
browserHistory.visit("instagram.com"); // User then visits 'instagram.com'.
browserHistory.back(1); // User goes back one step to 'google.com'.
browserHistory.back(1); // User goes back another step to 'takeuforward.org'.
browserHistory.forward(1); // User moves forward to 'google.com' again.
browserHistory.visit("takeuforward.org"); // User visits 'takeuforward.org', overwriting forward history.
browserHistory.forward(2); // No forward history, remains on 'takeuforward.org'.
browserHistory.back(2); // User goes back to 'google.com'.
browserHistory.back(7); // Attempts to go back 7 steps but only goes back to the homepage.

Complexity Analysis

• Constructor: O(1) - Only involves initializing a single node.
• Visit(URL): O(1) - Adding a new node to a doubly linked list is a constant time operation.
• Back(steps) and Forward(steps): O(steps) - Proportional to the number of steps taken, due to traversal through the linked list.

This design mirrors the functionality of real web browsers, offering an intuitive navigation experience while ensuring operations are performed efficiently.

An early morning adventure

On the early morning of February 1st, I decided to tackle a problem from the Striver's SDE sheet.

I came across an intriguing challenge titled "Set Matrix Zeroes".

Here's how I approached it:

Initially, I attempted a brute force method. The usual strategy of iterating through a matrix and setting rows and columns to zero has a drawback: it can lead to the loss of the matrix's original state, potentially zeroing out the entire matrix, which isn't the desired outcome. To avoid this, my approach involved marking the rows and columns that intersect at a zero element with a temporary value of -1. This way, the matrix's original elements remain unchanged until the final step, where a second pass converts all -1 values back to zeros.

The main drawback of this method is its inefficiency, with a time complexity that could be roughly estimated as (O((m times n)^2)), due to the need for multiple iterations over the matrix.

Seeking improvement, I explored an optimal solution that builds upon the brute force idea but introduces two marker arrays, one for rows and another for columns. As we scan the original matrix, we use these arrays to mark any row or column containing a zero. A subsequent iteration through the matrix then uses these markers to set the corresponding elements to zero. This refined approach reduces the number of iterations, achieving a time complexity of (O(2 times m times n)).

Despite the improvement, I wondered if there was an even better solution. Recalling that I had previously solved this problem on LeetCode under the title "Set Matrix Zeroes" (you can find the problem [here](https://leetcode.com/problems/set-matrix-zeroes/)), I revisited my submission. To my surprise, I had employed a different, more efficient strategy in my past solution, which can be viewed [here](https://leetcode.com/problems/set-matrix-zeroes/submissions/1004912402/).

The best solution I found leverages the first row and first column of the matrix as marker arrays, eliminating the need for additional space. A special variable is used to determine whether the first row or column should be entirely zeroed. This approach requires careful iteration from the second row and column onwards, with a final pass to address the first row and column as needed.

For those interested in the solutions, they are available on my GitHub repository at [this link](https://github.com/mathewjustin/2024-DsAndAlgo/tree/main/src/main/java/com/codepower/striver/arrays).

Thank you for taking the time to read this if you've made it this far.

Justin

An engineers view to religion

KEEP ONE HAND DISTANCE!

Moving from a wonderful organiztion !

Cycle travelled all the way from Bangalore to Kannan devan hills, Idukki. ;) 

A wonderful journey of last 3 years has come to an end. Moved out of MBRDI / DTICI ( Daimler Trucks Innovation Center India)

Automate fetch upstream using github actions

        I like to fork interesting github repositories and experiment with it. Those who do this actively might have faced the problem of upstream sync, where we need to sync our repository with the upstream repository. Imagine you forked a repository contains some articles which are being updated everyday, you will like them to have it synced everyday. I do ;) 

  Github introduced a feature called fetch upstream this year to solve this issue. But in this case you need to click on the fetch upstream button by yourself, this article is for the lazy ones who want it to be done automatically. 

   In this blog we are about to learn how to automate upstream fetch of any repository you cloned. We are using Github actions to do this. The below is the yaml configuration for my github action

   

Here you can see the cron is set to run at midnight, also as you might have already noticed i have created a simple bat file to be excecuted, you can see it below. Next step is to configure a github action with the yml file we created. Go to Actions tab

Click on New Workflow-> Skip this and set up workflow yourself.

Here you can select the yml file you created under your repository. Once you set it it up your fork will automatically sync every night. 

You can see this example live on my github repository :  every-programmer-should-know 

Cheap Fast Good

 

You can make a great software but you have to choose 2 out of this above 3. There is no way to get around!

Python linked List implementation

 

class Node:
     def __init__(self, data):
         self.data=data
         self.nextNode=None



class LinkedLIst:

    def __init__(self):
        self.head = None
        self.numberOFNodes=0
     # Here we get o(1) constant running time complexity for insertion.
    def insert_start(self,data):

        self.numberOFNodes=self.numberOFNodes+1
        new_node = Node(data)

        if not self.head:
            self.head=new_node
        else:
            new_node.nextNode=self.head
            self.head = new_node
 #Linear running time o(n)
    def insert_end(self,data):
        self.numberOFNodes=self.numberOFNodes+1
        new_node=Node(data)

        actual_node=self.head

        while actual_node.nextNode is not None:
            actual_node=actual_node.nextNode

        actual_node.nextNode=new_node

    def size_of_list(self):

        actual_node = self.head

        while actual_node is not None:
            print(actual_node)
            actual_node=actual_node.nextNode

    def traverse(self):
        actual_node=self.head

        while actual_node is not None:
            print(actual_node.data)
            actual_node=actual_node.nextNode

    def deleteAtHead(self):

        self.head=self.head.nextNode
        self.numberOFNodes=self.numberOFNodes-1

    def deleteAtTail(self):

        actual_node = self.head

        while actual_node.nextNode.nextNode is not None:
            actual_node=actual_node.nextNode

        actual_node.nextNode=None
        self.numberOFNodes=self.numberOFNodes-1



linked_list=LinkedLIst()
linked_list.insert_start(4)
linked_list.insert_start(3)
linked_list.insert_start('A String type')
linked_list.insert_start(1.232)
linked_list.insert_end(12.232)
linked_list.traverse()

print('Deleting at the front')
linked_list.deleteAtHead()
linked_list.traverse()

print('Delete at the last position')
linked_list.deleteAtTail()
linked_list.traverse()

Custom annotations in Spring Boot

           I had worked on spring framework extensively throughout my career. The one thing which I am always try to implement in any Spring project I work on is Custom annotation. Its a fancy stuff but useful in many ways. 

         Say you have numerous micro services (Duplicate code bases which will f*** you up) running on your cluster, the best and first thing you do is - Build a common library to push all your model classes, so called util package of your organization :p and the fancy stuffs  . I am fortunate that I get to do all these experiments early on my career. So lets start with the problem.

1. We have many micro services which are built on top of spring framework. We want to use a  common service bean in all our boot apps.  
2. This bean should be enabled with @EnableMyBean annotation.
3. Once the spring boot app loads it should intercept this annotation and inject our MyBean service to our Spring boot application.

So the first step to do is create the annotation itself

The @Import is from org.springframework.context.annotation package  You can find the documentation over here

Next is the implementation of MyBeanSelector class. We can define it as follows.

     Lets look at each components. First the importSelector interface. As the definition on the Spring document "Interface to be implemented by types that determine which @Configuration class(es) should be imported based on a given selection criteria, usually one or more annotation attributes." 

     This class is accountable for which Bean should be injected  to the spring context. It has many other cool features as well. Say you want to read some property from the environment in which the common library is used. Ie, from the Yaml file of the spring boot app which is using your common library. Then you can implement EnvironmentAware Interface. 

     

    Once we do the above, next we can define the actual service class inside "com.commons.service". 

So now You can use @EnableMyBean on your main method of the spring boot application. And you can Autowire MyService class anywhere inside your application. At the time of start up spring would automatically detect the @EnableMyBean annotation and push the Service Bean to the app's context.

Algorithms and Data Structures on Python - Notes 2

 Linked list

It needs a node class

It should have 2 basic characteristic

* Data

* Reference to the next node

It can be used to implement stack or queues. It does not allow random access as like in Array.

Obtaining a last node, locating a particular node requires an iteration over all or most of the items in the linked list. 

Advantage

* It is dynamic data structures(No need to specify size)

* It can allocate memory on run time

* It take O(1) constant time complexity to insert an item at the beggining or removing at the beggining, unlike array where as its O(n)

* Linked list can grow organically, unlike in array where we need o(n) for re-sizing here its just about updating the reference 

Disadvantages.

* Waste of memory due to references

* Nodes in the linked list must be read in order from the beginning as linked list have sequential access

* Difficult to do reverse travel , but we can enable this with back pointer. But this takes a memory

 

Inserting a references

* Inserting to the beginning takes O(1) constant time complexity. Because its just about adding a node

updating its next reference to the start of the linked list

* Inserting to the last node O(n) time complexity because we need to traverse throughout the linked list

to get to the last node, where last node will be pointing to a NULL reference. NULL reference is very much 

important in terms of linked list because that will be the last node of the linked list

Remove

Removing at the beginning is always fast because we don't need to search for item. Its 

only about removing, eg. In java assign to null.

Removing at a given point is O(n) linear time complexity.   

Algorithms and Data Structures on Python - Notes 1

 

         Data Structures Overview  

          Bad programmers worry about code , good programmers worry about data structures and their relationships! 

       Data structures provide efficient ways to store data. A proper data structure can boost an Algorithm. If we need to make a app performs good then we must care about selecting proper data structure.

     There is a tradeoff between running time complexity and memory time complexity. Eg. Dijktras algorithm with priority queue performs better but it will take more memory. If we need to minimize the memory then the application will be slow.

          Abstract data types  -  Data Structures 

Abstract data type is basically the logical implementation. We can use data structures like array or linked list to implement it. So Abstract data types are logical definition  and data structures are concrete implementations. This is the difference between abstract data types and data structures.

Arrays - Basics

         It can be N dimensional according to the needs. Arrays are good because it has O(1) time complexity to get by index. 

  Disadvantages are 

1. It is compile-time : it is no so dynamic data structures.
2. If it is full we need to create a bigger array to copy the contents. That operation is going to take O(N) time complexity
3. It is not able to store items with different type

Arrays - Operations

       Add : We can do it in O(1) constant time complexity because we are going to insert the element at the end of the array. And we certainly we should know the location where we are inserting.

                 If we insert to middle of  of the array, then we have to shift entire array and we ends up O(N) linear time complexity. 

       Remove : If we remove the last item then we will be able to do it on O(1). But to remove an item with a particular index then shifting is involved so we will end up with O(N). 

      Arrays are good data structures? It depends on the application it uses

Examples : pylearn_personal_git