CSE Company Interview Questions

PROBLEM : Efficiently count how many integers from 1 to N contains 0's as a digit. Input: First line of the input contains the number of test cases T. Each line of test case contains the integer N. Output: Number of integers that contain 0 as a digit are printed. Constraints: 1 <=T<= 100 1 <=N<= 10000 Example: Input: 3 100 987 20 Output: 10 179 2 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<iostream> using namespace std; int count_zeroes(int ) ; int main()  {     int t,no ;     cin>>t ;     while(t--)     {         cin>>no ;         cout<<count_zeroes(no)<<endl ;     }     return 0; } int count_zeroes(int no) {     int i,count ; ...

PROBLEM : Given an array A your task is to tell at which position the equilibrium first occurs in the array. Equilibrium position in an array is a position such that the sum of elements below it is equal to the sum of elements after it. Input: The first line of input contains an integer T denoting the no of test cases then T test cases follow. First line of each test case contains an integer N denoting the size of the array. Then in the next line are N space separated values of the array A. Output: For each test case in a new  line print the position at which the elements are at equilibrium if no equilibrium point exists print -1. Constraints: 1<=T<=100 1<=N<=100 Example: Input: 2 1 1 5 1 3 5 2 2 Output: 1 3 Explanation: 1. Since its the only element hence its the only equilibrium point 2. For second test case equilibrium point is at position 3 as elements below it (1+3) = elements after it (2+2) -------------------------------------------...

PROBLEM : Given a binary matrix your task is to complete the function printMat which prints all unique rows of the given matrix. The function takes three arguments the first argument is a matrix M and the next two arguments are row and col denoting the rows and columns of the matrix. Input: The first line of input is an integer T denoting the no of test cases.Then T test cases follow. Each test case consists of 2 lines . The first line of each test case is are two integers row and col denoting the no of rows and columns of matrix . Then in the next line are row*col space separated values of the matrix M. Output: The output will be the unique rows of the matrix separated by space . Note : Dont print new line after each row instead print "$" without quotes . Constraints: 1<=T<=20 1<=row,col<=40 0<=M[ ][ ]<=1 Example: Input 1 3 4 1 1 0 1 1 0 0 1 1 1 0 1 Output 1 1 0 1 $1 0 0 1 $ Explanation Above the matrix of size 3x4 looks like 1 ...

PROBLEM : Given an array and an integer k, find the maximum for each and every contiguous subarray of size k. 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 and the size of subarray 'k'. The second line contains 'N' space-separated integers A1, A2, ..., AN denoting the elements of the array. Output: Print the maximum for every subarray of size k. Constraints: 1 = T = 100 1 = N = 100 1 = k = N 0 =A[i]<1000 Example: Input: 2 9 3 1 2 3 1 4 5 2 3 6 10 4 8 5 10 7 9 4 15 12 90 13 Output: 3 3 4 5 5 5 6 10 10 10 15 15 90 90 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<iostream> using namespace std; void ...

PROBLEM : Given a number N, check if N is power of 4 or not. Input: You have to complete the method which takes 1 argument: the number N  .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 1 if N is power of 4, else return 0. Constraints: 1<=T<=50 1<=N<=100000000 Example: Input: 2 64 75 Output: 1 0 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- int isPowerOfFour(unsigned int n) {     if(n<4&&(n!=1))         return 0 ;     else if(n==1)         return 1;     else if(n%4!=0)         return 0 ;     else        return isPowerOfFour(n/4) ; ...

PROBLEM : Check if a given number is Fibonacci number. Fibonacci number is a number which occurs in Fibonacci series. Input: The first line of input contains an integer T denoting the number of test cases. Each test case contains a number. Output: Print "Yes" if the entered number is Fibonacci number else "No". Constraints: 1<=t<=100 1<=n<=100 Example: Input 2 34 41 Output Yes No -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<iostream> using namespace std; int Fibonacci(int ) ; int main()  { int t,no ; cin>>t ; while(t--) {    cin>>no ;    if(Fibonacci(no))        cout<<"Yes" ;    else        cout<<"No" ;    cout<<endl ; } return 0; } int F...

PROBLEM : Given a positive integer N, find the Nth fibonacci number. Since the answer can be very large, print the answer modulo 1000000007. Input: The first line of input contains T denoting the number of testcases.Then each of the T lines contains a single positive integer N. Output: Output the Nth fibonacci number. Constraints: 1<=T<=100 1<=N<=1000 Example: Input: 3 1 2 5 Output: 0 1 3 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<iostream> using namespace std; #define MOD 1000000007 long long Nth_Fibonacci_Number(int ) ; int main()  {     int t,no ;     cin>>t ;     while(t--)     {         cin>>no ;         cout<<Nth_Fibonacci_Number(no) ;        ...

PROBLEM : Given the first 2 terms of Geometric Series tell the nth term of the series. Ex. floor(2.3) =2 and floor(-2.3) = -3. Input: First line contains an integer, the number of test cases 'T'. Each test case in its first line should contain two positive integer a and b (First 2 terms of GP). In the second line of every test case it contains of an integer N. Output: In each seperate line print the Nth term of the Geometric Progression. Print the floor of the answer. Constraints: 1<=T<=30 -100<=a<=100 -100<=b<=100 1 <= N <= 5 Example: Input: 2 2 3 1 1 2 2 Output: 2 2 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<iostream> using namespace std; #include<math.h> int Series_GP(int ,int ,int ) ; int main()  { int t,n,a,b ; cin>>t ; while(t--) ...

PROBLEM : Given a Binary Number, Print its decimal equivalent. 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 single Binary number. Output: Print each Decimal number in new line. Constraints: 1< T <100 1<=Digits in Binary<=8 Example: 1 10001000 136 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<iostream> using namespace std; #include<math.h> int decimal_number(int ) ; int main()  { int t,no ; cin>>t ; while(t--) {    cin>>no ;    cout<<decimal_number(no)<<endl ; } return 0; } int decimal_number(int no) {     int i,sum,r ;     i=0 ;     sum=0 ;       ...

PROBLEM : Given an integer N, recursively sum digits of N until we get a single digit.  The process can be described below If N < 10       digSum(N) = N Else             digSum(N) = Sum(digSum(N)) Example: Input : 1234 Output : 1 Explanation : The sum of 1+2+3+4 = 10,               digSum(x) == 10               Hence ans will be 1+0 = 1 Input: The first line contains an integer T, total number of test cases. Then following T lines contains an integer N. Output: Repeated sum of digits of N. Constraints: 1 = T = 100 1 = N = 1000000 Example: Input 2 123 9999 Output 6 9 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<iostream> using namespace std; int Repeated_sum_of_di...

PROBLEM : Given a Binary Tree,  print the bottom view from left to right. A node x is there in output if x is the bottommost node at its horizontal distance from root. Horizontal distance of left child of a node x is equal to horizontal distance of x minus 1, and that of right child is horizontal distance of x plus 1. Examples:                       20                     /    \                   8       22                 /   \        \               5      3       25                     /   \                       10    14 For the above tree the ou...

PROBLEM : You are given a pointer to the root of a binary tree. Print the top view of the binary tree. You only have to complete the function. For example :      3    /   \   5     2  / \   / \ 1   4 6   7  \       /   9     8 Top View : 1 -> 5 -> 3 -> 2 -> 7 Input Format You are given a function, void top_view(node * root) { } Output Format Print the values on a single line separated by space. Sample Input      3    /   \   5     2  / \   / \ 1   4 6   7  \       /   9     8   Sample Output 1 5 3 2 7 Explanation      3    /   \   5     2  / \   / \ 1   4 6   7  \       /   9     8 From the top only nodes 1,5,3,2 and 7 will be ...

PROBLEM : Given an array A[ ] your task is to complete the function max_val which finds the maximum value of abs(i – j) * min(arr[i], arr[j]) where i and j vary from 0 to n-1. 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 size of the array. In the next line are N space separated values of the array A[ ] . Output: For each test case in a new line output will be the max values obtained. Constraints: 1<=T<=100 1<=N<=100 -100<=A[]<=1000 Example(To be used only for expected output): Input 2 4 3 2 1 4 4 8 1 9 4 Output 9 16 Explanation: (i) For the first test case a[0] = 3 and a[3] = 4 and thus result is  abs(0-3)*min(3,4) = 9. (ii) For the second test ase a[0]=8 and a[2]=9 thus result is abs(0-2)*min(8,9) = 16. --------------------------------------------------------------------...

PROBLEM : Calculate the product of all the elements in an array. Input: The first line of input contains an 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 contains an integer N.The second line of each test case contains N space separated integers denoting elements of the array A[ ]. Output: For each test case in a new line print the product of all elements. Constraints: 1 = T = 50 1 = N = 10 1 = A[i] = 5 Example: Input: 2 5 1 2 3 4 5 10 5 5 5 5 5 5 5 5 5 5 Output: 120 9765625 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<iostream> using namespace std; long long product(int [],int ) ; int main()  { int t,no,arr[10],i ; cin>>t ; while(t--) {    cin>>no ;   ...

PROBLEM : Given a boolean matrix mat[M][N] of size M X N, modify it such that if a matrix cell mat[i][j] is 1 (or true) then make all the cells of ith row and jth column as 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 r and c,r is the number of rows and c is the number of columns. The second line of each test case contains all the elements of the matrix in a single line separated by a single space. Output: Print the modified array. Constraints: 1 = T = 50 1 = r,c = 20 0 = Elements of matrix = 1 Example: Input: 3 2 2 1 0 0 0 2 3 0 0 0 0 0 1 3 4 1 0 0 1 0 0 1 0 0 0 0 0 Output: 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<iostream> using namespace std; #define MAX 2...

PROBLEM : Given two linked lists that represent two large positive numbers. Your task is to complete the function SubLinkedList which takes two arguments l1 and l2. The function subtracts the smaller number from larger one and return a pointer to the resultant linked list. 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 contains an integer n denoting the size of the first linked list (l1)  In the next  line are the space separated values of the first linked list. The third line of each test case contains an integer m denoting the size of the second linked list (l2). In the forth line are space separated values of the second linked list . Output: For each test case output will be space separated values of the resultant linked list. Constraints: 1<=T<=100 1<=n,m<=100 Example: Input: 1 3 1 0 0 1 1 Output: 0 9 9 --------------------------------------...

PROBLEM : The task is to complete the function  multiplyTwoLists which multiplies two linked lists l1 and l2 and returns their product . The function takes two linked list l1, l2 as its arguments. Note: The output could be large take modulo 10^9+7. 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 contains an integer n denoting the size of the first linked list (l1)  In the next  line are the space separated values of the first linked list. The third line of each test case contains an integer m denoting the size of the second linked list (l2). In the forth line are space separated values of the second linked list . Output: For each test case output will be an integer denoting the product of the two linked list. Constraints: 1<=T<=100 1<=n,m<=100 Example(To be used only for expected output): Input 2 2 3 2 1 2 3 1 0 0 2 1 0 Output 64 1000 ...

PROBLEM : Write a program to print Binary representation of a given 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. Output: Print binary representation of a number in 14 bits. Constraints: 1 = T = 100 1 = N = 5000 Example: Input: 2 2 5 Output: 00000000000010 00000000000101 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<iostream> using namespace std; void Binary_representation(int [],int ) ; int main()  { int t,no,i ; cin>>t ; while(t--) {    cin>>no ;      int arr[14]={0} ;    Binary_representation(arr,no) ;      for(i=0;i<14;i++)        cout<<arr[i] ;         cout...

PROBLEM : Given an N bit binary number, find the 1's complement of the number. The ones' complement of a binary number is defined as the value obtained by inverting all the bits in the binary representation of the number (swapping 0s for 1s and vice versa). Input: The first line of input takes the number of test cases, T. Then T test cases follow. The first line of each test case takes the number of bits, N. The second line of each test case takes N space separated integers denoting the N bits of the binary number. Output: Print the 1's complement for each test case in a new line. Constraints: 1<=T<=100 1<=N<=100 Example: Input: 3 2 1 0 2 1 1 3 1 0 1 Output: 0 1 0 0 0 1 0 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<iostream> using namespace std; void Complement(in...

PROBLEM : Construct an N input XOR Gate. An XOR Gate returns 1 if odd number of its inputs are 1, otherwise 0. Input: The first line of input takes the number of test cases, T. Then T test cases follow.Each test case consists of 2 lines. The first line of each test case takes the number of inputs to the XOR Gate, N. The second line of each test case takes N space separated integers denoting the inputs to the  XOR Gate. Note that the inputs can be either 1's or 0's. Output: For each test case on a new line print the output of the N input XOR Gate. Constraints: 1<=T<=100 1<=N<=100 Example: Input: 3 2 1 1 3 1 0 1 4 1 1 1 0 Output: 0 0 1 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<iostream> using namespace std; int result(int [],int ) ; int main()  { int t,arr[100],i,...

PROBLEM : Construct a 6 input gate which performs the following logical operation:  (not(A)).B + C.D +E.(not(F)) where A, B, C, D, E and F are the inputs to the 6 input gate. Input: The first line of input takes the number of test cases, T. Then T test cases follow. Each test case takes 6 space separated integers denoting the inputs to the 6 input gate, A, B, C, D,E and F. Note: the inputs can be either 1's or 0's. Output: Print the output of the 6 input gate for each test case on a new line. Constraints: 1<=T<=100 0<=A,B,C,D<=1 Example: Input: 3 1 1 0 0 1 1 1 1 1 1 1 1 1 0 0 1 1 1 Output: 0 1 0 Explanation: In the first test case, A=1, B=1, C=0, D=0, E=1, F=1 so (not(A)).B + C.D +E.(not(F)) = 0.1 + 0.0 + 1.0 = 0 + 0 + 0 = 0 In the second test case, A=1, B=1, C=1, D=1, E=1, F=1. so (not(A)).B + C.D +E.(not(F)) = 0.1 + 1.1 + 1.0 = 0 + 1 + 0 = 1 In the third test case, A=1, B=0, C=0, D=1, E=1, F=1. so (not(A)).B + C.D +E.(not(...