CSE Company Interview Questions

Piyush is lost in a magical park which contains N rows and M columns.In order to get out of park safely and return home, he needs atleast K amount of strength.Given a N by M pattern, your task is to find weather Piyush can ever escape the park. Piyush enters the park with strength S. The park is filled with some obstacles denoted by ‘.’ , some magical beans denoted by ‘* ’ and some blockades denoted as ‘#’. If he encounters an obstacle (.) , strength decreases by 2. If he encounters a magic bean ('*   ') , his strength increases by 5. Piyush can only walk row wise, so he starts from left of a row and moves towards right and he does this for every row. However when he encounters a blockade (#) , he cannot go any further in his current row and simply jumps to the start of a new line without losing any strength. Piyush requires a strength of 1 for every step. His strength should always be greater than K while traversing or else Piyush will get lost. Assume that Piyush can shift im...

Given an n x m matrix, where every row and column is sorted in increasing order, and a number x . Find if element x is present in the matrix or not. Input Format First line consists of two space separated integers N and M, denoting the number of element in a row and column respectively. Second line of each test case consists of N*M space separated integers denoting the elements in the matrix in row major order. Third line of each test case contains a single integer x, the element to be searched. Constraints 1 <= N,M <= 30 0 <= A[i] <= 100 Output Format Print 1 if the element is present in the matrix, else 0. Sample Input 3 3 3 30 38 44 52 54 57 60 69 62 Sample Output 0 Explanation Search the element in the sorted matrix. If the element is present print 1 otherwise print 0. In the sample input,in first case 62 is not present in the matrix so 0 is printed. Similarly, for second case 55 is present in the matrix so 1 is printed. Java Code: IDE Code:  https://ide.geeksforgee...

Take as input a 2-d array.Print the 2-D array in sprial form clockwise. Input Format Two integers M(row) and N(colomn) and further M * N integers(2-d array numbers). Constraints Both M and N are between 1 to 10. Output Format All M * N integers separated by commas with 'END' written in the end(as shown in example). Sample Input 4 4 11 12 13 14 21 22 23 24 31 32 33 34 41 42 43 44 Sample Output 11, 12, 13, 14, 24, 34, 44, 43, 42, 41, 31, 21, 22, 23, 33, 32, END Explanation For spiral level clockwise traversal, Go for first row-> last column ->last row -> first column and then do the same traversal for the remaining matrix. Java Code: IDE Code:  https://ide.geeksforgeeks.org/CeeHFpOMwa /* Amit Kumar 07-12-2020 IDE Code: https://ide.geeksforgeeks.org/CeeHFpOMwa */ package array ; import java.util.Scanner ; public class Array_SpiralPrint { public static Scanner scanner = new Scanner ( System . in ); public static void main ( String [] ar...

PROBLEM : Given an incomplete Sudoku configuration in terms of a 9x9  2-D square matrix (mat[][]) the task to print a solution of the Sudoku. For simplicity you may assume that there will be only one unique solution. Example For the above configuration the solution is 3 1 6 5 7 8 4 9 2 5 2 9 1 3 4 7 6 8 4 8 7 6 2 9 5 3 1 2 6 3 4 1 5 9 8 7 9 7 4 8 6 3 1 2 5 8 5 1 7 9 2 6 4 3 1 3 8 9 4 7 2 5 6 6 9 2 3 5 1 8 7 4 7 4 5 2 8 6 3 1 9 Input: The first line of input contains an integer T denoting the no of test cases. Then T test cases follow. Each test case contains 9*9 space separated values of the matrix mat[][] representing an incomplete Sudoku state where a 0 represents empty block. Output: For each test case in a new line print the space separated values of the solution of the the sudoku. Constraints: 1<=T<=10 0<=mat[]<=9 Example: Input: 1 3 0 6 5 0 8 4 0 0 5 2 0 0 0 0 0 0 0 0 8 7 0 0 0 0 3 1 0 0 3 0 1 0 0 8 0 9 0 0 8 6 3 0 0 5 0 5 0 0 ...

PROBLEM : The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other. Given an integer n, print all distinct solutions to the n-queens puzzle. Each solution contains distinct board configurations of the n-queens’ placement, where the solutions are a permutation of [1,2,3..n] in increasing order, here the number in the ith place denotes that the ith-column queen is placed in the row with that number. For eg below figure represents a chessboard [3 1 4 2]. Input: The first line of input contains an integer T denoting the no of test cases. Then T test cases follow. Each test case contains an integer n denoting the size of the chessboard. Output: For each test case, output your solutions on one line where each solution is enclosed in square brackets '[', ']' separated by a space . The solutions are permutations of {1, 2, 3 …, n} in increasing order where the number in the ith place denotes the ith-co...

PROBLEM : Given a 2D screen, location of a pixel in the screen ie(x,y) and a color(K), your task is to replace color of the given pixel and all adjacent same colored pixels with the given color K. Input: The first line of input contains an integer T denoting the no of test cases. Then T test cases follow. The first line of each test case contains Two integers N and M denoting the size of the matrix. Then in the next line are N*M space separated values of the matrix. Then in the next line are three values x, y and K. Output: For each test case print the space separated values of the new matrix. Constraints: 1<=T<=10 1<=M[][]<=100 Example: Input: 2 3 4 0 1 1 0 1 1 1 1 0 1 2 3 0 1 5 2 2 1 1 1 1 0 1 8 Output: 0 5 5 0 5 5 5 5 0 5 2 3 8 8 8 8 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<iostr...

PROBLEM : Consider a rat placed at (0, 0) in a square matrix m[][] of order n and has to reach the destination at (n-1, n-1). Your task is to complete the function which returns a sorted array of strings denoting all the possible directions which the rat can take to reach the destination at (n-1, n-1). The directions in which the rat can move are 'U'(up), 'D'(down), 'L' (left), 'R' (right). For example 1 0 0 0 1 1 0 1 1 1 0 0 0 1 1 1 For the above matrix the rat can reach the destination at (3, 3) from (0, 0) by two paths ie DRDDRR and DDRDRR when printed in sorted order we get DDRDRR DRDDRR. Input: The first line of input contains an integer T denoting the no of test cases. Then T test cases follow. Each test case contains two lines. The first line contains an integer n denoting the size of the square matrix. The next line contains n*n space separated values of the matrix m where 0's represents blocked paths and 1 represent valid path...

PROBLEM : In MATLAB, there is a very useful function called 'reshape', which can reshape a matrix into a new one with different size but keep its original data. You're given a matrix represented by a two-dimensional array, and two positive integers r and c representing the row number and column number of the wanted reshaped matrix, respectively. The reshaped matrix need to be filled with all the elements of the original matrix in the same row-traversing order as they were. If the 'reshape' operation with given parameters is possible and legal, output the new reshaped matrix; Otherwise, output the original matrix. Example 1: Input: nums = [[1,2],  [3,4]] r = 1, c = 4 Output: [[1,2,3,4]] Explanation: The row-traversing of nums is [1,2,3,4]. The new reshaped matrix is a 1 * 4 matrix, fill it row by row by using the previous list. Example 2: Input: nums = [[1,2],  [3,4]] r = 2, c = 4 Output: [[1,2],  [3,4]] Explanation: There is no way ...

PROBLEM : Given a MxN matrix, count the number of squares in the matrix. Input: The first line of input contains an integer T denoting the no of test cases. Then T test cases follow. Each test case contains two space seperated integers M and N, denoting the size of the Matrix. Output: For each test output a single integer denoting the total number of squares. Constraints: 1<=T<=102 1<=M,N<=10^4 Example: Input: 2 2 2 4 3 Output: 5 20 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<iostream> using namespace std; int main() { int t ; cin>>t ; while(t--){    int r,c ;    cin>>r>>c ;      long long num=0 ;    while(r&&c){        num+=r*c ;        r-- ; ...

PROBLEM : Given a N X N  matrix Matrix[N][N] of positive integers.  There are only three possible moves from a cell Matrix[r][c]. 1. Matrix[r+1][c] 2. Matrix[r+1][c-1] 3. Matrix[r+1][c+1] Starting from any column in row 0, return the largest sum of any of the paths up to row N-1. Input: The first line of the 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 order of matrix. Next line contains N*N integers denoting the elements of the matrix in row-major form. Output: Output the largest sum of any of the paths starting from any cell of row 0 to any cell of row N-1. Print the output of each test case in a new line. Constraints: 1<=T<=20 2<=N<=20 1<=Matrix[i][j]<=1000 (for all 1<=i<=N && 1<=j<=N) Example: Input: 1 2 348 391 618 193 Output: 1009 Explanation: In the sample test case, the ...

PROBLEM : You are given an n x n 2D matrix representing an image. Rotate the image by 90 degrees (clockwise). You need to do this in place. Note that if you end up using an additional array, you will only receive partial score. Example: If the array is 1 2 3 4 5 6 7 8 9 Then the rotated array becomes: 7 4 1 8 5 2 9 6 3 Input: The first line contains an integer 'T' denoting the total number of test cases. In each test cases, the first line contains an integer 'N' denoting the size of the 2D square matrix. And in the second line, the elements of the matrix A[][], each separated by a space in row major form. Output: For each test case, print the elements of the rotated array row wise, each element separated by a space. Print the output of each test case in a new line. Constraints: 1 = T = 70 1 = N = 10 1 = A [ i ][ j ] = 100 Example: Input: 2 3 1 2 3 4 5 6 7 8 9 2 56 96 91 54 Output: 7 4 1 8 5 2 9 6 3 91 56 54 96 ---------------------...

PROBLEM : The problem is to count all the possible paths from top left to bottom right of a MxN matrix with the constraints that from each cell you can either move only to right or down. Input: The first line of input contains an integer T denoting the number of test cases. The first line of each test case is M and N, M is number of rows and N is number of columns. Output: Print the number of paths. Constraints: 1 = T = 30 1 = M,N = 10 Example: Input 2 3 3 2 8 Output 6 8 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<iostream> using namespace std; int Number_of_paths(int ,int ) ; int main()  { int t,m,n ; cin>>t ; while(t--) {    cin>>m>>n ;    cout<<Number_of_paths(m,n)<<endl ; } return 0; } int Number_of_paths(int m,int n)...

PROBLEM : Given a matrix M of n*n size, the task is to complete the function which prints its elements in diagonal pattern as depicted below. matrix-diagonal-traversal Input: The first line of input contains an integer denoting the no of test cases. Then T test cases follow. Each test case contains an integer N denoting the size of the square matrix. In the next line are N*N space separated values of the matrix M. Output: For each test case output will be the space separated values of the matrix elements in diagnol form. Constraints: 1<=T<=100 1<=n<=20 Example(To be used only for expected output): Input: 2 3 1 2 3 4 5 6 7 8 9 2 1 2 3 4 Output: 1 2 4 7 5 3 6 8 9 1 2 3 4 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- /*You are required to complete this method */ void printMatrixDiagonal(int mat[MAX][MA...

PROBLEM : Given a binary matrix your task is to complete the function printMat which prints all unique rows of the given matrix. The function takes three arguments the first argument is a matrix M and the next two arguments are row and col denoting the rows and columns of the matrix. Input: The first line of input is an integer T denoting the no of test cases.Then T test cases follow. Each test case consists of 2 lines . The first line of each test case is are two integers row and col denoting the no of rows and columns of matrix . Then in the next line are row*col space separated values of the matrix M. Output: The output will be the unique rows of the matrix separated by space . Note : Dont print new line after each row instead print "$" without quotes . Constraints: 1<=T<=20 1<=row,col<=40 0<=M[ ][ ]<=1 Example: Input 1 3 4 1 1 0 1 1 0 0 1 1 1 0 1 Output 1 1 0 1 $1 0 0 1 $ Explanation Above the matrix of size 3x4 looks like 1 ...