focus_on_cp's blog

By focus_on_cp, history, 7 weeks ago, In English

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.

 
 
 
 
  • Vote: I like it
  • -11
  • Vote: I do not like it

»
7 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

»
7 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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.

»
7 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

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

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like 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

»
7 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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:)

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Coders please help