CSE Company Interview Questions

PROBLEM : Write a program to check whether a triangle is valid or not, when the three angles of the triangle are the inputs. A triangle is valid if the sum of all the three angles is equal to 180 degress. Input The first line contains an integer T, total number of testcases. Then follow T lines, each line contains three angles A, B and C of triangle separated by space. Output Display 'YES' or 'NO' if the triangle is Valid or not respectively. Constraints 1 = T = 1000 40 = A,B,C = 180 Example Input 3 30 40 110 45 45 90 180 0 0 Output YES YES NO       -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<iostream> using namespace std ; int main() { int t,a,b,c ; cin>>t ; while(t--) { cin>>a>>b>>c ; if(a+b+c==180) cout<<"YES" ;

PROBLEM : Three numbers A, B and C are the inputs. Write a program to find second largest among three numbers. Input The first line contains an integer T, total number of testcases. Then follow T lines, each line contains three integers A, B and C. Output Display the second largest among A, B and C. Constraints 1 = T = 1000 1 = A,B,C = 1000000 Example Input 3 120 11 400 10213 312 10 10 3 450 Output 120 312 10       -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<iostream> using namespace std ; int main() { int t,a,b,c,secLarg ; cin>>t ; while(t--) { cin>>a>>b>>c ; secLarg=((((a>b)&&(b>c))||((a<b)&&(b<c)))?b:(((b>a)&&(a>c))||((b<a)&&(a<c)))?a:c); cout<<secLarg<<endl ; } return 0 ;

PROBLEM : Given a string consisting of uppercase and lowercase characters, you need to sort uppercase and lowercase letters separately such that if the ith place in the original string had an Uppercase character then it should not have a lowercase character after being sorted and vice versa. 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 length of string. The second line contains a string of length N, consisting of uppercase and lowercase characters. Output: Print T lines consisting of a sorted strings for the particular test case. Constraints: 1 = T = 50 1 = N = 1000 Example: Input: 1 12 defRTSersUXI Output: deeIRSfrsTUX       -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : ---------------------------------------------------------------------

PROBLEM : Given an all upper case string, check if it is a combination of one of the following: 1) R 2) RY 3) RYY Input: First line contains an integer T denoting the number of test cases. Each of the following T lines will contain an upper case string. Output: Print YES if the sequence is correct, NO if not correct. Constraints: 1<=T<=1000 1<=10^5<= Size of String Example: Input: 3 RY RWR RRYY Output: YES NO YES       -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<iostream> using namespace std; #include<string.h> #include<malloc.h> int Subsequence_matching(char *) ; int main()  { int t,ans ; char *str ; str=(char*)malloc(100000*sizeof(char)) ; cin>>t ; while(t--) {    cin>>str ;    ans=Subsequence_matching(str) ;    if(ans)  

PROBLEM : All submissions for this problem are available. If Give an integer N . Write a program to obtain the sum of the first and last digit of this number. Input The first line contains an integer T, total number of test cases. Then follow T lines, each line contains an integer N. Output Display the sum of first and last digit of N. Constraints 1 = T = 1000 1 = N = 1000000 Example Input 3 1234 124894 242323 Output 5 5 5     -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<iostream> using namespace std ; int sum_end_start(int ) ; int main() { int t,no,sum ; cin>>t ; while(t--) { cin>>no ; sum=sum_end_start(no) ; cout<<sum<<endl ; } } int sum_end_start(int no) { int i,r,sum=0 ; i=no ; while(no!=0) { r=no%10 ; if((no==i)||(no/10==0))

PROBLEM : Given a string, eliminate all “b” and “ac” in the string, replace them in-place and iterate over the string once. 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 of length N. Output: Print the resultant substring after removing 'b' and 'ac' from string. Constraints: 1 = T = 200 1 = N = 200 Example: Input: 2 acbac aababc Output: aaac       -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<iostream> using namespace std; #include<string.h> #include<malloc.h> char* Remove_b_ac(char*) ; int main() { int t ; char *str; str=(char*)malloc(100*sizeof(char)) ; cin>>t ; while(t--) {    cin>>str ;    str=Remove_b_ac(str) ;    

PROBLEM : Given a string, the task is to remove all  duplicate characters from the string and print the resultant string.  The order of remaining characters in the output should be same as in the original string. 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 of length N. Output: Print the resultant substring after removing duplicate characters from string. Constraints: 1 = T = 100 1 = N = 100 Example: Input: 2 geeksforgeeks HappyNewYear Output: geksfor HapyNewYr       -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<iostream> using namespace std; #include<string.h> #include<malloc.h> char* Remove_duplicates(char*) ; int main() { int t ; char *str; str=(char*)mallo

PROBLEM : Given a binary string, count number of substrings that start and end with 1. For example, if the input string is “00100101”, then there are three substrings “1001”, “100101” and “101”. Input: The first line contains T denoting the number of testcases. Then follows description of testcases. Each case contains a string containing 0's and 1's. Output: For each test case, output a single line denoting number of substrings possible. Constraints: 1<=T<=100 1<=Lenght of String<=100 Example: Input: 1 10101 Output: 3       -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<iostream> using namespace std; #include<string.h> int Count_Substrings(char *) ; int main()  { int t,count; char str[100] ; cin>>t ; while(t--) {    cin>>str ;    count=0 ;

PROBLEM : Given a string s consisting of lowercase Latin Letters, find the first non repeating character in s. Input: The first line contains T denoting the number of testcases. Then follows description of testcases. Each case begins with a single integer N denoting the length of string. The next line contains the string s. Output:  For each testcase, print the first non repeating character present in string.  Print -1 if there is no non repeating character. Constraints:  1<=T<=30  1<=N<=100 Example: Input : 3 5 hello 12 zxvczbtxyzvy 6 xxyyzz Output : h c -1       -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<iostream> using namespace std; char Non_Repeating(char *,int) ; int main()  { int t,no ; char str[100],ele ; cin>>t ; while(t--) {    cin>

PROBLEM : Given a text and a pattern, Find whether the pattern exist in the text or not. If it is present print "found" without quotes else print "not found" without quotes. Input: The first line of input contains an integer T denoting the number of test cases. Each test case consist of a string in 'lowercase' only in a separate line. Output: Print "found" or "not found" in a separate line. Constraints: 1 = T = 30 1 = |s| = 100 Example: Input 1 geeksforgeeks geeks Output found     -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<iostream> using namespace std; #include<string.h> int Pattern_Searching(char *,char *) ; int main()  { int t,check; char str1[100],str2[100] ; cin>>t ; while(t--) {    cin>>str1 ;    cin

PROBLEM : Given two strings, check whether two given strings are anagram of each other or not. An anagram of a string is another string that contains same characters, only the order of characters can be different. For example, “act” and “tac” are anagram of each other. Input: The first line of input contains an integer T denoting the number of test cases. Each test case consist of two strings in 'lowercase' only, in a separate line. Output: Print "YES" without quotes if the two strings are anagram else print "NO". Constraints: 1 = T = 30 1 = |s| = 100 Example: Input: 2 geeksforgeeks forgeeksgeeks allergy allergic Output: YES NO       -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<iostream> using namespace std; #include<string.h> bool IsAnagram(char *,char *)

PROBLEM : Given a non-empty sequence of characters, return true if sequence is Binary, else return false Input: The task is to complete the method that takes a string as argument. We should not read any input from stdin/console. There are multiple test cases. For each test case, this method will be called individually. Output: Your function should return true str is binary, else false Constraints: 1<=T<=50 1<=Length of str<=10000 Example: Input: 2 101 75 Output: 1 0       -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- // Return true if str is binary, else false bool isBinary(string &str) {    int l ;    l=str.size() ;      int i ;    for(i=0;i<l;i++)     {           if((str[i]=='1')||(str[i]=='0'))             continue ;         else             return false ;     }

PROBLEM : Given a binary tree, print it vertically. The following example illustrates vertical order traversal.            1         /    \        2      3       / \    / \      4   5  6   7              \   \               8   9               The output of print this tree vertically will be: 4 2 1 5 6 3 8 7 9     -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- /* typedef struct BST { int info ; struct BST *left ; struct BST *right ; }tree ;---------------------------------------------*/ void find_MinMax_Vdist(tree *,int *,int *,int ) ; void Print_Vertical_Order(tree *,int ,int ) ; void Vertical_Order(tree *root) { if(root==NULL) return ; int min,max,dist; max=0 ; min=0 ; find_MinMax_Vdist(root,&max,&min,0) ; for(dist=min;dist<=max;dist++) { Print_Vertical_Order(root

PROBLEM : Given an array that represents a tree in such a way that array indexes are values in tree nodes and array values give the parent node of that particular index (or node). The value of the root node index would always be -1 as there is no parent for root. Construct the standard linked representation of given Binary Tree from this given representation. Input: parent[] = {1, 5, 5, 2, 2, -1, 3} Output: root of below tree           5         /  \        1    2       /    / \      0    3   4          /         6 Explanation: Index of -1 is 5.  So 5 is root. 5 is present at indexes 1 and 2.  So 1 and 2 are children of 5. 1 is present at index 0, so 0 is child of 1. 2 is present at indexes 3 and 4.  So 3 and 4 are children of 2. 3 is present at index 6, so 6 is child of 3. Input: parent[] = {-1, 0, 0, 1, 1, 3, 5}; Output: root of below tree          0        /   \       1     2      / \     3   4    /   5  / 6       ---------------------------------

PROBLEM : Given a binary tree, check whether it is a mirror of itself. For example, this binary tree is symmetric:      1    /   \   2     2  / \   / \ 3   4 4   3 But the following is not:     1    / \   2   2    \   \    3    3       -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- /* typedef struct BST { int info ; struct BST *left ; struct BST *right ; }tree ;---------------------------------------------*/ // same root is send as argument twice // Symmetric_Tree(root,root) ; int Symmetric_Tree(tree *root1,tree *root2) { if(root1==NULL&&root2==NULL) return 1 ; if(root1->info==root2->info) return (Symmetric_Tree(root1->left,root2->right)&&Symmetric_Tree(root1->right,root2->left)) ; return 0 ; } -----------------------------------------------------------

PROBLEM : Given a binary tree, find the maximum path sum. The path may start and end at any node in the tree. Example: Input: Root of below tree        1       / \      2   3 Output: 6 See below diagram for another example. 1+2+3     -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- /* For each node there can be four ways that the max path goes through the node: 1. Node only 2. Max path through Left Child + Node 3. Max path through Right Child + Node 4. Max path through Left Child + Node + Max path through Right Child */ /* typedef struct BST { int info ; struct BST *left ; struct BST *right ; }tree ;---------------------------------------------*/ int max_of(int ,int ) ; int max_sum_path(tree *root,int *maxSum) { if(root==NULL) return 0 ; int LSum,RSum,max1,max2 ; LSum=max_sum_path(root-&g

PROBLEM : Given a binary tree, find its minimum depth. The minimum depth is the number of nodes along the shortest path from root node down to the nearest leaf node. For example, minimum height of below Binary Tree is 2. Example Tree Note that the path must end on a leaf node. For example, minimum height of below Binary Tree is also 2.           10         /         5     -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- /* typedef struct BST { int info ; struct BST *left ; struct BST *right ; }tree ;---------------------------------------------*/ int height_tree(tree *) ; void level_count(tree *,int ,int *) ; int minimum_depth(tree *root) { int h,i,count,last ; h=height_tree(root) ; last=0 ; for(i=1;i<=h;i++) { count=0 ; level_count(root,i,&count) ; if(count!=0) return i ; } re

PROBLEM : Given a Binary Tree, write a function to check whether the given Binary Tree is Complete Binary Tree or not. A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible. See following examples. The following trees are examples of Complete Binary Trees     1   /   \  2     3          1     /    \    2       3   /  4        1     /    \    2      3   /  \    /  4    5  6 The following trees are examples of Non-Complete Binary Trees     1       \        3          1     /    \    2       3     \     /  \        4   5    6        1     /    \    2      3          /  \         4    5 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- /* typedef struct BST { int info ; struct BST *left ; struct BST *righ

PROBLEM : Given a Binary Tree, change the value in each node to sum of all the values in the nodes in the left subtree including its own. Example Input :      1    /   \  2      3 Output :     3   /   \  2     3 Input        1       / \      2   3     / \   \    4   5   6 Output:       12      / \     6   3    / \   \   4   5   6 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- /* typedef struct BST { int info ; struct BST *left ; struct BST *right ; }tree ;---------------------------------------------*/ int BST_left_subTreeSum(tree *root) { if(root==NULL) return 0 ; if(root->left==NULL&&root->right==NULL) return root->info ; int sumL,sumR ; sumL=BST_left_subTreeSum(root->left) ; sumR=BST_left_subTreeSum(root->right) ; root->info=root->info+sumL ;

PROBLEM : Using Morris Traversal, we can traverse the tree without using stack and recursion Preorder traversal : 6 3 1 5 8 7 11 9 13 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- /* typedef struct BST { int info ; struct BST *left ; struct BST *right ; }tree ;---------------------------------------------*/ void Morris_traversal_Preorder(tree *root) { if(root==NULL) return ; tree *curr ; while(root!=NULL) { if(root->left==NULL) { cout<<root->info<<" " ; root=root->right ; } else { curr=root->left ; while(curr->right!=NULL&&curr->right!=root) curr=curr->right ; if(curr->right==root) { curr->right=NULL ; root=root->right ; } else { cout<<root->info<<"

PROBLEM : Given an array ‘pre[]’ that represents Preorder traversal of a spacial binary tree where every node has either 0 or 2 children. One more array ‘preLN[]’ is given which has only two possible values ‘L’ and ‘N’. The value ‘L’ in ‘preLN[]’ indicates that the corresponding node in Binary Tree is a leaf node and value ‘N’ indicates that the corresponding node is non-leaf node. Write a function to construct the tree from the given two arrays. Example: Input:  pre[] = {10, 30, 20, 5, 15},  preLN[] = {'N', 'N', 'L', 'L', 'L'} Output: Root of following tree           10          /  \         30   15        /  \       20   5 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- /* typedef struct BST { int info ; struct BST *left ; struct BST *right ; }tree ;---------------------------

PROBLEM : Given Inorder Traversal of a Special Binary Tree in which key of every node is greater than keys in left and right children, construct the Binary Tree and return root. Examples: Input: inorder[] = {5, 10, 40, 30, 28} Output: root of following tree          40        /   \       10     30      /         \     5          28 Input: inorder[] = {1, 5, 10, 40, 30,                     15, 28, 20} Output: root of following tree           40         /   \        10     30       /         \      5          28     /          /  \    1         15    20 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- /* typedef struct BST { int info ; struct BST *left ; struct BST *right ; }tree ;------------------------------------*/ tree * construct_special_tree(int [],int ,int) ; int find_max_arrayPos(int [],int ,int ) ;

PROBLEM : Given a sorted circular linked list, insert a newnode so that it remains a sorted circular linked list.  For example,  if the input CLL is following. After insertion of 7, the above CLL should be changed to following Input: In this problem, method takes two argument: the address of the head of the linked list and the data which you have to insert. The function should not read any input from stdin/console. The Node structure 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: Set the * head_ref to head of resultant linked list. Note: If you use "Test" or "Expected Output Button" use below example format Constraints: 1<=T<=100 0<=N<=200 Example: Input: 2 3                           Size of Linked List 1 2 4                    Elements of Linked List 2

PROBLEM : Given a singly linked list and a key, count number of occurrences of given key in linked list. For example, if given linked list is 1->2->1->2->1->3->1 and given key is 1, then output should be 4. Input: You have to complete the method which takes two argument: the head of the linked list and int k. You should not read any input from stdin/console. 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: You have to count a number of occurrences of given key in linked list and return the count value. Note: If you use "Test" or "Expected Output Button" use below example format Example: Input: 1 8 1 2 2 4 5 6 7 8 2 Output: 2 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : ----------------

PROBLEM : Given a linked list of strings having n nodes check to see whether the combined string formed is palindrome or not. Example : Input  : a -> bc -> d -> dcb -> a -> NULL Output : True String "abcddcba" is palindrome. Output : a -> bc -> d -> ba -> NULL Output : False String "abcdba" is not palindrome. Input: You have to complete the method which takes one argument: the head of the linked list . You should not read any input from stdin/console.. There are multiple test cases. For each test case, this method will be called individually. Output: Your function should return True if the combined string is pallindrome else it should return False. Constraints: 1 <=T<= 231 1 <=n<= 1000 Example: Input : 2 5 a bc d dcb a 4 a bc d ba Output : True False Explanation: case 1 : as String "abcddcba" is palindrome the function should return true case 2 : as String "abcdba&q