Just took IMC OA. We are given 120 minutes for 2 problems.

Q1 - Does the Path Exist?

You start at (x, y) and would like to reach (a, b). In one step, you can go from (x, y) to:

1. (x + y, y)
2. (x, x + y)
3. (x + c, y + c)

In additional the the rules above, there are also obstacles that you must avoid. Obstacles exist on any cell (i, j) where i+j is a perfect square.

You will be given a, b, x, y, c. Determine whether a path exists.

Constraints

• 0 <= x, y, a, b <= 1000
• 1 <= c <= 15
• It is possible for (a, b) and/or (x, y) to be blocked.

My Solution

• Precompute a bad array of size 2001 to mark the perfect square.
• BFS and try all possibilities due to the low constraint. No need to overcomplicate this.
• Passed All testcases.
  

---

Q2 - Traffic Arragnment

There are two streets denoted as MAIN STREET (0), and FIRST STREET (1). These streets are 1-way and thus you need to help them determine the time (in second) in which the cars will be pass through the intersection! They follow the rules:

1. If in the previous second, there is a car from the FIRST STREET passing through the intersection, then the first car on the FIRST STREET gets to go.
2. If in the previous second, there is a car from the MAIN STREET passing through the intersection, then the first car on the MAIN STREET gets to go.
3. If in the previous second, there is no car passing through, then the first car on FIRST STREET gets to go.

You are given an array Arrival donoting the arrival time for car i, and an array Street denoting which street the car is on, with 0 being MAIN STREET and 1 being FIRST STREET.

Return an array of size Arrival.length such that ans[i] is the time on which car i passes through the intersection.

Constraints

1. 1 <= Arrival.length <= 100000
2. 1 <= Arrival[i] <= 1000000000
3. Arrival is sorted in non-decreasing order (2 cars can arrive together on the same street).
4. Street[i] is either 0 or 1

My Solution

• Maintain 2 queues. One for each street.
• Track the time and idx for the cars. Use a while loop that does not increment anything.
  • Inside the while loop, if both queues are empty or the time equals to the arrival time of current index for the car, enqueue the current car into the queue and increment idx, and set time to the current arrival time of that car.
  • Otherwise, process the queue according to the rule above and +1 to time at the end.
• Passed all testcases.