CSE Company Interview Questions

PROBLEM : Given a linked list, remove the loop in it if present. The task is to complete the function removeTheLoop which takes only one argument the head of the linked list . The function removes the loop in the linked list if present. Input: The first line of input will contain an integer T denoting the no of test cases . Then T test cases follow. Each test case contains 3 lines . The first line of each test case contains an integer N denoting the no of nodes of the linked list . In the next line are N space separated values denoting the values of the linked list. The next line after it contains an integer x denoting that the last node of the linked list pointing to the xth node thus resulting in cycle. Output: Your task is to remove the cycle if present output for each test case will be 1 if the loop is successfully removed from the linked list else 0. Constraints: 1<=T<=50 1<=N<=300 Example(To be used only for expected output) : Input: 2 3 1 3 4 2 ...

PROBLEM : Given a matrix where every cell has some number of coins. Count number of ways to reach bottom right from top left with exactly k coins. We can move to (i+1, j) and (i, j+1) from a cell (i, j). Input: First line contains number of test cases T. For each test case, first line contains the integer value 'k' denoting coins, second line contains an integer 'N' denoting the order of square matrix.Last line contains NXN elements in a single line in row-major order. Output: Number of paths are displayed as output to the user. '0' is displayed when no path is found. Constraints: 1 <=T<= 100 1 <=k<= 20 1 <=N<= 10 1 <=arr[i]<= 100 Example: Input: 2 16 3 1 2 3 4 6 5 9 8 7 12 3 1 2 3 4 6 5 3 2 1 Output: 0 2 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include...

PROBLEM : Given a matrix your task is to find the kth element which is obtained while traversing the matrix spirally. You need to complete the method findK which takes four arguments the first argument is the matrix A and the next two arguments will be n and m denoting the size of the matrix A and then the forth argument is an integer  k denoting the kth element . The function will return the kth element obtained while traversing the matrix spirally. Input: The first line of input is the no of test cases then T test cases follow . The first line of each test case has three integers n,m and k . Then in the next line are n*m space separated values of the matrix A [ ] [ ] . Output: The output for each test case will be the kth obtained element . Constraints: 1<=T<=100 1<=n,m<=20 1<=k<=n*m Example: Input 1 3 3 4 1 2 3 4 5 6 7 8 9 Output 6 Explanation The matrix above will look like 1 2 3 4 5 6 7 8 9 and the 4th element in spiral fashi...

PROBLEM : Traverse a 4x4 matrix of integers in spiral form. Input: The first line of input contains an integer T denoting the number of test cases. First four lines of the test case will contain four elements each. Output: Spiral array will be displayed in a single line. Constraints: 1 <=T<= 100 1 <=N<= 100 Example: Input: 1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Output: 1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<iostream> using namespace std; #define MAX 4 void Spirally_traversing_matrix(int [MAX][MAX]) ; int main()  { int t,i,j; int mat[MAX][MAX] ; cin>>t ; while(t--) {    for(i=0;i<4;i++)        for(j=0;j<4;j++)            cin>>mat[i][j] ; ...

PROBLEM : Given an n x m matrix, where every row and column is sorted in increasing order, and a number x . The task is to find whether element x is present in the matrix or not. Expected Time Complexity : O(m + n) Input: The first line of input contains a single integer T denoting the number of test cases. Then T test cases follow. Each test case consists of three lines. First line of each test case consist 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. Output: Corresponding to each test case, print in a new line, 1 if the element x is present in the matrix, otherwise simply print 0. Constraints: 1<=T<=200 1<=N,M<=30 Example: Input: 2 3 3 3 30 38 44 52 54 57 60 69 62 1 6 18 21 2...

PROBLEM : Given an integer K,return the kth row of pascal triangle. Pascal's triangle is a triangular array of the binomial coefficients formed by summing up the elements of previous row. Example of pascal triangle: 1 1 1 1 2 1 1 3 3 1 for K=3, return 3rd row i.e 1 2 1 Input: The first line contains an integer T,depicting total number of test cases. Then following T lines contains an integer N depicting the row of triangle to be printed. Output: Print the Nth row of triangle in a separate line. Constraints: 1 = T = 50 1 = N = 25 Example: Input 1 4 Output 1 3 3 1 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<iostream> using namespace std; void Pascal_Triangle(int ) ; int main()  { int t,no ; cin>>t ; while(t--) {    cin>>no ;    Pasc...

PROBLEM : Given an square matrix, turn it by 90 degrees in anti-clockwise direction without using any extra space. Input: The first line of input contains a single integer T denoting the number of test cases. Then T test cases follow. Each test case consist of two lines. The first line of each test case consists of an integer N, where N is the size of the square matrix.The second line of each test case contains NxN space separated values of the matrix M. Output: Corresponding to each test case, in a new line, print the rotated array. Constraints: 1 = T = 50 1 = N = 50 Example: Input 1 3 1 2 3 4 5 6 7 8 9 Output 3 6 9 2 5 8 1 4 7 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<iostream> using namespace std; #define MAX 50 void rotate_90deg(int [MAX][MAX],int ) ; int main()  { int t,no,mat[M...

PROBLEM : Given a N x N binary matrix A where each row and column of the matrix is sorted in ascending order , Your task is to complete the function  countZero which returns the count of  number of 0s present in it. Note : Elements in matrix can be either 1 or 0 Input: The first line of input will be the no of test cases then T test cases will follow . The second line of each test case contains two space separated integers M,N denoting the size of the 2 d matrix . Then in the next lines are the space separated values of the matrix A[ ] [ ] . Output: The output will be the number of zeroes present in the square matrix. Constraints: 1<=T<=50 1<=M,N<=50 0<=A[][]<=1 Example: Input 1 3 0 0 0 0 0 1 0 1 1 Output 6 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- /*you are required to complete th...

PROBLEM : Given a square matrix of size M×M . Your task is to calculate the sum of its diagonals. Input: The first line of input contains an integer T denoting the number of test cases. Then T test cases follow. First line of each test case contains a single integer M denoting the size of the square matrix. The next  line contains M*M space separated values of the matrix A. Output: For each test case in a new line print the sum of diagonals of the matrix. Constraints: 1 = T = 20 2 = N = 10 1 = A[i] = 20 Example: Input: 1 3 1 1 1 1 1 1 1 1 1 Output: 6 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<iostream> using namespace std; #define MAX 10 int sum_matrix(int [MAX][MAX],int ) ; int main()  { int t,no,mat[MAX][MAX] ; int i,j ; cin>>t ; while(t--) {    cin...

PROBLEM : A Toeplitz (or diagonal-constant) matrix is a matrix in which each descending diagonal from left to right is constant, i.e., all elements in a diagonal are same. Given a matrix A of order N X M your task is to complete the function isToeplitz which returns true if the matrix is Toeplitz otherwise returns false. 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 of each test case contains two integers N and M denoting the order of the matrix . Then in the next line are N*M space separated values of the matrix. Output: The output for each test case will be 1 if the matrix is Toeplitz else it will be 0. Constraints: 1<=T<=50 1<=N,M<=40 1<=A[][]<=100 Example(To be used only for expected output): Input 2 3 3 6 7 8 4 6 7 1 4 6 2 3 1 2 3 4 5 6 Output 1 0 Explanation (i) The first test case represents a 3x3 matrix which looks lik...

PROBLEM : Your task  is to implement the function strstr. The function takes two strings as arguments(s,x) and  locates the occurrence of the string x in the string s. The function returns and integer denoting  the first occurrence of the string x . 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 strings str and target. Output: For each test case in a new line output will be an integer denoting the first occurrence of the target  string in the string s. Return -1 if no match found. Constraints: 1<=T<=100 1<=length of (s,x)<=1000 Example: Input 2 GeeksForGeeks Fr GeeksForGeeks For Output -1 5 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION :( using KMP algo ) -------------------------------------------------------------------------------- /* The function should...

PROBLEM : Write a function to reverse alternate levels  of a perfect binary tree. For example Given tree:                a             /     \            b       c          /  \     /  \         d    e    f    g        / \  / \  / \  / \        h  i j  k l  m  n  o Modified tree:               a             /     \            c       b          /  \     /  \         d    e    f    g        / \  / \  / \  / \   ...

PROBLEM : Write a program to Validate an IPv4 Address. Your task is  to complete the function isValid which returns 1 if the ip address is valid else returns 0. The function takes a string ip as its only argument . Input: The first line of each test case contains an integer T denoting the number of test case . Then T test cases follow . Each test case takes a string ip. Output: For each test case output will be 1 if the string is a valid ip address else 0. Constraints: 1<=T<=50 1<=length of string <=50 Example(To be used only for expected output) : Input 2 222.111.111.111 5555..555 Output 1 0 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- /* The function returns 1 if IP string is valid else return 0 You are required to complete this method */ bool check(char *,int ,int ) ; int isValid(char *ip)...

PROBLEM : LALU wanted to purchase a laptop so he went to a nearby sale.There were n Laptops at a sale. Laptop with index i costs ai rupees. Some Laptops have a negative price — their owners are ready to pay LALU if he buys their useless Laptop. LALU can buy any Laptop he wants. Though he's very strong, he can carry at most m Laptops, and he has no desire to go to the sale for the second time. Please, help LALU find out the maximum sum of money that he can earn. Input: First line of the input contains T denoting the number of test cases.Each test case has 2 lines : first line has two spaced integers n m. second line has n integers [a0...ai...an-1]. Output: The maximum sum of money that LALU can earn, given that he can carry at most m Laptops. Constraints: 1=T=10 1=n,m=100 -1000=ai=1000 Sample Input: 1 5 3 -6 0 35 -2 4 Sample Output: 8 Explanation: LALU takes the laptops with -6 and -2 and thus earns 8 rupees. ------------------------------------------...

PROBLEM : Given a string S, containing special characters and all the alphabets, reverse the string without affecting the positions of the special characters. Input The first line of input contains an integer T denoting the number of test cases. Then T test cases follow. The first line of each test case contains a case-insensitive string S. Output Print out the reversed string without  affecting special characters. Constraints 1 <= T <= 100 0 <   S  <= 100 Examples Input 3 A&B abc%sld* dakA&*hA@#N Output B&A dls%cba* NAhA&*ka@#d -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<iostream> using namespace std; #include<string.h> string Special_array_reversal(string ) ; int main()  { int t ; string str ; cin>>t ; while(t--) ...

PROBLEM : For a given array find out the GCD of the array. Input: First line of input contains the number of test cases 'T'. First line of test case contain an the size 'N' of array. Second line of test cases contain the array elements. Output: Find GCD and print it in seperate line. Constraints: 1 <= T <= 32 1 <= N <= 20 1 <= Arr[i] <= 100 Example: Input: 1 2 5 10 Output: 5 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<iostream> using namespace std; int GCD_of_Array(int [],int ) ; int findGCD(int ,int ) ; int main()  { int t,arr[20],i,no ; cin>>t ; while(t--) {    cin>>no ;    for(i=0;i<no;i++)        cin>>arr[i] ;          no=GCD_of_Array(arr,no) ;   ...

PROBLEM : Given two numbers represented by two arrays, write a function that returns sum array. The sum array is an array representation of addition of two input arrays. It is not allowed to modify the arrays. Input: The first line of input contains an integer T denoting the number of test cases. The first line of each test case contains two integers M and N separated by a space. M is the size of arr1 and N is the size of arr2. The second line of each test case contains M integers which is the input for arr1. The third line of each test case contains N integers which is the input for arr2. Output: Print the sum list. Constraints: 1 = T = 100 1 = N = M = 1000 0 = arr1[i],arr2[i]= 9 Example: Input: 2 3 3 5 6 3 8 4 2 16 4 2 2 7 5 3 3 7 3 3 6 8 3 0 5 0 6 4 3 3 8 Output: 1 4 0 5 2 2 7 5 3 3 7 3 3 6 8 3 4 8 4 4 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -----------------------------------...

PROBLEM : Given a sorted array which is rotated 'N' times. Find the value of 'N'. Input: The first line contains an integer T, depicting total number of test cases. Then following T lines contains an integer N depicting the size of array and next line followed by the value of array. Output: Print the value of 'n'. Constraints: 1 = T = 40 1 = N = 100 0 = A[i] = 100 Example: Input 2 5 5 1 2 3 4 5 1 2 3 4 5 Output 1 0 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<iostream> using namespace std; int Rotation(int [],int ) ; int main()  { int t,arr[100],i,no ; cin>>t ; while(t--) {    cin>>no ;    for(i=0;i<no;i++)       cin>>arr[i] ;          no=Rotation(arr,no) ;    cout...

PROBLEM : Given a string S of length N, you have to tell whether it is good or not. A good string is one where the distance between any two adjacent character is exactly 1. Consider that the alphabets are arranged in cyclic manner from 'a' to 'z'. Hence, distance between any character 'i' and 'j' will be defined as minimum number of steps it takes 'i' to reach 'j'. Here, character 'i' can start moving clockwise or anti-clockwise in order to reach at position where character 'j' is placed. Your task is simple, where you just need to print "YES" or "NO" (without quotes) depending on whether the given string is Good or not Input: First line of the input contains T denoting the number of test cases.Then T lines follow. Each line contains a string S. Output: Print  the answer for each testcase in a separate line. Constraints: 1=T=50 1=|S|=50 Note: S contains only lowercase alphabetic chara...

PROBLEM : Given a binary tree you need to check if it follows max heap property or not. Input: The task is to complete the method which takes one argument, root of Binary Tree. The struct Node has a data part which stores the data, pointer to left child and pointer to right child.There are multiple test cases. For each test case, this method will be called individually. Output: The function should return true if property holds else false. Constraints: 1 <=T<= 30 1 <=Number of nodes<= 100 1 <=Data of a node<= 1000 Example: Input: 2 2 5 2 L 5 3 R 4 10 20 L 10 30 R 20 40 L 20 60 R Output: 1 0 There are two test cases.  First case represents a tree with 3 nodes and 2 edges where root is 5, left child of 5 is 2 and right child of 5 is 3.   Second test case represents a tree with 4 edges and 5 nodes. -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -----------------------...

PROBLEM : Given a number n, find the smallest number that has same set of digits as n and is greater than n. If x is the greatest possible number with its set of digits, then print “not possible”. Input: The first line of input contains an integer T denoting the number of test cases. The first line of each test case is n,n is the number. Output: Print the greater number than n with same set of digits and if not possible then print "not possible" without double quote. Constraints: 1 = T = 100 1 = n = 100000 Example: Input 2 143 431 Output 314 not possible -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<iostream> using namespace std; #include<string.h> #include <algorithm>  // for sort() function                   char* Next_greater_nu...

PROBLEM : Given an array A[ ] of N positive integers, print out the missing elements in the range [0 - 999].If there are more than one missing, collate them using hyphen ( - ), otherwise just print the number. Example:  Input:   {88 3, 2, 400, 0, 10}  Output:   [ 1 4-9 11-87 89-399 401-999 ] Input The first line of input contains an integer T denoting the number of test cases. Then T test cases follow. The first line of each test case contains a positive integer N, denoting the length of the array A[ ]. The second line of each test case contains a N space separated positive integers, denoting the elements of the array A[ ].   Output Print out the range of missing number or the number itself  separated by space enclosed in square brackets : [ n1 n2 n3-n6 n8-n9 ] Constraints 1 <= T <= 100 0 <   N <= 30 0 <= A[ ] < 1000 Examples Input 3 5 62 8 34 5 332 4 13 0 32 500 5 2 0 9 15 999 Output [ 0-4 6-7 9-...

PROBLEM : Given an array, reverse every sub-array formed by consecutive k elements. Input: The first line of input contains a single integer T denoting the number of test cases. Then T test cases follow. Each test case consist of two lines. The first line of each test case consists of an integer N, where N is the size of array.The second line of each test case contains N space separated integers denoting array elements.The third line of each test case consists of an integer K. Output: Corresponding to each test case, in a new line, print the modified array. Constraints: 1 = T = 100 1 = N = 500 1 = A[i] = 500 Example: Input 1 5 1 2 3 4 5 3 Output 3 2 1 5 4 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<iostream> using namespace std; void Reverse_array_in_groups(int [],int ,int ) ; void reverse(in...

PROBLEM : In a given array A find the maximum value of |Ai – i| – |Aj – j| where i is not equal to j. Input: The first line of input contains a single integer T denoting the number of test cases. Then T test cases follow. Each test case consist of two lines. The first line of each test case consists of an integer N, where N is the size of array.The second line of each test case contains N space separated integers denoting array elements. Output: Corresponding to each test case, in a new line, print the maximum value. Constraints: 1 = T = 100 1 = N = 200 1 = A[i] = 1000 Example: Input 1 5 9 15 4 12 13 Output 12     Explanation a[1]-1 - a[2]-2 = (15-1)-(4-2) = 12 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : --------------------------------------------------------------------------------  #include<iostream> using namespace std; #include<limits.h> int Max_value(i...

PROBLEM : Given an array of distinct elements, Your task is to find the third largest element in it. You have to complete the function thirdLargest which takes two argument . The first argument is the array a[] and the second argument is the size of the array (n). The function returns an integer denoting the third largest element in the array a[]. Input: The first line of input contains an integer T denoting the number of test cases. Then T test cases follow . The first line of each test case is N,N is the size of array.The second line of each test case contains N space separated values of the array a[ ]. Output: Output for each test case will be  the third largest element of the array . Constraints: 1 = T = 100 1 = N = 100 1 = A[ ] = 100 Example(To be used for only expected output): Input: 1 5 2 4 1 3 5 Output: 3 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -----------------------------...