CSE Company Interview Questions

PROBLEM : Given a stack, the task is to sort it such that the top of the stack has the greatest element. Input: The first line of input will 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 stack. Then in the next line are N space separated values which are pushed to the the stack. Output: For each test case output will be the popped elements from the sorted stack. Constraints: 1<=T<=100 1<=N<=100 Example(To be used only for expected output): Input: 2 3 3 2 1 5 11 2 32 3 41 Output: 3 2 1 41 32 11 3 2 Explanation: For first test case stack will be 1 2 3 After sorting 3 2 1 When elements  popped : 3 2 1 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- /*The structure of the class is class SortedStack{ p

PROBLEM : Given a string 's', your task is to complete the function checkString which returns true if it is possible to convert 's' to a string that is repetition of a substring with 'k' characters else returns false, where in order to convert we can replace one substring of length k with k characters. Examples: Input: str = "abcbedabcabc",  k = 3 Output: 1 Replace "bed" with "abc" so that the whole string becomes repetition of "abc". Input: str = "bcacbcac", k = 2 Output: 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 a string s. The second line of each test case contains an integer n. Output: For each test case in a new line output will be 1 if it is possible to convert the string else 0. Constraints: 1<=T<=100 1< |Length of string| <=100

PROBLEM : Given an array A[] of size n and an integer k, your task is to complete the function countDistinct which prints the count of distinct numbers in all windows of size k in the array A[]. Example Input:  A[] = {1, 2, 1, 3, 4, 2, 3};             k = 4 Output: 3 4 4 3 Explanation: First window is {1, 2, 1, 3}, count of distinct numbers is 3 Second window is {2, 1, 3, 4} count of distinct numbers is 4 Third window is {1, 3, 4, 2} count of distinct numbers is 4 Fourth window is {3, 4, 2, 3} count of distinct numbers is 3 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 two integers n and k. 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 space separated values denoting counts of distinct numbers in all windows of size k in the array A[]. Constraints: 1<=T<=100 1<=n,k<=100 1<=A[]<=100

PROBLEM : Given an array having both positive an negative integers . Your task is to complete the function maxLen which returns the length of maximum subarray with 0 sum . The function takes two arguments an array A and n where n is the size of the array A . Input: The first line of input contains an element T denoting the No of test cases. Then T test cases follow. Each test case consist of 2 lines. The first line of each test case contains a number denoting the size of the array A. Then in the next line are space separated values of the array A . Output: For each test case output will be the length of the largest subarray which has sum 0 . Constraints: 1<=T<=100 1<=N<=100 -1000<=A[]<=1000 Example: Input 1 8 15  -2  2  -8  1  7  10 23 Output 5 Explanation In the above test case the  largest subarray with sum 0 will be -2  2  -8  1  7 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION

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 : Given a binary tree and a integer value K, the task is to find all nodes in given binary tree having K leaves in sub-tree rooted with them. If no node is found then print -1. Input: The first line of input  contains an integer T denoting the no of test cases. First line of each test case consists of two integers N and K, denoting Number of Nodes in binary Tree and number of leaves in sub-tree rooted with them. Second line of each test case consists of the struct Node, which has a data part which stores the data, pointer to left child and pointer to right child. Output: For each test case print the respective output in each line. Constraints: 1<=T<=100 1<=N,K<=100 1<=value of nodes<=100 Example(To be used only for expected output): Input: 2 2 1 0 1 L 0 2 R 4 2 0 1 L 0 2 R 2 3 R 2 4 L Output: -1 2 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -----------------------