CSE Company Interview Questions

You are given a one dimensional array that may contain both positive and negative integers, find the sum of contiguous subarray of numbers which has the largest sum. For example, if the given array is {-2, -5, 6, -2, -3, 1, 5, -6}, then the maximum subarray sum is 7. Input Format The first line consists of number of test cases T. Each test case consists of two lines. The first line of each testcase contains a single integer N denoting the number of elements for the array A. The second line of each testcase contains N space separated integers denoting the elements of the array. Constraints 1 <= N <= 100000 1 <= t <= 20 -100000000 <= A[i] <= 100000000 Output Format Output a single integer denoting the maximum subarray sum for each testcase in a new line. Sample Input 2 4 1 2 3 4 3 -10 5 10 Sample Output 10 15 Explanation For the first testcase, maximum subarray sum is generated by the entire array - 1+2+3+4 = 10 For the second testcase , maximum subarray sum is generate...

You are given a one dimensional array that may contain both positive and negative integers, find the sum of contiguous subarray of numbers which has the largest sum. For example, if the given array is {-2, -5, 6, -2, -3, 1, 5, -6}, then the maximum subarray sum is 7. Input Format The first line consists of number of test cases T. Each test case consists of two lines. The first line of each testcase contains a single integer N denoting the number of elements for the array A. The second line of each testcase contains N space separated integers denoting the elements of the array. Constraints 1 <= N <= 100000 1 <= t <= 20 -100000000 <= A[i] <= 100000000 Output Format Output a single integer denoting the maximum subarray sum for each testcase in a new line. Sample Input 2 4 1 2 3 4 3 -10 5 10 Sample Output 10 15 Explanation For the first testcase, maximum subarray sum is generated by the entire array - 1+2+3+4 = 10 For the second testcase , maximum subarray sum is generate...

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 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 : The problem is to find shortest distances between every pair of vertices in a given edge weighted directed Graph. 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 an integer V denoting the size of the adjacency matrix  and in the next line are V*V space separated values of the matrix (graph) . Output: For each test case output will be V*V space separated integers where the i-jth integer denote the shortest distance of ith vertex from jth vertex. Constraints: 1<=T<=20 1<=V<=20 -1000<=graph[][]<=1000 Example: Input 2 2 0 25 25 0 3 0 1 43 1 0 6 43 6 0 Output 0 25 25 0 0 1 7 1 0 6 7 6 0 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<iostream> using namespace std; #d...

PROBLEM : Implement wildcard pattern matching with support for '?' and '*'. '?' Matches any single character. '*' Matches any sequence of characters (including the empty sequence). The matching should cover the entire input string (not partial). The function prototype should be: bool isMatch(const char *s, const char *p) Some examples: isMatch("aa","a") ? false isMatch("aa","aa") ? true isMatch("aaa","aa") ? false isMatch("aa", "*") ? true isMatch("aa", "a*") ? true isMatch("ab", "?*") ? true isMatch("aab", "c*a*b") ? false -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- class Solution { public:     bool isMatch(string str, string pattern) {        ...

PROBLEM : Given an array containing both negative and positive integers. Find the contiguous sub-array with maximum sum. 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. The second line contains N space-separated integers A1, A2, ..., AN denoting the elements of the array. Output: Print the maximum sum of the contiguous sub-array in a separate line for each test case. Constraints: 1 = T = 40 1 = N = 100 -100 = A[i] <= 100 Example: Input 2 3 1 2 3 4 -1 -2 -3 -4 Output 6 -1 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<iostream> using namespace std; int maxof(int a,int b){     return a>b?a:b ; } int main() { int...

PROBLEM : Given a rod of length n inches and an array of prices that contains prices of all pieces of size smaller than n. Determine the maximum value obtainable by cutting up the rod and selling the pieces. Input: First line consists of T test cases. First line of every test case consists of N, denoting the size of array. Second line of every test case consists of price of ith length piece. Output: Single line output consists of maximum price obtained. Constraints: 1<=T<=100 1<=N<=100 1<=Ai<=100 Example: Input: 1 8 1 5 8 9 10 17 17 20 Output: 22 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<iostream> using namespace std; #include<limits.h> int RodCutting(int [],int ) ; int maxof(int a,int ) ; int main() { int t ; cin>>t ; while(t--){    int no ; ...

PROBLEM : Given a String, find the longest palindromic subsequence Input: The first line of input contains an integer T, denoting no of test cases. The only line of each test case consists of a string S(only lowercase) Output: Print the Maximum length possible for palindromic subsequence. Constraints: 1<=T<=100 1<=|Length of String|<=1000 Examples: Input: 2 bbabcbcab abbaab Output: 7 4 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<iostream> using namespace std; #include<bits/stdc++.h> int LongestPalindromicSubsequence(string ) ; int max(int ,int ) ; int main() { int t ; cin>>t ; while(t--){    string str ;    cin>>str ;    cout<<LongestPalindromicSubsequence(str)<<endl ; } return 0; } int LongestPalindr...

PROBLEM : Given a string, find the length of the longest substring without repeating characters. Examples: Given "abcabcbb", the answer is "abc", which the length is 3. Given "bbbbb", the answer is "b", with the length of 1. Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring. -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- class Solution { public:     int lengthOfLongestSubstring(string s) {         if(s.length()==0)             return 0 ;                     int map[256] ;         int i, LastVisit, CurrLen,MaxLen ;         CurrLen=1 ;         MaxLen=1 ;   ...

PROBLEM : Given n, how many structurally unique BST's (binary search trees) that store values 1...n? For example, Given n = 3, there are a total of 5 unique BST's.    1         3     3      2      1     \       /     /      / \      \      3     2     1      1   3      2     /     /       \                 \    2     1         2                 3 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION :( Recursive Solution - Complexity O(2^n) ) -------------------------------------------------------------------------------- class Solution { public:     i...

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 : 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 : LOBO is a letter writer and he is  working in shop near post office. He has to write two types of letters which are: Corporate Letters: 12 letters of this type can be written in an hour. Informal Letters: 10 letters of this type can be written in an hour. You are to help him to save time. Given N number of letters, print the minimum number of hours he needs to put for combination of both the letters, so that no time is wasted. Input: The first line will contain T  denoting number of test cases. Then T test cases follow . Each test case will have an integer N. Output: For each test case in a new line , print the minimum number of hours LOBO needs to write the combination of both the letters. If it is NOT possible, print "-1". Constraints: 1=T=100 1=N=150 Example Input: 2 33 36 Output: -1 3 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : ---------------------------------------...

PROBLEM : Given a string, find the minimum number of characters to be inserted to convert it to palindrome. For Example: ab: Number of insertions required is 1. bab or aba aa: Number of insertions required is 0. aa abcd: Number of insertions required is 3. dcbabcd Input: The first line of input contains an integer T denoting the number of test cases. The first line of each test case is S. Output: Print the minimum number of characters. Constraints: 1 = T = 50 1 = S = 40 Example: Input: 3 abcd aba geeks Output: 3 0 3 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<string.h> #include<iostream> using namespace std; int Form_a_palindrome(string ) ; string reverse_string(string ,int ) ; int min(int ,int ,int ) ; int main() { int t ; string str ; cin>>t ; while(t--) { ...

PROBLEM : Given an array of digits (values lie in range from 0 to 9). The task is to count all the sub sequences possible in array such that in each subsequence every digit is greater than its previous digits in the subsequence. Examples: Input : arr[] = {1, 2, 3, 4} Output: 15 There are total increasing subsequences {1}, {2}, {3}, {4}, {1,2}, {1,3}, {1,4}, {2,3}, {2,4}, {3,4}, {1,2,3}, {1,2,4}, {1,3,4}, {2,3,4}, {1,2,3,4} Input : arr[] = {4, 3, 6, 5} Output: 8 Sub-sequences are {4}, {3}, {6}, {5}, {4,6}, {4,5}, {3,6}, {3,5} Input : arr[] = {3, 2, 4, 5, 4} Output : 14 Sub-sequences are {3}, {2}, {4}, {3,4}, {2,4}, {5}, {3,5}, {2,5}, {4,5}, {3,2,5} {3,4,5}, {4}, {3,4}, {2,4} 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 number of digits. The second line contains N space-separated digits. Output: Count of...

PROBLEM : Given a string you have to transform it into a palindrome . In order to acheive that you have to perform exactly k insertion of characters(you cannot perform any more or less number of insertions).Now you have to report whether the string can be converted to a palindrome by making exactly k insertions. Input : The first line contains the number of test cases T. For each test case the first line contains the length of the string N and the number of insertions k. The second line contains the string S. Output : For each test case, print "YES"(without quotes) if the string can be converted to a palindrome making exactly k insertions otherwise "NO"(without quotes). Constraints : 1 = T = 100 0<=k<=100000 The string consists of only lower case English Alphabets (a-z). Example: Input : 2 4 2 abac 5 3 abcde Output : YES NO Explanation : For the first test case abac can be transformed to cabbac (which is palindrome) adding two char...

PROBLEM : A Lucas Number is a number which is represented by the following recurrence Ln = Ln-1 + Ln-2 for n>1 L0 = 2 L1 = 1 Now given a number n your task is to find the nth lucas number. Note: Since the output could be very long take mod 1000000007 Input: The first line of input contains an integer T denoting the no of test cases. Then T test cases follow. Each line contains an integer n. Output: For each test case in a new line print the nth lucas no. Constraints: 1<=T<=100 1<=N<=100 Example: Input: 2 9 3 Output: 76 4 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<iostream> using namespace std; int Lucas_Number(int ) ; int main() { int t,no ; cin>>t ; while(t--) {    cin>>no ;    cout<<Lucas_Number(no)<<endl ; } re...

PROBLEM : Given two strings ‘X’ and ‘Y’, find the length of the longest common substring. Examples : Input : X = "GeeksforGeeks", y = "GeeksQuiz" Output : 5 The longest common substring is "Geeks" and is of length 5. Input : X = "abcdxyz", y = "xyzabcd" Output : 4 The longest common substring is "abcd" and is of length 4. Input : X = "zxabcdezy", y = "yzabcdezx" Output : 6 The longest common substring is "abcdez" and is of length 6. Input: First line of the input contains no of test cases  T,the T test cases follow. Each test case consist of 2 space separated integers A and B denoting the size of string X and Y respectively The next two lines contains the 2 string X and Y. Output: For each test case print the length of longest  common substring of the two strings . Constraints: 1<=T<=30 1<=size(X),size(Y)<=100 Example: Input: 2 6 6 ABCDGH ACDGHR 3...