Aditya Chatterjee's Blog, page 168

Minimum number of nodes to be removed such that no subtree has more than K nodes

We will be given a tree with N Nodes and N-1 edges and the number K. We have to find minimum numbers of Nodes that we have to need to deleted in order to make total numbers of node in every subtree less then or equal to K.

This problem can be solved in O(V^2) time and using the idea of Depth First Search.

Lets understand with few examplesExample 1

consider the following tree with 6 Nodes and 5 Edges

[image error]

lets the value of K be 3 so for this case if we want all the subtree having total nodes less th...

Number of substrings with exactly k distinct characters

In this OpenGenus article, we will be solving Find number of substrings with exactly k distinct characters problem. In this problem, we are given a string and our job is to count the total number of substrings of the given string that contains exactly k distinct characters. If no substring exists that contains exactly k distinct characters then return -1.

For example:

Input: xyz, k = 2Output: 2substrings are {"xy", "yz"}Input: xyx, k = 2Output: 3substrings are {"xy", "yx", "xyx"}Input: z...

Different ways to sort a Queue

In this article, we will be discussing 4 different ways to sort a queue. The first approach takes O(n) time and O(n) extra space whereas the second approach takes O(n^2) time and constant extra space (O(1)). We have covered the following techniques to sort a queue:

Method 1 : Using auxiliary arrayMethod 2 : O(1) space requiredMethod 3 : Using recursionMethod 4 : Using stackMethod 1 : Using auxiliary array

We use an auxiliary array to store all the elements of the queue. We then sort the ar...

endl vs \n (New Line) in C++

In C++, endl and /n are used to break lines or move the cursor to a new line. Both endl and \n may seem to be similar but has distinct differences which we have explored in this article in depth.

endl

endl stands for end line. endl is a predefined object of ostream class . it is a manipulator used to insert a new line and flush the output buffer.

cout

Example 1:

#includeusing namesapce std;void main(){ cout

Output:

HELLOWORLD

In the above example, HELLO is displayed first and then using...

Regular Expression (Regex) in Python

Everyone has used the feature of CTRL+F to find some text in documents, Regex also known as Regular Expresssion is advance form of that it allows the user to search for a pattern defined by him/her in the given set of input. Regex matching is termed as Greedy.

Let's say you want to find a given ip address of format(xxx.xxx.xxx.x) is present or not in a large set of document, it can be done two ways:-

1- Tradtional way is without using any form of regex in the code and to visit each character in ...

Implementing two stacks in one array

In this article, we will demonstrate how to implement 2 stacks in one array. Both stacks are independent but use the same array. We need to make sure one stack does not interfere with the other stack and support push and pop operation accordingly.

The topics we have covered in this article at OpenGenus are as follows:

Introduction to stack & arrayImplement 2 stack in 1 arrayApproach 1: Divide array in 2 partsApproach 2: Space efficient approachIntroductionStack

Stack is an abstract dat...

Reverse first K elements of Queue using Stack

To reverse the first K elements of a queue, we can use an auxiliary stack. We push the first k elements in the stack and pop() them out so and add them at the end of the queue. Popping the elements out of the queue reverses them.

We can do this in linear time O(N) with O(K) space.

To bring the remaining n-k elements to their correct positions, we simply need to remove them from the front and add them at the end of the queue. After this operation the first K elements of the queue will be reversed...

Time Complexity of Insertion Sort

Reading time: 15 minutes | Coding time: 5 minutes

Comprehend Insertion Sort Code the Algorithm Dive into Analysis

In this article, we have explored the time and space complexity of Insertion Sort along with two optimizations. Before going into the complexity analysis, we will go through the basic knowledge of Insertion Sort.
In short:

The worst case time complexity of Insertion sort is O(N^2)The average case time complexity of Insertion sort is O(N^2)The tim...

Set vs Map containers in C++

This article is to discuss the difference between a set and a map which are both containers in the Standard Template Library in C++.

TLDR

The map container stores unique key-value pairs in a sorted order, while a set container, which is like a specialized version of the map stores unique keys only, where the key is identical to the value it maps to.

Set containerA set is a sorted associated container of unique elementsEach element can occur only once, so duplicates are not allowed in setsEle...

How to phish? or Phishing Campaigns

“Hackers find more success with organizations where employees are under appreciated, over worked and under paid. Why would anyone in an organization like that care enough to think twice before clicking on a phishing email?”
― James Scott, Sr. Fellow, Institute for Critical Infrastructure Technology

Phishing
From Wikipedia, the free encyclopedia
Not to be confused with Fishing or Pishing.

Phishing is a type of social engineering where an attacker sends a fraudulent ("spoofed") message designe...