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

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 keep track of longest patch so far
Compare current patch length with longest patch length and update if necessary
Use a sorted data structure like a binary search tree to store the patches for efficient search
Time complexity: O(nlogn) where n is the number of updates by the contractor

Accepted Answer

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 is correct

Top Amazon SDE-2 interview questions & answers

Popular interview questions of SDE-2

Top HR questions asked in Amazon SDE-2