Hello guys Recently I gave many tests and got frustated because I could not get many,but even after the test i tried ,but could not get ideas,can u give ideas,these questions are from mutiple company.

(sprinklr) 1)Given a array of n(<10^5) numbers and also a number k,WE have to divide into k continuous segments which covers the whole array so that maximum of all segments is minimum

eg)n=5,k=3 ,arr[]={5,10,30,20,15} it's optimal to take {5,10},{30},{20,15},so that maximum of sum of all numbers in the subarray is minimised here minimum possible is max(5+10,30,20+15)=35

in the task they mentioned that : expected time complexity:o(n*(log(m))),m=sum of all dishes time duration

(Graviton)

2)we have 3 containers .Each consists of nx,ny,nz balls respectively(1<=nx,ny,nz<=10^5).bag1 cotains nx balls and on each ball a number is written,similarly for other balls in all bags(numbers written on balls <10^5),you can pick one ball from each container ,find number of ways such that sum of selected numbers is divisible by 7.

eg)a={5,6} ,b={7} ,c={2,1}

ans=2; bec he can pick{5,7,2} or {6,7,1}

(De shaw)

3)You gave your younger sister a maths problem. She currently knows about digits, numbers, comparison of numbers, and operations on numbers. So, you gave her 9 boxes containing pieces with digits '1', '2'... '9' respectively. Each box contains infinite pieces. You also gave her a number X. Picking a piece i from ith box reduces the X by reduction[i]. Now, you asked her to create the largest possible integer using the above pieces given that

She can use multiple pieces from the same box.

At the end. X should be reduced to 0.

In the time your sister is solving the problem manually, you planned to write a code for the same. Output 0 if no such number is possible.

Input Format:

The first line of input comprises of the size of reduction) array N.

Next N lines contain N space-separated integers denoting reduction[i].

Next line consists of an integer X.

Output Format:

Output a single line containing the answer.

Constraints:

1<=X, reduction[i] <= 1000

Sample Input 0

9

10 4 3 8 9 3 4 3 5

10

sample output: 887

Explanation 0

reduction =[10, 4, 3, 8, 9, 3, 4, 3, 5]. X=10 , digit — 1 2 3 4 5 6 7 8 9 The largest number you can create is 887. Using digit 8 two times and 7 once will reduce X by 3*2+4=10. Therefore, in the end, X will be reduced to 0.

You can solve (1) using binary search:

Guess a number, say G. This represents the maximum allowable sum of any of the k segments that you split your array into. Then split your array into k segments from left to right (making sure to fill each segment until you can't do so due to G. If you cannot find a split, then guess higher). Else guess lower. Record the lowest feasible value of G.

For (2), you can modulo the value on every ball with 7. This is because of the modulo arithmetic law $$$ (a + b) \% c = a \% c + b \% c $$$. Then you can use dynamic programming. The state is: how many ways are there to select balls from the first $$$i$$$ containers such that the sum is divisible by $$$k$$$ where $$$0 \le i \le 2$$$ and $$$0 \le k \le 6$$$. I will leave to you to work out the rest of the details.

(3) is just a slight variation of the knapsack problem — you can use an almost equivalent dynamic programming recurrence to deal with it.

For 3rd you can use straightforward 0/1 Knapsack using iterative version and retrieve the values. After that just sort those values in descending order and return

A similar question like first problem- https://www.interviewbit.com/problems/allocate-books/

How to solve Third problem?I thought of it for long time but did not get ideas.In a classical knapsack problem we find maximum sum of values, but here for a given sum there can be various possiblities (but which to choose),i am clueless ,some one please please please give idea and code if possible:)

Coders please help