Aditya Chatterjee's Blog, page 111

Max path sum between two nodes in Binary Tree

In this article, we have explored algorithms to find the Max path sum between two nodes in Binary Tree along with time and space complexity.

Table of Contents1) Introduction2) Naive approach3) Optimized approach4) Conclusion1) Introduction

A path in a binary tree is a sequence of consecutive nodes.

Consider the above binary tree, few of the paths are listed below

-1->3->2->4->5
-1->3->2->4->-6
5->4->-6
3->2->4

Among all the paths, 3->2->4->5 has the maximum sum

A path wit...

K-th smallest element of two sorted arrays

In this article, we have explored algorithms to find the K-th smallest element of two sorted arrays. This involve the idea of Binary Search.

Table of contents:

Basic approach to find K-th smallest element of two sorted arrays.Improved approach by reducing space complexity to constant.Further improved approaches

Pre-requisites

ArrayBinary searchIntroduction

In this article, we will learn various methods to find the kth smallest element of two arrays. We have multiple ways to solve the pro...

Apache ZooKeeper in System Design

In this article, we will look at Apache ZooKeeper and how it is useful in distributed systems.

Table of Contents

What is ZooKeeper?Distributed Systems and the Need for ZooKeeperZooKeeper ArchitectureZooKeeper Data ModelVarious Types of ZnodesSessionsWatchesWorking of ZooKeeperApplication of ZooKeeper in the Hadoop EcosystemWhat is ZooKeeper?

Apache ZooKeeper is a service that offers distributed synchronization, maintaining configuration metadata, naming, and group services to a distri...

Bigtable in System Design

In this article, we have explored the idea of Bigtable in System Design. It is an innovative database system developed by Google.

Table of contents:

Introduction to BigtableGoalsData ModelImplementation / How to use Bigtable?Best uses of BigtableCloud Bigtable PricingIntroduction to Bigtable

Bigtable is a revolutionary internal Google database system that helped to launch the NoSQL industry. Google had a problem in the mid-2000s. The web indexes behind its search engine had grown massive...

Sethi Ullman algorithm

The Sethi-Ullman algorithm is an optimal algorithm used for finding an optimal ordering of a computation tree. We will see two generalizations that increase its applicability without increasing the cost.

Table of contents.Introduction.Generalization 1.Generalization 2.An evaluation algorithm.Spilling registers.Implementation.Summary.References.Introduction.

Computations can be modeled as computation trees whereby the leaves are constant values while the internal nodes acquire their va...

L-Attributed and S-Attributed definitions and grammar

We have discussed two classes of definitions that can efficiently be implemented in connection to top-down or bottom-up parsing in compilers and corresponding attribute grammars that result from serious restrictions.

Table of contents.Introduction.S-Attributed Definitions.L-Attributed Definitions.L-attribute grammars.S-attribute grammars.Equivalence of L-attribute and S-attribute grammars.Summary.References.Prerequisites.Attribute Dependence Graph and Evaluation in Semantic Analysis...

System Design of Snapchat

This article will give an overview of the architecture, infrastructure and System Design of Snapchat, as well as provide some insight to the company (Snap Inc.'s) history.

Table of Contents

IntroductionDesign TermsBeginningsGrowth to ProblemsModernizationThe Various AppsMonolith to MicroservicesCurrent DayIntroduction

Snapchat is an American-developed social media app released in September 2011 that supports instant messaging, picture sharing, and more. The developer of the app, Sna...

Using Python for Data Analysis

In this article, we will learn how Python is used for Data Analysis and introduced Python libraries that are frequently used in Data Science such as Numpy, Pandas, Matplotlib, Seaborn and others.

Table of contentsSome python libraries used for data analysisNumPyPandasMatplotlib and Seaborn

Some python libraries used for data analysis

Python offers many packages/libraries that are curated for specific uses making python a computer programming language that is extremely diverse in its us...

Data Analysis tools

In this article, we will get the basic idea of what is data analysis and look into some tools that are used for data analysis.

Table of contentsWhat is Data analysis?Tools used for data analysis

What is Data analysis?

Data analysis is the process of collection, organization, transformation and modeling of data to draw conclusions, make predictions and also make informed decisions. A simple example of this is when we buy a new phone. We do so much research on the brands, models, the features...

Boundary Traversal of Binary Tree

In this article, we have explored the approach of Boundary Traversal of Binary Tree along with Time and Space Complexity.

Contents:

IntroductionImplementationResultComplexityIntroduction

When we capture only elements that exist on the Boundary of the Binary Tree is the kind of traversing, is what "Boundary Traversal of Binary Tree" refers to.

For example:

We can collect three following types of nodes:

1. (1&2) left end nodes and right end nodes

These are the nodes that you can see on ...