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

Question

Accepted Answer

The longest continuous patch of a road repaired by a contractor is determined.

Iterate through the updates and keep track of the start and end points of each patch
Calculate the length of each patch and update the longest patch if necessary
Return the start and end points of the longest patch

Accepted Answer

The road is 12 K. M.
3.2-7.9=4.7
1.2-3.2=2.0
Therefore 6. 7 K. M repair 
Balanced 12-6.7= 5.3 K. M.    
     4.7
     2.0
     5.3
------------
    12.0 K. M
========= 
The Contractor is the incharge of the reparing road.

Top Amazon Software Developer interview questions & answers

Popular interview questions of Software Developer

Top HR questions asked in Amazon Software Developer