Asymptotic analysis of an algorithm refers to defining the mathematical boundation/framing of its run-time performance. When it comes to analysing the complexity of any algorithm in terms of time and space, we can never provide an exact number to define the time required and the space required by the algorithm, [...]
Introduction Some applications involve grouping N distinct objects into a collection of Disjoint sets. Two important operations are then finding which set a given object belongs to and uniting the two sets. A disjoint set data structure maintains a collection S={ S1 , S2 ,…, Sk } of disjoint dynamic [...]
In hashing, large keys are converted into small keys by using hash functions. The values are then stored in a data structure called hash table. The idea of hashing is to distribute entries (key/value pairs) uniformly across an array. Each element is assigned a key (converted key). By using that [...]
Tries are an extremely special and useful data-structure that are based on the prefix of a string. The prefix of a string is nothing but any n letters such that n ≤ |S| that can be considered beginning strictly from the starting of a string. The name trie comes from its use for retrieval. A Trie [...]
A Hamiltonian path (or traceable path) is a path in an undirected or directed graph that visits each vertex exactly once. A graph that contains a Hamiltonian path is called a traceable graph. A graph is Hamiltonian-connected if for every pair of vertices there is a Hamiltonian path between the [...]
Tree is a non-linear data structure which organizes data in hierarchical structure. Root: First node of the tree Edge :- Connecting link between any two nodes is called as EDGE. In a tree with 'N' number of nodes there will be a maximum of 'N-1' number of edges. Parent :- [...]
Both techniques use optimal substructure (optimal solution “contains optimal solution for subproblems within it”). In dynamic programming, solution depends on solution to subproblems. That is, compute the optimal solutions for each possible choice and then compute the optimal way to combine things together. In greedy algorithm we choose what looks [...]
An in-place algorithm is an algorithm which transforms input using no auxiliary data structure. However a small amount of extra storage space is allowed for auxiliary variables. The input is usually overwritten by the output as the algorithm executes. In-place algorithm updates input sequence only through replacement or swapping of [...]
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining. For water to get collected on Bar B, There should be Bar on Left side and Right Side of Bar B whose height [...]
Question : Find the Bitwise XOR of the value of all sub arrays of array A. Input : A = [1,2] Output : 0 Explanation : Sub Arrays :[1], [2], [1,2] (XOR of all subarrays = 0) Solution: To find XOR of all sub arrays (consecutive element of array), we [...]