CSE Company Interview Questions

PROBLEM : Given a number N, print all its unique prime factors and their powers in N. N = 100 Factor Power 2 2 5 2 N = 35 Factor Power 5 1 7 1 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 prime factors and their powers separated by spaces. The output should be printed in increasing order of prime factors. Constraints: 1 = T = 200 2 = N = 10000 Example: Input: 2 100 35 Output: 2 2 5 2 5 1 7 1 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<iostream> using namespace std; #include<math.h> void Prime_Factors_Powers(int ) ; void find_prime(int [],int ) ; int main() { ...

Sphenic Number

PROBLEM : A Sphenic Number is a positive integer N which is product of exactly three distinct primes. The first few sphenic numbers are 30, 42, 66, 70, 78, 102, 105, 110, 114, … Given a number N, your task is to find whether it is a Sphenic Number or not. Examples: Input : 30 Output : 1 Explanation : 30 is the smallest Sphenic number, 30 = 2 × 3 × 5 the product of the smallest three primes Input : 60 Output : 0 Explanation : 60 = 22 x 3 x 5 has exactly 3 prime factors but is not a sphenic number 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 1 if N is a Sphenic Number else print 0. Constraints: 1<=T<=100 1<=N<=1000 Example: Inpu...

Stack using two queues

PROBLEM : Implement a Stack using 2 queue q1 and q2 . 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 2 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) 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 from the stack . You are required to complete the two methods push which take one argument an integer 'x' to be pushed into the stack and pop which returns a integer poped out from the stack. Constraints: 1<=T<=100 1<=Q<=100 1<=x<=100 Example: Inpu...

Queue using two Stacks

PROBLEM : Implement a Queue using 2 stacks s1 and s2 . 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 2 Types (i) 1 x (a query of this type means pushing 'x' into the queue) (ii) 2 (a query of this type means to pop element from queue and print the poped element) 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 queue is empty else the element poped out from the queue . You are required to complete the two methods push which take one argument an integer 'x' to be pushed into the quee and pop which returns a integer poped out from othe queue. Constraints: 1<=T<=100 1<=Q<=100 1<=x<=100 Example: Inp...

Rotate a 2D array without using extra space

PROBLEM : You are given an n x n 2D matrix representing an image. Rotate the image by 90 degrees (clockwise). You need to do this in place. Note that if you end up using an additional array, you will only receive partial score. Example: If the array is 1 2 3 4 5 6 7 8 9 Then the rotated array becomes: 7 4 1 8 5 2 9 6 3 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 the 2D square matrix. And in the second line, the elements of the matrix A[][], each separated by a space in row major form. Output: For each test case, print the elements of the rotated array row wise, each element separated by a space. Print the output of each test case in a new line. Constraints: 1 = T = 70 1 = N = 10 1 = A [ i ][ j ] = 100 Example: Input: 2 3 1 2 3 4 5 6 7 8 9 2 56 96 91 54 Output: 7 4 1 8 5 2 9 6 3 91 56 54 96 ---------------------...

Minimum steps to get desired array

PROBLEM : Consider an array with n elements and value of all the elements is zero. We can perform following operations on the array. 1. Incremental operations: Choose 1 element from the array and increment its value by 1. 2. Doubling operation: Double the values of all the elements of array. Given an array of integers of size N. Print the smallest possible number of operations needed to change the array from all zeros to desired array. Input: The first line of input contains an integer T denoting the number of test cases. The first line of each test case is an integer N where N is the size of array . The second line of each test case contains N input A[i]. Output: Print the smallest possible number of the operations needed to change the array from all zeros to desired array. Constraints: 1 = T = 50 1 = N = 100 1 = A[i] = 200 Example: Input: 3 3 16 16 16 2 2 3 2 2 1 Output: 7 4 3 Explanation : In first test case, the output solutio...

Find Prime numbers in a range

PROBLEM : Generate all prime numbers between two given numbers. Input: 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 a single line containing two space separated integers m and n. Output: For every test case print all prime numbers p such that m <= p <= n, space separated. Separate the answers for each test case by a new line. Constraints: 1<=T<=60 1 <= m <= n <= 100000, n - m <= 100000 Example: Input: 2 1 10 3 5 Output: 2 3 5 7 3 5 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<iostream> using namespace std; void Prime_numbers_range(int ,int ) ; int main() { int t,n1,n2 ; cin>>t ; while(t--) { ...

Return two prime numbers

PROBLEM : Given an even number ( greater than 2 ), return two prime numbers whose sum will be equal to given number. There are several combinations possible. Print only first such pair. NOTE: A solution will always exist, read Goldbach’s conjecture. Also, solve the problem in linear time complexity, i.e., O(n). Input: The first line contains T, the number of test cases. The following T lines consist of a number each, for which we'll find two prime numbers. Note: The number would always be an even number. Output: For every test case print two prime numbers space separated, such that the smaller number appears first. Answer for each test case must be in a new line. Constraints: 1 = T = 70 1 = N = 10000 Example: Input: 5 74 1024 66 8 9990 Output: 3 71 3 1021 5 61 3 5 17 9973 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------...

Next sparse binary number

PROBLEM : Given an integer n in the input, find its next sparse binary number.A sparse binary number is a number whose binary representation does not contain any consecutive 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 number 'N' Output: Print next Sparse binary number,if the input number is not sparse else print the number itself. Constraints: 1 = T = 100 1 = n = 100000 Example: Input 2 3 5 Output 4 5 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<iostream> using namespace std; int Next_sparse_binary_number(int ) ; int sparse(int ) ; int main() { int t,no ; cin>>t ; while(t--) { cin>>no ; cout<<Next_sparse_binary_number(no)<<endl ; } retu...

Convert array into Zig-Zag fashion

PROBLEM : Given an array of distinct elements, rearrange the elements of array in zig-zag fashion in O(n) time. The converted array should be in form a < b > c < d > e < f.The relative order of elements is same in the output i.e you have to iterate on the original array only. 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 array in Zig-Zag fashion. Constraints: 1 = T = 100 1 = N = 100 0 =A[i]<=10000 Example: Input: 2 7 4 3 7 8 6 2 1 4 1 4 3 2 Output: 3 7 4 8 2 6 1 1 4 2 3 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------...

Finding Position

PROBLEM : Some people are standing in a queue. A selection process follows a rule where people standing on even positions are selected. Of the selected people a queue is formed and again out of these only people on even position are selected. This continues until we are left with one person. Find out the position of that person in the original queue. 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,number of people standing in a queue. Output: Print the position(original queue) of that person who is left. Constraints: 1 = T = 1000 1 = N = 100000000 Example: Input 1 5 Output 4 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<iostream> using namespace std; #include<math.h> int Finding_Position(int ) ; int main() { ...

Strong Number

PROBLEM : Write a program to check whether a number is strong or not. A number is called strong number if sum of the factorial of its digit is equal to number itself. For example: 145 as 1! + 4! + 5! = 1 + 24 + 120 = 145 Input: First line contains number of test cases T. Then following T lines contains an integer N. Output: Output "Strong" if given number is strong else "Not Strong" . Constraints: 1<=T<=50 0<=N<=1000 Example: Input: 2 145 10 Output: Strong Not Strong -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<iostream> using namespace std; int Is_Strong(int ) ; int factorial(int ) ; int main() { int t,no ; cin>>t ; while(t--) { cin>>no ; if(Is_Strong(no)) cout<<"Strong" ; els...

Three Great Candidates

December 28, 2016

PROBLEM : The hiring team of Google aims to find 3 candidates who are great collectively. Each candidate has his or her ability expressed as an integer. 3 candidate are great collectively if product of their abilities is maximum. Find the maximum collective ability from the given pool of candidates. Input: The first line of input contains an integer T denoting the number of test cases. Then T test cases follow. First line of each test case conatins an interger N denoting the number of candidates. The second line of each test case contains N space separated elements denoting the ablities of candidates. Output: Corresponding to each test case, print the desired output(maximum collective ability of three candidates) in a newline. Constraints: 1 = T = 100 3 = N = 1000 -1000 = ability = 1000 Example: Input 1 6 0 -1 3 100 70 50 Output: 350000 Explanation 70*50*100 = 350000 which is the maximum possible. --------------------------------------------------------...

Number of paths

December 28, 2016

PROBLEM : The problem is to count all the possible paths from top left to bottom right of a MxN matrix with the constraints that from each cell you can either move only to right or down. 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 number of rows and N is number of columns. Output: Print the number of paths. Constraints: 1 = T = 30 1 = M,N = 10 Example: Input 2 3 3 2 8 Output 6 8 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<iostream> using namespace std; int Number_of_paths(int ,int ) ; int main() { int t,m,n ; cin>>t ; while(t--) { cin>>m>>n ; cout<<Number_of_paths(m,n)<<endl ; } return 0; } int Number_of_paths(int m,int n)...

Move all negative elements to end

PROBLEM : Given an unsorted array having both negative and positive integers. The task is place all negative element at the end of array without changing the order of positive element and negative element. Examples: Input : A[] = {1, -1, 3, 2, -7, -5, 11, 6 } Output : 1 3 2 11 6 -1 -7 -5 Input : A[] = {-5, 7, -3, -4, 9, 10, -1, 11} Output : 7 9 10 11 -5 -3 -4 -1 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: For each test case in a new line output the modified array. Constraints: 1<=T<=100 1<=N<=100 -1000<=A[]<=1000 Example: Input: 2 8 1 -1 3 2 -7 -5 11 6 8 -5 7 -3 -4 9 10 -1 11 ...

AVL Tree Insertion

PROBLEM : Given a root of the tree you need to perform N AVL tree insertion operations on it. You need to complete the method insertToAVL which takes 2 arguments the first is the root of the tree and the second is the value of the node to be inserted.The function should return the root of the modified tree. Note: Your code will be checked for each insertion and will produce an output 1 if all the nodes for a particular test case were correctly inserted else 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 2 lines . The first line of each test case contains an integer N denoting the no of nodes to be inserted in the AVL tree and in the next line are N space separated values denoting the values of the nodes to be inserted to the tree. Output: For each test case output will be 1 if the node was correctly inserted else 0. Constraints: 1<=T<=100 1<=N<=100 Example(To be used on...

Max sum path in two arrays

PROBLEM : Given two arrays, the task is to complete the function max_path_sum that takes 4 argument The first two arguments represent the 2 arrays A[], B[] and the last two arguments l1, l2 denote the size of array A and B respectively. The function returns the sum of the maximum sum path to reach from beginning of any array to end of any of the two arrays . Note: You can switch from one array to another array only at common elements. eg A [ ] = {2,3,7,10,12} B [ ] = {1 5 7 8} Here We start from first element of B which is 1, then we move to 5, then 7. From 7, we switch to A (7 is common) and traverse 10 and 12. Thus The result will be 1+5+7+10+12 =35 Input: The first line of input contains an integer T denoting the no of test cases . Then T cases follow. Each test case contains 3 lines. The first line contains two space separated integers l1 and l2 denoting the length of the two sorted array A and B. In the second line is the space separated values of array A and in th...

Palindromic Array

PROBLEM : Given a Integer array A[] of n elements. Your task is to complete the function PalinArray. Which will return 1 if all the elements of the Array are palindrome otherwise it will return 0. 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 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[]. Output: For each test case in a new line print the required result. Constraints: 1<=T<=50 1<=n<=20 1<=A[]<=10000 Example: Input: 2 5 111 222 333 444 555 3 121 131 20 Output: 1 0 Explanation: For First test case. n=5; A[0]=111 //which is a palindrome number. A[1]=222 //which is a palindrome number. A[2]=333 //which is a palindrome number. A[3]=444 //which is a palindrome number. A[4]=555 //which is a palindrome number. As...

Min Subsets with Consecutive Numbers

PROBLEM : Given an array of distinct positive numbers, the task is to calculate the number of subsets (or subsequences) from the array such that each subset contains consecutive numbers. 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 the length of the array. Next line contains N space seperated integers of the array. Output: For each test case output a new line denoting count of number of such subset's that contains consecutive numbers. Constraints: 1<=T<=100 1<=N<=50 Example: Input 2 11 100 56 5 6 102 58 101 57 7 103 5 3 10 100 105 Output 3 3 Explanation Test Case 1 - {5, 6, 7}, { 56, 57, 58, 59}, {100, 101, 102, 103} are 3 subset in which numbers are consecutive. Test Case 2 - {10}, {100} and {105} are 3 subset in which numbers are consecutive. -------------------------------------------------------------------------------- SIM...

Find Number of Numbers

PROBLEM : Given an array A[] of n elements. Your task is to complete the Function num which returns an integer denoting the total number of times digit k appears in the whole array. For Example: A[]={11,12,13,14,15}, k=1 Output=6 //Count of the digit 1 in the array 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 contain an integer n denoting the size of the array A[]. Then in the second line are n space separated values of the array A[] .In the third line of each test case contains an integer k, which is the digit to be counted. Output: For each test case in a new line print the number of elements counted. Constraints: 1<=T<=100 1<=n<=20 1<=A[]<=1000 Example(To be used for expected output): Input: 2 5 11 12 13 14 15 1 4 0 10 20 30 0 Output: 6 4 -------------------------------------------------------------------------------- SIMPLE c++ ...

Maximum value in a bitonic array

PROBLEM : Given an array of elements which is first increasing and then decreasing, find the maximum element in the array. 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 size of array The second line of each test case contains N integers which are the array elements. Output: Print the maximum element in the array. Constraints: 1 = T = 50 3 = N = 100 1 = a[i] = 100000 Example: Input 2 9 1 15 25 45 42 21 17 12 11 5 1 45 47 50 5 Output 45 50 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<iostream> using namespace std; int largest(int [],int ,int ) ; int main() { int t,no,i ; int arr[100] ; cin>>t ; while(t--) { cin>>no ; for(i=0;i<no;i++) ...

Pythagorean Triplet

PROBLEM : Given an array of integers, write a function that returns true if there is a triplet (a, b, c) that satisfies a2 + b2 = c2. Input: The first line contains 'T' denoting the number of testcases. Then follows description of testcases. Each case begins with a single positive integer N denoting the size of array. The second line contains the N space separated positive integers denoting the elements of array A. Output: For each testcase, print "Yes" or "No" whtether it is Pythagorean Triplet or not. Constraints: 1<=T<=50 1<=N<=100 1<=A[i]<=100 Example: Input: 1 5 3 2 4 6 5 Output: Yes -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<iostream> using namespace std; #include<algorithm> #include<math.h> bool Pythagorean_Triplet(int [],in...

Sum of Middle Elements of two sorted arrays

PROBLEM : Given 2 sorted arrays A and B of size N each. Print sum of middle elements of the array obtained after merging the given arrays. Input: The first line contains 'T' denoting the number of testcases. Then follows description of testcases. Each case begins with a single positive integer N denoting the size of array. The second line contains the N space separated positive integers denoting the elements of array A. The third line contains N space separated positive integers denoting the elements of array B. Output: For each testcase, print the sum of middle elements of two sorted arrays. The number of the elements in the merged array are even so there will be 2 numbers in the center n/2 and n/2 +1. You have to print their sum. Constraints: 1<=T<=50 1<=N<=1000 1<=A[i]<=100000 1<=B[i]<=100000 Example: Input : 1 5 1 2 4 6 10 4 5 6 9 12 Output : 11 -------------------------------------------------------------...

Implement Queue using Linked List

PROBLEM : Implement a Queue using Linked List. 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 2 Types (i) 1 x (a query of this type means pushing 'x' into the queue) (ii) 2 (a query of this type means to pop element from queue and print the poped element) 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 queue is empty else the element poped out from the queue . You are required to complete the two methods push which take one argument an integer 'x' to be pushed into the quee and pop which returns a integer poped out from othe queue. Constraints: 1<=T<=100 1<=Q<=100 1<=x<=100 Example: Input 1 5...

Check if given four points form a square