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<<PatternCount(str)<<e

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() ;        q.pop() ;              cout<<curr<<" " ;        int Curr=curr

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                               There are 4 leaves, hence 4 root to leaf paths:   Path                      Number   6->3->2                   632   6->3->5->7                6357   6->3->5->4                6354   6->5>4                    654   Answer = 632 + 6357 + 6354 + 654 = 13997 Input: The task is to complete the method which takes one argument, root of Binary Tree. The 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 meth

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 will be formed by

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++ IMPLEMENTATIO

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