The NP-hard problems are solved in polynomial time by non-deterministic machines and are difficult to find but simple to prove. NP (Nondeterministic Polynomial) is a class of decision problems in computer science where a proposed solution can be verified quickly. NP-hard problems are at least as challenging as the hardest problems in NP, and solving ...
Simple chaining (sometimes referred to as Separate chaining), is a collision resolution strategy followed in the concept of Hashing. As per the simple chaining strategy whenever there is a collision in HashTable, instead of looking for any other slot we prefer putting the data in the initial bucket i.e.i.e. generated by the hash function. So we would require some sort ...
Problem Statement Write a program that implements the operations of queue using an array Implementation of Queue using Array Operations The queue is the linear data structure that works on the principle of FIFO( First In First Out). In queue insertion and deletion of elements takes place at two different ends. The addition of an element ...
Problem Statement Find all strongly connected components in O(V+E) time using Kosaraju’s algorithm. Strongly connected Component(SCC) – In a directed graph a strongly connected component is a component of the graph in which there is a path between every pair of vertices. Example Example of strongly connected component in a graph : Example Explanation In the above Example diagram ...
The line sweep algorithm is based on the idea of using a vertical imaginary line that moves in the rightward direction upon the occurrences of certain events defined by the current problem at hand. The line sweep algorithm is used to solve problems such as closest pair, line segment intersections, the union of rectangles, convex hull, Manhattan ...
This article explains the concept of isomorphism in graph data structures. A pair of given graphs are said to be isomorphic graphs if they are structurally equivalent. It means there exists a mapping(bijection) between the vertices of the two graphs. Using this mapping, one graph can be converted into the other by replacing its vertices ...
Problem Statement You are given a set of N jobs, where each job is having a deadline and a profit associated with it. You can only earn a profit if you complete the job within its given deadline. You can perform the job either before the deadline or strictly on the deadline, not after that. Rules: Input Format: The jobs will be ...
The common prefix between the two most dissimilar strings is the longest common prefix for an array of strings. For instance, there is no common prefix in the array apple, ape, and zebra since the two most distinct strings in the array, “ape” and “zebra,” do not share any initial letters. In this article, we will learn about the ...
Problem Statement Given the array $ar[]$ of size, $n$ has positive and negative integers. From the array $ar[]$, find the length of the largest subarray having a 0 sum. As we have to find the length of the largest subarray. So, first of all, it is required to understand what is a subarray Subarray :A ...
Problem Statement k number of arrays are given, the task is to merge all the given integer arrays in such a manner that the resultant array is sorted in the runtime only. Note: arrays are of equal size. Example: Output: Explanation The array at the output is sorted by combining elements of all the three ...