### focus_on_cp's blog

By focus_on_cp, history, 2 months ago,

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

1. She can use multiple pieces from the same box.

2. 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.

• -11

 » 2 months ago, # | ← Rev. 2 →   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.
 » 2 months ago, # | ← Rev. 3 →   0 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.
 » 2 months ago, # |   +1 (3) is just a slight variation of the knapsack problem — you can use an almost equivalent dynamic programming recurrence to deal with it.
 » 2 months ago, # |   0 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
 » 2 months ago, # | ← Rev. 2 →   0 A similar question like first problem- https://www.interviewbit.com/problems/allocate-books/
 » 7 weeks ago, # |   0 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:)
 » 7 weeks ago, # |   0 Coders please help