SDE - 1

You are given an array “ARR” of N integers. Your task is to find the total number of distinct subarrays of A having at most K odd elements.

Note:

Two subarrays are distinct when they have at least one different element.

Example:

If ARR = [3,2,3], and K = 1 
then there are 4 subarrays with at most K odd elements:
 [3], [3,2], [2,3],[2]

You are given an array 'arr' of 'N' distinct integers. Your task is to find all the non-empty subsets of the array.

Note: You can return the subsets in any order, you don’t have to specifically sort them.

Example:

arr=[3,4,5]
subsets ={3}, {3,4}, {3,4,5}, {3,5}, {4}, {4,5}, {5}

You have been given the start and end times of 'N' intervals. Write a function to check if any two intervals overlap with each other.

Note :

If an interval ends at time T and another interval starts at the same time, they are not considered overlapping intervals.

Given an integer ‘N’ representing the number of pairs of parentheses, Find all the possible combinations of balanced parentheses with the given number of pairs of parentheses.

Note :

Conditions for valid parentheses:
1. All open brackets must be closed by the closing brackets.

2. Open brackets must be closed in the correct order.

For Example :

()()()() is a valid parentheses.
)()()( is not a valid parentheses.

Ninja got a map in his hand with ‘N’ cities numbered 0 to ‘N’, connected with bridges. He asks his sister to delete some cities from the map.

He will ask his sister a ‘Q’ query. Each query is denoted by an integer ‘X’, meaning that he will delete the city ‘X’. He wants to see if the new map obtained after deleting the city node will have more connected components than the previous map.

He wants to build the program for the queries given by his sister for the above condition.

Ninja knows that you are a very good programmer and can help him in writing the code for the above. Help Ninja!

Note:

A connected component in the map is the maximum subset of cities that are connected i.e we can go from one city to any other in that subset.

You have been given a sorted array of length ‘N’. You need to construct a balanced binary search tree from the array. If there can be more than one possible tree, then you can return any.

Note:

1. A balanced binary tree is a binary tree structure in which the left and right subtrees of every node differ in height by no more than 1.

2. A binary search tree is a binary tree data structure, with the following properties
    a. The left subtree of any node contains nodes with value less than the node’s value.
    b. The right subtree of any node contains nodes with values equal to or greater than the node’s value.
    c. Right, and left subtrees are also binary search trees.

Example:

Below tree, is a balanced binary search tree

Below tree is not a balanced tree as the height of the left subtree and right subtree of node ‘5’ differs by more than 1. Moreover, the tree is also not a BST as node ‘2’ is less than node ‘3’ but ‘2’ is the right child of ‘3’.

You are given a 'Nx3' 2-D array 'Jobs' describing 'N' jobs where 'Jobs[i][0]' denotes the id of 'i-th' job, 'Jobs[i][1]' denotes the deadline of 'i-th' job, and 'Jobs[i][2]' denotes the profit associated with 'i-th job'.

You will make a particular profit if you complete the job within the deadline associated with it. Each job takes 1 unit of time to be completed, and you can schedule only one job at a particular time.

Return the number of jobs to be done to get maximum profit.

Note :

If a particular job has a deadline 'x', it means that it needs to be completed at any time before 'x'.

Assume that the start time is 0.

For Example :

'N' = 3, Jobs = [[1, 1, 30], [2, 3, 40], [3, 2, 10]].

All the jobs have different deadlines. So we can complete all the jobs.

At time 0-1, Job 1 will complete.
At time 1-2, Job 3 will complete.
At time 2-3, Job 2 will complete.

So our answer is [3 80].

He gave me to write a code in Java using OOP.

Later asked me advantages of abstraction and interfaces.

Later he asked me questions like if I give you 1 million dollar where and how will you use it?