This repository will have solutions of problems asked in interview.
-
Using Built In method Collections.reverse(Arrays.asList(arr)) Using Auxillary Array (Auxillary Space) T(n) -> O(n) & S(n) -> O(n) By Swapping First and Last Element of Array one by one (Using two pointers) T(n) -> O(n) -
By Simple Linear Search of max and min element using two variables and comparing each element one by one. T(n) -> O(n) & S(n) -> O(1) By comparing in pairs of elements in an array. It is best method among others in terms of number of comparisions. T(n) -> O(n) & S(n) -> O(1) -
Using Built In method - Arrays.sort(array) T(n) = O(nlogn) -
By sorting Algorithm or built-In function T(n) = O(nlogn) S(n) = O(1) By using Counting Sort T(n) = O(n) + O(n) = O(2n) By using Switch case or Dutch National Flag Algorithm T(n) = O(n) S(n) = O(1) -
You have been given an empty array(ARR) and its size N. The only input taken from the user will be N and you need not worry about the array. Your task is to populate the array using the integer values in the range 1 to N(both inclusive) in the order - 1,3,.......4,2. Note: You need not print the array. You only need to populate it. Input Format : The first line contains an Integer 't' which denotes the number of test cases or queries to be run. Then the test cases follow. The first and the only line of each test case or query contains an integer 'N'. Output Format : For each test case, print the elements of the arra/listy separated by a single space. Output for every test case will be printed in a separate line. Constraints : 1 <= t <= 10^2 0 <= N <= 10^4 Time Limit: 1sec Sample Input 1 : 1 6 Sample Output 1 : 1 3 5 6 4 2 Sample Input 2 : 2 9 3 Sample Output 2 : 1 3 5 7 9 8 6 4 2 1 3 2 -
By Sorting the array T(n) = O(nlogn) + O(n) S(n) = O(1) By using extra rray to store Frequency of each element from input array T(n) = O(n) + O(n) = O(2n) S(n) = O(n) -
By using temporary array of size of both the arrays i.e n1 & n2 T(n) = O(n1 + n2) S(n) = O(n1 + n2) ------ -
By using 3 loops T(n) = O(n^3) By Kadane's Algorithm - Take sum of elements till its positive else return max negative element T(n) = O(n) S(n) = O(1) -
First Ask the Interviewer What are the ranges of values in the matrix
If ans is - All values will be positive on the sides of zero ----- -
By sorting the array and checking adjacent elements T(n) = O(n) + O(nlogn) S(n) = O(1) By using counting sot algorithm T(n) = O(n) S(n) = O(n) By LinkedList Cycle method T(n) = O(n) S(n) = O(1) -
In Pascal's triangle, each number is the sum of the two numbers directly above it as shown:
Interviewer can ask 3 types of ques based on this - a. Given Number of rows i.e N=5 and print the first N rows of Pascals Triangle T(n) = O(n) S(n) = O(n) b. Given N =5, print the Nth row only --> Approach-1 => Find nth element for each row and column by using below formula T(n) = O(n^2) S(n) = O(n^2) --> Approach-2 => Find nth element for each row and column optimally T(n) = O(n) S = O(1) c. Given row number and column number i.e r & c, print the element present at that rownumber & column number ` --> Formula :- r-1 C c-1 (C = combination - nCr) example :- r=4 c=3 element = 4-1 C 3-1 = 3 C 2 = 3*2 / 2*1 = 3 (answer)
-
4C3 - 432 / 321 = 4/1 = 4
-
7C2 - 76 / 21 = 7*3 = 21
-
Input - 1 3 5 4 2 - 1 4 2 3 5 BREAKDOWN -----> 5 \ 3 4 \ INCREASING ORDER 1 2 \ step 1 - Find the breakdown point ---> Linear traverse the array from back find A[i] < A[i+1] , index1 = i+1 T(n) = O(n) ---> Again Linearly Traverse the array from back to get the slightly greater than that element , find A[index1] < A[index2] ans swap them , index1 = i+1 T(n) = O(n) ---> Again Traverse the array from back and reverse the right half T(n) = O(n) T(n) = O(n) S(n) = O(n) -
First Ask the Interviewer whether the Intervals are sorted or not
KARNA HAI .....
- Base Case
- Smaller Problem Solution
- Processing steps
-
Write a program to find x to the power n (i.e. x^n). Take x and n from the user. You need to return the answer. Do this recursively. Input format : Two integers x and n (separated by space) Output Format : x^n (i.e. x raise to the power n) Constraints : 1 <= x <= 30 0 <= n <= 30 Sample Input 1 : 3 4 Sample Output 1 : 81 Sample Input 2 : 2 5 Sample Output 2 : 32 -
Given is the code to print numbers from 1 to n in increasing order recursively. But it contains few bugs that you need to rectify such that all the test cases pass. Input Format : Integer n Output Format : Numbers from 1 to n (separated by space) Constraints : 1 <= n <= 10000 Sample Input 1 : 6 Sample Output 1 : 1 2 3 4 5 6 Sample Input 2 : 4 Sample Output 2 : 1 2 3 4 -
Given an array of length N, you need to find and return the sum of all elements of the array. Do this recursively. Input Format : Line 1 : An Integer N i.e. size of array Line 2 : N integers which are elements of the array, separated by spaces Output Format : Sum Constraints : 1 <= N <= 10^3 Sample Input 1 : 3 9 8 9 Sample Output 1 : 26 Sample Input 2 : 3 4 2 1 Sample Output 2 : 7 -
Given an array of length N and an integer x, you need to find if x is present in the array or not. Return true or false. Do this recursively. Input Format : Line 1 : An Integer N i.e. size of array Line 2 : N integers which are elements of the array, separated by spaces Line 3 : Integer x Output Format : 'true' or 'false' Constraints : 1 <= N <= 10^3 Sample Input 1 : 3 9 8 10 8 Sample Output 1 : true Sample Input 2 : 3 9 8 10 2 Sample Output 2 : false -
Given an array of length N and an integer x, you need to find and return the first index of integer x present in the array. Return -1 if it is not present in the array. First index means, the index of first occurrence of x in the input array. Do this recursively. Indexing in the array starts from 0. Input Format : Line 1 : An Integer N i.e. size of array Line 2 : N integers which are elements of the array, separated by spaces Line 3 : Integer x Output Format : first index or -1 Constraints : 1 <= N <= 10^3 Sample Input : 4 9 8 10 8 8 Sample Output : 1 -
Given an array of length N and an integer x, you need to find and return the last index of integer x present in the array. Return -1 if it is not present in the array. Last index means - if x is present multiple times in the array, return the index at which x comes last in the array. You should start traversing your array from 0, not from (N - 1). Do this recursively. Indexing in the array starts from 0. Input Format : Line 1 : An Integer N i.e. size of array Line 2 : N integers which are elements of the array, separated by spaces Line 3 : Integer x Output Format : last index or -1 Constraints : 1 <= N <= 10^3 Sample Input : 4 9 8 10 8 8 Sample Output : 3 -
Given an array of length N and an integer x, you need to find all the indexes where x is present in the input array. Save all the indexes in an array (in increasing order). Do this recursively. Indexing in the array starts from 0. Input Format : Line 1 : An Integer N i.e. size of array Line 2 : N integers which are elements of the array, separated by spaces Line 3 : Integer x Output Format : indexes where x is present in the array (separated by space) Constraints : 1 <= N <= 10^3 Sample Input : 5 9 8 10 8 8 8 Sample Output : 1 3 4 -
Given an integer N, count and return the number of zeros that are present in the given integer using recursion. Input Format : Integer N Output Format : Number of zeros in N Constraints : 0 <= N <= 10^9 Sample Input 1 : 10204 Sample Output 1 : 2 Sample Input 2 : 708000 Sample Output 2 : 4 -
Given k, find the geometric sum i.e. 1 + 1/2 + 1/4 + 1/8 + ... + 1/(2^k) using recursion. Input format : Integer k Output format : Geometric sum Constraints : 0 <= k <= 1000 Sample Input 1 : 3 Sample Output 1 : 1.875 Sample Input 2 : 4 Sample Output 2 : 1.93750 -
Check whether a given String S is a palindrome using recursion. Return true or false. Input Format : String S Output Format : 'true' or 'false' Constraints : 0 <= |S| <= 1000 where |S| represents length of string S. Sample Input 1 : racecar Sample Output 1: true Sample Input 2 : ninja Sample Output 2: false -
Write a recursive function that returns the sum of the digits of a given integer. Input format : Integer N Output format : Sum of digits of N Constraints : 0 <= N <= 10^9 Sample Input 1 : 12345 Sample Output 1 : 15 Sample Input 2 : 9 Sample Output 2 : 9
- Optimal Substructure - In this , Bigger Problem depends upon smaller problem
- Overlapping Subproblem - In this, SubProblem should repeat again and again
-
A child runs up a staircase with 'n' steps and can hop either 1 step, 2 steps or 3 steps at a time. Implement a method to count and return all possible ways in which the child can run-up to the stairs. Input format : The first and the only line of input contains an integer value, 'n', denoting the total number of steps. Output format : Print the total possible number of ways. Constraints : 0 <= n <= 10 ^ 4 Time Limit: 1 sec Sample Input 1: 4 Sample Output 1: 7 Sample Input 2: 10 Sample Output 2: 274 -
Min Steps To One Given a positive integer 'n', find and return the minimum number of steps that 'n' has to take to get reduced to 1. You can perform any one of the following 3 steps: 1.) Subtract 1 from it. (n = n - 1) , 2.) If its divisible by 2, divide by 2.( if n % 2 == 0, then n = n / 2 ) , 3.) If its divisible by 3, divide by 3. (if n % 3 == 0, then n = n / 3 ). Write brute-force recursive solution for this. Input format : The first and the only line of input contains an integer value, 'n'. Output format : Print the minimum number of steps. Constraints : 1 <= n <= 200 Time Limit: 1 sec Sample Input 1 : 4 Sample Output 1 : 2 Explanation of Sample Output 1 : For n = 4 Step 1 : n = 4 / 2 = 2 Step 2 : n = 2 / 2 = 1 Sample Input 2 : 7 Sample Output 2 : 3 Explanation of Sample Output 2 : For n = 7 Step 1 : n = 7 - 1 = 6 Step 2 : n = 6 / 3 = 2 Step 3 : n = 2 / 2 = 1 -
a. Problem statement:
The binary number system only uses two digits, 0 and 1. Any string that represents a number in
the binary number system can be called a binary string. You are required to implement the
following function:
int OperationsBinaryString(char *str);
The function accepts a string 'str' as its argument. The string 'str' consists of binary digits
separated with an alphabet as follows:
• 'A' denotes AND operation
• 'B' denotes OR operation
• 'C' denotes XOR operation
You are required to calculate the result of the string 'str', scanning the string left to right, taking
one operation at a time, and return the same.
Note:
• No order of priorities of operations is required.
• Length of 'str' is odd
• If 'str' is NULL or None(in case of python), return -1
Example:
Input:
str: ICOCICIAOBI
Output:
1