DEV Community: Karhik Suryadevara

Graph Coloring Problem: Cracking Complexity with Elegant Solutions

Karhik Suryadevara — Mon, 22 Apr 2024 16:38:14 +0000

what is the graph coloring problem?

In the graph coloring problem, we are tasked with assigning colors to each node in a graph in such a way that no two adjacent nodes share the same color. This concept is akin to coloring a map where neighbouring regions should have different colors. By solving this problem, we can unlock powerful solutions for a variety of graph-related challenges

Consider the following illustration of a graph:

In this example, each circle represents a node, and the lines connecting them represent edges. Now, let's explore different ways to color this graph:

Based on the two possibilities of coloring a graph, it's evident that we require a minimum of two colors to ensure that no two adjacent nodes share the same color, thus satisfying the constraint.

Through the process of graph coloring, we'll explore how this seemingly simple task can provide an easy solution to a complex problem.

Problem

Note: The problem was taken from codesignal a platform like leetcode

You are the head zookeeper at a large zoo. You've been contacted by schools in the area that want to bring in classes so that students can feed the animals. The animals can only be fed once a day, so no two classes can come on the same day if they want to feed the same animals.

You have a list classes, such that classes[i] is a list of animals that the ith class wants to feed. Classes i and j cannot come on the same day if an animal in classes[i] also appears in classes[j] (for i ≠ j). Your job is to determine the minimum number of days you would need to have all the classes come to feed the animals if they can all come within 5 days. If it isn't possible for all the classes to come within 5 days, return -1 instead.

Examples

For classes = [["Tiger", "Lima", "Frog"], ["Tiger", "Zebra","Lion"], ["Tiger", "Rabbit"], ["Emu", "Zebra", "Rabbit"]], the output should be

solution(classes) = 3.

Classes 0, 1, and 2 all want to feed the Tiger, so they have to come on different days. Class 3 cannot come on the same day as class 1 (because of the Zebra) or class 2 (because of the Rabbit), but they can come on the same day as class 0. Therefore it only takes 3 days for all the classes to visit the zoo.
For classes = [["Tiger", "Lima", "Frog"], ["Tiger", "Zebra", "Lion"], ["Tiger", "Rabbit"], ["Lima", "Zebra", "Rabbit"]], the output should be

solution(classes) = 4.

Each class has to come on a separate day, because every pair of classes has at least one animal in common.
For classes = [["Lion", "Emu"], ["Giraffe", "Peacock"], ["Lima"], ["Tiger", "Cheetah", "Slugs"], ["Snakes", "Sealion"]], the output should be

solution(classes) = 1.

No classes have animals in common, so they can all come on the same day.

Now to solve the problem, my initial thought was to

try a recursive backtracking approach, In this method, the recursive function takes two arguments: currentClassIdx, which represents the index of the class currently being processed, and days, an array of sets where each set represents the animals to feed on the ith day. During each recursive call, we have a few options to consider: we can either dedicate an entire new day to this class by appending a new set to days array with the animals to feed, or we can try to merge it with existing days if there are no common animals. We'll choose the option that leads to the minimum number of days. The base case is reached when we've processed all the classes, indicated by currentClassIdx being out of bounds, at which point we return the length of the days array. This approach is pretty straightforward and easy to understand. Let's take a closer look!

Brute force Solution



def solution(classes):
    classes = [set(x) for x in classes]

    def minimumDaysToCoverAllClasses(currentClassIdx, days):
        if len(days) > 5:
            return float('inf')
        if currentClassIdx >= len(classes):
            return len(days)
        res = float('inf')
        currentClassAnimals = classes[currentClassIdx]
        # new day for this class
        days.append(currentClassAnimals)
        res = min(res, minimumDaysToCoverAllClasses(currentClassIdx+1, days))
        days.pop()
        # try merging this class into existing days
        for i, animals in enumerate(days):
            # no common animals
            if animals.isdisjoint(currentClassAnimals):
                days[i] = animals.union(currentClassAnimals)
                res = min(res, minimumDaysToCoverAllClasses(currentClassIdx+1, days))
                # backtrack
                days[i] = animals
        return res

    days = []
    currentClassIdx = 0

    daysRequired = minimumDaysToCoverAllClasses(currentClassIdx, days)
    if daysRequired == float('inf'):
        return -1
    return daysRequired

The time complexity of the above solution is a bit tricky to calculate and get it exact but it would definitely be something greater than exponential O(n!) , so can we do better?

This is where the graph coloring can be used , it’s hard to see the connection at first I was not able to find the solution and after some time and went through the solutions to find the graph coloring approach solution , once I learnt about it I was amazed that such a complex problem can be solved easily with graph coloring algorithm so decided to share it here, now let us have a look at the graph coloring algorithm

Graph coloring Solution

We will represent each class as a node and if there is common animal to feed between 2 classes then there is a edge between those 2 nodes

Example:

For classes = [["Tiger", "Lima", "Frog"], ["Tiger", "Zebra","Lion"], ["Tiger", "Rabbit"], ["Emu", "Zebra", "Rabbit"]]

Classes 0, 1, and 2 all want to feed the Tiger, so there is an edge between these 3 classes or nodes.

Class 3 has an edge to class 1 (because of the Zebra) and class 2 (because of the Rabbit).

For the above graph we need at least 3 colors to color the graph to satisfy the constraint of no 2 adjacent nodes have the same color, one possible way to color the graph is shown below

It does not matter what colors we choose we just need to find the minimum colors needed to color the graph while ensuring that no 2 adjacent nodes have the same color or in other words minimum days required (each day represents a color) to cover all the classes satisfying the constraint of no 2 classes can come on the same day if they have a common animal to feed.

we will start solving the problem by converting the given information to a graph and once we have a graph representing the above information, we can start coloring the graph to see how many minimum days required to cover all the classes.

As the problem states if the minimum days is less than 5 we return it else -1 , we will add a condition to achieve this but the idea remains the same we are trying to find minimum colors required to color the graph such that no 2 adjacent nodes have the same color or the minimum days required to cover all the classes such that no 2 classes come on same day, here each day represents a color. I hope you are able to see the connection I am trying to explain, now let's have a look at the code



def solution(classes):
    g = [[] for _ in range(len(classes))]
    for u, c1 in enumerate(classes):
        for v, c2 in enumerate(classes):
                # check if 2 classes have a common animal and add the edge
            if u != v and set(c1) & set(c2): g[u].append(v)
    return solve(g, 0, [0 for _ in range(len(g))])

# color node u in each recursive call
# once all the nodes are colored count the colors it took to color all the nodes
def solve(g, u, colors):
    if u == len(g): return max(colors)
    # check the adjacent neibhours colors, we can't use those colors
    used = set(colors[v] for v in g[u])
    # choose a color for this node out of available colors
    for color in [c for c in range(1, 6) if c not in used]:
        colors[u] = color
        colorsRequired = solve(g, u + 1, colors)
        if 0 <= colorsRequired < 6: return colorsRequired
    return -1

The time complexity of the above solution is O(5^c) where c is number of classes as you can see this solution is much more efficient.

Conclusion

The key insight lies in recognizing how to represent the problem information as a graph. Once we have this representation, coloring the graph using techniques like recursion and backtracking becomes straightforward. This approach allows us to determine either the minimum days required or the minimum number of colors needed to satisfy the problem constraints.

Understanding how to translate real-world scenarios into algorithmic representations is crucial. Once we grasp this conceptual framework, solving similar problems becomes more manageable and intuitive.

Unifying React Development: Patterns You Should Know

Karhik Suryadevara — Fri, 22 Sep 2023 14:34:25 +0000

Introduction

React is one of today's most popular JavaScript frameworks, and for good reason. It offers both flexibility and ease of use. By "flexibility," I mean that React provides multiple ways to accomplish the same task. For instance, you can fetch data from a server using either the useEffect hook or a custom hook or an async Thunk using redux.

While this flexibility makes React appealing, it can also lead to challenges. Imagine a scenario where multiple developers work on the same project, each choosing a different approach to data fetching. Such inconsistencies can create problems in a React application, leading to a fragmented codebase that is difficult to maintain.

In this blog, we will explore how to address these challenges by adopting some well-known, community-approved patterns. These patterns offer tested and reliable ways to achieve specific functionalities in React. So, let's dive in!

Layout Components

layout components are the components that deal with arranging other components in the page. we achieve this by splitting the layout styles into their own component and pass the components we want to display as children to layout component. This helps by separating the component itself from where it's being displayed which makes the component more reusable.

Example: Modal layout component

This component is designed to display content prominently against a blurred background. By encapsulating this behavior within the Modal component, we make it effortlessly reusable across the entire application.

// Modal.jsx
import styled from "styled-components";

const ModalBackground = styled.div`
  position: fixed;
  z-index: 1;
  left: 0;
  top: 0;
  width: 100%;
  height: 100%;
  overflow: auto;
  background-color: rgba(0, 0, 0, 0.5);
`;

const ModalBody = styled.div`
  background-color: white;
  margin: 10% auto;
  padding: 20px;
  width: 50%;
`;

const Modal = ({ children, isOpen }) => {
  return (
    <>
      {isOpen && (
        <ModalBackground>
          <ModalBody>{children}</ModalBody>
        </ModalBackground>
      )}
    </>
  );
};

export default Modal;

// usage in App.jsx
function App() {
  const [showTermsAndConditions, setShowTermsAndConditions] = useState();
  return (
    <>
      <button onClick={() => setShowTermsAndConditions(true)}>Terms and Conditions</button>
      <Modal isOpen={showTermsAndConditions}>
        <div>
          <h1>Terms and Conditions</h1>
          <p>
            Lorem ipsum dolor sit amet consectetur adipisicing elit. Soluta molestias maxime nesciunt neque laboriosam,
            harum expedita quidem dignissimos, aliquid impedit illo voluptatum? Possimus voluptatem quia modi molestias
            deleniti, voluptas facere?
          </p>
          <button onClick={() => setShowTermsAndConditions(false)}>Close</button>
        </div>
      </Modal>
    </>
  );
}

HOC

Higher-Order Components (HOCs) serve as a powerful and flexible pattern in React for augmenting the behavior of existing components. They are particularly invaluable in legacy codebases, offering a seamless way to extend component functionality without introducing breaking changes. By wrapping the original component within a HOC, you can inject new props, manipulate state, or even alter the rendering behavior, all while keeping the original component intact.

Example: List Component

Imagine you have a List component that displays a collection of items. Now, let's say you want to enhance this component to show a loading text or an animation while the data is being fetched from an API. This is where the Higher-Order Component (HOC) pattern shines. By wrapping your existing List component with a HOC, you can seamlessly introduce this new loading feature without altering the core functionality of the List component itself.

// List.jsx
const List = ({ items }) => {
  return (
    <ul>
      {items.map((item, index) => (
        <p key={index}>{item}</p>
      ))}
    </ul>
  );
};

export default List;

// listWithLoading.js
const withLoading = (ListComponent) => {
  return ({ isLoading, ...listProps }) => {
    console.log(listProps, isLoading);
    if (isLoading) {
      return <h2>Loading...</h2>;
    }
    return <ListComponent {...listProps} />;
  };
};

export default withLoading;

// usage 
const initialItems = ["gone girl", "fight club", "batman"];
const Index = () => {
  const [items, setItems] = useState([]);

  useEffect(() => {
    // mimic api call
    setTimeout(() => {
      setItems([...initialItems]);
    }, 2000);
  }, []);

  return (
    <>
      <div>
        <h1>List without loading feature</h1>
        <List items={items} />
      </div>
      <div>
        <h1>List with loading feature</h1>
        <ListWithLoading isLoading={items.length === 0} items={items} />
      </div>
    </>
  );
};

export default Index;

Compound Components

Compound components are used in scenarios where you have a complex UI component that needs to share implicit state or behavior among its children, but you also want to allow for customization and flexibility in how those children are rendered. Compound components simplify the management of complex state and allows us to write readable and maintainable code.

Example: Tabs Component

This Tabs component will serve as a container for multiple Tabs, each responsible for rendering individual tab and their corresponding content. By leveraging the compound components pattern, we can centralize the management of the active tab state while offering the flexibility to customize the appearance and behavior of each tab.

// Tabs.jsx
import React, { useState } from "react";

function Tabs({ children }) {
  const [activeTabIndex, setActiveTabIndex] = useState(0);
  return (
    <div style={{ display: "flex", width: "max-content" }}>
      {React.Children.map(children, (child, index) => {
        return React.cloneElement(child, { index, activeTabIndex, setActiveTabIndex });
      })}
    </div>
  );
}

function Tab({ index, children, activeTabIndex, setActiveTabIndex }) {
  return (
    <div style={{ display: "flex", flexDirection: "column" }}>
      {React.Children.map(children, (child) => {
        return React.cloneElement(child, { index, activeTabIndex, setActiveTabIndex });
      })}
    </div>
  );
}

function TabHeader({ children, index, activeTabIndex, setActiveTabIndex }) {
  return (
    <button onClick={() => setActiveTabIndex(index)} style={{ fontSize: index === activeTabIndex ? "bold" : "" }}>
      {children}
    </button>
  );
}

function TabContent({ children, index, activeTabIndex }) {
  return <>{index === activeTabIndex ? children : null}</>;
}

export { Tabs, Tab, TabHeader, TabContent };

// usage 
function App() {
  return (
    <Tabs>
      <Tab>
        <TabHeader>Tab 1</TabHeader>
        <TabContent>Content 1</TabContent>
      </Tab>
      <Tab>
        <TabHeader>Tab 2</TabHeader>
        <TabContent>Content 2</TabContent>
      </Tab>
    </Tabs>
  );
}

Custom hooks

Custom hooks serve as a powerful tool for encapsulating complex state management and behavior within a React component. Once developed, these hooks can be effortlessly reused across multiple components that share the same requirements. By isolating this intricate logic into a custom hook, you not only enhance code reusability but also significantly simplify the state and behavior management in each individual component.

Example: useUser hook

This hook is designed to fetch the currently logged-in user's information while also managing two crucial states: isLoading and isSessionExpired. The isLoading state provides a way to display a loading indicator during the data-fetching process, and the isSessionExpired state helps in handling session expiration scenarios. By encapsulating these functionalities within a custom hook, we can easily reuse this logic across multiple components, thereby adhering to the principles of clean, maintainable, and DRY (Don't Repeat Yourself) code.

// useUser.js
import { useState, useEffect } from "react";

// fetch logged in user
export default function useUser() {
  const [user, setUser] = useState(null);
  const [isLoading, setIsLoading] = useState(true);
  const [isSessionExpired, setSessionExpired] = useState(null);

  useEffect(() => {
    async function fetchData() {
      try {
        // mimic api call and response
        const token = localStorage.getItem("access_token");
        const response = await fetch("https://my_app/api", {
          headers: {
            Authorization: `Bearer ${token}`,
          },
        });

        if (response.ok) {
          const data = await response.json();
          setUser(data);
          setIsLoading(false);
          setSessionExpired(false);
        } else if (response.status === 401) {
          setSessionExpired(true);
          setIsLoading(false);
        } else {
          throw new Error("Something went wrong");
        }
      } catch (error) {
        console.error("Error:", error);
        setIsLoading(false);
      }
    }

    fetchData();
  }, []);

  return {
    user,
    isLoading,
    isSessionExpired,
  };
}

// usage
function App() {
  const { user, isLoading, isSessionExpired } = useUser();
  if (isLoading) {
    return <h1>Loading... your profile</h1>;
  }
  if (!isLoading && !isSessionExpired) {
    return <h1>Something went wrrong on our side, please try again after some time</h1>;
  }
  if (!isLoading && isSessionExpired) {
    return <h1>Session expired please login</h1>;
  }
  return (
    <div>
      <h1>My profile</h1>
      <h3>{user?.name}</h3>
    </div>
  );
}

code: https://github.com/karthik2265/react-patterns

Conclusion

n this blog post, we've explored some of the most effective design patterns in React - Layout Components, Higher-Order Components (HOCs), Compound Components, and Custom Hooks. These patterns not only help in writing clean and maintainable code but also solve specific challenges in React development, such as managing complex state and enhancing component reusability.
While these are some of my personal favorites, the landscape of design patterns in React is vast and continuously evolving. Each project may have unique requirements that could be better served by other patterns or a combination thereof. Therefore, I encourage you to not stop here. Dive deeper into the React ecosystem, experiment with these patterns, and discover which ones fit best for your specific coding challenges.
Remember, the key to becoming a proficient React developer lies in continuous learning and adaptation. So, keep exploring, keep coding, and most importantly, keep sharing your knowledge with the community.
This conclusion wraps up the blog by summarizing the key points, encouraging further exploration, and inspiring continuous learning. It also provides a sense of closure to the reader.
Thank you for reading until the end. Please consider following the writer and this publication. Visit Stackademic to find out more about how we are democratizing free programming education around the world.

How to setup eslint and prettier in an existing node and typescript project.

Karhik Suryadevara — Thu, 06 Oct 2022 07:23:20 +0000

What and Why

Different Developers have different style and way of writing code .

Example
In typescript/javascript we have 2 ways for accessing a property in an object, so some developer may prefer dot notation and some may prefer bracket notation.



let x = {a: 1}
console.log(x.a)
console.log(x['a'])

Similarly some developers prefer single quotes for strings while others might prefer double quotes. This can be bad because when you look at code written by 2 different developers in the same project, it looks odd and not so good.

So to solve these kind of problems and maintain a standard style, formatting and to catch problematic patterns of code, we use a tool called Eslint.

This tool can be used to impose some rules like strings should be only double quotes, dot-notation must be used instead of bracket notation for accessing a property in an object and formatting rules.

Prettier

Prettier is a very good tool used for formatting, Most developers prefer prettier because the built in formatting provided by Eslint is not very good.

So, now that we know why these tools are used, let's see how to add Eslint and prettier to an existing node typescript project

Run the following command in the terminal at the root of your project



npm init @eslint/config

Eslint will ask you few questions, such as

we want to use ESLint to find problems, syntax and style so choose the 3rd option and click enter.

Choose this option according to the type of modules you are using in your project.

Choose None, since we have a node with typescript project.

Choose yes

choose only node.

We could answer few questions and setup a custom style, but we are better off using a standard and popular style guide. so choose Use a popular style guide and click enter

Checkout the github repos of these style guides and choose one you like. I prefer standard-with-typescript

Choose based on your preference. I prefer json

It will ask you to install some packages, click yes

Choose the package manager used in your project

When the packages are downloaded we get a .eslintrc config file like this

.eslintrc



{
    "env": {
        "commonjs": true,
        "es2021": true,
        "node": true
    },
    "extends": "standard-with-typescript",
    "overrides": [
    ],
    "parserOptions": {
        "ecmaVersion": "latest"
    },
    "rules": {
    }
}

To ignore the files and folders we dont want to lint create a .eslintignore file at the root level (package.json level) of your project and specify the files and folders which needs to be ignored by ESLint

.eslintignore



node_modules
tests

Now let's add prettier (code formatting tool).

we need to install 3 more packages for this step



npm install --save-dev eslint-config-prettier eslint-plugin-prettier prettier

We need to edit the .eslintrc config file to tell ESLint that we are going to use prettier for formatting and the config file at the end should look like this



{
  "env": {
    "commonjs": true,
    "es2021": true,
    "node": true
  },
  "parser": "@typescript-eslint/parser",
  "extends": ["standard-with-typescript", "prettier"],
  "plugins": ["prettier"],
  "overrides": [],
  "parserOptions": {
    "ecmaVersion": "latest",
    "project": "./tsconfig.json"
  },
  "rules": {
    "prettier/prettier": ["error"]
  }
}

note: make sure you specify the path to .tsconfig file correctly in the parserOptions.

The final step is to add the following scripts in the package.json file



"lint": "eslint . --config .eslintrc.json",
"lint:fix": "eslint . --fix --config .eslintrc.json"

run the lint command to see the errors and lint:fix to fix the automatically fixable errors. Some errors might not be fixable automatically with the lint:fix command and you have to fix these manually.

Doing this will ensure that the code is more readable, organized and avoiding problematic code patterns.

Thanks for reading 😀

DFS and BFS of a graph

Karhik Suryadevara — Wed, 09 Mar 2022 15:17:47 +0000

What is DFS(depth first search)?

It's an algorithm to traverse a graph in a depth first manner, i.e. going deep into one branch before backtracking and continuing the process until all vertices are visited.

Example

Pick vertex 0 traverse 1, 2 and then backtrack to 1 and traverse 2, 3, 4 and then backtrack to traverse 4. So the final result would be [0, 1, 2, 3, 4]
Note: [0, 4, 3, 2, 1] is also correct.

To implement the algorithm, we need a set to keep track of visited nodes and an array to store the result

Algorithm
1) pick any vertex
2) if the vertex is not in the set, go to step 3
3) add the vertex to the set and the result array, and repeat the process for each vertex of the current vertex.

Code

def depth_first_search(graph, currVertex, seen, result):
  if currVertex in seen: return
  seen.add(currVertex)
  result.append(currVertex)
  for vertex in graph[currVertex]:
    depth_first_search(graph, vertex, seen, result)


# main function 
def dfs(v, graph):
  result = []
  seen = set()
  depth_first_search(graph, 0, seen, result)
  return result

What is BFS(breadth first search)?

It's an algorithm to traverse a graph in breadth first manner, i.e. traversing all the vertices of a vertex and then moving to another vertex and repeat the process until all the vertices are visited.

Example

Pick vertex 0 traverse its vertices 1, 4 and then take vertex 1 and traverse its vertices 2, 3, 4. So the final result would be [0, 1, 4, 2, 3]
Note: [0, 4, 1, 3, 2] is also correct.

we need a queue, set and an array to implement the algorithm
Algorithm
1) pick a vertex
2) add the vertex to the queue
3) while queue is not empty, pop the queue and traverse the vertices of popped vertex and do step 2 for each vertex of the vertices, if the vertex is not in the set

Code

from collections import deque

def bfs(graph, seen, q, vertex, res):
    q.append(vertex)
    seen.add(vertex)
    res.append(vertex)
    while q:
        currVertex = q.popleft()
        for v in graph[currVertex]:
            if v not in seen:
                seen.add(v)
                res.append(v)
                q.append(v)

# main function
def bfsOfGraph(v, adj):
    q = deque()
    res = []
    seen = set()
    bfs(adj, seen, q, 0, res)
    return res

Uses of BFS and DFS
1) Using DFS we can find the path between vertex u, v and also check if the graph is strongly connected.
2) BFS can be used to find neighbors of a vertex

Problems on BFS and DFS
1) Implement DFS: geeks-for-geeks-link
2) Implement BFS: geeks-for-geeks-link

Topological Sorting in a directed acyclic graph(DAG)

Karhik Suryadevara — Thu, 10 Feb 2022 16:52:44 +0000

What is Topological Sort ?

It is an ordering of vertices in DAG, such that for every edge u to v, u comes before v.

Important point to note
1) It is not possible to do a topological sort if the graph has a cycle, since in a cycle it is impossible to know the order of vertices
2) There can be many possible orders of topological sorting

Example

Possible Topological Orders:

[1, 2, 3, 4, 5, 6, 7, 8]
[3, 2, 1, 4, 5, 6, 7, 8]
[1, 2, 3, 4, 7, 6, 5, 8]

Uses of topological sorting

1) Managing tasks which are dependent on other tasks, suppose task B can only be completed if task A has been completed. So the graph would be:
A --> B
and the topological order would be [A, B].
2) Managing courses and prerequisite courses, for example we have an Algebra(Al) course which has a prerequisite of Basic-Math(BM) course, the graph would be:
BM --> Al
and the topological order would be [BM, Al] meaning a student should complete BM course before taking Al course.

Algorithm

We need a hash set to store the vertices we have visited and a stack to store the order.

1) Pick a vertex(v) let's name it current-vertex from the graph and

2) If the current-vertex is not in hash set

add the current vertex to hash set
get all the children of current-vertex and recursively call the step 2 for each child vertex
add the current-vertex to stack

3) reverse the stack, and we get the topological order

Code

    def topological_sort(self, graph, seen, stk, current_vertex):
        # 2) if current_vertex not in hash set
        if current_vertex not in seen:
            seen.add(current_vertex)
            current_vertex_children = graph[current_vertex]
            for child in current_vertex_children:
                self.topological_sort(graph, seen, stk, child)
            stk.append(current_vertex)


    # *** Main function ***
    def topoSort(self, v, graph):
        # v = no of vertices in the graph
        # graph is represented using an adjacency list
        stk = []
        seen = set()
        # 1) pick a vertex
        for vertex in range(v):
            self.topological_sort(graph, seen, stk, vertex)
        # 3) reverse the stk
        stk.reverse()
        return stk

Problems which can be solved using topological sort

Implementing topological sort for a DAG: geeks-for-geeks-problem-link

Order of courses in topological order: leetcode-problem-link

Check if all the courses can be completed: leetcode-problem-link

Binary Search Tree implementation in java

Karhik Suryadevara — Mon, 10 May 2021 16:24:04 +0000

Binary search tree(bst) key points

1) binary search tree is a nonlinear data structure
2) In a bst each node has at most 2 children
3) it takes logarithmic time (O(long)) to find an element or insert an element in a bst, for comparison, it takes O(n) i.e linear time to find an element in an array.
4) no duplicates are allowed in bst

code to implement bst in java

import java.util.ArrayList;
import java.util.List;

public class BinarySearchTree {
    public TreeNode root;

    BinarySearchTree(int rootValue) {
        root = new TreeNode(rootValue);
    }

    BinarySearchTree() {
        root = null;
    }

    public boolean insert(int value) {
        if (root == null) {
            root = new TreeNode(value);
            return true;
        } else {
            return insert(value, root);
        }
    }

//    ********************************* Breadth first search ***************************************

    public List<Integer> BreadthFirstSearch() {
        return BreadthFirstSearch(root);
    }

    public List<Integer> BreadthFirstSearch(TreeNode root) {
        ArrayList<Integer> bfs_list = new ArrayList<Integer>();
        ArrayList<TreeNode> q = new ArrayList<TreeNode>();
        q.add(root);
        while (q.size() > 0) {
            TreeNode currNode = q.remove(q.size() - 1);
            bfs_list.add(currNode.value);
            if (currNode.left != null) {
                q.add(0, currNode.left);
            }
            if (currNode.right != null) {
                q.add(0, currNode.right);
            }
        }
        return bfs_list;
    }
    //    ******************************************************************************************

    //  ******************** Depth first search inorder,preorder,postorder **********************

    public List<Integer> depthFirstSearch_InOrder() {
        ArrayList<Integer> dps_lst = new ArrayList<Integer>();
        return traverseInOrder(root, dps_lst);
    }

    public List<Integer> traverseInOrder(TreeNode root, List<Integer> dps_lst) {
        if (root.left != null) traverseInOrder(root.left, dps_lst);
        dps_lst.add(root.value);
        if (root.right != null) traverseInOrder(root.right, dps_lst);
        return dps_lst;
    }

    public List<Integer> depthFirstSearch_PreOrder() {
        ArrayList<Integer> dps_lst = new ArrayList<Integer>();
        return traversePreOrder(root, dps_lst);
    }

    public List<Integer> traversePreOrder(TreeNode root, List<Integer> dps_lst) {
        dps_lst.add(root.value);
        if (root.left != null) traversePreOrder(root.left, dps_lst);
        if (root.right != null) traversePreOrder(root.right, dps_lst);
        return dps_lst;
    }

    public List<Integer> depthFirstSearch_PostOrder() {
        ArrayList<Integer> dps_lst = new ArrayList<Integer>();
        return traversePostOrder(root, dps_lst);
    }

    public List<Integer> traversePostOrder(TreeNode root, List<Integer> dps_lst) {
        if (root.left != null) traversePostOrder(root.left, dps_lst);
        if (root.right != null) traversePostOrder(root.right, dps_lst);
        dps_lst.add(root.value);
        return dps_lst;
    }

    //    ******************************************************************************************

    //    *************************** insert a node **********************************

    public boolean insert(int value, TreeNode root) {
        if (root.value == value) return false;
        if (value < root.value) {
            if (root.left != null) return insert(value, root.left);
            else {
                root.left = new TreeNode(value);
                return true;
            }
        } else {
            if (root.right != null) return insert(value, root.right);
            else {
                root.right = new TreeNode(value);
                return true;
            }
        }
    }

    //    ******************************************************************************************



    //    ******************* delete a node from tree **********************

    public List<TreeNode> findNodeAlsoItsParent(int value) {
        TreeNode parent = null;
        return findNodeAndItsParent(parent, root, value);
    }

    public List<TreeNode> findNodeAndItsParent(TreeNode parent, TreeNode root, int value) {
        ArrayList<TreeNode> lst = new ArrayList<TreeNode>();
        if (value == root.value) {
            lst.add(parent);
            lst.add(root);
            return lst;
        }
        if (value < root.value) {
            if (root.left != null) {
                return findNodeAndItsParent(root, root.left, value);
            } else {
                return null;
            }
        } else {
            if (root.right != null) {
                return findNodeAndItsParent(root, root.right, value);
            } else {
                return null;
            }
        }
    }

    public void delete(int value) {
        List<TreeNode> lst = findNodeAlsoItsParent(value);
        TreeNode nodeToBeDeleted = lst.get(1);
        TreeNode parentNode = lst.get(0);
        List<Integer> nodes = new ArrayList<Integer>();
        List<Integer> effectedNodes = traversePreOrder(nodeToBeDeleted, nodes);
        effectedNodes.remove(effectedNodes.indexOf(value));

        if (parentNode == null) {
//            if the node to be deleted is root
            root = null;
        } else {
            if (parentNode.left.value == value) parentNode.left = null;
            else parentNode.right = null;
        }
//        rearrange the binary tree from the effected nodes array
        for (int i : effectedNodes) {
            this.insert(i);
        }
    }
    //    ******************************************************************************************


    //  ***************************** TreeNode ****************************************
    public static class TreeNode {
        public int value;
        public TreeNode left;
        public TreeNode right;

        TreeNode(int value) {
            this.value = value;
            this.left = this.right = null;
        }
    }
//    *********************************************************************************************
}

driver code

BinarySearchTree myBST = new BinarySearchTree();
        myBST.insert(100);
        myBST.insert(21);
        myBST.insert(111);
        myBST.insert(20);
        myBST.insert(50);
        myBST.insert(101);
        myBST.insert(112);

//                 100
//             /        \
//            21        111
//           / \        /  \
//         20   50     101  112

        System.out.println("Breadth First Search " + myBST.BreadthFirstSearch());
        System.out.println("Depth First Search In Order " + myBST.depthFirstSearch_InOrder().toString());
        System.out.println("Depth First Search Pre Order " + myBST.depthFirstSearch_PreOrder().toString());
        System.out.println("Depth First Search Post Order " + myBST.depthFirstSearch_PostOrder().toString());
        myBST.delete(100);
        System.out.println("Depth First Search In Order " + myBST.depthFirstSearch_InOrder().toString());

output


Breadth First Search [100, 21, 111, 20, 50, 101, 112]
Depth First Search In Order [20, 21, 50, 100, 101, 111, 112]
Depth First Search Pre Order [100, 21, 20, 50, 111, 101, 112]
Depth First Search Post Order [20, 50, 21, 101, 112, 111, 100]
after deleting root node i.e 100
Depth First Search In Order [20, 21, 50, 101, 111, 112]

Singly LinkedList implementation in JAVA

Karhik Suryadevara — Thu, 29 Apr 2021 03:34:13 +0000

What is a linked list

1) each element in a linked list is called a node.
2) It is similar to an array, each node in the linked list has the data part and a link to the next node.
3) linked lists have O(1) time complexity for insertion or deletion at the beginning i.e at position 0.

How to implement

-> Java has builtin LinkedList which you can import from the utility library
-> or you can implement your own LinkedList

Built-in LinkedList

        LinkedList<String> x = new LinkedList<String>();
//        to add elements to the list
        x.add("1"); // here the first element we added becomes the head
        x.add("2");
        x.add("3");
        x.add("4");
        x.add("5");
        x.remove("5");

//      to traverse the linked list
        Iterator<String> i = x.iterator();
        while(i.hasNext()){
            System.out.print(i.next()+"->");
        }

implementing a LinkedList, my approach:

// LL stands for LinkedList
public class LL {
    public Node head;

    public LL() {
        head = null;
    }

    public LL(int data) {
        head = new Node(data);
    }

    public void add(int data) {
        if (head != null) {
            head.appendToTail(data);
        } else {
            head = new Node(data);
        }
    }

    public void printList() {
        Node dummy = head;
        while (dummy != null) {
            System.out.print(dummy.data + "->");
            dummy = dummy.next;
        }
        System.out.print("null");
    }

    public void delete(int d) {
        Node newHead = new Node(0);
        newHead.next = head;
        Node previous = newHead;
        Node current = head;

        while (current != null) {
            if (current.data == d) {
                previous.next = current.next;
            } else {
                previous = current;
            }
            current = current.next;
        }

        head = newHead.next;

    }

    public class Node {
        Node next = null;
        int data;

        public Node(int data) {
            this.data = data;
        }

        void appendToTail(int d) {

            Node end = new Node(d);
            Node n = head;
            while (n.next != null) {
                n = n.next;
            }
            n.next = end;

        }
    }
}

Try out these challenges on LinkedList to get a good grasp

# Big O

Karhik Suryadevara — Wed, 28 Apr 2021 11:17:05 +0000

Why Big O

Big O is used to compare algorithms and analyze the efficiency of an algorithm, since comparing the time taken to execute an algorithm is not very accurate, because different computers have different processing speed's and an algorithm might run faster or slower depending on computer specifications.

What is big O?

To put it simply it is a way of analyzing an algorithm or a function with respect to the size of the input. Here input could be an array or a string anything.

To better understand let us say you have to send a file to your friend, you can do it by sending it online or you could go to him and hand it over, here if you choose to send it online it takes linear time i.e O(n) see the image below, if your file is 10MB it takes say 4 seconds if your file is 20MB it takes 8 seconds and if your file is 1TB then it might take even a day, so the time complexity to send the file depends on the input size, the time increases linearly as input increases. But if you choose to go over and hand it to him that is constant time O(1) (see the image below), i.e the time to send doesn't depend on the size of the file it takes the same amount of time to deliver 10MB or 1TB.

So Big O is a measure of the increase of time with respect to the input size.

Now let us look at some algorithms and find their time complexities

Ex 1: The following program prints all the elements in an array one by one

 public static void traverseArray(int[] array) {
        for (int i : array) {
            System.out.println("i :" + i);
        }
    }

Here the time complexity is O(N)linear time where N is the size of the array, i.e the time taken to execute increases linearly with an increase in input size i.e array size, because we have to do an operation i.e printing the element for all elements in the array, assume one operation takes one second and if we have 5 elements the total time is 5 seconds and if we have 20 elements the total time is 20 seconds i.e the time grows linearly with respect to the input.

Ex 2: The following program prints all pairs of elements in an array

public static void traverseArray(int[] array) {
        for (int i : array) {
            for (int j : array) {
                System.out.println("(" + i + "," + j + ")");
            }
        }

Here the time complexity is O(N*2) where N is size of the input.
why O(N2)? because for each element there is O(N) work to be done in the inner loop, and this has to be repeated for every element in the outer loop so big O becomes O(N*N) i.e O(N*2).

TO get a better understanding checkout these resources:
Youtube video
examples of big O analysis

Binary tree and BinarySearch tree implementation in Python

Karhik Suryadevara — Mon, 05 Apr 2021 10:58:57 +0000

Binary tree

Binary tree is a non-linear data structure.
In a binary tree each node has at most '2' children.

Code to implement Binary tree

# # # Binary tree
class treeNode:
    def __init__(self,val = None):
        self.val = val
        self.left = None
        self.right = None

root = treeNode(1)
root.left = treeNode(2)
root.right = treeNode(3)
# #       1
# #     /  \
# #    2    3
root.left.left = treeNode(4)
root.left.right = treeNode(5)
# #           1
# #         /  \
# #        2    3
# #       / \
# #      4   5

Output

print(root.left.right.val) # -> 5
print(root.left.left.val)  # -> 4

Binary Search tree

Binary search tree is a type of Binary tree in which nodes are inserted based on two conditions.
If the node to be inserted is less than the parent then 'insert left'.
If the node to be inserted is more than the parent then 'insert right'.

Code to implement Binary Search Tree

# # # Binary search tree
class binarySearchTree:
    def __init__(self,val=None):
        self.val = val
        self.left = None
        self.right = None

    def insert(self,val):
        # check if there is no root
        if (self.val == None):
            self.val = val
        # check where to insert
        else:
            # check for duplicate then stop and return
            if val == self.val: return 'no duplicates aloowed in binary search tree'
            # check if value to be inserted < currentNode's value
            if (val < self.val):
                # check if there is a left node to currentNode if true then recurse
                if(self.left):
                    self.left.insert(val)
                # insert where left of currentNode when currentNode.left=None
                else: self.left = binarySearchTree(val)

            # same steps as above here the condition we check is value to be inserted > currentNode's value
            else:
                if(self.right):
                    self.right.insert(val)
                else: self.right = binarySearchTree(val)




    def breadthFirstSearch(self):
        currentNode = self
        bfs_list = []
        queue = []
        queue.insert(0,currentNode)
        while(len(queue) > 0):
            currentNode = queue.pop()
            bfs_list.append(currentNode.val)
            if(currentNode.left):
                queue.insert(0,currentNode.left)
            if(currentNode.right):
                queue.insert(0,currentNode.right)

        return bfs_list

    # In order means first left child, then parent, at last right child
    def depthFirstSearch_INorder(self):
        return self.traverseInOrder([])

    # Pre order means first parent, then left child, at last right child
    def depthFirstSearch_PREorder(self):
        return self.traversePreOrder([])

    # Post order means first left child, then right child , at last parent
    def depthFirstSearch_POSTorder(self):
        return self.traversePostOrder([])

    def traverseInOrder(self, lst):
        if (self.left):
            self.left.traverseInOrder(lst)
        lst.append(self.val)
        if (self.right):
            self.right.traverseInOrder(lst)
        return lst

    def traversePreOrder(self, lst):
        lst.append(self.val)
        if (self.left):
            self.left.traversePreOrder(lst)
        if (self.right):
            self.right.traversePreOrder(lst)
        return lst

    def traversePostOrder(self, lst):
        if (self.left):
            self.left.traversePostOrder(lst)
        if (self.right):
            self.right.traversePostOrder(lst)
        lst.append(self.val)
        return lst

    def findNodeAndItsParent(self,val, parent = None):
        # returning the node and its parent so we can delete the node and reconstruct the tree from its parent
        if val == self.val: return self, parent
        if (val < self.val):
            if (self.left):
                return self.left.findNodeAndItsParent(val, self)
            else: return 'Not found'
        else:
            if (self.right):
                return  self.right.findNodeAndItsParent(val, self)
            else: return 'Not found'

    # deleteing a node means we have to rearrange some part of the tree
    def delete(self,val):
        # check if the value we want to delete is in the tree
        if(self.findNodeAndItsParent(val)=='Not found'): return 'Node is not in tree'
        # we get the node we want to delete and its parent-node from findNodeAndItsParent method
        deleteing_node, parent_node = self.findNodeAndItsParent(val)
        # check how many children nodes does the node we are going to delete have by traversePreOrder from the deleteing_node
        nodes_effected = deleteing_node.traversePreOrder([])
        # if len(nodes_effected)==1 means, the node to be deleted doesn't have any children
        # so we can just check from its parent node the position(left or right) of node we want to delete
        # and point the position to 'None' i.e node is deleted
        if (len(nodes_effected)==1):
            if (parent_node.left.val == deleteing_node.val) : parent_node.left = None
            else: parent_node.right = None
            return 'Succesfully deleted'
        # if len(nodes_effected) > 1 which means the node we are going to delete has 'children',
        # so the tree must be rearranged from the deleteing_node
        else:
            # if the node we want to delete doesn't have any parent means the node to be deleted is 'root' node
            if (parent_node == None):
                nodes_effected.remove(deleteing_node.val)
                # make the 'root' nodee i.e self value,left,right to None,
                # this means we need to implement a new tree again without the delted node
                self.left = None
                self.right = None
                self.val = None
                # construction of new tree
                for node in nodes_effected:
                    self.insert(node)
                return 'Succesfully deleted'

            # if the node we want to delete has a parent
            # traverse from parent_node
            nodes_effected = parent_node.traversePreOrder([])
            # deleting the node
            if (parent_node.left == deleteing_node) : parent_node.left = None
            else: parent_node.right = None
            # removeing the parent_node, deleteing_node and inserting the nodes_effected in the tree
            nodes_effected.remove(deleteing_node.val)
            nodes_effected.remove(parent_node.val)
            for node in nodes_effected:
                self.insert(node)

        return 'Successfully deleted'


bst = binarySearchTree()
bst.insert(7)
bst.insert(4)
bst.insert(9)
bst.insert(0)
bst.insert(5)
bst.insert(8)
bst.insert(13)

#          7
#        /  \
#      /     \
#     4        9
#    / \      /  \
#   0   5    8    13


print('IN order: ',bst.depthFirstSearch_INorder()) # useful in sorting the tree in ascending order
print('PRE order:' ,bst.depthFirstSearch_PREorder()) # pre order is useful in reconstructing a tree
print('POST order:', bst.depthFirstSearch_POSTorder()) # useful in finding the leaf nodes

print(bst.delete(5))
print(bst.delete(9))
print(bst.delete(7))

# after deleting
print('IN order: ',bst.depthFirstSearch_INorder())

Output

IN order:  [0, 4, 5, 7, 8, 9, 13]

PRE order: [7, 4, 0, 5, 9, 8, 13]

POST order: [0, 5, 4, 8, 13, 9, 7]

Successfully deleted
Successfully deleted
Successfully deleted

IN order:  [0, 4, 8, 13]

Applications of Binary trees

Used in many search applications where data is constantly entering/leaving because binary trees have logarithmic time lookup.
Binary Space Partition - Used in almost any 3D video game to determine which objects need to be rendered.

Implementation of Queue in python

Karhik Suryadevara — Thu, 01 Apr 2021 17:42:26 +0000

Queue is a type of data structure. Queue is based on the principle first in first out (FIFO) i.e first inserted element will be deleted first.
In queue Insertion of elements is done at one end i.e rear and deleting of elements is done at other end i.e front .
Queue works similar to queue at a ticket counter the first person in the queue is the front and the last person is the rear.

Now let us look at the code to implement a queue using a LinkedList.

Code

class node:
    def __init__(self,val):
        self.val = val
        self.next = None

class queue:
    def __init__(self):
        self.front = None
        self.rear = None

# push element on rear side
    def push(self,val):
        if (self.rear == None):
            self.front = node(val)
            self.rear = self.front
        else:
            new_node = node(val)
            self.rear.next = new_node
            self.rear = self.rear.next

# pop deletes the first inserted element in queue in front side
    def pop(self):
        if (self.front == None):
            print('No elements to pop in Queue')

        else:
            self.front = self.front.next

# To show where front is currently at
    def show_front(self):
        print('front: ',self.front.val)

# To show where rear is currently at
    def show_rear(self):
        print('rear: ', self.rear.val)

    def display_queue(self):
# To display the whole queue we have to traverse the linkedList
# Using a dummy node starting from head
        q = []
        dummy = self.front
        while(dummy):
            q.append(dummy.val)
            dummy = dummy.next
# Reverse 'q' to avoid confusion
        q.reverse()
        print('Queue data: ', q)

Input

x = queue() # instantiates a queue object named 'x' 
x.push(1)
x.push(2)
x.push(3)
x.push(4)
x.push(5)
x.push(6)
x.push(7)

x.display_queue(), x.show_front(), x.show_rear()
x.pop()
# front is changed after pop operation
x.display_queue(), x.show_front(), x.show_rear()

Output

Queue data:  [7, 6, 5, 4, 3, 2, 1]
front:  1
rear:  7
# after pop operation
Queue data:  [7, 6, 5, 4, 3, 2]
front:  2
rear:  7

stack in python using LinkedList or List

Karhik Suryadevara — Tue, 30 Mar 2021 15:56:43 +0000

Stack is a type of data structure. They are preferred over arrays or lists due to their fast insert and delete operations.
Stack works on the last in first out (LIFO) principle i.e insertion and deletion happens at only one end.
stack has an O(1) time complexity for pop or push operation.

look at the code below to understand how to implement stack on our own and how to use it.

Note: We can implement a stack using LinkedList or lists in python. Both implementations work fine and have the same time complexities for all the operations but I prefer implementing them using a list because it's much easier.

stack using list

class stack:
    def __init__(self):
        self.data = []

    def push(self,elem):
        self.data.append(elem)

    def pop(self):
     try:
        popped_item = self.data.pop()
        return popped_item
     except IndexError:
        print('Stack Underflow')

    def peek(self):
     try:
        print(self.data[len(self.data)-1])
     except IndexError:
        print('No elements in stack')

    def size(self):
      return len(self.data)

my_stack = stack()
my_stack.push('1')
my_stack.push('2')
my_stack.push('3')
print("data:", my_stack.data, "size:", my_stack.size())

Output

data: ['1','2','3'] size: 3

stack using LinkedList

class node:
  def __init__(self,val):
    self.val = val
    self.next = None

class linkedListStack:

  def __init__(self):
    self.head = None

  def push(self,val):
    if (self.head == None):
      self.head = node(val)
    else:
      new_node = node(val)
      new_node.next = self.head
      self.head = new_node

  def pop(self):
    if (self.head == None):
      print('Stack underflow')
    else:
      popped_val = self.head.val
      self.head = self.head.next
      return popped_val

  def peek(self):
    if (self.head==None):
      print(None)
    else:
      print(self.head.val)

  def display_stack(self):
    dummy = self.head
    while(dummy):
      print(dummy.val,end=" <- ")
      dummy = dummy.next

lls = linkedListStack() 
lls.push(1)
lls.push(2)
lls.push(3)
lls.push(4)
lls.pop()
lls.peek()
lls.display_stack()

Output

3
3 <- 2 <- 1 <-