11 weeks ago

Rohit • 610

Hyderabad

Location: Bangalore and Hyderabad

Link: Software Engineering Roles

Question 1

Professor X has to solve the perennial problem of the budget for school picnic Each student is identified by a unique Roll Number (r[i]) and a Unique Identification Number(a[i]). The total amount of the trip will be calculated as the sum of the cost of each of the rounds as long as there are at least two students remaining in the class. In a single round:

• Professor will select two students in his class, let them be p and q.
• Choose Unique Identification Number(a[p]) of one and Roll Number(r[q]) of the other. Add the value a[p] r[q] to the amount of trip. Or another option is vice versa, a[q] r[p]
• Return one (say p) back to the class, while the other (say q) will go and sit in the bus outside or vice versa, i.e., return q to the class and p goes and sits in the bus. Note p and q are indexes of the students.

In the last round, both students will go to the bus.

The professor needs your help. You need to find the minimum possible amount of the trip, considering all the possible ways in which the student can be selected and organized. Help him out.

As this amount can be very large find its mod with 10^9+7.

Input

• The first line contains a positive integer n: the number of students.
• The second line contains a list of N positive integers a; the i-th of these represents the Unique Identification Number on the i-th student.
• The third line contains a list of N positive integers r; the i-th of these represents the Roll number on the i-th student.

Output

The minimum possible total that can be attained if students are selected optimally.

Constraints

• 1 <= n <= 10^3
• 1 <= a[i] <= 10^9
• 1 <= r[i] <= 10^5

Sample Test Case

3
23  45  56
11  14  3

Explanation: Professor X will first select student and student3, adding the value (a1 r[3]) i.e 23 3 = 69 to the total. student will go and sit in the bus while student3 will return back to the class. In the next round, professor will select the remaining students i.e student2 and student3. He will be adding the value (a[2] r[3]) i.e 45 3 = 135 to the total. After this, no more pairs of students will remain in the class so the minimum possible amount will be 69 + 135 = 204.

• [execution time limit] 4 seconds (py3)
• (input) integer n
• [input] array.integer64 a
• [input] array.integer64 r
• (output) integer64

Question 2

Bob is painting a wall. The wall contains N sections and he has already painted some sections of the wall randomly. The wall consists of a string of length N containing lower-case alphabets 'a' to 'z' denoting the color of the section.

In 1 operation, Bob can paint a single section of the wall to any new colour. He is now tired and does not want to do more than k operations. So, he decides to create a continuous segment of the wall which is completely the same colour (a range [i, j] where all wall[k] are equal, i <= k <= j).

What is the maximum length of such a segment he can create.

Constraints

• 1 <= N <= 5* 10^5
• wall[i] = 'a' to 'z'
• 0 <= k <= 5 * 10^5

Example

wall = "abaab"

k = 1

Output = 4

Bob can paint the 2nd to 'a' (New Wall = 'aaaab') to get the maximum painted segment of length 4 of colour 'a'

• [execution time limit] 4 seconds (py3)
• [input] string wall, Defines the colour of the section wall[i] = 'a' to 'z
• [input] integer k, The amount of operations, Bob can perform
• (output) integer, The maximum painted segment of the wall

Question 3

Given an array, you have to make some delete operations on it.

• Delete any p elements from it.
• Now delete a groups of 2 consecutive elements from the remaining array
• Now delete r groups of 3 consecutive elements from the remaining array.

After all these operations, the sum of elements of the resultant array should be the maximum possible. Return this maximum value.

Example

For arr = [3, 1, 0, 5, 1, 6, 5, -1, -100], p = 1, q = 1, r = 1, the output should be solution (arr, p, q, r) = 16. Here, after deleting 1, [-1, -100] and [3, 1, 0], resultant array will be: [5, 6, 5], having sum = 5 + 6 + 5 = 16.

Here if we delete any other element, resultant sum will be less than 16. For eg, if we delete [3], [1, 0], [5, 1, 6], resultant array will be: [5, -1, -100] , having sum = 5 + (-1) + (-100) = -96 which is less than 16.

• [execution time limit] 4 seconds (py3)

• [input] array.integer arr

Guaranteed constraints:

1 <= arr.length <= 100

-10^5 <= arr[i] <= 10^5

• [input] integer p

• [input] integer q

• [input] integer r

Guaranteed constraints:

0 <= p, q, r <= 30

p + 2q + 3r < arr.length.

• (output) integer, The maximum sum of elements of the resultant array after making required deletions

18 months ago

Ayush Kumar Shaw 110

Solution to Question 3

It's easy to observe that the order in which we delete the elements does not matter. We can ultimately get the array with the maximum sum by performing the operations in any order. So, we can use dymanic programming to solve the problem. We can maintain a 4 state dp table dp[i][j][k][l] which denotes the maximum sum of the remaining array after processing j deletions of the first type, k deletions of the second type and l deletions of the third type, on the first i array elements. The transitions will be simple enough as we can select the last group that we are deleting in the first i elements and then take the maximum value using the dp table.

dp[i][j][k][l]=max(a[i]+dp[i-1][j][k][l],dp[i-1][j-1][k][l],dp[i-2][j][k-1][l],dp[i-3][j][k][l-1])

The final time complexity of the solution is O(n * p * q * r) which is fast enough. The final answer is stored in dp[n][p][q][r].

Implementation

    int n,p,q,r,mod=1e9+7;
    cin >> n >> p >> q >> r;
    vector < int > a(n+1);
    for(int i=1;i <= n;i++){
        cin>>a[i];
    }
    int dp[n+1][p+1][q+1][r+1];
    memset(dp,-mod,sizeof(dp));
    dp[0][0][0][0]=0;
    for(int i=1; i <= n;i++){
        for(int j=0;j <= p;j++){
            for(int k=0;k <= q;k++){
                for(int l=0;l <= r;l++){
                    if(j+2*k+3*l > i) continue;
                    dp[i][j][k][l]=max(dp[i][j][k][l],a[i]+dp[i-1][j][k][l]);
                    if(j >= 1){
                        dp[i][j][k][l]=max(dp[i][j][k][l],dp[i-1][j-1][k][l]);
                    }
                    if(k >= 1 && i >= 2){
                        dp[i][j][k][l]=max(dp[i][j][k][l],dp[i-2][j][k-1][l]);
                    }
                    if(l >= 1 && i >= 3){
                        dp[i][j][k][l]=max(dp[i][j][k][l],dp[i-3][j][k][l-1]);
                    }
                }
            }
        }
    }
    cout << dp[n][p][q][r];

8 months ago

Akshay Sharma 990

Chandigarh

Question 2

overview

We are having a string of size N that contains characters from 'a to 'z' that denotes the colour of each index wall. In one section bob can paint a single section of colour to any new colour. He wanted to create a continuous segment(walls of the same colour) by not performing more than K operation and we have to return the maximum length that he can paint.

Approach

• The question is more likely the flip the 0 to get the maximum number of consecutive 1s.
• Similarly, in this question, we are given paint from 'a' to 'z' and we have to perform k operation to get the maximum number of colours in a segment.
• Check for every 26 characters. Traverse the array for every character and check the longest wall segment until the no of different characters reaches k.
• Here we are using 2 pointer approach. Both the pointers (r,l) start from index '0'.
• Then we start incrementing r pointer till we are getting 'charcter' or till the number of fliped 'wall[paint]' is less than k and regularly check for the max length of the subarray.
• At any point of time, the number of flipped wall[paint] becomes more than k we increment l till the number of flipped 'wall[paint]' is less than k.
• Now again l pointer is at starting of another valid subarray. We again increment r and repeat the above process.
• Time Complexity: O(N*26) as we are checking for each character from 0 to 26

Pseudo Code

int helper(string A, int n, int k, char ch)
{
int maxlen = 1;
int cnt = 0;
int l = 0, r = 0;
while (r < n)
{

    if (A[r] != ch)
        ++cnt;

    while (cnt > k)
    {
        if (A[l] != ch)
            --cnt;
        ++l;
    }

    maxlen = max(maxlen, r - l + 1);
    ++r;
}
return maxlen;
}

2.1 years ago

lxtz • 10

send the solution with code of question 1 and 3

4 months ago

Ujjwal Srivastava 320

Bengaluru

Question 1

Solution

• Let vector v_id contains pair of {a[i],i} and v_roll_no contains pair of {r[i],i}.
• Sort the vector v_id in ascending order.
• Sort the vector v_roll_no in ascending order.
• Let the first element in v_id which contains the smallest a[i] has an index lets say a_small_idx = v_id[0].second.

• Let the first element in v_roll_no contains the smallest r[i] has an index lets say r_small_idx = v_roll_no[0].second.

  • if a_small_idx ==r_small_idx

    • Initialise answer as 0.
    • Iterate over all indexes except a_small_idx and add following to the answer: answer+= min(a[cur_index]*r[r_small_idx], a[a_small_idx]*r[cur_index]). Also answer %=mod.

  • if a_small)idx != r_small_idx

    • Initialise answer as 0.
    • Iterate over all indexes except a_small_idx and r_small_idx and add following to the answer: answer+= min(a[cur_index]*r[r_small_idx], a[a_small_idx]*r[cur_index]). Also answer %=mod.
    • At last add answer+=a[a_small_idx]*r[r_small_idx],answer %=mod.

• At last print the answer.