CSE Company Interview Questions

PROBLEM : Given a Binary search tree. Your task is to complete the function which will return the Kth largest element without doing any modification in Binary Search Tree. Input: The first line of input contains an integer T, denoting the no of test cases. Then T test cases follow. Each test case consists of three lines. The first line of each test case contains an integer N denoting the no of elements in BST. Then in the next line are N space separated values of the BST. The third line of each test case contains an integer k for k largest element. Output: Print the kth largest element in each line. Constraints: 1<=T<=20 1<=N , K<=20 Example(To be used only for expected output): Input: 1 7 50 30 20 40 70 60 80 3 Output: 60 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- /*The Node structure is defined as s...

PROBLEM : Write a function to connect all the adjacent nodes at the same level in a binary tree. Structure of the given Binary Tree node is like following. struct Node{   int data;   Node* left;   Node* right;   Node* nextRight; } Initially, all the nextRight pointers point to garbage values. Your function should set these pointers to point next right for each node. Example: Input Tree        10       / \      3   5     / \   \    4   1   2 Output Tree        10--->NULL       / \      3-->5-->NULL     / \   \      4-->1-->2-->NULL Input: The task is to complete the method which takes one argument, root of Binary Tree. There are multiple test cases. For each test case, this method will be called individually. Output: The function should update nextRigh...

PROBLEM : Given a N X N  matrix Matrix[N][N] of positive integers.  There are only three possible moves from a cell Matrix[r][c]. 1. Matrix[r+1][c] 2. Matrix[r+1][c-1] 3. Matrix[r+1][c+1] Starting from any column in row 0, return the largest sum of any of the paths up to row N-1. Input: The first line of the 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 order of matrix. Next line contains N*N integers denoting the elements of the matrix in row-major form. Output: Output the largest sum of any of the paths starting from any cell of row 0 to any cell of row N-1. Print the output of each test case in a new line. Constraints: 1<=T<=20 2<=N<=20 1<=Matrix[i][j]<=1000 (for all 1<=i<=N && 1<=j<=N) Example: Input: 1 2 348 391 618 193 Output: 1009 Explanation: In the sample test case, the ...

PROBLEM : Given a Binary Tree you need to  find maximum value which you  can get by subtracting value of node B from value of node A, where A and B are two nodes of the binary tree and A is an ancestor of B . You are required to complete the function maxDiff . 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: The task is to complete the function maxDiff which takes 1 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 return an integer denoting the maximum difference. Constraints: 1 <=T<= 30 1 <=Number of nodes<= 100 1 <=Data of a node<= 1000 Example Input 1 2 5 2 L 5 1 R Output 4               5   ...

PROBLEM : Given an array A[] of N integers where each value represents number of chocolates in a packet. Each packet can have variable number of chocolates. There are m students, the task is to distribute chocolate packets such that : 1. Each student gets one packet. 2. The difference between the number of chocolates given to the students in packet with maximum chocolates and packet with minimum chocolates is minimum. Examples Input : A[] = {3, 4, 1, 9, 56, 7, 9, 12}         m = 5 Output: Minimum Difference is 6 We may pick 3,4,7,9,9 and the output is 9-3 = 6 Input : A[] = {7, 3, 2, 4, 9, 12, 56}         m = 3 Output: Minimum difference is 2 We can pick 2, 3 and 4 and get the minimum difference between maximum and minimum packet sizes. ie 4-2 = 2 Input: The first line of input contains an integer T, denoting the no of test cases. Then T test cases follow. Each test case consists of three lines. The first line of each test case...

PROBLEM : Given Linked List Representation of Complete Binary Tree, construct the Binary tree.Your task is to complete the function convert which takes two arguments the first being the head denoting the head of the linked list and the second argument is root denoting the root of the tree to be constructed. Note : The complete binary tree is represented as an linked list in a way where If root node is stored at position i, its left, and right children are stored at position 2*i+1, 2*i+2 respectively. Input: The first line of input is the no of test cases T. Then T test cases follow . Each test case contains 2 lines. The first line contains an integer N denoting the no of nodes of the linked list . Then in the next line are N space separated Ki values of the linked list . Output: Output of each test case will be the level order traversal of the the constructed binary tree. You do not have to  print it . Constraints: 1<=T<=100 1<=N<=100 1<=Ki <=10...

PROBLEM : Given a Binary Tree, print the diagnol traversal of the binary tree. Consider lines of slope -1 passing between nodes. Given a Binary Tree, print all diagonal elements in a binary tree belonging to same line. Input : Root of below tree Output : Diagonal Traversal of binary tree :  8 10 14 3 6 7 13 1 4 Input: The task is to complete the method which takes 1 argument, root of Binary 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 out the diagonal traversal of the binary tree. 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 4 10 20 L 10 30 R 20 40 L 20 60 R Output 1 2 3 10 30 20 60 40 There are two test casess.  First case represents a tree with 3 nodes and 2 edges whe...

PROBLEM : Given a list of non negative integers, arrange them in such a manner that they form the largest number possible. The result is going to be very large, hence return the result in the form of a string. Input: The first line of input consists number of the test cases. The description of T test cases is as follows: The first line of each test case contains the size of the array, and the second line has the elements of the array. Output: In each separate line print the largest number formed by arranging the elements of the array in the form of a string. Constraints: 1 = T = 70 1 = N = 100 0 = A[i] = 1000 Example: Input: 2 5 3 30 34 5 9 4 54 546 548 60 Output: 9534330 6054854654 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<iostream> using namespace std; #include<algorithm> #include...

PROBLEM : Equilibrium index of an array is an index such that the sum of elements at lower indexes is equal to the sum of elements at higher indexes . Now Given an array your task is to complete the function findEquilibrium which returns the index of the first Equilibrium point in the array. The function takes  two arguments. The first argument is the array A[ ] and the second argument is the size of the array A. Input: The first line of input takes an integer T denoting the no of test cases, then T test cases follow. The first line of each test case is an integer N denoting The size of the array . Then in the next line are N space separated values of the array. Output: For each test case output will be the equilibrium index of the array .If no such index exist output will be -1. Constraints: 1<=T<=100 1<=N<=100 -100<=A[]<=100 Example(To be used only for expected output): Input 2 4 1 2 0 3 4 1 1 1 1 Output 2 -1 --------------------------...

PROBLEM : Given an array A[] of N integers where each value represents number of chocolates in a packet. Each packet can have variable number of chocolates. There are m students, the task is to distribute chocolate packets such that : 1. Each student gets one packet. 2. The difference between the number of chocolates given to the students in packet with maximum chocolates and packet with minimum chocolates is minimum. Examples Input : A[] = {3, 4, 1, 9, 56, 7, 9, 12}         m = 5 Output: Minimum Difference is 6 We may pick 3,4,7,9,9 and the output is 9-3 = 6 Input : A[] = {7, 3, 2, 4, 9, 12, 56}         m = 3 Output: Minimum difference is 2 We can pick 2, 3 and 4 and get the minimum difference between maximum and minimum packet sizes. ie 4-2 = 2 Input: The first line of input contains an integer T, denoting the no of test cases. Then T test cases follow. Each test case consists of three lines. The first line of each test ca...

PROBLEM : Given an array A of integers, find the maximum of j - i subjected to the constraint of A[i] <= A[j]. Example : A : [3 5 4 2] Output : 2 for the pair (3, 4) 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 array and next line followed by the value of array. Output: Print the maximum difference of the indexes i and j in a separtate line. Constraints: 1 = T = 30 1 = N = 1000 0 = A[i] = 100 Example: Input 1 2 1 10 Output 1 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<iostream> using namespace std; int Maximum_Index(int [],int ) ; int main()  { int t,no,i ; int arr[1000] ; cin>>t ; while(t--) {    cin>>no ;    for(i=0;i<no;i++) ...

PROBLEM : A prime number is a Circular Prime Number if all of its possible rotations are itself prime numbers. Now given a number N check if it is Circular Prime or Not. Input: The first line of input contains an integer T denoting the number of test cases. Then T test cases follow. Each test case contains an integer N. Output: For each test case in a new line print 1 if the number is circular prime else 0. Constraints: 1<=T<=100 1<=N<=104 Example: Input: 2 197 101 Output: 1 0 Explanation: For first test case: 197 is a Circular Prime because all rotations of 197 are 197, 719, 971 all of the 3 are prime number's hence 197 is a circular prime For second test case: 101 isn't a prime number as rotation of 101 yields 110 which isn't a prime number hence 101 isn't circular prime -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : ------------------------------------------...

PROBLEM : Given an array A[] of n elements.The task is to make a sorted array which will contain all distinct digits present in A[]. 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. Then in the next line are N space separated integers of the array. Output: For each test case in a new line print the distinct array of digits. Constraints: 1<=T<=100 1<=n<=200 1<=A[]<=1000 Example: Input: 2 3 131 11 48 4 111 222 333 446 Output: 1 3 4 8 1 2 3 4 6 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<iostream> using namespace std; void Distinct_Digit_Array(int [],int ) ; int main()  { int t,no,i ; int arr[1000] ; cin>>t ; while(t--) { ...

PROBLEM : Given an array of integers and two numbers k1 and k2. Find sum of all elements between given two k1’th and k2’th smallest elements of array. It may be assumed that (1 <= k1 < k2 <= n) and all elements of array are distinct. 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. Third line contains two space seperated integers denoting k1'th and k2'th smallest elements. Output: For each test case in a new line output the sum of all the elements between k1'th and k2'th smallest elements. Constraints: 1<= T <= 100 1<= k1< K2 <= N <=50 Example: Input 2 7 20 8 22 4 12 10 14 3 6 6 10 2 50 12 48 13 2 6 Output 26 73 Explanation: Test Case 1 - 3rd smallest element is 10 6th smallest element is 20 Sum of all element between k1 ...

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

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

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

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

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

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