Solve five hard algorithm problems
Company: Pinterest
Role: Machine Learning Engineer
Category: Coding & Algorithms
Interview Round: Onsite
The coding rounds covered the following algorithmic problems:
1. **Transform one array into another using range `+1/-1` operations**
You are given two integer arrays `nums` and `target` of equal length `n`. In one operation, choose a contiguous subarray `nums[l..r]` and either add `1` to every element in that subarray or subtract `1` from every element in that subarray. Return the minimum number of operations needed to transform `nums` into `target`.
2. **Build a target array from zeros using range increments**
Start with an array of `n` zeros. In one operation, choose a contiguous subarray and add `1` to every element in it. Given a target array of non-negative integers, return the minimum number of operations required to construct the target array.
3. **Minimize the maximum load when assigning jobs**
You are given an array `jobs`, where `jobs[i]` is the time required for job `i`, and an integer `k` for the number of workers. Assign each job to exactly one worker. The load of a worker is the sum of job times assigned to that worker. Return the minimum possible value of the maximum worker load.
4. **Place boxes into a warehouse from one side**
You are given an array `boxes` of box heights and an array `warehouse` of room heights arranged from left to right. You may reorder the boxes arbitrarily, but boxes can only be inserted from the left entrance. A box can pass through a room only if its height is no greater than the height limit of every room it must pass. Each room can store at most one box. Return the maximum number of boxes that can be placed in the warehouse.
5. **Place boxes into a warehouse from either side**
This is the same setup as the previous problem, except each box may be inserted from either the left entrance or the right entrance. You may still reorder the boxes arbitrarily, and each room can hold at most one box. Return the maximum number of boxes that can be placed.
Quick Answer: This set of problems evaluates algorithm design and problem-solving skills across array manipulation, range-update techniques, load-balancing and partitioning strategies, and combinatorial packing, testing competencies in complexity analysis, data-structure use, and optimization under constraints.
Part 1: Minimum Range +/-1 Operations to Match Target
You are given two integer arrays nums and target of equal length. In one operation, choose any contiguous subarray nums[l..r] and either add 1 to every element in that subarray or subtract 1 from every element in that subarray. Return the minimum number of operations needed to transform nums into target.
Constraints
- 0 <= n <= 2 * 10^5
- -10^9 <= nums[i], target[i] <= 10^9