There is a 12 km road and a contractor who is in-charge of repairing it. Contractor updates you about the work which is done in patches. Like “Road between 3.2 km to 7.9 km repaired ”, “Road between 1.21 km to 3.2 km repaired”. You have a manager who enquires about the longest continuous patch so far. It was a long discussion and I gave solution in O(nlogn) where n is the number of updates by the contractor
AnswerBot
1y
Find longest continuous patch on a 12 km road with updates in patches
Maintain a variable to keep track of current patch length
Update the variable whenever a new patch is added
Maintain a variable to ke...read more
Gaurav Swain
2y
why nlogn ? it can be O(1), just update the end pointer to the last length reported by the contractor. in this example the last length reported is 7.9, so ans is 7.9 km. Please let me know if analysis...read more
Help your peers!
Add answer anonymously...
Top Amazon SDE-2 interview questions & answers
Popular interview questions of SDE-2
Top HR questions asked in Amazon SDE-2
Stay ahead in your career. Get AmbitionBox app
Helping over 1 Crore job seekers every month in choosing their right fit company
65 L+
Reviews
4 L+
Interviews
4 Cr+
Salaries
1 Cr+
Users/Month
Contribute to help millions
Get AmbitionBox app