Google Interview Question


Country: United States
Interview Type: In-Person




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

3 words : Unweighted Interval Scheduling. The twist here is that you can only select an interval[j] after having selected interval[i] if it starts after interval[i].end + w[i][j] and is not in the same week as i. Here is the algorithm.

1. Convert all time values to hour for consistency
2. Each site represents an interval. If not given in that format already, create an array containing start , end and index of site form which this interval was taken. Add an interval with start==end with index=start site.
3. Sort that array based on end time
4. Initialise count =0 and start with first interval and do the following till all intervals are exhausted:
4.1 Let i = current interval
4.2 Iteratively find the first j such that interval[j].start>=interval[i].end + w[i][j] and is not in the same week as i
4.3 i = j ; ++count
5. return count

Above is a greedy solution to Unweighted Interval Scheduling. To see the proof why it works: [www] .cse.psu.edu/~asmith/courses/cmpsc465/S12/lec-notes/CMPSC465-S12-Lec-17-greedy-algs.pptx.pdf , slide 9

- anantpushkar009 November 14, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Hi Anant, I don't think greedy approach will work here. This question is bit different from interval scheduling. In interval scheduling once one event will get completed you can schedule any event which starts after the first will end. Here we are getting additional constraint that, next city should be reachable from current city in given time. For example suppose you are at city A, there are two city B and C which can be reached from A in given time, and both has festival on next week. Suppose festival in B falls before festival in C. In this case with greedy approach you will go to city B. But suppose there is some other city D which has festival in next week (one week later of B and C). Suppose D is reachable from C in one week time but not from B. In this case our selection C would have given better solution.

I think we need to explore all the possibility. It will be solved with DP.

- ajeetpr.singh November 19, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Lets say the year has only one holiday and all the sites are giving gifts. Then the schedule is clear, but the way to travel to all of them not. Because it reduces to the TSP. This problem is NP-hard.

- Ehsan November 27, 2014 | 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