Question

Triology | CodeNation | Coding | OA | SDE | 17th July 2022 | Set-1

Answer 1

Question 4

You are given some ranges [l, r] and a pseudocode to check whether i exists in the range or not. The pseudocode:

while(l < r) {
    int m = (l+r)/2
    if(i < m) {
        r = m-1;
    } else if(i > m) {
        l = m+1;
    } else {
        cout << "Found";
        break;
    }
}

You need to find the probability that the psudocode will fail. For example, given range [2, 9], the probability that it will fail is 1/2, since 2, 4, 6 and 9 will not be found with the code and total number of elements is 8, so probability 4/8 = 1/2. You have to answer the queries modulo 10^9+7, so the final answer for the above range would be 500000004. The input is a 2D array where each element array is of size 2 denoting the range [l, r].

1 <= l <= r <= 10^6 for each query.

The input consists of a 2d array.

 

Solution : 

This can be solved using dynamic programming. We calculate the number of elements which give correct answer and then subtract it from the length of the segment to get the incorrect answers. Every time we have a segment, we can see that the number of elements we get from it is dependent on the subparts we divide it into. For some length 'len', we have 1 answer for the midpoint and then we divide into two parts, one of size (len/2) and the other of size (len-len/2-1), since we are not taking the middle element for the next steps. The relation to calculate the number of correct elements given the length of the segment is as follows:

R(len) = {
           0 if len = 1,
           1 if len = 2 or len = 3,
           R(len/2)+R(len-len/2-1)+1 otherwise, (len/2 denotes floor division)
}

We add 1 to the last case because we can get 1 element from that length and R(len/2)+R(len-len/2-1) from the subparts.

So we call R(r-l+1) for every query to get the answer, and we can use a map or array to store the answers for the subproblems, so it won't time out for larger cases.

 

Answer 2

Question 3

You are a fruitshop owner and you have A fruits each with different size, denoted by array B. You also have a special essence with which you attract customers. You can use the essence on any number of fruits. You need to find the minimum number of fruits on which you have to use the essence so that the following conditions hold:

1. If you have used the essence on the ith fruit, then you have to use it on all fruits having size greater than the ith fruit.

2. There must be atleast one subarray(contiguous) of length atleast C, such that the number of fruits having essence is greater than the number of fruits not having essence in that subarray.

1 <= A <= 10^5

1 <= B[i] <= A

1 <= C <= A

The input consists of A, the array B and an integer C.

Solution : 

The idea is to use binary search on the minimum size of fruit to get the answer. This works because if we apply essence to that fruit, then all other fruits having size greater than them will be applied with essence, so we need to find the maximum among all such minimums. To check whether this works or not we can apply another binary search on the length of segment to find the maximum segment for which the 2nd condition holds and check whether that length is greater than or equal to C or not. We can do this using a prefix array in which we store 1 for the values which have value greater than or equal to the current fruit size in binary search and -1 for the others. If there is some segment for which the sum is greater than 0 for the current length, then we can check if it works for some greater length or not. If the final length is greater than or equal to C, we check if it is possible to do the same thing with some greater fruit size or not. So the final answer for the fruit size will give us the answer.

TLDR;

Binary search on fruit size:
  build an array with 1s(for indices having elements greater than or equal to current fruit size) and -1s(for others)
  Binary search on length:
    check for every index if there exists an index such that the sum of that subarray is greater than 0 and the second index is atleast (current length) distance away from the first index.
    return maximum length for which the 2nd condition holds.
  Check whether maximum length returned is greater than or equal to C or not, if yes, try to increase the fruit size, else decrease it.
return final fruit size

 

Answer 3

Question 2

You are given a string A, which only consists of characters 'R' and 'G'. You need to pick 4 elements such that they form a good subsequence. A good subsequence is defined as substrings in which there are 2 'G' followed by 2 'R' or vice versa, namely "RRGG" or "GGRR". You need to find the number of ways in which you can get good subsequences from the string.

1 <= |A| <= 10^6

Input consists of the string A.

 Solution :

We store the number of 'G' characters and 'R' characters in a suffix. Then we start iterating from the front side of the string and keep a count of the number of 'G' and 'R' till any point. If the current element is 'R', then we add to answer the number of characters 'R' occuring after the current element multiplied by the number of ways we can choose 2 'G' characters from the previous part. This essentially means that we calculate the number of "GGRR" subsequences, in which we fix the position of the first 'R' and then calculate the current answer for it and add it to the final answer. Similarly we can calculate the number of "RRGG" subsequences.

Answer 4

There were 4 questions in total, with points distribution as 200-200-200-350 : 

Question 1

You are given an array A with N elements, not necessarily distinct. You can swap any element with any other element, and you have to answer the number of ways in which you can get a good array. A good array is defined as an array for which A[1] > A[N], (1-indexed). Note that if there are two arrays with same A[1] and A[N], and the other elements are different, then both the arrays are considered same.

1 <= N <= 10^4

1 <= A[i] <= 10^5

Input consists of N and the array A.

Solution : 

The simple solution is to count the number of distinct elements in the array, lets denote it by p, then the answer is C(p, 2) = p*(p-1)/2.