CSE Company Interview Questions

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

Check if a number can be expressed as x^y

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

Permutations in array

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

Minimize the sum of product

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

Power of 2

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

Max Level Sum in Binary Tree

January 22, 2017

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

Topological sort

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

Detect cycle in an undirected graph

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

Detect cycle in a directed graph

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

Depth First Traversal for a Graph

PROBLEM : Write a function to print the depth first traversal for a graph from a given source s. Input: The task is to complete the function DFS which takes 3 arguments an integer denoting the starting node (s) of the dfs travel , a graph (g) and an array of visited nodes (vis) which are initially all set to false . There are multiple test cases. For each test case, this method will be called individually. Output: The function should print the depth first traversal for the graph from the given source. Note : The expected output button always produces DFS starting from node 1. Constraints: 1 <=T<= 100 1 <=Number of edges<= 100 Example: Input: 1 4 1 2 1 3 1 4 3 5 Output: 1 2 3 5 4 //dfs from node 1 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- /* You have to complete th...

Check if two strings are k-anagrams or not

PROBLEM : Given two strings of lowercase alphabets and a value k, Your task is to complete the function which returns if two strings are K-anagrams of each other or not. Two strings are called k-anagrams if following two conditions are true. 1. Both have same number of characters. 2. Two strings can become anagram by changing at most k characters in a string. Input: The first line of input contains an integer T denoting the no of test cases. Then T test cases follow. Th first line of input contains two Strings Str1 and Str2. And next line contains an integer k, which denotes number of characters can be replaced. Output: Print the respective output in the respective line. Constraints: 1<=T<=100 1<=K<=|length of String| Example: Input: 1 fodr gork 2 Output: 1 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- ...

Letter Writer

January 17, 2017

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

Number of 1's in smallest repunits

January 17, 2017

PROBLEM : Every number whose unit’s digit is 3 has a repunit as its multiple. A repunit is a number which has only ones. It is of the form (10n – 1)/9. Example: 3 divides 111, 13 divides 111111. A positive integer N will be given whose unit’s digit is 3. The task is to find the number of 1s in the smallest repunit which is divisible by the given number 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 consists of a single line containing a positive integer N whose unit’s digit is 3. Output: Corresponding to each test case, in a new line, print the number of 1s in the smallest repunit multiple of the number. Constraints: 1 = T = 100 1 = N = 107 Example: Input 2 3 23 Output 3 22 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #inclu...

Perfect Numbers

January 17, 2017

PROBLEM : Given a number and check if a number is perfect or not. A number is said to be perfect if sum of all its factors excluding the number itself is equal to the number. Input: First line consists of T test cases. Then T test cases follow .Each test case consists of a number N. Output: Output in a single line 1 if a number is a perfect number else print 0. Constraints: 1<=T<=300 1<=N<=10000 Example: Input: 2 6 21 Output: 1 0 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<iostream> using namespace std; #include<math.h> bool Perfect_Numbers(int ) ; int main() { int t,no ; cin>>t ; while(t--) { cin>>no ; if(Perfect_Numbers(no)) ...

Form a palindrome

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

Count Increasing Subsequences

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

Palindromic Strings

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

Lucas Number

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

Longest Common Substring

January 12, 2017

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

Number of Coins

January 12, 2017

PROBLEM : Given a value V, if we want to make change for V cents, and we have infinite supply of each of C = { C1, C2, .. , Cm} valued coins, what is the minimum number of coins to make the change? Input: The first line of input contains an integer T denoting the number of test cases. The first line of each test case is V and N,V is the value of cents and N is the number of coins. The second line of each test case contains N input C[i],value of available coins. Output: Print the minimum number of coins to make the change, if not possible print -1. Constraints: 1 = T = 100 1 = V = 10000 1 = N = 50 1 = C[i] = 100 Example: Input 1 7 2 2 1 Output 4 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<limits.h> #include<iostream> using namespace std; int Number_Coins(int [],int ,int ) ; int min_of(i...

Consecutive 1's not allowed

January 12, 2017

PROBLEM : Count number of binary strings without consecutive 1’s Problem Description: Given a positive integer N, count all possible distinct binary strings of length N such that there are no consecutive 1’s. Output your answer mod 10^9 + 7. 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 contain an integer N representing length of the binary string. Output: Print the count number of binary strings without consecutive 1’s of length N. Constraints: 1 = T = 10 1 = N = 70 Example: Input: 2 3 2 Output: 5 3 Explaination: For first test case 5 strings are (000, 001, 010, 100, 101) For second test case 3 strings are (00,01,10) -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<iostream> using namespace std; in...

Merge two BST 's

PROBLEM : Given two BST, Your task is to complete the function merge which prints the elements of both BSTs in sorted form. 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 each test case contain's an integer N and M denoting the size of the two BST's. Then In the next two line are space separated values of the two BST's. Output: The function should print the elements of both BST's in sorted form. Constraints: 1<=T<=100 1<=N,M<=100 Example(To be used only for expected output): Input: 2 3 3 1 33 4 6 7 1 2 2 1 6 9 2 Output: 1 1 4 6 7 33 1 2 6 9 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- /* The structure of Node is struct Node { int data; Node * right, * left; };*/ ...

Delete keys in a Linked list

PROBLEM : Given a single linked list and an integer x your task is to complete the function deleteAllOccurances which deletes all occurences of a key x present in the linked list. The function takes two arguments: the head of the linked list and an integer x. The function should return the head of the modified linked list. Input: The first line of input contains an element T, denoting the no of test cases. Then T test cases follow. Each test case contains three lines. The first line of each test case contains an integer N denoting the no of elements of the linked list. Then in the next line are N space separated values of the linked list. The third line of each test case contains an integer x. Output: The output for each test case will be the space separated value of the returned linked list. Constraints: 1<=T<=300 1<=N<=100 1<=x<=N Example(To be used only for expected output): Input: 2 5 2 2 1 4 4 4 6 1 2 2 3 2 3 2 Output: 2 2 1 1 3 3 ...

Reverse each word in a given string

PROBLEM : Given a String of length N reverse each word in it. Words are separated by dots. Input: The first line contains T denoting the number of testcases. Then follows description of testcases. Each case contains a string containing dots and characters. Output: For each test case, output a String in single line containing the reversed words of the given String. Constraints: 1<=T<=10 1<=Length of String<=2000 Example: Input: 2 i.like.this.program.very.much pqr.mno Output: i.ekil.siht.margorp.yrev.hcum rqp.onm -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<iostream> using namespace std; #include<string.h> string Reverse_each_word(string ) ; string reverse(string ,int ,int ) ; int main() { int t ; string str ; cin>>t ; while(t--) { cin>>...

Count ways to reach the n’th stair

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 matter). 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. Answer your output % 10^9+7. Constraints: 1<=T<=1000 1<=N<=100 Example: Input: 3 4 10 24 Output: 5 89 75025 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<iostream> using namespace std; #include<math.h> long long Count_nth_stair(long long ) ; int main() { int t ; long long no ; cin>>t ; while(t--) { cin>>no ; ...

Padovan Sequence