Coding Guide

Question: Given a String S, reverse the string without reversing its individual words. Words are separated by dots. Example 1: Input: S = i.like.this.program.very.much Output: much.very.program.this.like.i Explanation: After reversing the whole string(not individual words), the input string becomes much.very.program.this.like.i

CheatSheet for Searching Algorithms 1. Linear Search int search(int arr[], int x) { int n = arr.length; for(int i = 0; i < n; i++) { if(arr[i] == x) return i; } return -1; } The time complexity of above algorithm is O(n). 2. Binary Search // Returns location of key, or -1 if not found // Returns location of key, or -1 if not found int BinarySearch(int A[], int l, int r, int key) { int m; while( l <= r ) { m = l + (r-l)/2; if( A[m] == key ) // first comparison return m; if( A[m] < key ) // second comparison l = m + 1; else r = m - 1; } return -1; } The time complexity of Binary Search Theta(log(n)) Auxiliary Space: O(1) in case of iterative implementation. In case of recursive implementation, O(Logn) recursion call stack space. 3. The Ubiquitous Binary Search // Invariant: A[l] <= key and A[r] > key // Boundar...

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...