Aditya Chatterjee's Blog, page 167

Time & Space Complexity of Counting Sort

In this article, we have explained the time complexity of Counting Sort for Average case, Worst case and Best case and also, covered the space complexity using Mathematical analysis.

Table of contents:

Introduction to Counting SortTime Complexity analysisWorst case time complexityBest case time complexityAverage case time complexitySpace ComplexityConclusion on time and space complexityComparison with other sorting algorithms

In short,

Time complexity: O(N+K)Space Complexity: O(K)Wor...

How I became an Author while being a student?

This article captures how I became a technical Author in a couple of months while being a student. I wanted to become an Author for a long time but did not have the idea of how to accomplish it. It all started with an Internship, expressing my interest of authoring a book with my mentor and working on the idea with full focus for a couple of months.

Over this article, I have shared my journey and some of the lessons I learnt which you should follow as well.

A Litte bit about myself 👧

I am Srisht...

Essential components of Ruby: OOP, Data Types, Methods, Variables

In this article, we have covered the essential components of Ruby such as OOP concepts like class and object, Data Types, Methods, Variables and much more.

Table of contents:

Classes and Objects in RubyVariables, Constants, Literals, Booleans and nilNumbers, Strings, Symbols, Arrays, Hashes, Ranges, Regular expressions, Procs, Percent StringsData Types: Numbers, Strings, Symbols, Hashes, Arrays, BooleanMethodsClasses and Objects

A class is a blueprint, or a prototype, from which objects a...

In memory Database [Explained]

In memory Database is a type of Database that is stored in main memory (instead of hard disk) which makes to significantly fast (100X improvement) with some limitations. In this article, we explain everything about in-memory database and present an real system design example where in-memory database is used.

Table of Contents:

Introduction to DatabaseAbout In Memory DataBasesRedis (In memory DB)Memcached (In memory DB)Aerospike (In memory DB)HazelCast (In memory DB)In memory vs on disk da...

Merkle Tree [Explained]

Merkle tree is named after Ralph Merkle, it is a tree data structure where non-leaf nodes are a hash of its child nodes and leaf nodes are a hash of a block of data. It has a branching factor of 2 (it can have a maximum of 2 children). Merkel trees allow efficient and secure verification of the contents of a large data structure.

Note: Merkle Tree is a USPTO patented Algorithm/ Data Structure and hence, you cannot use it in production without permission or by paying royality to Ralph Merkle. Mer...

Check if a string is a subsequence of another string

In this problem, we will see how we can check whether a string is a subsequence of another string. Now we will consider an example to understand the given problem.

Let's say we have a string 'Welcome to OpenGenus' and a substring OGenus.
Now we need to find whether we have a substring or not.

mainString = S1 = "Welcome to OpenGenus";Subsequences (S2) are:OpenGenusOGenusWlcomepen [Notice we have deleted few characters in mainString]

Hence, S2 is a subsequence of S1 if we can convert S1 to ...

Find index such that sum of left sub-array = right sub-array (Equilibrium Index)

For a given array, we need to find an index such that sum of left sub-array = right sub-array also called the Equilibrium Index.
Equilibrium index is the index of the element in the array such that the sum of all the elements left to the index is equal to the sum of all the elements right to the index .

(A[0] + A[1] + … + A[i-1]) = (A[i+1] + A[i+2] + … + A[n-1]), where 0

input:
[3, 4, 1, 5, 2, 6]
output:
3
Explanation:
The left and right sub array for index '3' is [3, 4, 1] and [2, 6] respecti...

Finding LCM of an array of numbers

The Problem
Find the LCM of the given array of positive numbers.
The LCM (Least Common Multiple) of two or more numbers is the smallest number that is evenly divisible by all numbers in the set.

Examples

Input: arr[] = {1, 2, 3, 4, 8, 28, 36}Output: 504Input: arr[] = {16, 18, 20, 30}Output: 720

We have explored 2 approaches:

Method 1 (using GCD)Method 2 (without using GCD)Method 1 (using GCD)

We know that,
LCM(a, b) = (a*b)/GCD(a, b), where GCD stands for Greatest Common Divisor.
The ab...

Fixed width integer types (int8) in C++

If I ask you, "What is the size of an integer in C++?, what would be your answer?

4 bytes?2 bytes?8 bytes?
Well, here's the thing, it may be a slight oversimplification to keep it this way but C++ doesn't have a fixed size for integers.
What C++ does have is a lower limit for integer size.
C++ guarantees that signed short, unsigned short, signed int, and unsigned int are at least 16 bits or 2 bytes.But, why isn't the size fixed?

Well, the reason goes back to 1969-1973 when C was being devel...

Finding 2 elements with difference k in a sorted array

In this OpenGenus article, we will explore a problem (Finding 2 elements with difference k in a sorted array), and find various methods of solving the problem, based on varying complexity. While this problem itself might be of some merit, let us focus more on the underlying idea, which serves as the core to many other problems.

Note that the language used to show example codes is C++, because, I believe it is the most apt language for studying algorithms.

Problem Statement

Given a sorted array ...