CSE Company Interview Questions

PROBLEM : Given a string, your task is to find the number of patterns of form 1[0]1 where [0] represents any number of zeroes (minimum requirement is one 0) there should not be any other character except 0 in the [0] sequence. Input: The first line contains T denoting the number of testcases. Then follows description of testcases. Each case contains a string. Output: For each test case, output the number of patterns. Constraints: 1<=T<=20 1<=Length of String<=2000 Example: Input: 2 100001abc101 1001ab010abc01001 Output: 2 2 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<iostream> using namespace std; #include<string.h> int PatternCount(string ) ; int main() { int t ; string str ; cin>>t ; while(t--){    cin>>str ;    cout<<Pattern...

PROBLEM : Given a number n, Write a program that generates and prints all binary numbers with decimal values from 1 to n. 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. Output: Print all binary numbers with decimal values from 1 to n in a single line. Constraints: 1 = T = 100 1 = N = 500 Example: Input 2 2 5 Output 1 10 1 10 11 100 101 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<iostream> using namespace std; #include<queue> int main() { int t,no ; cin>>t ; while(t--) {    cin>>no ;    queue<int> q ;    q.push(1) ;      while(no--)    {        int curr=q.front() ;       ...

PROBLEM : Manoj, Vinoj and Jegan are the famous coders of TCE. One fine day Vinoj and Jegan challenge Manoj to solve a puzzle. That is Vinoj will select one string A. Similarly Jegan will choose one string B with the same size. You need to help Manoj to find the longest subsequence X of a string A which is a substring Y of a string B. Example A : ABCD B : BACDBDCD The answer would be 3 as because 'ACD' is the longest subsequence of A which is also a substring of B. Input: The first line of input contains an integer T. Then T test cases follow. Each test case contains two space separated strings A and B. Output: For each test case in a new line print the required output. Constraints: 1<=T<=12 1<=Length of strings <=100 Example: Input: 2 ABCD BACDBDCD A A Output: 3 1 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : ----------------------------------------------------------------...

PROBLEM : A sorted array A[ ] with distinct elements is rotated at some unknown point, the task is to find the minimum element in it. Expected Time Complexity: O(Log 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 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 minimum element in the array. Constraints: 1 = T = 100 1 = N = 500 1 = A[i] = 1000 Example: Input 1 5 4 5 1 2 3 Output 1 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<iostream> using namespace std; #define max 500 int Minimum_eleme...

PROBLEM : Implement a Stack in which you can get min element in O(1) time and O(1) space. Input (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. First line of each test case contains an integer Q denoting the number of queries . A Query Q is of 3 Types (i)   1 x (a query of this type means  pushing 'x' into the stack) (ii)  2 (a query of this type means to pop element from stack and print the poped element) (iii) 3 (a query of this type means to print the minimum element from the stack) The second line of each test case contains Q queries seperated by space. Output: The output for each test case will  be space separated integers having -1 if the stack is empty else the element poped out  or min element from the stack . You are required to complete the three methods push which take one argument an integer 'x' to be pushed into the stack , pop which r...

PROBLEM : Given two array A1[] and A2[], sort A1 in such a way that the relative order among the elements will be same as those are in A2. For the elements not present in A2. Append them at last in sorted order. 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 the number of elements in A1 and N is the number of elements in A2. The second line of each test case contains M elements. The third line of each test case contains N elements. Output: Print the sorted array according order defined by another array. Constraints: 1 = T = 50 1 = M = 50 1 = N = 10 & N = M 1 = A1[i], A2[i] = 1000 Example: Input: 1 11 4 2 1 2 5 7 1 9 3 6 8 8 2 1 8 3 Output: 2 2 1 1 8 8 3 5 6 7 9 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<i...

PROBLEM : Given a binary tree, where every node value is a Digit from 1-9 . Find the sum of all the numbers which are formed from root to leaf paths. For example consider the following Binary Tree.            6                                        /   \                                 3     5                           /   \     \      2    5      4                     /  \                              7    4                         ...

PROBLEM : Given N activities with their start and finish times. Select the maximum number of activities that can be performed by a single person, assuming that a person can only work on a single activity at a time. Note : The start time and end time of two activities may coincide. Input: The first line contains T denoting the number of testcases. Then follows description of testcases. First line is N number of activities then second line contains N numbers which are starting time of activies.Third line contains N finishing time of activities. Output: For each test case, output a single number denoting maximum activites which can be performed in new line. Constraints: 1<=T<=50 1<=N<=1000 1<=A[i]<=100 Example: Input: 1 6 1 3 0 5 8 5 2 4 6 7 9 9 Output: 4 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- ...

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 weights and values related to n items and the maximum capacity allowed for these items. What is the maximum value we can achieve if we can pick any weights any number of times for a total allowed weight of W? Input: The first line of input contains an integer denoting the no of test cases. Then T test cases follow . Each test case contains two integers N and W denoting the no of items and the total allowed weight. In the next two lines are space separated values of the array denoting values of the items (val[]) and their weights (wt[]) respectively. Output: For each test case in a new line print the  maximum value which we can achieve if we can pick any weights any number of times for a bag of size W. Constraints: 1<=T<=100 1<=N, W<=1000 1<=wt[], val[]<=100 Example: Input: 2 2 3 1 1 2 1 4 8 1 4 5 7 1 3 4 5 Output: 3 11 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENT...

PROBLEM : Given an array of n elements, the task is to find the greatest number such that it is product of two elements of given array. If no such element exists, print -1. Input :  A[] = {10, 3, 5, 30, 35} Output:  30 Explanation: 30 is the product of 10 and 3. Input :  A[] = {2, 5, 7, 8} Output:  -1 Explanation: Since, no such element exists. Input :  A[] = {10, 2, 4, 30, 35} Output:  -1 Input :  A[] = {10, 2, 2, 4, 30, 35} Output:  4 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 size of the array. Then in the next line are n space separated values of the array. Output: For each test case in a new line print the required output. Constraints: 1<=T<=100 1<=n<=100 1<=A[]<=100 Example: Input: 2 4 2 5 7 8 6 10 2 2 4 30 35 Output: -1 4 --------------------------------------------------...

PROBLEM : Given a positive integer, return its corresponding column title as appear in an Excel sheet. For example:     1 -> A     2 -> B     3 -> C     ...     26 -> Z     27 -> AA     28 -> AB NOTE: The alphabets are all in uppercase. Input: The first line contains an integer T, depicting total number of test cases. Then following T lines contains an integer N. Output: Print the string corrosponding to the column number. Constraints: 1 = T = 40 1 = N = 10000000 Example: Input 1 51 Output AY -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<iostream> using namespace std; #include <string> #include <algorithm> string Excel_Sheet(int ) ; int main() { int t ; long no ; cin>>t ; whi...

PROBLEM : Given a positive integer n, find if it can be expressed as xy where y > 1 and x > 0 and x and y both are both integers. Input: The first line of input contains an integer T denoting the no of test cases. Then T test cases follow . Each test cases contains an integer N. Output: For each test case in a new line print 1 if the number can be expressed as  xy else print 0. Constraints: 1<=T<=1000 1<=n<=100 Example: Input: 2 8 5 Output: 1 0 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<iostream> using namespace std; #include<math.h> bool expressedXY(int ) ; int main() {     int t,no ;     cin>>t ;     while(t--)     {         cin>>no ;         cout<<(expressedXY(n...

PROBLEM : Given two arrays of equal size n and an integer k. The task is to permute both arrays such that sum of their corresponding element is greater than or equal to k i.e A[i] + B[i] >= k. Examples: Input : A[] = {2, 1, 3},         B[] = { 7, 8, 9 },         k = 10. Output : 1 Permutation  A[] = { 1, 2, 3 } and B[] = { 9, 8, 7 } satisfied the condition A[i] + B[i] >= K. Input : A[] = {1, 2, 2, 1},         B[] = { 3, 3, 3, 4 },         k = 5. Output : 0 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 three lines.The first line of input contains two integers n and k . Then in the next two lines are space separated values of the array A and B. Output: For each test case in a new  line print the required answer. Constraints: 1<=T<=100 1<=n,k<=200 Example: Input: 2 3...

PROBLEM : Given two arrays, A and B, of equal size n, the task is to find the minimum value  of A[0] * B[0] + A[1] * B[1] +…+ A[n-1] * B[n-1], where shuffling of elements of arrays A and B is allowed. Examples: Input : A[] = {3, 1, 1} and B[] = {6, 5, 4}. Output : 23 Minimum value of S = 1*6 + 1*5 + 3*4 = 23. Input : A[] = { 6, 1, 9, 5, 4 } and B[] = { 3, 4, 8, 2, 4 } Output : 80. Minimum value of S = 1*8 + 4*4 + 5*4 + 6*3 + 9*2 = 80. Input: The first line of input contains an integer denoting the no of test cases. Then T test cases follow. Each test case contains three lines. The first line of input contains an integer N denoting the size of the arrays. In the second line are N space separated values of the array A[], and in the last line are N space separated values of the array B[]. Output: For each test case in a new line print the required result. Constraints: 1<=T<=100 1<=N<=50 1<=A[]<=20 Example: Input: 2 3 3 1 1 6 5 4 5 6 1 9 ...

PROBLEM : Given a positive integer N, check if N is a power of 2. Input: The first line contains 'T' denoting the number of test cases. Then follows description of test cases. Each test case contains a single positive integer N. Output: Print "YES" if it is a power of 2 else "NO". (Without the double quotes) Constraints: 1<=T<=100 0<=N<=10^18 Example: Input : 2 1 98 Output : YES ?NO Explanation:  (2^0 == 1) -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<iostream> using namespace std; int main()  { long long t,no,x=2,flag=0 ; cin>>t ; while(t--) {      cin>>no ;    x=2 ;flag=0 ;    if(no==1)        { cout<<"YES"<<endl ;            flag=1 ;} ...

PROBLEM : Given a Binary Tree having positive and negative nodes, the task is to find maximum sum level in it. Examples: Input :           4                     /   \                   2    -5                  / \     / \               -1   3 -2  6 Output: 6 Explanation : Sum of all nodes of 0'th level is 4 Sum of all nodes of 1'th level is -3 Sum of all nodes of 0'th level is 6 Hence maximum sum is 6 Input :       1                /   \              2      3            /  \      \           4    5      8       ...

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