Amazon Interview Question for SDE1s


Country: United States
Interview Type: In-Person




Comment hidden because of low score. Click to expand.
1
of 1 vote

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.
Example: 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

- Saket February 04, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

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;
	}

- Adnan Ahmad April 06, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Is there a limit on the number of pages or chapters a user can read in a day?

- AJ February 02, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

// 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

- Satish February 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Are there any objectives? Like minimize the maximum pages read in one day?

If there are no objectives then you can just read the whole book the first day.

- JB February 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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]

- GOKU April 17, 2016 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More