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

lists= [[1.2,3.2],[3.2,7.9],[8.2,9.6],[9.6,10.2]]
merged=[] 
merge ="FALSE"
for i in range(len(lists)):
    merge ="FALSE"
    for j in range(i+1,len(lists)):
        if  lists[i][1] == lists[j][0]:
            merge="TRUE"
            merged.append([lists[i][0],lists[j][1]])
            break
    if not merge:
        merged.append(lists[i])
    
dict1={tuple(lis):lis[1]-lis[0] for lis in merged }
result=max(dict1.values())
print(result)

Top Amazon SDE interview questions & answers

Popular interview questions of SDE

Top HR questions asked in Amazon SDE