CSE Company Interview Questions

PROBLEM : Given an array arr[] of n integers, construct a Product Array prod[] (of same size) such that prod[i] is equal to the product of all the elements of arr[] except arr[i]. 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 size of array. The second line of each test case contains N input A[i]. Output: Print the Product array prod[]. Constraints: 1 = T = 10 1 = N = 15 1 = C[i] = 20 Example: Input 2 5 10 3 5 6 2 2 12 20 Output 180 600 360 300 900 20 12 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<bits/stdc++.h> using namespace std; int main() { int t ;     cin>>t ;     while(t--)     {         int no ;         cin>>no ...

PROBLEM : Given an string in roman no format (s)  your task is to convert it to integer . Input: The first line of each test case contains the no of test cases T. Then T test cases follow. Each test case contains a string s denoting the roman no. Output: For each test case in a new line print the integer representation of roman number s. Constraints: 1<=T<=100 1<=roman no range<4000 Example: Input 2 V III Output 5 3 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<bits/stdc++.h> using namespace std; int value(char r) {     if (r == 'I')         return 1;     if (r == 'V')         return 5;     if (r == 'X')         return 10;     if (r == 'L')         return 5...

PROBLEM : Given an array and an integer k, find the maximum for each and every contiguous subarray of size k. Input: The first line of 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 size of array and the size of subarray 'k'. The second line contains 'N' space-separated integers A1, A2, ..., AN denoting the elements of the array. Output: Print the maximum for every subarray of size k. Constraints: 1 = T = 200 1 = N = 100 1 = k = N 0 =A[i]<1000 Example: Input: 2 9 3 1 2 3 1 4 5 2 3 6 10 4 8 5 10 7 9 4 15 12 90 13 Output: 3 3 4 5 5 5 6 10 10 10 15 15 90 90 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<bits/stdc++.h> using namespace std; i...

PROBLEM : Given an integer array, you need to find the two elements such that their sum is closest to zero. 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,the size of array Each test case consist of a N integers which are the array elements. Output: Print the two numbers in ascending order such that their sum is closest to zero. Constraints: 1 = T = 100 1 = N = 1000 -100007 = a[i] = 100007 Example: Input 3 3 -8 -66 -60 6 -21 -67 -37 -18 4 -65 2 -24 -73 Output -60 -8 -18 4 -73 -24 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<bits/stdc++.h> using namespace std; int main() { int t ;     cin>>t ;     while(t--)     {         int no ;       ...

PROBLEM : Given an array of positive integers. All numbers occur even number of times except one number which occurs odd number of times. Find the number. Expected Time Complexity: O(n) Expected Auxiliary Space?: Constant 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, print in a new line, the number which occur odd number of times. Constraints: 1 = T = 100 1 = N = 202 1 = A[i] = 1000 Example: Input 1 5 8 4 4 8 23 Output 23 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<io...

PROBLEM : Given an array C[] of integers, find out the maximum difference between any two elements such that larger element appears after the smaller number in C[]. Examples: If array is [2, 3, 10, 6, 4, 8, 1] then returned value should be 8 (Diff between 10 and 2). If array is [ 7, 9, 5, 6, 3, 2 ] then returned value should be 2 (Diff between 7 and 9). 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 size of array. The second line of each test case contains N input C[i]. Output: Print the maximum difference between two element. Otherwise print -1 Constraints: 1 = T = 80 2 = N = 100 1 = C[i] = 500 Example: Input: 2 7 2 3 10 6 4 8 1 5 1 2 90 10 110 Output: 8 109 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<iostream...

PROBLEM : Given a string S, find the longest palindromic substring in S. Substring of string S: S[ i . . . . j ] where 0 = i = j < len(S) Palindrome string: A string which reads the same backwards. More formally, S is palindrome if reverse(S) = S. Incase of conflict, return the substring which occurs first ( with the least starting index ). Input: The first line of input consists number of the test cases. The following T lines consist of a string each. Output: In each separate line print the longest palindrome of the string given in the respective test case. Constraints: 1 =T= 100 1 = str= 100 Example: Input: 1 aaaabbaa Output: aabbaa -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : DP solution O(n^2) -------------------------------------------------------------------------------- #include<bits/stdc++.h> using namespace std; string GetSubString(string str,int start,int end){   ...

PROBLEM : Given a sequence of moves for a robot, check if the sequence is circular or not. A sequence of moves is circular if first and last positions of robot are same. A move can be on of the following.         G - Go one unit     L - Turn left     R - Turn right Input: The first line of input contains an integer T denoting the number of test cases. The first line of each test case is a String in capital letter, sequence of moves consisting only {R,G,L}. Output: Print Given sequence of moves is circular if first and last positions of robot are same. else Given sequence of moves is NOT circular. Constraints: 1 = T = 50 1 = size of string = 200 Example: Input: 3 GLGLGLG GLLG GGGGL Output: Circular Circular Not Circular -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #inclu...

PROBLEM : Given an input stream of n characters consisting only of small case alphabets the task is to find the first non repeating character each time a character is inserted to the stream. Example Flow in stream : a, a, b, c a goes to stream : 1st non repeating element a (a) a goes to stream : no non repeating element -1 (5, 15) b goes to stream : 1st non repeating element is b (a, a, b) c goes to stream : 1st non repeating element is b (a, a, b, c) 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 stream. Then in the next line are x characters which are inserted to the stream. Output: For each test case in a new line print the first non repeating elements separated by spaces present in the stream at every instinct when a character is added to the stream, if no such element is present print -1. Constraints: 1<=T<=200 1<=N<=500 Exa...

PROBLEM : Implement the next permutation, which rearranges numbers into the numerically next greater permutation of numbers. If such arrangement is not possible, it must be rearranged as the lowest possible order ie, sorted in an ascending order. For example: 1,2,3 -> 1,3,2 3,2,1 -> 1,2,3 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 array of next permutation in a separate line. Constraints: 1 = T = 40 1 = N = 100 0 = A[i] = 100 Example: Input 1 6 1 2 3 6 5 4 Output 1 2 4 3 5 6 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<iostream> #include<algorithm> using namespace std; void swap(int *a,int *b) {   ...

PROBLEM : Given an unsorted array of non-negative integers, find a continuous sub-array which adds to a given number. Input: The first line of input contains an integer T denoting the number of test cases. Then T test cases follow. Each test case consists of two lines. The first line of each test case is N and S, where N is the size of array and S is the sum. The second line of each test case contains N space separated integers denoting the array elements. Output: Corresponding to each test case, in a new line, print the starting and ending positions of first such occuring subarray if sum equals to subarray, else print -1. Note: Position of 1st element of the array should be considered as 1. Expected Time Complexity: O(n) Constraints: 1 = T = 100 1 = N = 100 1 = an array element = 200 Example: Input: 2 5 12 1 2 3 7 5 10 15 1 2 3 4 5 6 7 8 9 10 Output: 2 4 1 5 Explanation : In first test case, sum of elements from 2nd position to 4th position is 12 In ...

PROBLEM : Write a program to sort an array of 0's,1's and 2's in ascending order. Input: The first line contains an integer 'T' denoting the total number of test cases. In each test cases, First line is number of elements in array 'N' and second its values. Output: Print the sorted array of 0's, 1's and 2's. Constraints: 1 <= T <= 100 1 <= N <= 100 0 <= arr[i] <= 2 Example: Input : 2 5 0 2 1 2 0 3 0 1 0 Output: 0 0 1 2 2 0 0 1       -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<iostream> using namespace std; void swap(int arr[],int a,int b) {     int temp ;     temp=arr[a] ;     arr[a]=arr[b] ;     arr[b]=temp ; } int main() { int t ; cin>>t ; while(t--) {    int no ;    cin...

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 an array of positive and negative numbers, find if there is a subarray (of size at-least one) with 0 sum. Input: The first line of input contains an integer T denoting the number of test cases. Then T test cases follow. Each test case contains an integer n denoting the size of the array. The next line contains n space separated integers forming the array. Output: Print "Yes" ( without quotes) if there exist a subarray of size at least one with sum equal to 0 or else print "No" ( without quotes). Constraints: 1<=T<=100 1<=n<=10^4 -10^5<=a[i]<=10^5 Example: Input: 2 5 4 2 -3 1 6 5 4 2 0 1 6 Output: Yes Yes         -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<iostream> #include <bits/stdc++.h> #include<unordered_set> using namespac...

PROBLEM : Given an array of 0's and 1's your task is to complete the function maxLen which returns  size of  the  largest sub array with equal number of 0's and 1's . The function maxLen takes 2 arguments .The first argument is the array A[] and second argument is the size 'N' of the array A[] . Input: The first line of the input is T denoting the number of test cases . Then T test cases follow . Each test case contains two lines . The first line of each test case is a number N denoting the size of the array and in the next line are N space separated values of A [ ]. Output: For each test case output in a new line the max length of the subarray . Constraints: 1<=T<=100 1<=N<=100 0<=A[ ] <=1 Example: Input (To be used only for expected output) : 2 4 0 1 0 1 5 0 0 1 0 0 Output 4 2       -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : --------------...

PROBLEM : We are given two sorted array. We need to merge these two arrays such that the initial numbers (after complete sorting) are in the first array and the remaining numbers are in the second array. Extra space allowed in O(1). Example: Input: ar1[] = {10};        ar2[] = {2, 3}; Output: ar1[] = {2}         ar2[] = {3, 10} Input: ar1[] = {1, 5, 9, 10, 15, 20};        ar2[] = {2, 3, 8, 13}; Output: ar1[] = {1, 2, 3, 5, 8, 9}         ar2[] = {10, 13, 15, 20}         -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<bits/stdc++.h> using namespace std ; int main(){ int t ; cin>>t ; while(t--) { int n1,n2 ; cin>>n1>>n2 ; int arr1[n1] ; int arr2[n2] ; for(int i=0;i<n1...