CSE Company Interview Questions

PROBLEM : An array is bitonic if it is comprises of an increasing sequence of integers followed immediately by a decreasing sequence of integers. Given such a array, you need to find a element X in it and print its index. In case, X does not exist in the array print "OOPS! NOT FOUND" without quotes. Note: It is guaranteed that array consist of distinct elements. And array indexing is from 0. Input: First line will consist  a number T, the number of test cases. Each test case will then consist of two numbers N and X. N being the array size and X being the element to be searched for. Next line will consist of N space separated integers. Output: Print the required answer on separate lines. Constraints: 1<=T<=10 1<=N<=200 -100<=A[i]<=100 Example: INPUT 1 5 2 1 2 7 4 3 OUTPUT 1 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : ----------------------------------------------...

PROBLEM : Given two unsorted arrays arr1[] and arr2[]. They may contain duplicates. For each element in arr1[] count elements less than or equal to it in array arr2[]. 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 two integers m and n denoting the size of the two arrays. The following two lines will contain both the arrays respectively. Output: Print the count of elements less than or equal to it in arr2 for each element in arr1. Constraints: 1<=T<=10^5 1<=m,n<=10^5 1<=arr1[i],arr2[j]<=10^5 Example: Input: 2 6 6 1 2 3 4 7 9 0 1 2 1 1 4 5 7 4 8 7 5 1 4 48 3 0 1 1 5 Output: 4 5 5 6 6 6 5 6 6 6 3 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- // function to count for each element in 1st array, // elements...

PROBLEM : Given a sorted array with possibly duplicate elements, the task is to find indexes of first and last occurrences of an element x in the given array. Examples: Input : A[] = {1, 3, 5, 5, 5, 5 ,67, 123, 125}           x = 5 Output : First Occurrence = 2          Last Occurrence = 5 Input : A[] = {1, 3, 5, 5, 5, 5 ,7, 123 ,125 }           x = 7 Output : First Occurrence = 6          Last Occurrence = 6 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 size of the array. Then in the next line are N space separated values of the array. The last line of each test case contains an integer x. Output: For each test case in a new line print two integers separated by space denoting the first and last occurrence of the element x. If the element is not present i...

PROBLEM : Given two sorted arrays. There is only 1 difference between the arrays. First array has one element extra added in between. Find the index of the extra element. 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 number of elements in array. The second line of each test case contains N space separated values of the array A[]. The Third line of each test case contains N-1 space separated values of the array B[]. Output: Return the index of the corresponding extra element in array A[].(starting index 0). Constraints: 1<=T<=100 1<=N<=100 1<=Ai<=1000 Example: Input: 2 7 2 4 6 8 9 10 12 2 4 6 8 10 12 6 3 5 7 9 11 13 3 5 7 11 13 Output: 4 3 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : ------------------------------------------------------------...

PROBLEM : Given a sorted array of integers, every element appears twice except for one. Find that single one in linear time complexity and without using extra memory. 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 number that appears only once in the array. Constraints: 1 = T = 70 1 = N = 100 0 = A[i] = 100000 Example: Input: 1 11 1 1 2 2 3 3 4 50 50 65 65 Output: 4 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION :( O(n) Solution using Bitwise) -------------------------------------------------------------------------------- #include<iostream> using namespace std; int main() { int t ; cin>>t ; while(t--) {    int no ;    cin>>n...

PROBLEM : Gautam and Subhash are two brothers. They are similar to each other in all respects except one. They have different ways of searching. When Gautam has to search for an item from a lot, he goes through all the items one by one and stops when he finds the item. However Subhash has an entirely different and interesting way of searching. However the search works only for items which are sorted. He goes to the middle of the lot, if he finds the desired item, he stops, if not, he checks whether the middle item is smaller or larger than the required item. If larger, he repeats the same process for the first half of the lot, otherwise second half. One day, the two brothers sit in a contest in which they have to find a name out of a sorted dictionary. Whoever finds out the name first will win the contest. The audience is very eager to know who will win and hence they want you to predict. Input: The first line of input takes the number of test cases, T. The next T lines take the...

PROBLEM : Given a sorted array having no duplicates, arr[] and a value, x, find floor of x in given array. Floor of x is the largest element in arr[] such that the element is smaller than or equal to x. If floor exists, then return index of it, else return -1. Examples: Input : arr[] = {1, 2, 8, 10, 11, 12, 19}, x = 5 Output : 1 1 is index of 2. 2 is the largest element in arr[] smaller than 5. Input : arr[] = {1, 2, 8, 10, 11, 12, 19}, x = 20 Output : 6 19 is the largest element in arr[] smaller than 20. Input : arr[] = {1, 2, 8, 10, 11, 12, 19}, x = 0 Output : -1 Since floor doesn't exist, output is -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 and x, N is the size of array. The second line of each test case contains N array elements. Output: Print index of floor of x if it exists, else print -1 Constraints: 1 = T = 500 1 = N = 1000 0 = X = 1000 1 = arr[i] = 10000 ...

PROBLEM : A sorted array A[ ] with distinct elements is rotated at some unknown point, the task is to find the minimum element in it. Expected Time Complexity: O(Log 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 consist of two lines. The first line of each test case consists of an integer N, where N is the size of array. The second line of each test case contains N space separated integers denoting array elements. Output: Corresponding to each test case, in a new line, print the minimum element in the array. Constraints: 1 = T = 100 1 = N = 500 1 = A[i] = 1000 Example: Input 1 5 4 5 1 2 3 Output 1 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<iostream> using namespace std; #define max 500 int Minimum_eleme...

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

PROBLEM : Given an n x m matrix, where every row and column is sorted in increasing order, and a number x . The task is to find whether element x is present in the matrix or not. Expected Time Complexity : O(m + 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 three lines. First line of each test case consist of two space separated integers N and M, denoting the number of element in a row and column respectively. Second line of each test case consists of N*M space separated integers denoting the elements in the matrix in row major order. Third line of each test case contains a single integer x, the element to be searched. Output: Corresponding to each test case, print in a new line, 1 if the element x is present in the matrix, otherwise simply print 0. Constraints: 1<=T<=200 1<=N,M<=30 Example: Input: 2 3 3 3 30 38 44 52 54 57 60 69 62 1 6 18 21 2...