Amazon Interview Question
SDE1sCountry: United States
Interview Type: In-Person
Java implementation of above idea...
public static List<Set<Integer>> readBook(Map<Integer, Integer> pagesPerChapter, int totalDays){
// Store pages count in the array {like 10, 20, 50, 90, 100}
int pages[] = new int[pagesPerChapter.size()];
pages[0] = pagesPerChapter.get(1);
for(int index = 1; index < pages.length; index++){
pages[index] = pages[index - 1] + pagesPerChapter.get(index+1);
}
int averagePages = pages[pages.length-1]/totalDays;
List<Set<Integer>> chaptersPerDay = new ArrayList<>();
int index = 0, product = 1;
while(index < pages.length){
int closest = getClosestToValueIndex(pages, index, averagePages*product++);
Set<Integer> chapters = new HashSet<>();
for(int value = index; value <= closest; value++){
chapters.add(value+1);
}
index = closest+1;
chaptersPerDay.add(chapters);
}
return chaptersPerDay;
}
private static int getClosestToValueIndex(int[] data, int low, int key) {
int high = data.length - 1;
while (low < high) {
int mid = (low + high) / 2;
if(data[mid] == key){
return mid;
} else {
int d1 = Math.abs(data[mid] - key);
int d2 = Math.abs(data[mid+1] - key);
if (d2 <= d1) {
low = mid+1;
} else {
high = mid;
}
}
}
return high;
}
// Wrote a python script for the problem statement
// Basically the concept is to divide Chapter by Days and then subtract chapters read and subtract a day from the Total Chapters and Total days and then repeat the loop of divide and subtract
import math
Chapters = int(raw_input('Enter the number of Chapters'))
TDays = raw_input('Enter the number of Days available to complete the Book')
Days = float(TDays)
EachDay = 1
while (EachDay <= int(TDays)) :
NumberofChaptersEachDay = math.ceil(float(Chapters) / float(Days))
print 'Chapters to be read on', EachDay, ' is :', NumberofChaptersEachDay, '\n'
Chapters = Chapters - NumberofChaptersEachDay
Days = Days - 1
EachDay = EachDay + 1
Try distributing equal number of pages every day in case number of days are less than the chapters available then unequal number of pages will be distributed therefore try minimizing the variance from the average pages per day
dp[i][j] denotes the minimum variance from A where i denotes number of days , j is number of chapters left and
A is (total pages)/(days)
therefore dp[i][j] = min(dp[i-1][k] + (pageCount*(j-k) - A)^2) for all k in [1 j]
The basic idea is to get the total number of pages in the book / Number of days. This will give approx. pages that the user has to read each day. Now find the nearest chapter ending from this average and assign those chapters to each day.
- Saket February 04, 2015Example: Chapter 1 - 10 pages, Chapter 2 - 10 pages, Chapter 3 - 30 pages, Chapter 4 - 40 pages, Chapter 5 - 10 pages.
Number of days = 4
Average = 100/4 = 25 pages per day.
Day 1 : Chapter 1 + Chapter 2
Day 2: Chapter 3
Day 3: Chapter 4
Day 4: Chapter 5