CSE Company Interview Questions

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 : Given a directed graph, find out if a vertex j is reachable from another vertex i for all vertex pairs (i, j) in the given graph. Here reachable mean that there is a path from vertex i to j. The reach-ability matrix is called transitive closure of a graph. Input: First line consists of T test cases. First line of every test case consists of N , denoting number of vertices. Second line consists of N*N spaced integer(Only 0 and 1), denoting the edge b/w i to j. Output: Single line output, print the trasitive closure formed of graph. Constraints: 1<=T<=100 1<=N<=100 Example: Input: 1 4 1 1 0 1 0 1 1 0 0 0 1 1 0 0 0 1 Output: 1 1 1 1 0 1 1 1 0 0 1 1 0 0 0 1 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : (using  Floyd Warshall ) -------------------------------------------------------------------------------- #include<iostream> using namespace std; #define MAX 1000 vo...

PROBLEM : Given a directed graph, a source vertex ‘s’ and a destination vertex ‘d’, print the count of all paths from given ‘s’ to ‘d’. Input: First line consists of T test cases. First line of every test case consists of V and E, denoting the vertices and edges. Second line of every test case consists of 2*E spaced integers denoting the edge between vertices. Third line of every test case consists of S and D. Output: Single line output, print the count of all paths from 's' to 'd'. Constraints: 1<=T<=100 1<=V,E<=10 Example: Input: 1 4 6 0 1 0 2 0 3 2 0 2 1 1 3 2 3 Output: 3 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<iostream> using namespace std; #include <list> class graph {     int v ;     list<int> *adj ;         public : ...

PROBLEM : Consider a directed graph whose vertices are numbered from 1 to n. There is an edge from a vertex i to a vertex j iff either j = i + 1 or j = 3i. The task is to find the minimum number of edges in a path in G from vertex 1 to vertex n. Input:  The first line of input contains an integer T denoting the number of test cases. The description of T test cases follows. Each test case contains a value of n. Output:  Print the number of edges in the shortest path from 1 to n. Constraints: 1<=T<=30 Example:  1<=n <=1000 Example: Input: 2 9 4 Output: 2 2 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<iostream> using namespace std; int main() {     int t ;     cin>>t ;     while(t--)     {         int no ;...

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 : Write a function to print the bredth first traversal for a graph from a given source s. Input: The task is to complete the function BFS which takes 3 arguments an integer denoting the starting node (s) of the bfs travel , a  graph (g)  and an array of visited nodes (vis)  which are initially all set to false . There are multiple test cases. For each test case, this method will be called individually. Output: The function should print the breath first traversal for the graph from the given source. Note : The expected output button always produces BFS starting from node 1. Constraints: 1 <=T<= 100 1 <=Number of  edges<= 100 Example: Input: 1 4 1 2 1 3 1 4 3 5 Output: 1 2 3 4 5    //bfs from node 1 There is  one test cases.  First line of each test case represent an integer N denoting no of edges and then in the next line N pairs of values a and b are fed which denotes there is a unidirectional edge f...

PROBLEM : Given N * M string array of O's and X's Return the number of 'X' total shapes. 'X' shape consists of one or more adjacent X's (diagonals not included). Example (1): OOOXOOO OXXXXXO OXOOOXO answer is 1 , shapes are  : (i)     X     X X X X     X     X Example (2): XXX OOO XXX answer is 2, shapes are (i)  XXX (ii) XXX Input: The first line of input takes the number of test cases, T. Then T test cases follow. Each of the T test cases takes 2 input lines. The first line of each test case have two integers N and M.The second line of N space separated strings follow which indicate the elements in the array. Output: Print number of shapes. Constraints: 1<=T<=100 1<=N,M<=50 Example: Input: 2 4 7 OOOOXXO OXOXOOX XXXXOXO OXXXOOO 10 3 XXO OOX OXO OOO XOX XOX OXO XXO XXX OOO Output: 4 6 -------------------------------------------------------------------------------- SIMPLE c++...

PROBLEM : A group of connected 1s forms an island now your task is to complete the method findIslands which returns the no of islands present. The function  takes three arguments the first is the boolean matrix A and then the next two arguments are N and M denoting the size of the matrix A . Input: The first line of input will be the no of test cases T then T test cases follow. The first line of each test case contains Two space separated integers N and M. Then in the next line are the NxM inputs of the matrix A separated by space . Output: The output in the expected output will be the total no of islands present. Constraints: 1<=T<=100 1<=N,M<=50 0<=A[][]<=1 Example(To be used only for expected output) : Input 1 3 3 1 1 0 0 0 1 1 0 1 Output 2 Explanation The graph will look like 1 1 0 0 0 1 1 0 1 Here  two islands will be formed First island will be formed by elements { A[0][0] ,  A[0][1], A[1][2], A[2][2] } Sec island wil...

PROBLEM : Given a directed graph you need to complete the function topoSort which returns an array having the topologically sorted elements of the array and takes two arguments . The first argument is the Graph graph represented as adjacency list and the second is the number of vertices V . Note : There can be multiple topological sorts of a Graph.  The driver program that calls your function doesn't match your output element by element, but checks whether the output produced by your function is a valid topological sort or not. Input: The first line of input takes the no of test cases then T test cases follow . Each test case contains two lines . The first  line of each test case  contains two integers E and V representing no of edges and the no of vertices . Then in the next line are E  pairs of integers u v representing an edge from u to v in the graph. Output: For each test case output will be 1 if the topological sort is done correctly else it will be 0...

PROBLEM : Given a undirected graph  your task is to complete the method isCycle  to detect if there is a cycle in the undirected graph or not. You should not read any input from stdin/console. There are multiple test cases. For each test case, this method will be called individually. Input (only to be used for Expected Output): The first line of the input contains an integer 'T' denoting the number of test cases. Then 'T' test cases follow. Each test case consists of two lines. Description of  test cases is as follows: The First line of each test case contains two integers 'N' and 'M'  which denotes the no of vertices and no of edges respectively. The Second line of each test case contains 'M'  space separated pairs u and v denoting that there is a bidirectional  edge from u to v . Output: The method should return true if there is a cycle else it should return false. Constraints: 1 <=T<= 100 1<=N,M<=100 0 <=u,v<...

PROBLEM : Given a directed graph  your task is to complete the method isCycle  to detect if there is a cycle in the graph or not. You should not read any input from stdin/console. There are multiple test cases. For each test case, this method will be called individually. Input (only to be used for Expected Output): The first line of the input contains an integer 'T' denoting the number of test cases. Then 'T' test cases follow. Each test case consists of two lines. Description of  test cases is as follows: The First line of each test case contains two integers 'N' and 'M'  which denotes the no of vertices and no of edges respectively. The Second line of each test case contains 'M'  space separated pairs u and v denoting that there is an unidirected  edge from u to v . Output: The method should return true if there is a cycle else it should return false. Constraints: 1 <=T<= 100 1<=N,M<=100 0 <=u,v<= N-1 Exampl...

PROBLEM : Write a function to print the depth first traversal for a graph from a given source s. Input: The task is to complete the function DFS which takes 3 arguments an integer denoting the starting node (s) of the dfs travel , a  graph (g)  and an array of visited nodes (vis)  which are initially all set to false . There are multiple test cases. For each test case, this method will be called individually. Output: The function should print the depth first traversal for the graph from the given source. Note : The expected output button always produces DFS starting from node 1. Constraints: 1 <=T<= 100 1 <=Number of  edges<= 100 Example: Input: 1 4 1 2 1 3 1 4 3 5 Output: 1 2 3 5 4    //dfs from node 1 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- /* You have to complete th...