Coding Guide

The Longest Increasing Subsequence (LIS) problem is to find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order. For example, the length of LIS for {10, 22, 9, 33, 21, 50, 41, 60, 80} is 6 and LIS is {10, 22, 33, 50, 60, 80}. More Examples: Input : arr[] = {3, 10, 2, 1, 20} Output : Length of LIS = 3 The longest increasing subsequence is 3, 10, 20 Input : arr[] = {3, 2} Output : Length of LIS = 1 The longest increasing subsequences are {3} and {2} Input : arr[] = {50, 3, 10, 7, 40, 80} Output : Length of LIS = 4 The longest increasing subsequence is {3, 7, 40, 80} Code: import java.util.*; import java.lang.*; import java.io.*; class LongestIncreasingSeq { public static void main (String[] args) { Scanner sc=new Scanner(System.in); int t=sc.nextInt(); for(int y=0;y<t;y++) { int n=sc.nextInt(); int arr[]=new int[n]; int L[]=new int[n]; for(int i=0;i<n;i++) ...

Problem Statement: Given an array and an integer k, find the maximum for each and every contiguous subarray of size k. Input: The first line of input contains an integer T denoting the number of test cases. The description of T test cases follows. The first line of each test case contains a single integer 'N' denoting the size of array and the size of subarray 'k'. The second line contains 'N' space-separated integers A1, A2, ..., AN denoting the elements of the array. Output: Print the maximum for every subarray of size k. Constraints: 1 ≤ T ≤ 100 1 ≤ N ≤ 100 1 ≤ k ≤ N 0 ≤A[i]<1000 Example: Input: 2 9 3 1 2 3 1 4 5 2 3 6 10 4 8 5 10 7 9 4 15 12 90 13 Output: 3 3 4 5 5 5 6 10 10 10 15 15 90 90 Video Tutorial  Code:   import java.util.*; import java.lang.*; import java.io.*; class Subarray { public static void main (String[] args) { Scanner sc=new Scanner(System.in); int t=sc.nextInt(); for(int u=0;u<t;u++) { int...

Problem Statement: Given a  Directed and Acyclic Graph  having  N N  vertices and  M M  edges, print topological sorting of the vertices. Input: First line consists of two space separated integers denoting  N N  and  M M . Each of the following  M M  lines consists of two space separated integers  X X  and  Y Y  denoting there is an from  X X  directed towards  Y Y . Output: Print  N N  space separated integers denoting the topological sort, if there are multiple ordering print the lexicographically smallest one. Constraints: 1 ≤ N ≤ 10 1 ≤ N ≤ 10 1 ≤ M ≤ 20 1 ≤ M ≤ 20 1 ≤ X , Y ≤ N Code: import java.util.*; import java.io.*; class TestClass {     public static void main(String args[] ) throws Exception {         Scanner sc=new Scanner(System.in);         int n=sc.nextInt();         int m=...

Following is detailed algorithm. 1.1 Create an empty stack 2.1 Do following while root is not NULL a) Push root's right child and then root to stack. b) Set root as root's left child. 2.2 Pop an item from stack and set it as root. a) If the popped item has a right child and the right child is at top of stack, then remove the right child from stack, push the root back and set root as root's right child. b) Else print root's data and set root as NULL. 2.3 Repeat steps 2.1 and 2.2 while stack is not empty. Code: import java.util.ArrayList; import java.util.Stack; // A binary tree node class Node { int data; Node left, right; Node(int item) { data = item; left = right; } } class BinaryTree { Node root; ArrayList<Integer> list = new ArrayList<Integer>(); // An iterative function to do postorder traversal // of a given binary tree ArrayList<Integer> postOrderIterative(Node node) { Stack<N...

Problem Statement: Given a string  S  consisting only of opening and closing curly brackets  '{'  and  '}'  find out the minimum number of reversals required to make a balanced expression. Input The first line of input contains an integer  T  denoting the number of test cases. Then  T  test cases follow.  The first line of each test case contains a string  S  consisting only of  {  and  } . Output Print out minimum reversals required to make  S  balanced.If it cannot be balanced, then print  -1 . Constraints 1 <=  T  <= 100 0 <    S   <= 50 Examples   Input 4 }{{}}{{{ {{}}}} {{}{{{}{{}}{{ {{{{}}}} Output 3 1 -1 0 Expected Complexity Time :   O(n) Space : O(n) Code: import java.util.*; import java.lang.*; import java.io.*; class GFG { public static void main (String[] args) { Scanner sc=new Scanner(S...

Problem Statement: Given an undirected weighted connected graph, it is required to find the Really Special SubTree in it. The Really Special SubTree is defined as a subgraph consisting of all the nodes in the graph and There is only one exclusive path from a node to every other node. The subgraph is of minimum overall weight (sum of all edges) among all such subgraphs. While creating the Really Special SubTree, start by picking the edge with smallest weight. If there are edges of equal weight available at an instant, then the edge to be chosen first among them is the one with minimum value of sum of the following expression : u + wt + v , where u and v are the node numbers of the corresponding edge and wt is the weight. Even then if there is a collision, choose any one of them. While doing the above, ensure that no cycle is formed while picking up edges. Finally, you need to print the overall weight of the Tree so formed using above rules. Code: im...

Problem Statement: Walter and Jesse's friend Mike had helped them in making Crymeth and hence, they wanted to give him a share. For deciding the share, they both decided to choose one number each,  X  and  Y  and found out that  K th  Highest Common Factor of their two numbers is a good amount of Crymeth that can be given to Mike . Walter and Jesse did this activity for  D  days in total. For each day, find out what quantity of Crymeth they decided to give to Mike. Input: First line contains a natural number  D  - the total number of days. D  lines follow. Each line contains three natural numbers -  X ,  Y  and  K . Output: For each day, print the quantity given to Mike on a new line. If the  K th  HCF of  X  and  Y  does not exist, simply print " No crymeth today " (Without the quotes) Constraints: 1  ≤  D  ≤  10 3 1  ≤  X, Y, K ...