CSE Company Interview Questions

PROBLEM : Given an array that contains odd number of occurrences for all numbers except for a few elements which are present even number of times. Find the elements which have even occurrences in the array in O(n) time complexity and O(1) extra space. Note: In some array, array contains only odd number then you have to print only a blank new line. 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 elements which have even occurrences in the array. Constraints: 1 = T = 100 1 = N = 200 1 = A[i] = 63 Example: Input 3 11 9 12 23 10 12 12 15 23 14 12 15 5 23 12 56 34 32 4 10 34 10 56 Output 12 23 15 10 --...

PROBLEM : Given a string, find length of the longest substring with all distinct characters.  For example, for input "abca", the output is 3 as "abc" is the longest substring with all distinct characters. Input: The first line of input contains an integer T denoting the number of test cases. The first line of each test case is String str. Output: Print length of smallest substring with maximum number of distinct characters. Note: The output substring should have all distinct characters. Constraints: 1 = T = 100 1 = size of str = 10000 Example: Input 2 abababcdefababcdab geeksforgeeks Output: 6 7 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION :(Using Auxilary arry) -------------------------------------------------------------------------------- #include<iostream> using namespace std; #include<string.h> int Longest_Distinct_characters_string(string ) ; int ma...

PROBLEM : You are given weights and values of N items, put these items in a knapsack of capacity W to get the maximum total value in the knapsack. Note that we have only one quantity of each item, In other words, given two integer arrays val[0..N-1] and wt[0..N-1] which represent values and weights associated with N items respectively. Also given an integer W which represents knapsack capacity, find out the maximum value subset of val[] such that sum of the weights of this subset is smaller than or equal to W. You cannot break an item, either pick the complete item, or don’t pick it (0-1 property). 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 four lines. The first line consists of N the number of items. The second line consists of W, the maximum capacity of the knapsack. In the next  line are N space separated positive integers denoting the values of the N items and in the fourth ...

PROBLEM : Given a singly linked list of 0s and 1s find its decimal equivalent    Input  : 0->0->0->1->1->0->0->1->0    Output : 50   Decimal Value of an empty linked list is considered as 0. Since the answer can be very large, answer modulo 1000000007 should be printed. Input: The task is to complete the method which takes one argument: the head of the linked list. The struct Node has a data part which stores the data and a next pointer which points to the next element of the linked list. There are multiple test cases. For each test case, this method will be called individually. Output: The function should return should decimal equivalent modulo 1000000007 Constraints: 1 <=T<= 200 0 <=N<= 100 Data of Node is either 0 or 1 Example: Input: 2 3 0 1 1   4 1 1 1 0 Output: 3 14 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION :(U...

PROBLEM : Given an array of integers, sort the array according to frequency of elements. For example, if the input array is {2, 3, 2, 4, 5, 12, 2, 3, 3, 3, 12}, then modify the array to {3, 3, 3, 3, 2, 2, 2, 12, 12, 4, 5}. If frequencies of two elements are same, print them in increasing order. 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 each sorted array in a seperate line. For each array its numbers should be seperated by space. Constraints: 1 = T = 70 30 = N = 130 1 = A [ i ] = 60 Example: Input: 1 5 5 5 4 6 4 Output: 4 4 5 5 6 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION :(Using Auxilary arry) -------...

PROBLEM : Given a rope of length n meters, cut the rope in different parts of integer lengths in a way that maximizes product of lengths of all parts. You must make at least one cut. Input: The first line of input contains an integer T denoting the number of test cases. The first line of each test case is length of rope denoted by N. Output: Print the maximizes product of lengths of all parts. Constraints: 1 = T = 50 1 = N = 100 Example: Input: 2 2 5 Output: 1 6 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION :(Using Auxilary arry) -------------------------------------------------------------------------------- #include<iostream> using namespace std; long long Max_rope_cutting(int ) ; int main()  { int t,no ; long long ans ; cin>>t ; while(t--) {    cin>>no ;    ans=Max_rope_cutting(no) ;    cout<<ans<<endl ;...

PROBLEM : Given a binary tree, print nodes of extreme corners of each level but in alternate order. Example: Binary Tree For above tree, the output is 1 2 7 8 31 – print rightmost node of 1st level – print leftmost node of 2nd level – print rightmost node of 3rd level – print leftmost node of 4th level – print rightmost node of 5th level Input: The task is to complete the method which takes one argument, root of the 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 print extreme nodes in alternte manner. Constraints: 1 <=T<= 30 1 <=Number of nodes<= 100 1 <=Data of a node<= 1000 Example: Input: 2 2 1 2 R 1 3 L 7 20 8 L 20 22 R 8 4 L 8 12 R 12 10 L 12 14 R 22 25 R Output: 1 3 20 8 25 10 There are two test casess.  First case represents a t...

PROBLEM : Find the largest rectangular area possible in a given histogram where the largest rectangle can be made of a number of contiguous bars. For simplicity, assume that all bars have same width and the width is 1 unit. Input: The first line contains an integer 'T' denoting the total number of test cases. In each test cases, the first line contains an integer 'N' denoting the size of array. The second line contains N space-separated integers A1, A2, ..., AN denoting the elements of the array. The elements of the array represents the height of the bars. Output: In each seperate line the maximum rectangular area possible from the contigous bars. Constraints: 1<=T<=30 1<=N<=100 1<=A[i]<=1000 Example: Input: 1 7 6 2 5 4 5 1 6 Output: 12 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION :(Using Auxilary arry) -----------------------------------------------------...

PROBLEM : Given an array arr[] of size n where every element is in range from 0 to n-1. Rearrange the given array so that arr[i] becomes arr[arr[i]]. This should be done with O(1) extra space. Input: First line contains an integer denoting the test cases 'T'. Every test case contains an integer value depicting size of array 'N' and N integer elements are to be inserted in the next line with spaces between them. Output: Print all elements of the array after rearranging, each separated by a space, in separate line for each test case. Constraints: 1 <= T <= 70 1 <= N<= 100 1 <= Arr[i] <= 100 Arr[i]<=N Example: Input: 3 2 1 0 5 4 0 2 1 3 4 3 2 0 1 Output: 0 1 3 4 2 0 1 1 0 3 2 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION :(Using Auxilary arry) -------------------------------------------------------------------------------- #include<iostream>...

PROBLEM : Given an array consisting of N numbers your task is to find the minimum sum of the array such that out of 3 consecutive  elments you need to add atleast one. Input: First line consists of T Test cases. Each test case contains 2 lines . The first line consists of a number N specifying the number of elements in an array and the next line contains N elements. Output: Output in a single line minimum sum that can be obtained. Constraints: 1<=T<=100 1<=N<=43 Example: Input: 2 6 1 2 3 6 7 1 12 1 2 3 6 7 1 8 6 2 7 7 1 Output: 4 7 Explanation: For First Test case moving from left to right 3+1 For second Test case moving from left to right 3+1+2+1. When 3 is added next 3 consecutive elements be 6 7 and 1 and so on. -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<iostream> using nam...

PROBLEM : Given an array and a number k where k is smaller than size of array, the task is to find the k’th smallest element in the given array. It is given that all array elements are distinct. Input: First Line of input contains an 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 contains an integer N denoting size of the array. Second line contains N space separated integer denoting elements of the array. Third line of the test case contains an integer K. Output: Corresponding to each test case, print the desired output in a new line. Constraints: 1<=T<=100 1<=N<=1000 K<N Example: INPUT 2 6 7 10 4 3 20 15 3 5 7 10 4 20 15 4 Output: 7 15 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- // can use mearge s...

PROBLEM : Given an integer, the task is to find factorial of the number. 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 number whose factorial is to be found Output: Print the factorial of the number in separate line. Constraints: 1 = T = 100 1 = N = 1000 Example: Input 3 5 10 2 Output 120 3628800 2 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<iostream> using namespace std; #define MAX 10000 void Factorials_of_large_numbers(int ) ; int multiply(int arr[],int ,int ) ; int main()  { int t,no ; cin>>t ; while(t--) {    cin>>no ;    Factorials_of_large_numbers(no) ;    cout<<endl ; } return 0; } void Factorials_of_large_numbers(int no) ...

PROBLEM : For given string ‘str’ of digits, find length of the longest substring of ‘str’, such that the length of the substring is 2k digits and sum of left k digits is equal to the sum of right k digits. Input: The first line of input contains an integer T denoting the number of test cases. The description of T test cases follows. Each test case contains a string str of length N. Output: Print the resultant substring of length 2k such that sum of left k elements is equal to right k elements and if there is no such substring print 0. Constraints: 1 = T = 100 1 = N = 100 0 = k = 100 Example: Input: 2 000000 1234123 Output: 6 4 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<iostream> using namespace std; #include<string.h> int Longest_Even_Length_Substring(string ) ; int max(int ,int )...

PROBLEM : You will be given N number of strings. You have to find the lexicographically smallest string and the lexicographically largest string among these strings. Input: The first line of input contains a single integer T denoting the number of test cases. Then T test cases follow. The first line of each test case consists of N. In the next line are N space separated strings of lower case Latin letters only. Output: Corresponding to each test case, in a new line, print the lexicographically smallest string and the lexicographically largest string among the given strings separated by a single space between them. Constraints: 1 = T = 100 1 = N = 10 1 = Length of each string = 40 Example: Input 3 3 a ab abc 3 a a b 3 z xy t Output a abc a b t z -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<iost...

PROBLEM : Given two strings, one is a text string and other is a pattern string. The task is to print the indexes of all the occurences of pattern string in the text string. For printing, Starting Index of a string should be taken as 1. Note: Strings contain only lower case alphabets. Input: First line of the input contains an integer 'T' denoting the total number of test cases. Then T test cases follow. Each test consists of two lines. First line of each test case contains the text string. Second line of each test case contains the pattern string. Output: Print indexes all the occurences of the pattern strings in the text string in a single line seprated by spaces. Print -1 if no pattern found. Constraints: 1 <= T <= 100 1 <= Sizeof of text String <= 10000 1 <= Sizeof pattern String <= Sizeof text String Example: Input : 2 batmanandrobinarebatfriends bat abcsdu edu Output : 1 18 -1 ----------------------------------------------...

PROBLEM : Given a string and a pattern, Replace all the continuous occurrence of pattern with a single X in the string. For a clear view see the example below. Input: The first line of input contains an integer T denoting the number of test cases. The first line of each test case is string str. The second line of each test case contains a string s,which is a pattern. Output: Print the modified string str. Constraints: 1 = T = 100 1 = size of str,s = 1000 Example: Input 2 abababcdefababcdab ab geeksforgeeks geeks Output XcdefXcdX XforX -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<iostream> using namespace std; #include<string.h> #include<malloc.h> char* Replace_by_X(char *,char *) ; int compare(char *,char *,int ) ; int main()  { int t ; char *str,*patt ; str=(ch...

PROBLEM : Given n non-negative integers in array representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining. For example: Input: arr[]   = {2, 0, 2} Output: 2 Structure is like below |  | |_| We can trap 2 units of water in the middle gap. Input: arr[]   = {3, 0, 0, 2, 0, 4} Output: 10 Structure is like below         | |       | |    |  | |__|_| We can trap "3*2 units" of water between 3 an 2, "1 unit" on top of bar 2 and "3 units" between 2 and 4.  See below diagram also. Below is another example. Input: The first line of input contains an integer T denoting the number of test cases. The description of T test cases follows. Each test case contains an integer N followed by N numbers to be stored in array. Output: Print trap units of water in the middle gap. Constraints: 1<=T<=100 3<=N<=100 0<=Arr[i]<1...

PROBLEM : Given an array A of length N. Determine if there exists an element in the array such that the sum of the elements on its left is equal to the sum of the elements on its right. If there are no elements to the left/right, then the sum is considered to be zero. Formally, find an i, such that, A1+A2...Ai-1 =Ai+1+Ai+2...AN. Input:  The first line contains T, the number of test cases. For each test case, the first line contains N, the number of elements in the array A. The second line for each test case contains N space-separated integers, denoting the array A. Output: For each test case print YES if there exists an element in the array, such that the sum of the elements on its left is equal to the sum of the elements on its right; otherwise print NO in a separate line. Constraints: 1= T = 30 1= N =100000 1= Ai = 2×10000 1= i =N Example: Input 1 4 1 2 3 3 Output: YES --------------------------------------------------------------------------...

PROBLEM : Given an array of integers, sort the array into a wave like array and return it. In other words, arrange the elements into a sequence such that a1 >= a2 <= a3 >= a4 <= a5..... Example Given [1, 2, 3, 4] One possible answer : [2, 1, 4, 3] Another possible answer : [4, 1, 3, 2]  NOTE : If there are multiple answers possible, return the one thats lexicographically smallest. 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 square matrix and next line followed by the value of array. Output: Print the array into wave like array. Constraints: 1 = T = 30 1 = N = 100 0 = A[i] = 100 Example: Input 1 5 5 7 3 2 8 Output 3 2 7 5 8 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include...

PROBLEM : Given an unsorted array of size n. Array elements are in range from 1 to n. One number 'A' from set {1, 2, …n} is missing and one number 'B' occurs twice in array. Find these two numbers. 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 B, the repeating number followed by A which is missing in a single line. Constraints: 1 = T = 40 1 = N = 100 1 = A[i] = N Example: Input 2 2 2 2 3 1 3 3 Output 2 1 3 2 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<iostream> using namespace std; void bu...

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 Kadanes_Algorithm(int [],int ) ; int maxof(int ,int ) ; int main() { in...

PROBLEM : Given a binary matrix, find out the maximum size square sub-matrix with all 1s. 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 and m,n is the number of rows and m is the number of columns. The second line of each test case contains array C[n][m] in row major form. Output: Print maximum size square sub-matrix. Constraints: 1 = T = 100 1 = n,m = 50 0 = C[n][m] = 1 Example: Input: 3 5 6 0 1 0 1 0 1 1 0 1 0 1 0 0 1 1 1 1 0 0 0 1 1 1 0 1 1 1 1 1 1 2 2 1 1 1 1 2 2 0 0 0 0 Output: 3 2 0 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<iostream> using namespace std; #define R 50 #define C 50 int Largest_square(int mat[R][C],int ,int ) ; int min(int ,int ,int ) ; int main()  { int t,r,c,ans,i,j,mat[R]...

PROBLEM : For a given string delete the elements which are appearing more than once consecutively. All letters are of lowercase. Input: The first line contains an integer 'T' denoting the total number of test cases. In each test cases,  a string will be inserted. Output: In each seperate line the modified string should be output. Constraints: 1<=T<=31 1<=length(string)<=100 Example: Input: 1 aababbccd Output: ababcd -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<iostream> using namespace std; #include<string.h> string Consecutive_elements(string ) ; int main()  { int t ; string str ; cin>>t ; while(t--) {    cin>>str ;    str=Consecutive_elements(str) ;    cout<<str<<endl ; } return 0; } stri...

PROBLEM : There are n stairs, a person standing at the bottom wants to reach the top. The person can climb either 1 stair or 2 stairs at a time. Count the number of ways, the person can reach the top (order does not matter). Order does not matter means for n=4 {1 2 1},{2 1 1},{1 1 2} are considered same. Input: The first line contains an integer 'T' denoting the total number of test cases. In each test cases, an integer N will be given. Output: Print number of possible ways to reach Nth stair. Constraints: 1<=T<=1000 1<=N<=100 Example: Input: 1 4 Output: 3 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<iostream> using namespace std; long long Count_nth_stair(long long ) ; int main()  { int t ; long long no ; cin>>t ; while(t--) {    cin>>no ; ...