Uber | SDE II | Online Assessment | April 15th 2023
Anonymous User
588

Total Questions - 2 Algorithimic

Algorithm Question 1
  • Problem Statement:
Imagine a horizontal line where ubers are standing parlallel to the line. Each uber has a coordinate [l, r].
Given a list of coordinates find the markers where there is atleast one uber standing. 

A marker is a point on a horizontal line.
  • Example
Input: coordinates = [[3,6], [-1,5],[4,7] 
Output: 9
Explanation: Markers at 2 0, -1, 7, 6, 5, 4, 3, 1 have atleast one uber
  • Approach
For every uber coordinate given there always exits atleast one uber in that range inclusively. 
We should just avoid over counting the same range.
For example [-1, 5] and [3,6 ] we should avoid counting [3,5] again. So we just merge all the coordinates. 
For each merged coordinate [start, end] the no. of markers = end - start + 1; 
Algorithmic Question 2
  • Problem Statement:
Given a list of cabTripTimes which indicates that cab i takes cabTripTimes[i] time to complete one trip.
Find the min time it takes to complete n trips. At time t we can start multiple trips. 
Assume there is no buffer in between starting trips again.
  • Example
Input: cabTripTimes = [1,2], n = 3 
Output: 2 
Explanation: 
At time t = 0; start trips 1, 2
At time t = 1; end trip 1, and start trip 1. 
At time t = 2; end trip 2, end trip 1, 

Earliest time to end 3 trips is 2.
  • Approach
Used a PriorityQueue of pairs which had endTime and tripTime of a cab with min endTime as priority.
Start a loop from time = 1. pop all the elements from the queue which have the same endTime as time and decrement n for each pop. 
Add each pair back to the queue with endTime = endTime + tripTime.
Break loop when n == 0 and return time.
  • Similar Question: I think there are Similar questions to this on leetcode but could not find it.

All Test cases passed for both the solutions. I really tried to get a Math solution for Q2. I would appreciate to get any other improved approach than what I tried. Thanks

Comments (5)