Piyush Nirala

Search This Blog

Differences between Set, Multi-set, Unordered_set, Unordered_multi-set

Posted by Piyush Nirala May 20, 2020

Get link
Facebook
X
Pinterest
Email
Other Apps

Tabular Representation

STL C++

Get link
Facebook
X
Pinterest
Email
Other Apps

Comments

Hashing Dashing with Sliding Window

As the name suggests, we will see hashing but before that, let's see a problem : Given two strings s1 and s2, write a function to return true if s2 contains the permutation of s1. In other words, one of the first string's permutations is the substring of the second string. Example 1: Input: s1 = "ab" s2 = "eidbaooo" Output: True Explanation: s2 contains one permutation of s1 ("ba"). Some ideas came to my mind while solving this : How will I check whether one string is a permutation of another string? If one string is a permutation of another string then they must one common metric. What is that? Both strings must have the same character frequencies if one is a permutation of another. Which data structure should be used to store frequencies? So finally we can store them in array/Maps. Let's make a frequency array and Map respectively:

Binary Lifting Technique and the Least Common Ancestor Problem

Finding LCA using Binary Lifting Let G be a tree. For every query of the form (u, v) we want to find the lowest common ancestor of the nodes u and v , i.e. we want to find a node w that lies on the path from u to the root node, that lies on the path from v to the root node, and if there are multiple nodes we pick the one that is farthest away from the root node. In other words the desired node w is the lowest ancestor of u and v . In particular if u is an ancestor of v , then u is their lowest common ancestor. A naïve approach would be something as follows:- To calculate the LCA of two nodes first we will bring both the nodes to the same height by making the node with greater depth jump one parent up the tree till both the nodes are at the same height. Once, both the nodes are at the same height we can then start jump...

Constructing a Graph/Tree in C++

Graph is a data structure that consists of following two components: 1. A finite set of vertices also called as nodes. 2. A finite set of ordered pair of the form (u, v) called as edge. The pair is ordered because (u, v) is not same as (v, u) in case of a directed graph(di-graph). The pair of the form (u, v) indicates that there is an edge from vertex u to vertex v. The edges may contain weight/value/cost. A tree is a special graph in which, if there exists any path between two nodes, then that is the only path. In easy language a tree can be said as a graph with no cycles. Tree is basically used to store data in a hierarchical form. An undirected graph with 5 vertices and 7 edges. In this article I am going to tell how to construct a tree/graph in your codes: Following two are the most commonly used representations of a graph. 1. Adjacency Matrix 2. Adjacency List Adjacency Matrix: Adjacency Matrix is a 2D array of size V x V where V is the numb...

Powered by Blogger

Differences between Set, Multi-set, Unordered_set, Unordered_multi-set

Comments

Post a Comment