Programming_hack

A programming is actually a set of instruction which we are actually giving to machine and it perform their task according to that.... 

  Given a NxM matrix containing Uppercase English Alphabets only. Your task is to tell if there is a path in the given matrix which makes the sentence “CODINGNINJA” . There is a path from any cell to all its neighbouring cells. For a particular cell, neighbouring cells are those cells that share an edge or a corner with the cell. Input Format : The first line of input contains two space separated integers N and M, where N is number of rows and M is the number of columns in the matrix. Each of the following N lines contain M characters. Please note that characters are not space separated. Output Format : Print 1 if there is a path which makes the sentence “CODINGNINJA” else print 0. Constraints : 1 <= N <= 1000 1 <= M <= 1000 Time Limit: 1 second Sample Input 1: 2 11 CXDXNXNXNXA XOXIXGXIXJX Sample Output 1: 1 bool hasPath ( vector < vector < char >> & board , int n , int m ) { // Write your code here. } #include < iostream > #include ...

  An island is a small piece of land surrounded by water . A group of islands is said to be connected if we can reach from any given island to any other island in the same group . Given V islands (numbered from 0 to V-1) and E connections or edges between islands. Can you count the number of connected groups of islands. Input Format : The first line of input contains two integers, that denote the value of V and E. Each of the following E lines contains two integers, that denote that there exists an edge between vertex a and b. Output Format : Print the count the number of connected groups of islands Constraints : 0 <= V <= 1000 0 <= E <= (V * (V-1)) / 2 0 <= a <= V - 1 0 <= b <= V - 1 Time Limit: 1 second Sample Input 1: 5 8 0 1 0 4 1 2 2 0 2 4 3 0 3 2 4 3 Sample Output 1: 1 #include < iostream > using namespace std ; int main () { // Write your code here }

  Given an undirected graph G(V,E), find and print all the connected components of the given graph G. Note: 1. V is the number of vertices present in graph G and vertices are numbered from 0 to V-1. 2. E is the number of edges present in graph G. 3. You need to take input in main and create a function which should return all the connected components. And then print them in the main, not inside function. Print different components in new line. And each component should be printed in increasing order (separated by space). Order of different components doesn't matter. Input Format : The first line of input contains two integers, that denote the value of V and E. Each of the following E lines contains two space separated integers, that denote that there exists an edge between vertex a and b. Output Format : Print different components in new line. And each component should be printed in increasing order of vertices (separated by space). Order of different components doesn't matter....

  Given an undirected graph G(V,E), check if the graph G is connected graph or not. Note: 1. V is the number of vertices present in graph G and vertices are numbered from 0 to V-1. 2. E is the number of edges present in graph G. Input Format : The first line of input contains two integers, that denote the value of V and E. Each of the following E lines contains two integers, that denote that there exists an edge between vertex a and b. Output Format : The first and only line of output contains "true" if the given graph is connected or "false", otherwise. Constraints : 0 <= V <= 1000 0 <= E <= (V * (V - 1)) / 2 0 <= a <= V - 1 0 <= b <= V - 1 Time Limit: 1 second Sample Input 1: 4 4 0 1 0 3 1 2 2 3 Sample Output 1: true Sample Input 2: 4 3 0 1 1 3 0 3 Sample Output 2: false Sample Output 2 Explanation The graph is not connected, even though vertices 0,1 and 3 are connected to each other but there isn’t any path from vertices 0,1,3 to vertex...

  Given an undirected graph G(V, E) and two vertices v1 and v2 (as integers), find and print the path from v1 to v2 (if exists). Print nothing if there is no path between v1 and v2. Find the path using BFS and print the shortest path available. Note: 1. V is the number of vertices present in graph G and vertices are numbered from 0 to V-1. 2. E is the number of edges present in graph G. 3. Print the path in reverse order. That is, print v2 first, then intermediate vertices and v1 at last. 4. Save the input graph in Adjacency Matrix. Input Format : The first line of input contains two integers, that denote the value of V and E. Each of the following E lines contains two integers, that denote that there exists an edge between vertex a and b. The following line contain two integers, that denote the value of v1 and v2. Output Format : Print the path from v1 to v2 in reverse order. Constraints : 2 <= V <= 1000 1 <= E <= (V * (V - 1)) / 2 0 <= a <= V - 1 0 <= b <...

  You are given an array ‘Arr’ consisting of ‘N’ distinct integers and a positive integer ‘K’. Find out Kth smallest and Kth largest element of the array. It is guaranteed that K is not greater than the size of the array. Example: Let ‘N’ = 4, ‘Arr’ be [1, 2, 5, 4] and ‘K’ = 3. then the elements of this array in ascending order is [1, 2, 4, 5]. Clearly, the 3rd smallest and largest element of this array is 4 and 2 respectively. Input format: The first line of input contains an integer ‘T’ denoting the number of test cases. The next 2*T lines represent the ‘T’ test cases. The first line of each test case contains two space-separated integers ‘N’ and ‘K’ respectively. The second line of the test case contains ‘N’ space-separated integers representing elements of the array ‘Arr’. Output format : For each test case, print a line consisting of two space-separated integers that represent the Kth smallest and Kth largest elements of the array. Note: You do not need to print anythin...

  For a given integer array/list 'ARR' of size 'N' containing all distinct values, find the total number of 'Inversions' that may exist. An inversion is defined for a pair of integers in the array/list when the following two conditions are met. A pair ('ARR[i]', 'ARR[j]') is said to be an inversion when: 1. 'ARR[i] > 'ARR[j]' 2. 'i' < 'j' Where 'i' and 'j' denote the indices ranging from [0, 'N'). Input format : The first line of input contains an integer 'N', denoting the size of the array. The second line of input contains 'N' integers separated by a single space, denoting the elements of the array 'ARR'. Output format : Print a single line containing a single integer that denotes the total count of inversions in the input array. Note: You are not required to print anything, it has been already taken care of. Just implement the given function. Constraints : ...

  You are given weights and values of N items. You have to select and put these selected items in a knapsack of capacity W. Select the items in such a way that selected items give the maximum total value possible with given capacity of the knapsack. Note:  You are allowed to break the items in parts. Input Format: The first line of input contains two space separated integers, that denote the value of N and W. Each of the following N lines contains two space separated integers, that denote value and weight, respectively, of the N items. Constraints: 1 <= N = 2*10^5 1 <= W <= 10^9 1 <= value, weight <= 10^5 Time Limit: 1 sec Output Format: Print the maximum total value upto six decimal places. Sample Input 1: 4 22 6 4 6 4 4 4 4 4 Sample Output 1: 20.000000 Explanation: The total weight of all the items is 16 units, which is less than the total capacity of knapsack, i.e 22 units. Hence, we will add all the items in the knapsack and total value will be 20 units....

  You are given a string of length N. You need to reverse the string word by word. There can be multiple spaces between two words and there can be leading or trailing spaces but in the output reversed string you need to put a single space between two words, and your reversed string should not contain leading or trailing spaces. For example : If the given input string is " Welcome to Coding Ninjas", then you should return "Ninjas Coding to Welcome" as the reversed string has only a single space between two words and there is no leading or trailing space. Input Format : The first line of input contains a single integer T, representing the number of test cases or queries to be run. Then the T test cases follow. The first and only one of each test case contains a string that you need to reverse word by word. Output Format : For every test case, print the reversed string such that there should be only one space between two strings and there should not be any traili...

  You are given a string ‘S’, you need to find the length of the longest substring that contains at most two distinct characters. Note: A string ‘B’ is a substring of a string ‘A’ if ‘B’ that can be obtained by deletion of, several characters(possibly none) from the start of ‘A’ and several characters(possibly none) from the end of ‘A’. Follow up : Can you try to solve this problem in O(N) time and O(1) space. Example : If ‘S’ = “ninninja” Then, “ninnin” is the longest substring that contains at most two distinct characters. We will print the length of this substring which is equal to 6. Input Format : The first line contains a single integer ‘T’ denoting the number of test cases, then each test case follows: The first line of each test case contains a string ‘S’, denoting the input string. Output Format : For each test case, print the length of the longest substring containing at most two distinct characters. Output for each test case will be printed in a separate line. Note :...