The Knapsack problem is a class of optimization problems in which we have to find the maximal answer among all the various possibilities given in the question. There are three types of knapsack problems $i.e.$ 0-1 Knapsack, Fractional Knapsack, and Unbounded Knapsack. In this article, we will be seeing the fractional knapsack Problem in detail. ...
Problem Statement Given a binary tree, and two values v1 and v2, find the lowest common ancestor of nodes with their values as v1 and v2. Where the lowest common ancestor of two nodes (Node1 and Node2) is the deepest node of which Node1 and Node2 are descendants. Note that here we consider that a node is the descendant of itself also. Examples Example 1 – Input ...
A Queue is an abstract linear data structure serving as a collection of elements that are inserted (enqueue operation) and removed (dequeue operation) according to the First in First Out (FIFO) approach. Takeaways Introduction to Queue A queue is a linear sequence of items arranged in an ordered fashion. It is based on the FIFO (First In First Out) i.e.i.e. item can only be inserted at ...
Problem Statement Given a singly linked list, use the merge sort algorithm to sort the list in the ascending order of their node’s values. Example Input Output Example Explanation The nodes in the input are not arranged in any particular order, while they are arranged in ascending order of their value in the output. Constraints ...
Problem Statement Given a root node of a binary tree, print its level order traversal in spiral order. Example InputLet’s assume we have the following binary tree – Note that only the address of the root node is provided as the input. Output Example Explanation The simple level order traversal of the tree is – ...
A bipartite graph (also referred to as a bigraph), is a graph whose vertices can be segregated into two disjoint sets such that no two vertices in the same set have an edge between them. They are equivalent to two-colorable graphs (a graph that can be colored with two colors such that no two adjacent ...
Problem Statement Partitioning of any string ss is considered to be palindrome partitioning if every substring of the partition is a palindrome. In this problem, you have been given a string ss and you need to determine the fewest cuts needed for a palindrome partitioning of the given string. Examples Example 1 Input : abaaabOutput : Explanation : abaaab can be partitioned into a|baaab. It can be shown ...
Postfix notation (also known as Reverse Polish Notation) is a way to represent an expression, where operators follow their corresponding operands. Evaluating an expression represented as postfix notation can easily be done using the stack data structure. Scope Takeaways Introduction Postfix notation is one of the few ways to represent algebraic expressions. It is used ...
What is N Queen Problem? The N-Queen is the problem of placing n queens on a chessboard of dimensions $n\times n$ such that no queen can attack another queen in a single move. Problem Statement We need to check if there exists such an arrangement of n queens and if it exists then print the ...
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 ...