Round 1
Questions:
Question 1: Trucks dispatch packages in a city. There are n trucks numbered 0, 1, .., n - 1 used for dispatching goods. Assuming the trucks are parked along the x-coordinate axis, the coordinates of these trucks can be represented as a non-decreasing array called position, where the truck numbered i is parked at position[i].
Each truck can move towards increasing positions of x-coordinates only. At the start of the day, each truck is refuelled. There is a gas station at the position of truck number n - 1, i.e., at position[n - 1], and all other trucks can travel to this position for refuelling. The total distance travelled is the sum of distances travelled by each truck to reach the last x-coordinate position. Thus, the total distance is:
(position[n - 1] - position[0]) + (position[n - 1] - position[1]) + ... + (position[n - 1] - position[n - 1])
Two additional gas stations are located at the positions of two trucks, positions a and b. Treat a and b as 1-based indexes into the position array. Given q queries of the form (a, b) where a < b, find the total distance travelled by all the trucks to refuel their tanks. Assume additional gas stations are installed at position[a - 1] and position[b - 1] for each query, and that each truck stops at the nearest gas station going in the forward direction (increasing position). Note that each query is independent, and there is always a gas station at the last position.
Example:
There are n = 5 trucks, and their positions are position = [3, 6, 10, 15, 20]. There is q = 1 query with extra gas stations at extraGasStations = [[2, 4]].
Once extra gas stations are installed at position[2 - 1] = 6 and position[4 - 1] = 15:
- 0th truck will move towards x = 6.
- 1st truck will not move since there is already a gas station installed.
- 2nd truck will move towards x = 15. Recall that trucks can move in increasing x-coordinate/position only.
- 3rd truck will not move since there is already a gas station installed.
- 4th truck will not move since there is already a gas station installed.
Total distance travelled:
(6 - 3) + (6 - 6) + (15 - 10) + (15 - 15) + (20 - 20) = 3 + 0 + 5 + 0 + 0 = 8.
Question 2: There are multiple delivery centers and delivery warehouses all over the world! The world is represented by a number line from -10^9 to 10^9. There are n delivery centers, with the i-th one at location center[i]. A location x is called a suitable location for a warehouse if it is possible to bring all the products to that point by traveling a distance of no more than d.
At any one time, products can be brought from one delivery center and placed at point x. Given the positions of n delivery centers, calculate the number of suitable locations in the world. That is, calculate the number of points x on the number line (-10^9 ≤ x ≤ 10^9) where the travel distance required to bring all the products to that point is less than or equal to d.
Note: The distance between point x and center[i] is |x - center[i]|, their absolute difference.
Candidate's Approach
No approach provided.
Interviewer's Feedback
No feedback provided.