Task 1

You want to visit your friend, who lives abroad. It is time to plan the whole journey, both there and back. The trip will be long, so you would like to make it interesting. You do not want to revisit the same places or go along the same paths twice. Also, you do not have much time, so you do not want to head back from any point.

You will represent your planned path by a string containing four letters: N for north, S for south, E for east, and W for west. For example, a path going north, east, east, north, west, south would be notated as "NEENWS".

You have already made a plan of the outward part of your journey. How will you plan the shortest path back home, fulfilling the criteria described above?

Write a function:

class Solution {  
    public String solution(String forth);  
}

that, given a string forth of length N, which denotes the path leading to your friend, returns one of the shortest possible paths back home and fulfills the above conditions. You can assume that you are heading north at both the beginning and the end of the first part of your journey (the first and the last element in forth are equal to N). Moreover, forth does not contain any occurrence of the letter S.

Examples

1. Given forth = "NEENWN", your function may return "WWSSSE". It may also return "WSWSSE".

---

Task 2

There are N cities (numbered from 1 to N, from left to right) arranged in a row and N-1 one-way roads between them:
1 → 2 → 3 → ... → N-1 → N.

The government has a plan to build M new roads. The roads will be built one by one. The K-th road will connect the A[K]-th city with the B[K]-th city (roads are numbered from 0 to M-1). Each road will lead from the left to the right, from a city with a smaller number to a city with a larger number. No two roads will intersect. Formally, there will be two roads A → B and C → D, such that A < C < B < D.

Jack lives in city number 1 and his school is located in city number N. He wants to know the distance from home to school after each new road is built.

Write a function:

class Solution {  
    public int[] solution(int[] A, int[] B, int N);  
}

that, given two arrays A, B consisting of M integers each and an integer N, returns an array D consisting of M integers, where D[K] denotes the distance from home to school after building the first K roads. The distance is the minimum number of roads required to move between two cities.

Examples

1. GivenA = [2, 5, 1], B = [4, 7, 4] and N = 7, the function should return [5, 4, 3].
   • After building the first road (2 → 4), the shortest path from home to school is: 1 → 2 → 4 → 5 → 6 → 7, and its length is 5.
   • After building the second road (5 → 7), the shortest path from home to school is: 1 → 2 → 4 → 5 → 7, and its length is 4.
   • After building the third road (1 → 4), the shortest path from home to school is: 1 → 4 → 5 → 7, and its length is 3.
2. GivenA = [1, 1], B = [7, 4] and N = 7, the function should return [1, 1].
   • After building the first road (1 → 7), the shortest path from home to school is 1. The roads built subsequently do not improve the result.
3. GivenA = [30, 50, 40], B = [40, 60, 50] and N = 100, the function should return [90, 81, 72].
   • Each new road shortens the distance from home to school by 9.

Write an efficient algorithm for the following assumptions:

• N is an integer within the range [1,100,000].
• M is an integer within the range [0,100,000].
• Each element of A and B is a unique integer within the range [1,N].
• Each element of A is smaller than the corresponding element of B.
• The new roads are added in the range [0,M-1].

---

我们长期稳定承接各大科技公司如TikTok、Google、Amazon等的OA笔试代写服务，确保满分通过。如有需求，请随时联系我们。

We consistently provide professional online assessment services for major tech companies like TikTok, Google, and Amazon, guaranteeing perfect scores. Feel free to contact us if you're interested.