Aditya Chatterjee's Blog, page 137

System Design of Pastebin

In this article, we will be looking into the system design of Pastebin which is a content hosting service for simple text files. The scale of use of this applications makes the System Design interesting.

Table of Content:What is PastebinKey Features/ Use casesConstraints and Capacity AssumptionsDiving into The DesignConclusionWhat is Pastebin

Pastebin is an online content hosting service where users can store text files(i.e source code snippets, etc) called "pastes" over the internet, ei...

Persistent Trie

In this article, we discuss the Trie data structure and how to make it persistent to solve various problems optimally.

Table of contents:

What is a Trie?Persistency of a data structurePersistent TrieTime and Space Complexity AnalysisComparison between basic and persistent trieExample Problem

Pre-requisites:

TrieApplications of Trie Data StructureWhat is a Trie?

This is a special tree that can store strings in an ordered efficient way.
We can visualize it as a graph, that is each node ...

Time and Space Complexity of Heap data structure operations

In this article, we have explored the Time and Space Complexity of Heap data structure operations including different cases like Worst, Average and Best case. At the end, we have added a table summarizes the complexities.

List of OperationsInsertionBest Case: O(1)Worst Case: O(logN)Average Case: O(logN)DeletionBest Case: O(1)Worst Case: O(logN)Average Case: O(logN)SearchingBest Case: O(1)Worst Case: O(N)Average Case: O(N)Getting max value & min valueSorting O(Nl...

Project on Reconstructing Face using PCA

In this article, we have demonstrated a project "face" where we find the set of faces when combined, resulting in face of person A. We do this using Machine Learning techniques like Principal Component Analysis, Face Reconstruction and much more.

Codebase on GitHub: github.com/OpenGenus/facePublished as a pip package face-reconsDeveloped by: Srishti Guleria

It can be installed by running below command in the terminal :

pip install face-recons==0.0.1

After successfully installing the package...

Delete middle element of Queue

In this article, we discuss how to delete the middle element of a queue without using other data structures. We have explained both iterative and recursive approach.

Table of contents:

Introduction to QueueProblem statement: Delete the middle element from queueIterative ApproachRecursive ApproachTime and Space Complexity Analysis

Pre-requisites:

Queue Data StructureDelete middle element of StackIntroduction to Queue

A queue is an abstract linear data structure that stores elements in a...

Delete middle element of Stack

In this article, we discuss an iterative and recursive approach to delete the middle element of a stack.

Table of contents:

A brief introduction to StacksProblem StatementIterative ApproachRecursive ApproachTime and Space Complexity Analysis

Pre-requisite:

Stack data structureDelete middle element of QueueA brief introduction to Stacks

A stack is a linear data structure that follows LIFO(last in first out).
Picture a stack of plates, the last to be stacked(push) is the first to be remo...

Nearest smaller and greater numbers with same number of set bits

In this article, we shall explore the various ways we can find the Nearest smaller and greater numbers with same number of set bits for given number.

We shall see two approaches

The brute force approachThe Bit manipulation

Table of contents:

Understanding the problemBrute-force approachTime Complexity for this approachBit manipulation approachNearest Greater NumberNearest Lesser NumberTime Complexity

So, let's get started!

Understanding the problem

Suppose we are given a number, sa...

Find mirror image of point in 3D plane

In this article, we will learn how to find the mirror image of a point (x,y,z) in 3D-plane.

Table of contents:

Equation of plane in 3-DimensionImplementationStepsCodeOutputTime Complexity

Prerequisite: Find mirror image of point in 2D plane

Equation of plane in 3-Dimension

a. x + b. y + c. z + d = 0

where,
a,b,c = directions ratios of normal to the plane

Point P(x1,y1,z1) :

Assume a point P(x1,y1,z1) in the 3D plane.

Direction ratios relation :

(x - x1) / a = (y - y1) / b = (z - z1) / c...

Error recovery in Compiler Design

In this article, we will discuss about various types of errors that occurs in the compiler design and what are those methods with the help of which this error can be recovered in a compiler.

Table of contents:

Introduction to Error in Compiler DesignTypes of errorsError recovery methodsSummary Table

In short:

ErrorsRecovery methodsLexical phase errorsPanic modeSyntactic phase errorsPanic, statement mode, error
production , global correctionSemantic errorsSymbol table

Pre...

Peephole Optimization in Compiler Design

In terms of compiler optimization, classical compilers used a method called Peephole Optimization, which is a powerful optimization approach. During the early stages of implementation, this approach was mostly used with string pattern matching on regular expressions, which are known as classic peephole optimizers. The string pattern matching technique is considered as a processing of the input of the syntax of assembly code in classical optimizers, but its meaning is lost. This article analyses ...