HackerRank Coding Interview 5. Assigned Parking

Time to complete — 35minutes

Question Type = Medium

Asked in = Microsoft, Uber, Lyft, Bloomberg, Morgan Stanley, Apple, and Google.

Skills: arrays, sorting, greedy algorithm, prefix array

Insights — It should be read very carefully read and you must ask questions in between.

Question —

There are n cars located on a 2-dimensional plane at positions (x[i], y[i]) where 0 ≤ i ≤ n. They need to be parked in a straight line parallel to the x-axis with no spaces between them. The fuel consumed to move a car is abs(x[finish] — x[start]) + abs(y[finish] — y[start]). Determine the minimum fuel cost to arrange the cars side-by-side in a row parallel to the x-axis.

Example

x = [1, 4]

y = [1, 4]

One optimal solution is:

• The car initially at position (1, 1) moves to (3, 1) for a cost of abs(3–1) + abs(1–1) = 2 + 0 = 2.
• The car initially at position (4, 4) moves to (4, 1) for a cost of 0 + 3 = 3.

The total fuel consumed is 2 + 3 = 5.

Function Description