Aditya Chatterjee's Blog, page 158

Why O(1) time complexity does not exist? + Memory Model

In this article, we have taken an in-depth look at the operations or algorithms that have a constant time in terms of asymptotic notation of time complexities. Is O(1) really a practical way of representing the time complexity of certain algorithms/ operations?

Table of content:

Getting started with the Memory modelLet's talk about O(1)Digging deep into access timeTesting our claimConclusions
5.1 Physical analysis
5.2 Analysis of algorithms

Let's find out!

1. Getting started with the Memor...

Reversal Algorithm to rotate an array

In this article, we have discussed Reversal algorithm. It is widely used for rotating arrays. This algorithm is specifically useful for rotating array by any number of places because it efficiently does the operation in O(N) time and O(1) auxiliary space. It uses the concept of reversing an array as a utility function.

Table of content:

Problem statement: RotationReversal AlgorithmExample: Dry RunImplementations of Reversal AlgorithmTime ComplexitySpace ComplexityProblem statement: Rotat...

RPC vs REST

In this article, we have covered the differences between REST and RPC. REST stands for Representational State Transfer and RPC stands for Remote Procedural Call.

Table of content:

Differences between RPC and RESTRESTRPC

We will get started now.

1. Differences between RPC and REST

RPC is action-oriented. In contrast, REST is resource-oriented.

REST utilizes HTTP methods GET, POST, PUT, PATCH, and DELETE to perform CRUD operations. However, RPC only supports GET and POST requests.

REST ...

Deleting Duplicate Characters of String

We have explored the problem of Deleting Duplicate Characters of String such that the resulting string is lexicographically the smallest among all possibilities.

Table of Contents:ProblemLexicographical orderExampleObservationsSolution 1ImplementationComplexitySolution 2Implementation2Complexity2Problem Statement

Given a string, our goal is to remove duplicate letters such that in the resulting string every letter appears exactly once and is in smallest lexicographical order of all ...

k-th Largest Element in a stream

In this article, we will discuss the problem K-th largest Element in a stream, and understand the different methods that can be used to solve the problem efficiently.

Table of content:

Problem StatementApproach 1: Sorting the ArrayApproach 2: Using min-heap

We will dive into the problem now.

Problem Statement

Design a class to find the kth largest element in a stream. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Implement KthLargest class:

KthLa...

Shuffle an array [2 approaches]

In this article, we have explored two approaches to shuffle an array. The first approach uses an auxiliary array while the second approach is in-place and is known as Fisher Yates Algorithm.

Table of content:

IntroductionApproach 1: Using auxiliary arrayApproach 2: Fisher Yates Algorithm

Let us get started.

Introduction

Given an array, we need to shuffle it randomly. All possible permutations of the array elements must be equally likely to be produced after shuffling. In this article, we dis...

2D list in C++ STL (Defining and Sorting)

In this article, we will begin with a brief recap of what lists are, followed by an introduction to 2-dimensional lists (2D list), where we shall explore creating and defining 2D lists in C++ STL and sorting them.

Table of content:

Lists in C++ STL2D list in C++ STLSorting individual list elements of the 2D listSorting the entire 2-D list by comparing elements from individual listsSorting the 2-D list according to the value of its elements present at a particular index

Let us begin!

Lists ...

Array Interview Questions [MCQ with answers]

This is the list of Interview Questions based on Array Data Structure. You must practice these Multiple Choice Questions. This will help you master Array Coding Questions for Interviews at companies like Google and Microsoft.

Go through this article to learn more about arrays and practice different coding problems before you attempt the questions:

50+ Practice Coding Problems on ArrayQuestion 1What is the minimum number of comparisons required to find the largest element in an array of N el...

Brian Kernighan's Algorithm

In this article, we will learn what are set bits and how to count them. And we will also learn about Brian Kernighan's algorithm a famous algorithm to find the number of set bits in a number.

Table of content:

IntroductionBrute force methodBrian Kernighan's AlgorithmComplexity of Brian Kernighan's AlgorithmConclusionIntroduction

Brian Kernighan's algorithm is used to calculate the number of set bits in a given number. But what is a set bit?

In computers, we know that data is represented a...

Number of sub-strings with each character occurring even times

This article discusses different algorithmic approach which we can use to find number of sub-strings with each character in it occurring even number times for a given string.

Table of ContentsPre-requisitesNaive methodNaive method algorithmNaive method C codeQuestionEfficient approachEfficient approach algorithmEfficient approach C codeComplexity Pre-requisites

Arrays, Strings in C, Generate all sub-strings of a string, Bitwise operations, Dictionary or key-value representatio...