Books Allocation - Google Interview Question | Binary Search, Part 4 | DSA-One Course #25
Books Allocation - Google Interview Question | Binary Search, Part 4 | DSA-One Course #25
Hey guys, In this video we’re going to solve an important problem on Binary search. It’s called Books Allocation - Minimise the maximum number of Pages read by a student.
🥳 Join our Telegram Community:
Telegram channel: https://telegram.me/realanujbhaiya
Telegram group: https://telegram.me/dsa_one
🚀 Follow me on:
Instagram: https://www.instagram.com/Anuj.Kumar…
Linkedin: https://www.linkedin.com/in/sharma-ku…
Twitter: https://twitter.com/realanujbhaiya
💸 Use coupon code ANUJBHAIYA on GeeksforGeeks to avail discounts on courses!
📚 Complete DSA Playlist: • DSA-One Course - The Complete Data St…
Complete Android Development Playlist: • Android Development Tutorial for Begi…
Hashtags:
#anujbhaiya #dsaone
Ignore these tags:
book allocation problem
min allocation of books
allocate books
asset allocation
allocate books algorithm
warren buffett asset allocation
allocation
binary search problem example
binary search interview problem
memory allocation
problems
static memory allocation
dynamic memory allocation
asset allocation portfolio
asset allocation model
dynamic memory allocation lecture
example of static memory allocation
dynamic memory allocation in c
binary search
binary search algorithm
binary search problem example
binary search tree
binary search competitive programming
competitive programming binary search
upper bound binary search
first occurrence binary search
binary search competitive coding
aggressive cows binary search
book allocation problem
optimisation problem binary search
exponentiation using binary search
binary search in c
binary search interview questions
lower bound binary search
binary search
coding interview
binary search tree
google coding interview
google interview
google
google interview questions
binary search tree interview questions
interview
binary tree
google interview question
binary search algorithm
google coding interview questions
validate binary search tree
programming interview
google technical interview
binary search interview problem
binary search interview questions
google coding interview question and answer
Content
0 -> In today's video we're going to do an advance question based on Binary search.
2.914 -> This question is not like the normal binary search questions.
4.829 -> You won't be able to say that, binary search will be applied, just by watching.
8.457 -> But, it gets optimized when we apply binary search. What is the question??
11.533 -> Question is to Allocate minimum pages?
13.971 -> I've written a little statement. Minimise the maximum numbers of pages read by a student.
17.757 -> Let me explain the question.
19.869 -> 5 books are given inside this array.
23.9 -> And each element tells you that how many pages are there in the book at the position.
28.229 -> This has 10 pages, 20 pages, 5 pages, and so on.
31.171 -> along with that few students are given, suppose 2 students are given here.
36.746 -> Suppose you've 2 students and you've to distribute these books between them.
41.386 -> You've to distribute all the books.
43.536 -> and in such a way so that the maximum number of pages read by any student is minimised.
49.786 -> Alright!!! let me explain it clearly to you.
52.2 -> that maximum number of pages read by a student is minimised. So, first of all it contains constraints
56.003 -> It has 2 constraints, let's understand them. First one is
59.018 -> that the book that you'll give to each student, you'll give it in contiguous fashion
63 -> You'll give 10, 20 , 5 to the first student and to the 2nd student you'll give 25 and 5.
67.601 -> You can't give 5 and 15 just after giving 10 to the first student.
72.463 -> You can't skip in between.
74.086 -> the books will be given in a contiguous fashion.
76.775 -> and 2nd constraint is, that the book that you'll give to any student, then all the pages of that book should be read by the same student.
83.372 -> Both the students cannot split the book between them.
86.214 -> Suppose, this book has 20 pages, then you can't give 10-10 pages to each student. You can't do that.
93.337 -> So these are our constraints.
94.726 -> and in this way we've to minimise the maximum pages read by a student.
99.008 -> So, we've 2 students.
101.429 -> and if we assign them the book, suppose this is the 1st student and this is the 2nd student.
105.472 -> Suppose we gave the the 2nd book to the first student, so he read 10 pages.
109.176 -> and we gave the rest of the books to the 2nd student. So how many pages did he read?
112.957 -> 25 ---45, right!!
116.171 -> So, the maximum number of pages read by the student here is 45.
120.231 -> Is 45 a minimum number?
122.056 -> Can this be our answer?
123.258 -> Let's check if 45 can be or not?
125.078 -> One answer can be any of these? 10 and 45 distribution can be an option.
128.714 -> Next distribution can be, to give 10 and 20 to the first student. So, 20 +10 = 30
135.429 -> And the rest are, 25.
137.914 -> Right!!
138.514 -> So, here the maximum no. of pages read by a student is 30
141.541 -> Obviously, 30 < 45 and we've to give the minimum answer.
144.957 -> So, 30 can be the answer. 45 won't be the answer.
147.4 -> Let' see another distribution as well.
149 -> Suppose, you gave first 3 books to the 1st student. You're giving in a contiguous fashion.
153.987 -> You're not skipping and giving the other book.
156.629 -> So, you gave these 3 books to the 1st student and the remaining 2 books to the 2nd student.
160.264 -> In this case 35 pages will be read by this student and the rest of the 20 pages will be read by the 2nd student.
168.444 -> So, here the maximum no. of pages read by the student is 35.
171.944 -> further on this number, we will go on increasing.
174.357 -> So, our answer is coming from this distribution, minimum answer which is 30.
179.382 -> Right!! So, 30 is the answer which is the maximum no. of pages read by a student which is minimised.
184.543 -> If you'll give lesser pages than 30 then it won't work. Suppose, you said that the 1st student read 28 or 29 pages
190.842 -> then it won't work this way.
192.006 -> So, 30 is the answer.
193.542 -> We've to tell how will this come. There are multiple ways to do it.
196.858 -> First, of all the Brute force , if you don't know that I'll explain it to you.
200.931 -> You know that there are 2 students.
202.557 -> which means you've to make a cut in this array. Like we did here.
208.286 -> then this will be read by one student and remaining can be read by the another one.
211.8 -> Suppose, next time you'll check by cutting here, this will be read by one student and the remaining will be read by the other one.
217.976 -> So, we can check by putting cuts.
220.5 -> Right!! So, there are 2 students. Suppose if you had 3 students instead of 2.
224.671 -> Then how will you apply the cut? You did the 1st cut.
227.637 -> And you did recursively call for this array.
230.714 -> You did the 1st cut and you had 1 student. Then when you recursively called it'll be 2 students,
236.943 -> because this book can be read by one student.
239.221 -> So, you can recursively solve in this way as well.
241.587 -> the time complexity from here will be O(2^n).
245.014 -> which is not a good time complexity. We can do better than this.
248.446 -> How can we do better? By applying Binary search, which is not visible how it can be applied
253.327 -> Because array is also unsorted. We apply binary search in a sorted array.
256.998 -> But, if you remember, I told you in the first Binary search video that where is binary search applied
261.384 -> either your array should be sorted
263.157 -> or you've to allocate in a contiguous fashion. So we've to allocate here in a contiguous fashion.
268.401 -> So binary search can be applied here as well.
270.786 -> and binary search will be applied here. So, it'll convert it to O(n log n) from O(2^n).
278.129 -> Alright!!
278.943 -> So, we're going to do a very good optimization here.
281.362 -> Let's see how will we do it. I'm not coding the solution of O(2^n).
287.438 -> But, I'll give the link, you can check how the brute force solution is going to work here.
292.001 -> Today we're going to see its optimized solution.
294.014 -> Let's discuss how will it be done.
295.358 -> Let's see how binary search will be applied in this example. So I've changed the example here.
299.501 -> Now we've 4 books.
301.443 -> there are 2 students, where we've to distribute the book in between them and how will the binary search be applied
305.873 -> in O(n log n)
307.091 -> We know that binary search is applied in a range, between the highest and the lowest range and then we
312.416 -> come to the middle range, then we discard a part, we apply it in the 2nd part, it is used in this way.
317.357 -> Here, we've to first find the range from minimum to maximum no.
322.244 -> in which our answer could lie
324.271 -> minimum will be 30
328.829 -> How is it 30? Because 30 is the maximum no. of pages that can be read by any student.
333.486 -> If he is reading only 1 book.
335.115 -> If I'm telling any student to read only 1 book, then 30 can be its answer.
339.281 -> Right!! because 30 is the maximum.
342.071 -> and what will be maximum?
345.303 -> Maximum will be when he reads all the books, if he is reading 1 book then maximum answer will be 30
350.2 -> and if he is reading all the books, then answer will be 30+20= 50+20 which is 70
355.114 -> So we've got our range, the optimal answer will lie between 30 -70.
360.4 -> Now I'll try to find that answer. 30 won't be the answer, why?
364.629 -> because if you gave a student the book with 30 pages then you've to give the remaining books to the other student
369.468 -> and in that case it'll be 20+10+10=40
373.144 -> so, in that case our answer will be 40.
375.614 -> We won't consider 30 as the answer. Our answer will be between 30-70
380.333 -> Right!! Now let me show it in a graph, then 30 will be here and 70 here.
386.473 -> Let's try to find the mid. Mid will be ---min +max / 2 which is 50, right!
394.343 -> We'll check if maximum no. of pages read by a student is 50, atmost he can read 50 pages.
401.201 -> then can we assign the books between 2 students?
405.47 -> Let's check it.
407.029 -> So we've to assign 50 pages to 1 student.
409.629 -> So, we'll give 10, 10 so 20 pages. Then 40 pages, then if I try to assign the book with 30 pages then it'll have 70 pages
418.172 -> And we can only give 50 pages.
420.2 -> which means, we'll give the first 3 books to one student and the remaining 4th book will be given to another student, right!!
426.33 -> Let's do it this way.
427.643 -> if we'll do it this way then, we can see that our answer can be within 50.
432.515 -> 10+10+20=40, means we've to see that our answer will be within 50.
437.86 -> So, we can say that the numbers or pages between 70, you can easily distribute in it.
445.514 -> which means, our minimum answer will be between 0 to 49, right!!
450.3 -> somewhere between 30 - 50
452.643 -> So, we know that our optimal answer wouldn't be between 50-80.
456.614 -> because you can easily assign 50 to anyone. But, if we've to find minimum, then we've find it between 30-50.
462.77 -> So, our minimum will be 30 and maximum will be 49.
466.666 -> So, you can see binary search is working here. As you've discarded an entire part.
470.207 -> If you did not understand, just wait for a moment you'll be able to understand it.
474.094 -> So, we've to assign a book, let's try to find the mid again, between 30 - 49.
480.271 -> because we've already checked for 50. It'll be the answer.
484 -> If we get the answer between 30 - 49, then it can be minimsed as well.
487.119 -> We'll try to find mid between 30 - 49, so, its mid here.
491.757 -> So, let's try to find the mid, it'll be 79/2 which is 39.5
498.257 -> so let's assume it 39. Let's check if we've to assign 39 pages to any student atmost
504.501 -> then how many students will be required.
506.567 -> let's try to assign 39, so 10 then again 10 that is 20 pages, then if I'll give this one then again 20 pages will be together 40 pages.
512.83 -> and we don't have to look for 40 but just 39.
515.844 -> so, I can't give this to the student, so let's try to give 10 and 10 to a student, then I'll give 20 to the other student.
525.814 -> After that I'll try to give 30, but I won't be able to give it because it'll be 50 and we've to give utmost 39
532.214 -> So, I'll give only this book to the 2nd student. Then for this book, I need a 3rd student.
537.281 -> So, we need 3 students here, but we only have 2 students.
541.5 -> So, we can say that, we won't be able to do it in 39 or lesser pages than that.
546.671 -> Right!! So, it was 39. We can say that it won't work for 39 pages or lesser than that.
555.901 -> So, we'll discard this part as well.
557.442 -> And our range will be, 39 won't be the answer, so it'll be between 40 to 49.
563.586 -> Right!! Our range will be between 40- 49. So, minimum will be
567.471 -> mid +1 which is 40
571.986 -> maximum will be 49.
573.486 -> Now, let's try to find between them, then our mid will be -- 89/2 which is 44.5. So 44 will be our mid
583.071 -> So, let's come to 44
586 -> and if 44 was that no., we could give utmost 44 pages to any student
590.714 -> then how many student do we need here. So, let's assign again
594.229 -> I gave this book to a student then I gave this book as well. We can give 20 as well, as its 44
598.59 -> so total its 40 pages, but If I try to give this book then I won't be able to do as total it'll be 70 pages
602.243 -> which means you gave these 3 books to the 1st student, then you can give this book to the 3rd student, with 30 pages
607.2 -> so, we saw that it'll work with 44
610.229 -> so, if it works with 44, then it'll also work for 45, 46
613.543 -> so we also discard this range as we're trying to find the minimum answer. So, our answer will be somewhere between 40 to 43
621.757 -> Let's store 44 here. So earlier it was 50, now its 44, which is less than 50. So in this way our result will also be less
631.757 -> so we stored result as 44. So min will be 40
634.914 -> and max will be 43, mid will be 83/2 which is 41
639.843 -> Right!! So, let's see if the answer comes when we assign 41. Let's again try to assign 41.
645.214 -> So, it'll work with 41.
647.786 -> 10, 10 , 20----give these to one and give the remaining to the other, then it'll work within 41.
653.071 -> so, answer is feasible in 41. If its feasible in 41 then, it'll be feasible in 42, 43. We've to find the minimum answer.
659.568 -> So it'll be between 40 and 41
662.214 -> so, we already know 41
666.486 -> and we've to come till mid -1 , so maximum will be mid-1. So 41-1= 40
673.009 -> So, we've to find between 40 to 40.
676.243 -> So, mid will be again 40.
679.168 -> we can assign for 40, assign these 3 to one and this book to the other.
685.239 -> so, it'll work within 40 pages. Since its working with 40, we always do mid -1 to the high.
691.557 -> Now, if we do mid -1 to the high, then it'll be 39.
695.044 -> and as soon as our minimum is greater than maximum, we'll come out of it and our result is 40, which is the answer.
703.671 -> So, this is going to be our logic, let me just code as well.
706.185 -> You'll understand even better after coding, how all the logic works.
709.945 -> So, I've coded the same entire logic here, which I had explained it to you.
714.61 -> There is a function---minPages, in which you're giving an array and along with that no. of students that is k.
721.3 -> so, we made minimum in it, since we've to make a range for min and max which will be --maxOf(a);
727.311 -> maxOf is not a function, if you want you can make it yourself.
730.534 -> it'll take an array and it'll try to find the maximum value in it.
735.071 -> so, it'll do it in a single iteration.
737.014 -> that will be our minimum. Maximum will be --sumOf(a);
741.486 -> the sum of all the elements in this array will be our max. sumOf is also not a function, you can make it yourself.
748.857 -> It'll take an entire array and return the sum of all the elements in it.
754.386 -> So, if you see the example here, then this is an array--10, 5 and 20 and
759.286 -> k = 2
760.543 -> min =20, which is maxOf this array. Maximum is 20
765.457 -> and max will eb --sumOf(a); So the sum of this array is---25+10=35. So this is our max.
772.2 -> Now we'll move on.
773.472 -> For now our result will be 0, while (min
778.971 -> mid =min+max/2
780.943 -> 20+35/ 2= 27
783.386 -> so our mid is 27. So, we'll check if the answer is feasible for 27.
787.568 -> so, I've made Feasible function here.
791 -> this function takes an array, no. of students and along with that it takes that no. for which you want to check if its feasible or not.
799.1 -> So, I've made that into result here.
800.913 -> and it'll check how many students do you need for this answer, if you've to make it feasible.
805.879 -> I've made a student variable here, which tells for how many students is this result feasible.
810.986 -> For now, I've taken it 0, we'll slowly iterate in the array which is given.
815.834 -> and we'll try to add current element in the current sum
820.034 -> and we'll check if the no. of pages which are coming now is greater than my result.
824.192 -> if they are greater than my result then, its time to increase the student.
828.056 -> as you can't give this book to the current student.
830.473 -> so we'll do student ++
833.457 -> and we'll reset the sum along with it. Sum will be equal to the current element.
837.586 -> If you can give this book to the student, then you will do--sum += a[i ];
843.014 -> We'll go on doing this, at the end we'll know the no. of students required if we've to make this array feasible for this result.
850.514 -> And finally, we've to return boolean value
854.187 -> student < = k
856.132 -> this is a shortcut way to write.
859.3 -> Many times we write it in a shortcut way.
862.458 -> here, if the students are < = the given no. of students, then it'll return true otherwise it'll return false
872.25 -> if you want you can write it in if else way, but its a shorthand way of writing.
876.229 -> It'll be feasible when total no. of students coming out of this formula are less than equal to k.
883.476 -> So, if it is feasible, then for now store mid in the result and now try to find between left and mid -1.
892.743 -> so, max = mid -1
894.771 -> if this answer is not feasible, then our answer doesn't lie between left and mid, so we'll go from mid +1 to further.
903.313 -> so, mid = mid +1 and we'll run this loop again
906.472 -> This loop will run until our min is greater than max, and as soon as our min > max
911.557 -> we'll return the result, which will be the minimum value , which will also be answer.
915.695 -> in this way, you can see that it's going in between min and max in log n
922.356 -> and along with each log n you're also calling --is Feasible
926.498 -> if you'll check, then isFeasible is working in O(n)
930.261 -> that is why, you can say that it is log n*n.
933.657 -> So, we can say that this solution is working in O(n log n).
938.557 -> Let's dry run for this code how is it working.
941.568 -> So, let's run for this case, min will be 20 and max will be 35, mid = 27
946.029 -> mid =27, so let's check if its feasible or not for 27.
949.443 -> we'll check for 27, then how many students are coming? So, we gave book with 10 pages to one, we can also give the book with 5 so its 15.
955.544 -> Still less than 27, right!!
957.386 -> then we'll try to give this book it'll be 35, as soon as it'll be 35, it'll be greater than result.
962.858 -> then we'll do student ++
964.614 -> means you're giving this book to the other student. 2 students are coming from here and 2
970.138 -> which means 27 can be a feasible answer. If it is feasible, then we'll put result as 27.
975.986 -> as the result can be 27, then our answer can be less than 27
981.556 -> so, max will be mid -1. So mid was 27, so max will be 27-1=26
989.014 -> Now we'll try to find between 20 to 26
991.998 -> so let's see, if its feasible for 23.
994.6 -> Let's check for 23, it'll be 10+5 =15 and 20. So it is feasible for 23.
1000.091 -> So, you'll update the result that will be a little less which is 23.
1004.111 -> Our result will be 23 and max will be mid -1. So mid was 23 -1 which is 22
1010.8 -> max will be 22. We'll find the mid again, 3rd time our mid will be
1017.771 -> mid = 20+22/2 which is 42/2 which is 21
1024.029 -> mid is 21 and now let's check if its feasible for 21.
1027.004 -> Then it is feasible as 10 +5 =15 and 20, so it is feasible.
1032.29 -> since its feasible for 21 as well, then we'll update the result, which will be again 21
1038.386 -> Result will be 21 and max will be mid -1. Max will be updated from 22 to 20.
1043.206 -> Again, we'll find mid that is 20, on 4th time.
1050.071 -> We'll check if it is feasible for 20 or not. So , yes it is. 10+5 to onw an d20 to the other.
1055.596 -> so, it is also feasible for 20,right! Our result will be mid, it'll be updated to 20 from 21
1062.386 -> and max will be mid -1. So, mid is 20 and max will be 20-1 =19
1067.629 -> Now, our minimum is greater than maximum.
1070.777 -> As soon as min > max, you'll break from this while loop
1074.55 -> and you'll return result. For now the value stored in result is 20.
1078.671 -> That is why 20 is our answer.
1081.314 -> So, in this way this code is working. I hope you've understood. This video was until here.
1085.569 -> In the upcoming videos, we'll recap the DSA one course.
1090.586 -> So, we've studied a lot of topics till now.
1092.638 -> We'll revise all the topics and along with that there'll be some questions that I'll discuss with you all.
1096.74 -> Which will be practice questions for you.
1098.771 -> So, the DSA one course until now we'll be doing a recap in that.
1102.289 -> So, if you liked this video then do like it and do subscribe to the channel as well.
1106.197 -> I'll meet you in the next video.
1108.147 -> BYE!BYE!
1109.019 ->
Source: https://www.youtube.com/watch?v=BSihvQCh9-I