MICROSOFT: SWE Internship Test FY25 Off-Campus

There is a metro rail with K stations numbered from 0 to K - 1. There is a direct connection between stations if their numbers differ by one. Passengers can ride the metro line in both directions.

The fee for boarding the train is 1. Every time a passenger travels between two adjacent stations, the fee increases by 2. The metro system charges money at the end of each day based on the passenger's travel history for the day.

There is a total fee limit for a single day. The passenger cannot be charged more than the limit, even if their associated travel fees exceed the limit. The limit depends on the maximum station number the passenger visited during the day.

You are given arrays start and dest of length N, describing all the metro rides the passenger took during the day. During the x-th ride, the passenger boarded the train at station start[x] and left the train at station dest[x]. You are also given an array limit of length K. If the largest station number visited during the day is Y, then the fee limit for this passenger for that day is limit[Y].

Write a function:

int solution(int start[], int dest[], int N, int limit[], int K);

that, given the arrays start and dest, both of length N, and the array limit of length K, returns the amount of money the passenger will be charged at the end of the day.

• Example:

  1. For start = [1, 0, 2, 4], dest = [2, 2, 0, 5] and limit = [3, 17, 7, 4, 5, 17], the function should return 16.

     There were four rides:

     • Station 1 to station 2 (cost 3);
     • Station 0 to station 2 (cost 5);
     • Station 2 to station 0 (cost 5);
     • Station 4 to station 5 (cost 3);

     The total cost is 16. The largest visited station number is 5. The fee limit for station 5 is 17, so it does not apply in this case.

  2. For start = [1, 2, 0, 2, 3], dest = [2, 1, 2, 1, 2] and limit = [4, 8, 18, 16, 20], the function should return 16.

     There were five rides:

     • Station 1 to station 2 (cost 3);
     • Station 2 to station 1 (cost 3);
     • Station 0 to station 2 (cost 5);
     • Station 2 to station 1 (cost 3);
     • Station 3 to station 2 (cost 3).

     The total cost would be 17, but is capped at 16 (the daily limit for station 3).

  3. For start = [2, 2], dest = [4, 3] and limit = [1, 1, 1, 1, 9, 1, 1], the function should return 8.

     Assume that:

     • N is an integer within the range [1...30];
     • K is an integer within the range [2...50];
     • Each element of arrays start and dest is an integer within the range [0....K-1];
     • Each element of arrays limit is an integer within the range [1...3000];
     • Each ride has a different start and destination station.

In your solution, focus on correctness. The performance of your solution will not be the focus of the assessment.

You are given two arrays, A and B, each consisting of N integers. These arrays represent a grid with N columns and 2 rows, where A is the upper row and B is the lower row.

Your task is to go from the upper-left cell (represented by A[0]) to the bottom-right cell (represented by B[N-1]), moving only right and down, so that the maximum value over which you pass is as small as possible.

Write the function:

   int solution(int A[], int B[], int N);

That, given two arrays of integers, A and B, of length N, returns the maximum values on the optimal path.

Examples:

1. Given:
   A = [3, 4, 6],
   B = [6, 5, 4],
   the function should return 5. The optimal path is 3 → 4 → 5 → 4.

   Grid:

   3	4	6
   6	5	4

    note: bold number is shown as optimal path.

2. Given:
   A = [1, 2, 1, 1, 1, 4],
   B = [1, 1, 1, 3, 1, 1],
   the function should return 2. The optimal path is shown in the grid below.

   Grid:

   1	2	1	1	1	4
   1	1	1	3	1	1

    note: bold number is shown as optimal path.

3. Given:
   A = [-5, -1, -3],
   B = [-5, 5, -2],
   the function should return -1. The optimal path is (-5) → (-1) → (-3) → (-2).

   Grid:

   -5	-1	-3
   -5	5	-2

    note: bold number is shown as optimal path.

Write an efficient algorihm for the following assumptions::

• N is an integer within the range [1..100,000];
• Each element of arrays A and B is an integer within the range [-1,000,000,000...1,000,000,000].