Programming_hack

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

  You are given a sorted array ARR consisting of N integers and an integer 'X'. You need to find the first and last position of occurrence of X in the array. Note: 1. The array follows 0-based indexing, so you need to return 0-based indices. 2. If X is not present in the array, return “-1 -1”. 3. If X is only present once in the array, the first and last position of its occurrence will be the same. Follow Up: Try to solve the problem in O(log(N)) time complexity. Input Format: The first line contains the integer N, denoting the size of the sorted array. The second line contains N space-separated integers denoting the array elements. The third line contains the value X, whose first and last position of occurrence you need to find. Output Format: The only line of output should contain two space-separated integers, where the first and second integer will be the first and the last position of occurrence of X, respectively, in the array. Note: Just implement the given function. Yo...

  You are given with an integer k and an array of integers that contain numbers in random order. You have to find k largest numbers from given array. You need to save them in an array and return it. Note: 1. Time complexity should be O(n * logk) and space complexity should not be more than O(k). 2. Order of elements in the output is not important. Input Format: The first line of input contains an integer, that denotes the value of the size of the array. Let us denote it with the symbol N. The following line contains N space separated integers, that denote the value of the elements of the array. The following contains an integer, that denotes the value of k. Output Format : The first and only line of output contains k largest elements. Constraints: Time Limit: 1 sec Sample Input 1: 13 2 12 9 16 10 5 3 20 25 11 1 8 6 4 Sample Output 1: 12 16 20 25 #include< bits/stdc++.h > using namespace std ; vector < int > kLargest ( int arr [], int n , int k ) { // Write...

  Given an array, print the Next Greater Element (NGE) for every element. The Next greater Element for an element x, is the first greater element on right side of x in the array. Elements for which no greater element exist, consider next greater element as -1. Input format : Line 1 : Size of input array Line 2 : Array elements (separated by space) Constraints: Time Limit: 1 second Size of input array lies in the range: [1, 1000000] Sample Input 5 3 8 1 2 0 Sample Output 8 -1 2 -1 -1 #include < vector > #include< bits/stdc++.h > vector < int > nextGreaterElement ( vector < int > input ) { // Write your code here vector < int > ans ; stack < int > st ; for ( int i = input . size ()- 1 ; i >= 0 ; i --){ if ( st . empty ()) } }

  An integer matrix of size (M x N) has been given. Find out the minimum cost to reach from the cell (0, 0) to (M - 1, N - 1). From a cell (i, j), you can move in three directions: 1. ((i + 1), j) which is, "down" 2. (i, (j + 1)) which is, "to the right" 3. ((i+1), (j+1)) which is, "to the diagonal" The cost of a path is defined as the sum of each cell's values through which the route passes.  Input format : The first line of the test case contains two integer values, 'M' and 'N', separated by a single space. They represent the 'rows' and 'columns' respectively, for the two-dimensional array/list. The second line onwards, the next 'M' lines or rows represent the ith row values. Each of the ith row constitutes 'N' column values separated by a single space. Output format : Print the minimum cost to reach the destination. Constraints : 1 <= M <= 10 ^ 2 1 <= N <= 10 ^ 2 Time Limit: 1 sec Samp...