10 weeks ago

Rohit • 610

Hyderabad

Question 1

Shweta and Candies

Shweta is a college girl and she loves Candies. She wants to share some candies with her friend Radhika. She is having N candies such that the ith candy is of A[i] brand where 0 ≤ i ≤ N. Let us call this array as the brand array. She wants to share K candies with Radhika such that the K- sized subsequence of the candies has a minimum number of distinct brands among all possible subsequences of length K.

Formally you will have to help Shweta in determining the subsequence of length K in the given array which has a minimum number of distinct brands among all possible subsequences of length K.

You will have to print the total brands of candies Rahikha received.

Input Format:

• The first line contains two space-separated integers N and K representing the total number of candies and the number of candies to be shared with Radhika.
• The second line contains N space-separated integers A[i] representing the brand of the ith candy.

Constraints:

1 ≤ K ≤ N ≤ 100000

1 ≤ A[i] ≤ 1000000000

Output Format:

• For each test case, print a single integer denoting the total brands of candies Rahikha received.

Sample Input 0:

10  6

1   3   2   4   3   4   5   3   4   3

Sample Output 0:

2

Explanation

One of the possible K-sized subsequences [3 4 3 4 3 4] with 2 distinct brands which is the minimum.

===================================================

Question 2

Roy and Strings

Roy is playing with strings and he came up with a very weird question.

He gave you string str of size N having lower case English alphabets and an array of size N which contains N non-negative integer value for every character present in the string.

Your task is to delete characters from the string following the given instruction:

Delete exactly one occurrence of every character present in the string

for e.g. str=aabba and array is [2,3,1,2,3] so frequency of character “a"=3 and frequency of character "b"=2, let's say you deleted 0th index i.e. “a" and 2nd index i.e. "b" which results in frequency of character "a" = 2 and frequency of character "b" = 1 and updated array is [0,3,0,2,3].

Note: Deletion means updating the value of that character in the array as 0

You have to delete the characters in a manner that after all deletions, the sum of the array would be minimum.

Note: The value of every undeleted character will remain unchanged after any deletion, for eg

In the above-mentioned string after deleting 1st and 3rd character the value of 2nd, 4th, and 5th character is still unchanged i.e. 3,2,3

Input:

The first line contains a T-denoting number of test cases.

For every test case,

• The first line contains N i.e. size of the string.
• The second line contains a string of size N.
• The third line contains N space separated non-negative integer values as mentioned in the question.

Output:

For every test case, output the minimum sum of the array that you get in a new line.

Constraints:

1 ≤ T ≤ 10

0 ≤ N ≤ 1e5

“a” ≤ str[i] ≤ “z” for 0 ≤ i < N

0 ≤ value[i] ≤ 1e9 for 0 ≤ i < N

Note:you have to delete exactly one occurrence of every character in the string. 

Sample Input:

1

5

abcde

1 2 3 4 5

8 months ago

Akshay Sharma 990

Chandigarh

Question 1

Overview

• We are given an array of size N and an integer k
• we have to choose the subsequence of length k.
• We need to choose a subsequence of length k that has a minimum number of distinct elements.

Approach/Solution

• The brute Force Approach would be to choose all subsequency of length K and for each subsequency find the number of the distinct elements present in it and return the minimum one but the time complexity of this solution is really bad that is O(K*N^K) that didn't work for large test cases and interviewer also didn't expect such a harsh time complexity from you.
• The optimal approach that we can follow up on this is to use hashing on the above solution as we know we have to find any subsequence not the subarray.
• The first thing we can do is store the frequency of each element in the hashmap M.
• After that, we can do a traversal of the hashmap and put the frequency of each element in another array say count and sort the count array in decreasing order. Now all frequencies of elements are sorted from greatest to smallest.
• we can maintain two variables say result and length to store the result of minimum distinct elements and length to count the current length of subsequence.
• Traverse the count array and check if(length>=k) break; otherwise increment the length by v[i] and result by 1.
• After that print the result.
• Time complexity : O(N)

8 months ago

Shikhar Mehrotra 480

Chennai

Q2) Since we need to just delete one occurence of each character and minimize the remaining sum.
Hence it is better to delete individual characters maximum value position.
For example(Consider 0 based indexing)
Let's suppose 'a' is on 0,1,2 'b' is on 3,4,5 and array a[5, 7,2,4,8,10] And we need to delete exactly one occurence of each character than it is better to delete the position of individual characters with maximum value in array a
Hence for 'a' delete position 1(value=7) and for 'b' delete position 5(value=10) hence our answer is 5+2+0+4+8+0=19