Unlike physical data structures like arrays, lists, stacks, and queues, graphs and trees are abstract representations of data — often used to model networks, relationships, and hierarchical structures

Structure of graph:
A graph is a combination of nodes (which contains data, similar to linked list nodes) and these nodes are connected by edges.
Here’s where it gets interesting — in graphs, edges can be unidirectional, bidirectional, or even weighted, depending on the use case.
Depending on the structure or the type of edges, there are multiple type of graphs.
Some types of graphs:
1. Directed vs Undirected Graph: It depends on whether the edges are directed or not. For example, social media follow relationships (directed) vs. mutual friendships (undirected).
2. Weighted vs Unweighted Graph: It depends on whether the edges are weighted or not
3. Cyclic vs Acyclic Graph: It depends on whether the graph contains at least one cycle (a path where the start and end node are the same).
4. Connected vs Disconnected Graph: There is a path between every pair of vertices (for undirected graphs)
5. Tree : It is most common type of graph

Tree vs Graph:
A tree is a special kind of graph which is connected and does not contain any cycle. (as simple as that).
Additionally, a tree having n nodes will have n-1 edges. Binary Trees, N-ary Trees, and Trie structures are all specialised tree-based graphs.

Representation of graph:

Now, the question is how to represent the above structure in our code?
Do we create a completely new data structure for this? Actually, no!

We represent graphs using 2D array lists, which is termed as adjacency list when representing a graph.

So basically, if there are N number of nodes in a graph connected by M number of edges, for each node we will store a list of nodes, directly connected to that node. Now if the edges are weighted, we will store the pair of weight and the node reachable from that weighted edge.
Below is the function for initialising and representing a graph using adjacency list in Java programming language.

List<Integer> adj[] = new ArrayList[100000]; // global variable for storing graph

// function takes number of nodes as input and the list of edges.
// for this ex, I have considered an bidirection and unweighted graph
public void initialiseGraph(int nodes, int[][] edges) {
  for(int i=1; i<=nodes; i++)
  adj[i] = new ArrayList<>();
  for(int[] e : edges) {
    adj[e[0]].add(e[1]);
    adj[e[1]].add(e[0]);
  }
}

Now, when we understood the representation of the graph, we have to understand how to use this representation to traverse a graph.

Traversals of graph:
There are 2 different algorithms for traversing a graph:

Breadth-First Search
It is a graph traversal algorithm that explores nodes level by level, starting from a given source node. It uses a queue data structure to keep track of the nodes to visit next, ensuring that all immediate neighbours of a node are explored before moving deeper into the graph.
In other words, BFS visits all the nodes at the current level before moving on to nodes at the next level, making it ideal for shortest path problems (in unweighted graphs) and layer-wise exploration.

Data Structure Used: Queue (FIFO)
Time Complexity: O(V + E) where V is vertices and E is edges
Space Complexity: O(V) due to the visited array and queue

public void bfs(int source) {
    Queue<Integer> q = new LinkedList<>();
    q.add(source);
    boolean[] vis = new boolean[100001];
    vis[source] = true;
    while(!q.isEmpty()) {
        int node = q.poll();
        System.out.print(node + " ");
        // for each node, we will add all its unvisited neighbours in the queue
        for(Integer it : adj[node]) {
            if(!vis[it])
                q.add(it);
        }
    }
}

Depth First Search
It is a graph traversal algorithm that explores as far down a branch as possible before backtracking. It uses a stack (either explicitly or via recursion) to remember nodes to return to when it hits a dead end or already visited node.

DFS dives deep into a single path and only when that path is fully explored does it move to the next available branch. This makes it ideal for exploring all possible paths, detecting cycles, and performing topological sorting.

Data Structure Used: Stack (often implemented using recursion)
Time Complexity: O(V + E) where V is vertices and E is edges
Space Complexity: O(V) due to the recursion stack or explicit stack

public void dfs(int source) {
    boolean[] vis = new boolean[100001];
    dfsUtil(source, vis);
}

public void dfsUtil(int node, boolean[] vis) {
    vis[node] = true;
    System.out.print(node + " ");
    for(Integer it : adj[node]) {
        if(!vis[it])
            dfsUtil(it, vis);
    }
}

Some common and important problems for praciticng graph
1. Course schedule
2. Rotten oranges
3. Level order traversal of binary tree
4. Zigzag traversal of binary tree

Do like it and follow me on medium if this blog was helpful. 😊

Requirements and Goals of the System:

Functional Requirements

1. Build and deploy the code
2. Deployment time should be quick and deployment takes place on global servers
3. Rollback to previous version if some bug is found after deployment
4. Store audit of previous builds and deployments

Non Functional requirements:

1. Scalable and highly available: System should be scalable to handle larger deployments and it should be available at all times.
2. Eventual consistency: We will choose eventual consistency over strong consistency bcoz we need our system to be highly available at all times. So it is ok if the code is deployed on some servers of a region a little bit late then some other regions
3. Reliable

Capacity Estimation

1. The system should be extremely fast with a max time of 30 mins for the entire process of build and deployment.
2. Deployment will take place in multiple regions and each region will have lot of machines.
3. Due to large codebases the build files can take upto 10 GB space.

High Level System Design

Whenever, some code is pushed in the master branch, our system should take this latest code and start the build and deployment process for the same.
We will follow a microservice architecture with independent services responsible for building and deploying the code.
So, when the code is pushed in master, the builder service needs to be notified about it and then it should also be provided with the latest commit id from the master branch.

For this, we would be using a queuing mechanism, probably Kafka. Like, we can add the commit id, commit timestamp in the Kafka topic, and our builder service will be reading from this Kafka topic.
For instructions to build the code, we can use a mongoDb which will store documents like below:

We need these instructions bcoz in microservice architecture, different services can be written in different programming languages. The set of commands to get the build file will be different for each of them. Additionally, we also need to store the information about the build in a DB having below structure. It’s structure could be like the below schema.

Since the build file can be huge, we will use some kind of blob storage, probably S3 for storing the build files. Now using this build file, we will create a docker image. Our eventual plan would be that the deployment service will take this docker image and deploy in on the global servers.

Fallback mechanism:
For handling the condition when the builder service crashes while building, we will be monitoring the heart beats of the builder service regularly, and if it goes down, we will keep track of the time stamp at which it went down, so that when it comes up again, it will pick the commits from that time stamp only and start the build process again.

DEPLOYMENT SERVICE:
After the docker image is created, we need to notify our deployment service to deploy the image. Again we will use a queuing mechanism (probably Kafka) and push this docker image id along with the commit id in a seperate Kafka topic. The deployment service will take this docker image from the id in the Kafka topic and proceed with the deployment.
Now there can be 1000s of EC2 instances running at different location, but our build file needs to run on 3–5 instances only. (Its like having multiple pods of a service, but the count is still limited depending on the load).

We need to consider metrics like CPU and memory usage, throughput to decide on which EC2 instances, our service should be deployed.
We could also provide a monitoring service, which will show the health and status of the services deployed using kubernetes dashboard.

Rollback Mechanism:

If rollback is triggered at a certain timestamp, we will pick the commit Id and the docker image on the basis of timestamp, and deploy that docker image on our servers for efficient rollback.

Additionally, if any other process fails during build or deployment, we need to notify the user about the failure.

Thanks for reading the blog. I hope it was somewhat helpful. 😊

Problem statement:

There is a matrix of size m*n. Fire starts at some point (fx, fy). John is standing at point (x1, y1) and wants to reach (x2, y2) which is the escape cell for the matrix. John moves 1 step every second second either horizontally or vertically. Additionally, fire spreads from the initial point with a speed of 1 step per second along the x and y axes of initial starting point. Can you help John to identify whether he can reach the destination safely.

Constraints:
1 <= n,m <= 1000

Sample Input 1:
6 6
2 3 1 1 0 1
Output:
Yes

Sample Input 2:
6 6
2 3 1 1 4 4
Output:
No

Solution:
We need to calculate the time at which the fire will reach any cell. Let’s say that fire[i][j] be such time. Then we need to perform a breadth first search from the starting location of John and check if there is any possible path for him to reach the destination.

C++ solution

#include <bits/stdc++.h> 
using namespace std;

#define pii pair<int, int>
int dir[]={-1, 0, 1, 0, -1};

bool solve() {
    int n, m;
    cin >> n >> m;
    int fx, fy, x1, y1, x2, y2;
    cin >> fx >> fy >> x1 >> y1 >> x2 >> y2;
    queue<pii> q;
    q.push({fx, fy});
    vector<vector<int>> fire(n, vector<int> (m, INT_MAX));
    // to store the time in which fire will reach cell[i][j]
    fire[fx][fy]=0;
    while(!q.empty()) {
        int sz = q.size();
        while(sz--) {
            pii p = q.front();
            q.pop();
            int x=p.first, y=p.second;
            for(int i=0; i<4; i++) {
                int dx=x+dir[i], dy=y+dir[i+1];
                if(dx>=0 && dy>=0 && dx<n && dy<m) {
                    if(fire[dx][dy]==INT_MAX) {
                        fire[dx][dy]=fire[x][y]+1;
                        q.push({dx, dy});
                    }
                }
            }
        }
    }
    q.push({x1, y1});
    if(x1==x2 && y1==y2)
        return true;
    int dur=0;
    while(!q.empty()) {
        int sz = q.size();
        dur++;
        while(sz--) {
            pii p = q.front();
            q.pop();
            int x=p.first, y=p.second;
            for(int i=0; i<4; i++) {
                int dx=x+dir[i], dy=y+dir[i+1];
                if(dx>=0 && dy>=0 && dx<n && dy<m) {
                    if(fire[dx][dy] <= dur)
                        continue;
// if we reach destination cell before fire reaches it then solution exists
                    if(dx==x2 && dy==y2) 
                        return true;
                    q.push({dx, dy});
                }
            }
        }
    }
    return false;
}

int main() {
    if(solve()) {
        cout << "YES\n";
    }
    else {
        cout << "NO\n";
    }
}

A Rate Limiter limits the number of client requests allowed to be sent to the server over a specified period. If the API request count exceeds the threshold defined by the rate limiter, all the excess calls are blocked.

Let’s look at some of the benefits of rate limiter:

1. A rate limiter prevents DoS attacks, intentional or unintentional, by blocking the excess calls.
2. Reduces cost where the system is using a 3rd-party API service and is charged on a per-call-basis.
3. To reduce server load, a rate limiter is used to filter out excess requests caused by bots or users’ misbehaviour.

Design:

Before starting the design, a critical question is that where should the rate limiter be placed — on the client side or the server side ?

Client-side rate limiting can be used in some scenarios, but it has limitations:

1. Easy to Bypass: Malicious actors can tamper with client-side code to bypass the rate limit.
2. Inconsistent Enforcement: If each client implements its own rate limiting, enforcement may not be consistent across all users.

Server Side:

1. Security: Server-side rate limiting ensures enforcement across all clients. A malicious client cannot bypass the limit by simply modifying client-side code.
2. Centralised Control: The server has complete control over the rate limits, allowing for easier configuration and management
3. Scalability: Server-side rate limiting scales better as the system grows, as the rate limiting logic is applied at a central point.

Overall, server-side rate limiting offers a more secure, centralised, and scalable approach for protecting your system from abuse.

There are plenty of algorithms for rate limiting: we will look at some of them including a Token bucket, Leaky bucket, Sliding window counter, etc.

Token Bucket Algorithm

The token bucket algorithm is based on an analogy of a fixed capacity bucket into which tokens, normally representing a unit of bytes or a single packet of predetermined size, are added at a fixed rate.
This algorithm has a centralised bucket host where you take tokens on each request, and slowly drip more tokens into the bucket. If the bucket is empty, reject the request.

public class TokenBucket {

  // Using nanoseconds as the unit for rate
  private final int capacity; // Maximum number of tokens in the bucket
  private final long refillRateNanos; // Rate at which tokens are refilled (nanoseconds)
  private long lastRefillTimeNanos; // Time of the last refill (nanoseconds)
  private int availableTokens; // Current number of tokens in the bucket

  public TokenBucket(int capacity, long refillRate) {
    this.capacity = capacity;
    this.refillRateNanos = refillRate * 1_000_000_000L; // Convert refill rate to nanoseconds
    this.lastRefillTimeNanos = System.nanoTime();
    this.availableTokens = capacity;
  }

  public synchronized boolean tryConsume() {
    refillTokens();
    return availableTokens-- > 0;
  }

  private void refillTokens() {
    long currentTimeNanos = System.nanoTime();
    long elapsedNanos = currentTimeNanos - lastRefillTimeNanos;
    long newTokens = (elapsedNanos / refillRateNanos) * capacity;
    availableTokens = Math.min(capacity, availableTokens + (int) newTokens);
    lastRefillTimeNanos = currentTimeNanos;
  }

  public static void main() {

    TokenBucket bucket = new TokenBucket(10, 1); // 10 requests per second
    
    if (bucket.tryConsume()) {
      // Allow the request
    } else {
      // Reject the request (rate limit exceeded)
    }
  }
}

Above is the pseudo code for token bucket algorithm.

Sliding Window Algorithm

The Sliding Window Algorithm is a time-based method used to track and control the rate at which requests or operations can be made within a specific time window. It’s a dynamic system that adapts to changing traffic patterns, making it an effective tool for rate limiting in various applications.

Visualizing sliding window

Every time we get a request, we make a decision to either serve it or not; hence we check the number_of_requests made in last time_window_sec seconds. So this process of checking for a fixed window of time_window_sec seconds on every request, makes this approach a sliding window where the fixed window of size time_window_sec seconds is moving forward with each request.

public class SlidingWindowRateLimiter {

  private final long windowSizeNanos; // Window size in nanoseconds
  private final int maxRequests; // Maximum allowed requests within the window
  private final Queue<Long> timestamps; // Queue to store request timestamps

  public SlidingWindowRateLimiter(long windowSizeMillis, int maxRequests) {
    this.windowSizeNanos = windowSizeMillis * 1_000_000_000L;
    this.maxRequests = maxRequests;
    this.timestamps = new LinkedList<>();
  }

  public synchronized boolean tryAcquire() {
    cleanupWindow();
    if (timestamps.size() < maxRequests) {
      timestamps.add(System.nanoTime());
      return true;
    } else {
      return false;
    }
  }

  private void cleanupWindow() {
    long currentTimeNanos = System.nanoTime();
    while (!timestamps.isEmpty() && currentTimeNanos - timestamps.peek() > windowSizeNanos) {
      timestamps.poll();
    }
  }

  public static void main() {
    SlidingWindowRateLimiter limiter = new SlidingWindowRateLimiter(1000, 5); // 1 second window, 5 requests allowed
    if (limiter.tryAcquire()) {
      // Process request
    } else {
      // Reject request (rate limit exceeded)
    }
  }
}

Above is the pseudo code for sliding window algorithm.

Now, let’s look at the high level design of a system with rate limiter in place.

Every time the client make a request to the server, the request goes through the rate limiter, which is linked to a rule engine. This component focuses on defining and evaluating the rules for applying rate limiting. Ex. if a lot of requests are coming from a same IP, then that IP can be blocked. Also, for some websites there is a spike in traffic during certain times of the year, and hence the rate limit for those times has to be increased, which is made configurable through the rule engine.
Using the response of the rule engine and the rate limiter, it is decided whether the request will be denied or it will be a success.
Below is the HLD for a system using rate limiter

Some of the real life applications of rate limiter:

1. In a banking system you may request OTP (One Time Password) once every 5 minutes.
2. In a social media platform, a user maybe allowed to post maximum 5 posts per minute
3. You can register a new user from same IP maximum 5 times per day. This is case where we want to prevent bot/sock-puppet accounts

You are given a undirected and weighted graph of n nodes numbered from 0 to n-1. The graph consists of m edges represented by a 2D array edges, where edges[i] = [u, v, w] indicates that there is an edge between nodes u and v with weight w.
Consider all the shortest paths from node 0 to node n-1 in the graph. You need to find a boolean array answer where answer[i] is true if the edge edges[i] is part of at least one shortest path. Otherwise, answer[i] is false.

Return the array answer.

Consider the above graph as example:

Input:
n = 6, edges = [[0,1,4],[0,2,1],[1,3,2],[1,4,3],[1,5,1],[2,3,1],[3,5,3],[4,5,2]]

Output:
[true, true, true, false, true, true, true, false]

Explanation:
There are 3 shortest paths from node 0 to n-1 in the above graph.

Path 0 -> 1 -> 5 : The sum of weights is 4 + 1 = 5
Path 0 -> 2 -> 3 -> 5 : The sum of weights is 1 + 1 + 3 = 5
Path 0 -> 2 -> 3 -> 1 -> 5 : The sum of weights is 1 + 1 + 2 + 1 = 5

Solution:

One of the solutions can be to find all the shortest paths from 0 to n-1 and then take the union of all the edges lying in any of the shortest paths.
However, in a graph of n nodes, the time complexity of this solution will be more than n*O(nlogn) [nlogn for each shortest path if we use Dijkstra, and there can be a lot of shortest paths] , which a not a feasible solution if n ≤ 100000.

So, in order to optimise this, we need to first figure out the key condition using which we can definitely say if an edge will be a part of any shortest path or not.
Let’s say we have an array disFromSource[i] = shortest distance from source node to any other node and another array disFromDest[i] = shortest distance from destination to any other node. So, for any edge (u, v, w), it will the part of any shortest path if :
disFromSource[u]+disFromDest[v]+w = disFromSource[n-1]

To calculate the two required arrays, we need to run Dijkstra algorithm twice, once considering node 0 as source and then considering node n-1 as source.

Java code snippet

static ArrayList<int[]> adj[];

static long[] Dijkstra(int src, int n){
    long dis[] = new long[n];
    PriorityQueue<long[]> pq = new PriorityQueue<>(new Comparator<>() {
        public int compare(long a[], long b[]) {
            return a[1]>b[1] ? 1 : -1;
        }
    });
    Arrays.fill(dis, Integer.MAX_VALUE);

    dis[src] = 0;
    pq.add(new long[]{src, 0});

    while(pq.size()!=0){
        long curr[] = pq.remove();
        int u = (int)curr[0];
        if(curr[1] > dis[u])
            continue;
        for(int[] x : adj[u]){
            if(dis[x[0]] > dis[u] + x[1]){
                dis[x[0]] = dis[u]+x[1];
                pq.add(new long[]{x[0], dis[x[0]]});
            }
        }
    }
    return dis;
}

public boolean[] findAnswer(int n, int[][] edges) {
    adj = new ArrayList[n];
    int m = edges.length;

    for(int i=0; i<n; i++)
        adj[i] = new ArrayList<>();
    for(int[] e : edges) {
        adj[e[0]].add(new int[]{e[1], e[2]});
        adj[e[1]].add(new int[]{e[0], e[2]});
    }

    long disFromSource[] = Dijkstra(0, n);
    long disFromDest[] = Dijkstra(n-1, n);

    boolean[] ans = new boolean[m];
    long min = disFromSource[n-1];
    for(int i=0; i<m; i++) {
        int u=edges[i][0], v=edges[i][1], w=edges[i][2];
        
        if((long)w + disFromSource[u]+disFromDest[v] == min || (long)w+disFromDest[u]+disFromSource[v]==min)
            ans[i] = true;
        else
            ans[i] = false;
    }
    return ans;
}

Practice link for the problem:
https://leetcode.com/problems/find-edges-in-shortest-paths/

Thanks for reading !!
Please share feedback if you have any.

Composite Pattern consists of following objects.

1. Base Component — Base component is the interface for all objects in the composition. It can be an interface or an abstract class with some methods common to all the objects.
2. Leaf — Defines the behaviour for the elements in the composition. It is the building block for the composition and implements base component. It doesn’t have references to other Components.
3. Composite — It consists of leaf elements and implements the operations in base component.

The most common application for this design pattern is a file system. In a file system, a folder can have a list of files + subfolders inside it.

Base component (Interface)

public interface FileSystem {
    public void ls();
}

File class (leaf component in the design pattern)

public class File implements FileSystem {
    String fileName;

    public File(String name) {
        this.fileName = name;
    }

    @Override
    public void ls() {
        System.out.println("file name " + fileName);
    }
}

Directory (composite Object)

public class Directory implements FileSystem {

    String directoryName;
    List<FileSystem> fileSystemList;

    public Directory(String name) {
        this.directoryName = name;
        fileSystemList = new ArrayList<>();
    }

    public void add(FileSystem fileSystemObj) {
        fileSystemList.add(fileSystemObj);
    }

    @Override
    public void ls() {
        System.out.println("Executing ls for directory name " + directoryName);
        for(FileSystem fileSystemObj : fileSystemList) {
            fileSystemObj.ls();
        }
    }
}

Thanks for reading!!