SDE - 1

You are given a triangular array/list 'TRIANGLE'. Your task is to return the minimum path sum to reach from the top to the bottom row.

The triangle array will have N rows and the i-th row, where 0 <= i < N will have i + 1 elements.

You can move only to the adjacent number of row below each step. For example, if you are at index j in row i, then you can move to i or i + 1 index in row j + 1 in each step.

For Example :

If the array given is 'TRIANGLE' = [[1], [2,3], [3,6,7], [8,9,6,1]] the triangle array will look like:

1
2,3
3,6,7
8,9,6,10

For the given triangle array the minimum sum path would be 1->2->3->8. Hence the answer would be 14.

You are given an array of integers 'A' of size 'N' and a maximum score 'M'.

The score of a subsequence [ A[i1-1], A[i2-1] ... A[ik-1] ] is defined as the sum of ( i * k + A[i-1] ) for each element in the subsequence, where 'i' is the 1-based index of the element in the original array 'A' and 'k' is the length of the subsequence.

Your task is to find the length of the largest subsequence whose score is less than or equal to 'M'.

For Example :

Let 'N' = 4, 'A' = [3, 5, 1, 2] and 'M' = 20.
Let's check if a subsequence of length k = 2 is possible. To minimize the score, we choose the elements that have the smallest contribution ( i * k + A[i-1] ).
The contributions for k = 2 are:
For index 1 (value 3): 1 * 2 + 3 = 5
For index 2 (value 5): 2 * 2 + 5 = 9
For index 3 (value 1): 3 * 2 + 1 = 7
For index 4 (value 2): 4 * 2 + 2 = 10
The two smallest contributions are 5 and 7. The minimum score for a subsequence of length 2 is 5 + 7 = 12.
Since 12 <= 20, a subsequence of length 2 is possible.
Let's check for k = 3. The contributions would be ( i * 3 + A[i-1] ). The sum of the three smallest contributions is (1*3+3) + (3*3+1) + (2*3+5) = 6 + 10 + 11 = 27.
Since 27 > 20, a subsequence of length 3 is not possible.
Therefore, the answer is 2.

You are given an integer ‘N’ and two strings ‘S’ and 'R' each having size = ‘N’. You can scramble the string ‘S’ to obtain string 'R' using the following operations:

1. If the length of the string is greater than 1:

Select any random index and split the string into two non-empty substrings. For e.g: if the string is ‘S’, then divide it into two non-empty substrings ‘A’ and ‘B’ such that ‘S’ = ‘A’ + ‘B’.

You can choose to swap the two substrings or keep them in the same order, i.e., after this operation string ‘S’ may become either ‘S’ = ‘A’ + ‘B’ or ‘S’ = ‘B’ + ‘A’.

Apply the first step recursively on each of the two strings ‘A’ and ‘B’.

2. If the length of the string is equal to 1 then stop.

Your task is to return true if 'R' is a scrambled string of ‘S’ else return false.

Note:

1. Both the strings are non-empty and are of the same length.

2. You can apply the above operations any number of times on ‘S’.

3. The operations can only be applied on the string ‘S’.

4. ‘S’ and 'R' consist of lowercase letters only.

Design a data structure for LRU Cache.