CSE Company Interview Questions

PROBLEM : Your task  is to implement the function atoi. The function takes a string(str) as argument and converts it to an integer and returns it. 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 a string str . Output: For each test case in a new line output will be an integer denoting the converted integer, if the input string is not a numerical string then output will be -1. Constraints: 1<=T<=100 1<=length of (s,x)<=10 Example(To be used only for expected output) : Input: 2 123 21a Output: 123 -1 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- /*You are required to complete this method */ int atoi(string str) {     int len,i,no ;     len=str.length() ;     no=0 ;     ...

PROBLEM : Given an array of size n and a number k. We must modify array K number of times. Here modify array means in each operation we can replace any array element arr[i] by -arr[i]. We need to perform this operation in such a way that after K operations, sum of array must be maximum? Examples: Input : arr[] = {-2, 0, 5, -1, 2}         K = 4 Output: 10 // Replace (-2) by -(-2), array becomes {2, 0, 5, -1, 2} // Replace (-1) by -(-1), array becomes {2, 0, 5, 1, 2} // Replace (0) by -(0), array becomes {2, 0, 5, 1, 2} // Replace (0) by -(0), array becomes {2, 0, 5, 1, 2} Input : arr[] = {9, 8, 8, 5}         K = 3 Output: 20 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 three 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. ...

PROBLEM : Given an array representing preorder traversal of BST, print its postorder traversal. 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,N is the size of array. The second line of each test case contains N input A[i]. Output: Postorder traversal of the given preorder traversal is printed. Otherwise 'NO' is printed. Constraints: 1 <=T<= 55 1 <= N <= 1000 1 <= arr[i] <= 1000 Example: Input: 3 5 40 30 35 80 100 8 40 30 32 35 80 90 100 120 8 7  9 6 1 4 2 3 40 Output: 35 30 100 80 40 35 32 30 120 100 90 80 40 NO -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<iostream> using namespace std; typedef struct TREE {     int data ;     struct TREE *left ;     struc...

PROBLEM : Given an array, write a program that prints 1 if given array can represent preorder traversal of a BST, else prints 0. 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,N is the size of array. The second line of each test case contains N input A[i]. Output: Should print 1 if given array can represent preorder traversal of BST. Otherwise 0. Constraints: 1 <=T<= 55 1 <= N <= 1000 1 <= arr[i] <= 1000 Example: Input: 3 5 40 30 35 80 100 8 40 30 32 35 80 90 100 120 8 7  9 6 1 4 2 3 40 Output: 1 1 0 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<iostream> using namespace std; int Preorder_Traversal_BST(int [],int ,int ) ; int find_Rlarge(int [],int ,int ) ; int allR_greater(int [],int ,int ...

PROBLEM : Dr. Strange has developed some new powers since he has started programming. Now if a villan throws a 1 at him, he absorbs it and add it to his already existing binary string s. There are n villans and each of them throws a '1' at him. At each point you have to detemine the resulting string s. Input: First line of input contains n denoting the number of enemies. Each of the next n lines contain an integer l and a string s denoting the length of the existing binary string and the string itself. Output: For each of the n lines print a string denoting the resulting binary string at each steps. Constraints: 1<=n<=20 1<=l<=100 Example: Input: 2 4 1010 5 11100 Output 1011 11101 Explanation: For test case 1 : 1010+1 = 1011 as he absorbs 1 and add to the existing string -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : ---------------------------------------------------------...

PROBLEM : As usual Babul is back with his problem but this time with numbers. In his problem there is a number P (always a whole number) with N digits. Now he started finding out the largest possible even number formed by rearranging this N digit number. For example consider number 1324, after rearranging the digits the largest even number possible is 4312. Note: In case the number does not contain any even digit then output the largest odd number possible. Input: The first line of input will contain an integer T which is the no. of test cases. Each of the next T lines will contain a number P. Output: For each test case in a new line print the required result. Constraints: 1<=T<=100 1<=N<=1000 Example: Input: 5 1324 3415436 1023422 03517 3555 Output: 4312 6543314 4322210 75310 5553 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : --------------------------------------------------...

PROBLEM : Given an array of integers, the task is to find count of elements before which all the elements are smaller. First element is always counted as there is no other element before it. Input: The first line of input will contain no of test cases T . Then T test cases follow . Each test case contains 2 lines. The first line of each test case contains an integer N denoting the number of elements in the array, the next line contains N space separated integer's denoting the elements of the array. Output: For each test case in new line print the Number of Elements before which no element is bigger Constraints: 1<=T<=100 1<=N<=1000 Example: Input 2 6 10 40 23 35 50 7 3 5 4 1 Output 3 1 Explanation: Test Case 1 Input: arr[] =  {10, 40, 23, 35, 50, 7} Output: 3 The elements are 10, 40 and 50. No of elements is 3 Test Case 2 Input: arr[] = {5, 4, 1} Output: 1 There is only one element 5 No of element is 1 -------------------------...

PROBLEM : Given a sorted array A of size N, the task is to find whether an element exists in the array from where number of smaller elements is equal to number of greater elements. If Equal Point appears multiple times in input array, print the index of its first occurrence. If Equal Point doesn't exists then print -1. Examples : Input  : arr[] = {1, 2, 3, 3, 3, 3} Output : 1 Equal Point is arr[1] which is 2. Number of elements smaller than 2 and greater than 2 are same. Input  : arr[] = {1, 2, 3, 3, 3, 3, 4, 4} Output : -1 Input : arr[] = {1, 2, 3, 4, 4, 5, 6, 6, 6, 7} Output : 3 First occurrence of equal point is arr[3] Input: The first line of input contains T denoting the no of test cases . Then T test cases follow . The first line of each test case contains an Integer N and the next line contains N space separated values of the array A[ ] . Output: For each test case output the required result in a new line. Constraints: 1<=T<=100 1<=N...

PROBLEM : Find total number of Squares in a N*N cheesboard. Input: The first line contains an integer T, depicting total number of test cases. Then following T lines contains an integer N that is the side of the chessboard. Output: Each seperate line showing the maximum number of squares possible. Constraints: 1 = T = 100 1 = N = 100 Example: Input : 2 1 2 Output : 1 5 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<iostream> using namespace std; long long Total_square(int ) ; int main()  { int t,no ; cin>>t ; while(t--) {    cin>>no ;    cout<<Total_square(no) ;    cout<<endl ; } return 0; } long long Total_square(int no) {     long long count=0 ;         while(no)     {...

PROBLEM : For an integer n find number of trailing zeroes in n! . Input: The first line contains an integer 'T' denoting the total number of test cases. In each test cases, it contains an integer 'N'. Output: In each seperate line output the answer to the problem. Constraints: 1<=T<=100 1<=N<=1000 Example: Input: 1 9 Output: 1 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<iostream> using namespace std; int Trailing_zeroes(int ) ; int main()  { int t,no ; cin>>t ; while(t--) {    cin>>no ;    cout<<Trailing_zeroes(no)<<endl ; } return 0; } int Trailing_zeroes(int no) {    int i , count ;    count=0 ;      for(i=5;no/i>=1;i*=5)    {        count...

PROBLEM : Given an array with repeated elements, the task is to find the maximum distance between two occurrences of an element. Input: The first line of input will contain no of test cases T . Then T test cases follow . Each test case contains 2 lines. The first line of each test case contains an integer N denoting the number of elements in the array, the next line contains N space separated integer's. Output: For each test case in new line print the Maximum distance between two occurrences of an element Constraints: 1<=T<=100 1<=N<=1000 Example: Input 2 6 1 1 2 2 2 1 12 3 2 1 2 1 4 5 8 6 7 4 2 Output 5 10 Explanation Test case 1: arr[] = {1, 1, 2, 2, 2, 1} Max Distance: 5 Distance for 1 is: 5-0 = 5 Distance for 2 is : 4-2 = 2 Max Distance 5 Test case 2: arr[] = {3, 2, 1, 2, 1, 4, 5, 8, 6, 7, 4, 2} Max Distance 10 maximum distance for 2 is 11-1 = 10 maximum distance for 1 is 4-2 = 2 maximum distance for 4 is 10-5 = 5 --------...

PROBLEM : Given a singly linked list of integers, Your task is to complete a function that returns true if the given list is palindrome, else returns false. Input: The first line of input contains an integer T denoting the no of test cases. Then T testcases follow. Each test case contains 2 line the first line contains an integer N denoting the size of the linked list. In the next line are N space separated values of the nodes of the linked list. Output: For each test case output will be 1 if the linked list is a pallindrome else 0. Constraints: 1<=T<=1000 1<=N<=50 Example(To be used only for expected output): Input 2 3 1 2 1 4 1 2 3 4 Output: 1 0 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- /*The structure of the Node is struct Node {     int data;     struct Node* next; };*...

PROBLEM : Given a simple expression tree, which is also a full binary tree consisting of basic binary operators i.e., + , – ,* and / and some integers, Your task is to evaluate the expression tree. You need to complete the function evalTree which takes the root of the tree as its only argument and returns an integer denoting the result obtained by simplifying the expression 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 contains an integer N denoting the no of nodes. Then in the next line are N space separated values of the nodes of the Binary tree filled in continous way from the left to the right. Output: For each test case output will be the result obtained by simplifying the expression tree. Constraints: 1<=T<=100 2<=N<=50 Example(To be used only for expected Output): Input: 2 7 + * - 5 4 100 20 3 - 4 7 Output: 100 -3 Explanation: For the first test case t...

PROBLEM : A Professor conducts a Computer Science paper for all students. He had strictly ordered all students to sit according to their roll numbers. However when he started checking the papers, he found out that all the papers were randomly ordered. The students had sat randomly during the exam instead of sitting according to their roll numbers. Professor was very angry and he wanted to teach the students a lesson. He decides to sort the papers by Bubble Sort, count the number of swaps required for each and every student and deduct as many marks of a student as were the number of swaps required for that student. However he also has to maintain a class average of atleast M else he may lose his job. The Professor wants to know whether he should punish the students or save his job. Input: The first line of input takes an integer T denoting the total number of test cases. Then T test cases follow. Each test case has 3 input lines. The first line of each test case takes the numbe...

PROBLEM : Given a non-negative integer num, repeatedly add all its digits until the result has only one digit. Input: The first line contains 'T' denoting the number of testcases. Then follows description of testcases. The next T lines contains a single integer N denoting the value of N. Output: Output the sum of all its digit until the result has only one digit. Constraints: 1<=T<=30 1<=n<=10^9 Example: Input : 2 1 98 Output : 1 8 Explanation:  For example, if we conisder 98, we get 9+8  = 17 after first addition. Then we get 1+7 = 8.  We stop at this point because we are left with one digit. -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<iostream> using namespace std; int Repetitive_Addition(long long ) ; int main()  {     long long no ;     ...

PROBLEM : A magic number is defined as a number which can be expressed as a power of 5 or sum of unique powers of 5. First few magic numbers are 5, 25, 30(5 + 25), 125, 130(125 + 5), …. Given the value of n. find the nth Magic number. Input: The first line contains an integer T, depicting total number of test cases. Then following T lines contains an integer N depicting the value of N. Output: Print the nth magic number in a separate line. Constraints: 1 = T = 30 1 = N = 100 Example: Input: 2 1 2 Output: 5 25 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<iostream> using namespace std; int Magic_Number(int ) ; int main()  { int t,no ; cin>>t ; while(t--) {    cin>>no ;    cout<<Magic_Number(no)<<endl ; } return 0; } int M...

PROBLEM : Implement a Queue using Array. 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 1 2...

PROBLEM : Given a number n the task is to complete the function which returns an integer denoting the smallest number evenly divisible by each number from 1 to n. 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 output will be in new line denoting the smallest number evenly divisible by each number from 1 to n. Constraints: 1<=T<=50 1<=n<=25 Example(To be used only for expected output): Input: 2 3 6 Output: 6 60 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- /*You are required to complete this method */ long long lcm(long long ,long long ) ; long long gcd(long long ,long long ) ; long long getSmallestDivNum(long long no) {     int i ;     long long ans=1 ; ...

PROBLEM : Given a sample space S consisting of all perfect squares starting from 1, 4, 9 and so on. You are given a number N, you have to print the number of integers less than N in the sample space S. Input : The first line contains an integer T, denoting the number of test cases.Then T test cases follow. The first line of each test case contains an integer N, denoting the number. Output : Print the answer of each test case in a new line. Constraints : 1<=T<=100 1<=N<=10^18 Example Input : 2 9 3 Output : 2 1 -------------------------------------------------------------------------------- SIMPLE c IMPLEMENTATION : -------------------------------------------------------------------------------- #include <stdio.h> int square(int n) {     int i=1,temp=0,count=0;     while(temp<n)     {         temp=i*i;         count=count+1;         i++; ...

PROBLEM : A file contains data as follows( Student name, marks in 3 subjects) Shrikanth 20 50 60 Kiran 30 80 90 Find the student who has maximum average score. 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,N is the number of student. The second line of each test case contains N input Student name and marks in 3 subject. Output: Print the student who has maximum average score and maximum average score(in int). Constraints: 1 = T = 10 1 = N = 15 1 = s = 10 1 = marks = 100 Example: Input: 2 2 Shrikanth 20 30 10 Ram 100 50 10 3 Adam 50 10 40 Suresh 22 1 56 Rocky 100 90 10 Output: Ram 53 Rocky 66 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<iostream> using namespace std; #include<string.h> class student ...