9 weeks ago

John 910

Hyderabad

Question 1

Given an array umbrella of size N. umbrella[i] means the number of people that it can cover. Find the minimum number of umbrella needed to cover exactly amount person. If not possible, return -1.

constraint:

• 1 <= N <= 1000
• 1 <= amount <= 1000

Question 2

Given two arrays A and B of same length N.

You can select a subset of A and increment them by 1. You can only do this at most once.

You can also freely re-arrange elements in A.

Return True if A can be made into B, False otherwise.

Constraint

1 <= N <= 1e6

-1e6 <= A[i] <= 1e6

-1e6 <= B[i] <= 1e6

Function sigature

bool func(string A, string B){
    // implement your solution here.
}

Question 3

Given a grid. There are 3 types of trees in it, denoted as 0, 1, 2. Your task is to divide it into K parts such that each part has at least one tree of type 2.

Rules are as follows:

Vertical Cut through the whole grid, you will give the left part to a person, and it will no longer be considered.

Horizontal Cut through the whole grid, give the top part to a person, and it will no longer be considered.

Find the number of ways to do it. Because the number may be too large, return it modulo 1000000007.

Constraint

Not Given.

Question 4

There is a rectangular

forest with a total of m * n trees planted, with a

total of 3 species of trees, number 1 means pine

tree, 2 means poplar

tree and 3 means willow tree.

Now the forest needs to be divided into x parts

for x people to take care

of. The forest can be divided horizontally or vertically, and each division

needs to divide the whole forest into two parts. If the division is

horizontal, give the top one to one person and continue to divide the

forest below; if the division is vertical, give the left one to one person

and continue to divide the forest on the right. You need to make sure

that each person has at least one poplar tree.

Please calculate how many divisions there are in total. Since the answer

may be a very large number, please return the result of taking the

remainder of 10e9+7.

Example:

Input:forest = [[1, 2, 3], [2, 1, 2], [3, 1, 1]], number = 3.

Output: 4

8 months ago

Akshay Sharma 990

Chandigarh

Question 1

Overview

• We are given an array U of N size containing some number that specifies the number of people the U[i] (Umbrella) can cover.
• We are also given an integer X denoting people we need to choose some U[i] from the array that will be the minimal and cover all Xs
• If it is not possible to cover all X people then we can return -1;

Solution

• The Solution to the problem is relatively more straightforward if we first sort of array of Umbrellas in reverse order.
  • After sorting the array in reverse order we will start integrating our array and maintain a sum variable and check if sum+a[i]>=X if yes we will set some checker to true that was initially false and break our loop else we will keep increasing sum by a[i] and increase our counter variable by 1.
  • If we reach the end of our loop and the sum is still less than X we can return -1 in such case.
  • Time Complexity : O(N)

8 months ago

Akshay Sharma 990

Chandigarh

Question

Overview

• Given two arrays A and B both arrays have N integers
• We can choose some subset of K indexes from A and increase every element of those K indexes by 1.
• Permute the A and tell if it is possible to make both arrays equally
• If it is possible to make both arrays equal print 1 else print 0

Solution

• We are given two arrays and we can choose any k integers from 0 to n-1.
• Only operation we can do is in array A
• Choosing some subset is nothing as we can choose from any indexes from 0 to n-1 and increase one
• The first thing we can do is sort both arrays in ascending order as mentioned we can rearrange this array, So it's not necessary for elements should remain in the same position
• once we sort both of these arrays simply we can check if the array b[i] is greater than a[i] and the difference shouldn't be greater than one then we are good to go else if at any position if a[i] is greater than we can break our loop
• If in any case, the absolute difference is greater than 1 we can break the loop and return 0 or NO as an answer
• Time Complexity O(NlogN)