Aditya Chatterjee's Blog, page 160

Number of distinct substrings of length K

In this article, we have explained the approach to find the Number of distinct substrings of length K using Rolling hash technique, hash table and brute force approach.

Table of content:

Problem StatementMethod 1 - Brute ForceMethod 2 - Using hash tableMethod 3 - Rolling hash algorithm

We will dive into the problem "Number of distinct substrings of length K" now.

Problem Statement

Given a string of lowercase alphabets and an integer k as input, print the count of all possible substrings whi...

Number of rectangles from a given set of points

In this article, we have discussed how to find the number of rectangles (parallel to the axes) possible from a given set of coordinate points.

Table of content:

ExampleBrute Force ApproachEfficent ApproachAlgorithmImplementationComplexity AnalysisExample

Let us suppose we have the set of coordinates as [{1,1}, {7,1}, {1,4}, {1,5}, {7,4}, {7,5}]

8 | 7 | 6 | (1,5) (7,5)5 | * *4 | * *3 | (1,4) (7,4)2 | (1,1) (7,1)...

Introduction to OpenGL

In this article, we have introduced and explored the world of OpenGL and some topics that are related to it.

What is OpenGL?What is GLEW?What is GLFW?Shaders in OpenGLRendering PipelineStages of Rendering PipelineAdvantages of OpenGL1. What is OpenGL?

OpenGL (Open Graphics Library) is a cross-language, cross-platform application programming interface (API) that can be used to render 2D and 3D vector graphics with a ton of features and customization. The API can directly interact with th...

Subtraction using bitwise operations

Hello readers, we are gonna take a look at how can we subtract two numbers without using arithmetic operation. We will only use bitwise operations to perform subtraction.

Table of content:

What are bitwise operations?Subtraction using bitwise operationsSubtraction LogicImplementation of LogicComplexity Analysis

We will dive into bitwise subtraction now.

What are bitwise operations?

Similar to arithmetic operators like +, -, *, / in decimal number system, we have bitwise operators like AND ...

Dilated Convolution [explained]

Dilated convolution, also known as Atrous Convolution or convolution with holes, first came into light by the paper "Semantic Image Segmentation with Deep Convolutional Nets and Fully Connected CRFs". The idea behind dilated convolution is to "inflate" the kernel which in turn skips some of the points. We can see the difference in the general formula and some visualization.

Table of content:

Introduction to Dilated ConvolutionDilated convolution in TensorflowDilated convolution in actionDila...

Makoto Soejima (rng_58)

Makoto Soejima is a Competitive Programmer from Japan. He is also known as rng_58. He works at AtCoder. His Competitive Programming career started in 1999 and lasted till 2020. He is one of the 4 people ever to have won both Google Code Jam and Facebook Hacker Cup.

He is considered as one of the best Competitive Programmers in the World (see). He was a student at University of Tokyo.

Achievements

Major achievements by Makoto Soejima are:

International Mathematical Olympiad (IMO): 3 Gold (2007, ...

Shortest Path using Topological Sort

In this article, we have explained the algorithm to find the shortest path in a Directed Acyclic Graph using Topological Sort.

Table of content:

Problem StatementApproachPseudo Code for Topological Sorting (DFS)Pseudo Code for finding Shortest path using Topological SortingTime ComplexityComparison of Topological Sorting with other shortest distance finding algorithmsApplication of Topological SortingQuestion

We will dive into it now.

Problem Statement

We are given with a weighted direc...

Probabilistic / Approximate Counting [Complete Overview]

In this article, we will be introducing and exploring the idea of Probabilistic algorithms in depth with the different algorithms like Morris Algorithm, HyperLogLog, LogLog and others in this domain.

Table of content:

Overview of Probabilistic/ Approximate Counting algorithmsProblem statement of countingApproximate counting algorithm (Morris Algorithm)
3.1 Overview
3.2 Working
3.3 Applications
3.4 ComplexityHyperloglog algorithm
4.1 Overview
4.2 Loglog algorithm
4.3 Working
4.4 Improvements ...

Stateless and Stateful architecture [explained]

In this article, we have explained the Idea of stateless and stateful architecture ind depth. There seems to be a raging debate as to which is better, stateless architecture or stateful architecture. Additionally, there various misconceptions about the correct definition of these terms, especially in client and server systems.

Table of content:

Introduction: Stating a brief historyStateless Architecture
3. Advantages of Stateless applications
4. Disadvantages of Stateless applications
5. Examp...

Arithmetic Expression Evaluation using Stack

In this article, we have explained how an Arithmetic Expression (like 2 * 3 + 4) is evaluated using Stack. We have presented the algorithms and time/ space complexity.

Table of content:

Introduction to Arithmetic expressionsAlgorithm to evaluate Arithmetic expressionStep by Step ExampleImplementationTime & Space complexity

We will dive directly into the problem now.

Introduction to Arithmetic expressions

Arithmetic expressions can be represented in 3 forms:

Infix notationPostfix notation...