Uber Intern Software Engineer Interview Experience — OA with a Delivery-Cost, Truck-Collision, and Org-Tree Broadcast Problem

OA

Problem 1
There are n cities, each with a deliveryCharge value. Delivering from city i to city j can be costed in two ways:

1. The cost is abs(deliveryCharge[i] - deliveryCharge[j])
2. If city j is city i's unique nearest city, the cost is 1
   The distance between cities is defined as abs(deliveryCharge[i] - deliveryCharge[j]). Given a queries array where each entry is [Start, End], compute the minimum delivery cost from Start to End.

Problem 2
On a one-dimensional lane of length laneLength (ranging from 0 to laneLength), there are multiple trucks at different initial coordinates, each with its own velocity:

1. A positive velocity means the truck moves right, a negative velocity means it moves left
2. A truck is considered to have left the lane once it goes past the lane's boundary
3. When two trucks collide, they swap velocity and direction
   The task is to output the time at which the last truck leaves the lane.

Problem 3
The company's employees are organized as a tree, with the Root being the Boss. When data is passed to an employee, it is passed on to all of that employee's direct reports in ascending order of their child node values.
The input is a boss array, where boss[i] is the manager of employee i. Given a queries array, each query contains [StartNode, k]:

1. Following the ascending-order propagation rule described above, find the k-th employee to receive the data starting from StartNode
2. Return that employee's ID