Help with some questions

Revision en1, by aj116, 2024-01-29 19:17:46

Folks, any ideas on how to approach the following questions:

Q1. Given coins and minCoins both of size n < 10^5 and k < 10^5. coins[i] represents the cost of crossing the i-th toll and is subtracted from the number of coins you have after crossing the toll. If after crossing the i-th toll, you have atleast minCoins[i] remaining you get a star. Return an array of size n where arr[i] represents the number of stars which can be collected if you start to cross tolls from the i-th toll with k initial coins. Note that it is possible to have enough coins to continue even with remaining coins < minCoins[i] at a particular toll i. Ex: coins = [5, 7, 2, 1], minCoins = [4, 3, 2, 2], k = 10, ans = [1, 1, 2, 1]

I think a sliding window/two pointers on the coins array might work here but not 100% sure.

Q2. Given n < 10^5 numbers and k < 10^9, can the numbers be sorted just by swapping two number a[i], a[j] such that abs(a[i]-a[j]) <= k any number of times? Return boolean true/false. Ex: arr = [6, 5, 1, 2], k = 2, ans = false, arr = [2, 1, 6, 5], k = 2, ans = true For this problem, I think a set needs to be created starting from index i till the rightmost j possible. Then the set needs to be sorted in place. This process can be repeated till the end of the array and then it can be checked if the array is sorted. The set can be created by binary searching arr[i]-k or arr[i]+k in the existing set to see if arr[i] can be inserted into the set. If not, then this is the end of the current set.

Is there a better way to do this?

Q3. Given a graph with n < 10^5 nodes and m < 2*10^5 edges. Both nodes and edges have values. The pleasant value of a path in graph is the sum of node values minus the sum of edge values on that path. Return the maximum pleasant value of a path of length 4 starting from any node. All nodes and edges visited in a path must be unique. Ex: G = [[1, 2], [2, 3], [3, 4], [4, 5]], has paths 1-2-3-4 and 2-3-4-5

Any ideas for this?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English aj116 2024-01-29 19:17:46 2005 Initial revision (published)