16 days ago

John 690

Mumbai

Question 1

You are given a string S of length N, which contains only lowercase alphabets from 'a' to 'z'.

Let's define the score of a string as xor of the occurrence of each character in the string.

You are required to handle two types of queries

• 1 L R: You need to answer the score of the substring of S from L to R
• 2 X Y: Update the character at position X to Yth alphabet from 'a' to 'z'

Notes

• 1-based indexing is followed.
• The XOR operation takes two numbers as operands and does XOR on every bit of two numbers. The result of XOR is 1 if the two bits are different, otherwise, it is 0.
• Yth alphabet from 'a' to 'z' is the character at Ythindex (1-based) in string 'abcdefghijklmnopqrstuvwxyz'. For example, 4th alphabet is 'd'.
• A substring of a string is a contiguous subsequence of that string.

Task

For each query of type 1, output the score of the string.

Example

Assumptions

• S = 'abda'
• Q = 2
• queries = [[2,3,2],[1,1,3]]

Approach

• The first query

   Update 3rd index from left to 2nd alphabet from 'a' to 'z'. So we can change from 'a' to 'b'. The resulting string is 'abba'
  

• The second query

   The substring from 1 to 3 is abb. The frequency of character 'a' is 1 and the frequency of character 'b' is 2.
  
   Thus, the score of the substring is 1 *XOR* 2 = 3
  

Constraints

1 <= |T| <= 10

2 <= |S| <= 10^5

1 <= Q <= 10^5

1 <= L <= R <= |S|

1 <= X <= |S|

1 <= Y <= 26

Sample Input

1
tti
4
2 3 1
1 1 2
2 1 2
1 2 3

Sample Output

2   0

Question 2

Good String

Good string 

You are given a string S of length N, Q ranges of the form [L. R] in a 2D
array range. and a permutation arr containing numbers from 1 to N.

Task

in one operation, you remove the first unremoved character as per the permutation. However, the positions of other characters will not change.
Determine the minimum number of operations for the remaining string to be good.

Notes

• A string Is considered good if all the Q ranges have all distinct characters, Removed characters are not counted,
•  A range with all characters removed is considered to have all distinct characters
•  The sequence of n integers is called a permutation if it contains all Integers from 1 to n exactly once
• I-based Indexing Is followed

Example

Assumptions

* N=5 Q=2 S= "aaaaa"
arr=[2,4,1,3, 5]
ranges = [[1,2],[4,5]]

Approach

• After the first operation, the string becomes a_aaa
• After the second operation, the string becomes a_a_a
• Now, in both ranges, all characters are distinct

Hence, the output is 2
Function description

Complete the goodString function provided in the editor. This function
takes the following 6 parameters and retums the minimum number of
operations:

•  N Represents the length of the string
•  S: Represents the string
• arr. Represents the permutation according to which characters will be removed
• Q Represents the number of ranges
• ranges: Represents an array of 2 integer armays describing the ranges [L,R] which should have all distinct characters

Input Format

This is the input format that you must use to provide custom input
above the Compile and Test button).

• The first line contains a single integer T denoting the number of
• test cases. T also specifies the number of times you have to run
• the goodsString function on a different set of Inputs,
• For each test case:
  •  The first line contains 2 space-separated integers Nand Q.
  •  The second line contains the string S. Xs
  • The third line contains N space-separated integers denoting the permutation arr.
  •  Each of the Q following lines contains 2 space-separated Integers describing the range, L and R

For each test case , print a single integer in a single line  denoting the minimum number of operations required for the remaining string to be good

Constraints 

1 ≤  T ≤ 10

1 ≤ N ≤ 10⁵

1 ≤ Q ≤ 10⁵

1 ≤ arr_i ≤ N

1 ≤ L_i ≤  R_i ≤ N

Bonus Questions

Onsite Amazon Question asked in May, 2022

Question 3

You are given the root of a binary tree with 'n' nodes where each node in the tree has 'node.val' coins. There are 'n' coins in total throughout the whole tree. In one move, we may choose two adjacent nodes and move one coin from one node to another. A move may be from parent to child, or from child to parent. Return the minimum number of moves required to make every node have exactly one coin.

Example

    3
  /   \
 0     0

Input:

root = [3,0,0]

Output:

2

Explanation: From the root of the tree, we move one coin to its left child, and one coin to its right child.

Question 4

Given a string 's', return the lexicographically smallest subsequence of 's' that contains all the distinct characters of 's' exactly once.

Example 1

Input:

s = 'bcabc'

Output:

'abc'

Example 2

Input:

s = 'cbacdcbc'

Output:

'acdb'

Question 5

Given two strings 's' and 't' of lengths 'm' and 'n' respectively, return the minimum window substring of 's' such that every character in 't' (including duplicates) is included in the window. If there is no such substring, return the empty string ' '''' '.

Example

Input:

s = 'ADOBECODEBANC', t = 'ABC'

Output:

'BANC'

Explanation: The minimum window substring 'BANC' includes 'A', 'B', and 'C' from string t.

4 months ago

Akshay Sharma 940

Delhi

QUESTION 3

Solution

• Let's try to understand the approach using the diagram below:

  

• We traverse the child first (post-order traversal), and return the balance of coins. For example, if we get '+3' from the left child, that means that the left subtree has 3 extra coins to move out. If we get '-1' from the right child, we need to move 1 coin in.

• So, we increase the number of moves by 4 (3 moves out left + 1 move in right). We then return the final balance: r->val (coins in the root) + 3 (left) + (-1) (right) - 1 (keep one coin for the root).

Pseudo code `

    int ans=0;
    int recr(TreeNode *root)
    {
    if(!root) return 0;
    int left = recr(root->left);
    int right = recr(root->right);
    int curr = root->val + left + right;
    ans += abs(curr-1);
    return curr-1;
      }`

6 months ago

Yash Sahijwani 770

Solution for Question 1

Analysis

In the question, we are given a string followed by queries of two types - one for updating the string, and the other for finding the score in a given interval. The score has been defined as the XOR of the frequencies of each distinct character in the interval [l, r]. Since the number of queries in 10^5, we need an efficient method which works in O(logn) or O(1) for each query, to update the string as well calculate the new frequencies.

A basic method can be to create a prefix array for each letter from 'a' to 'z', where pref1[i] stores the total number of occurrences of the letter 'a' that come before or at the index i, and similarly for all the other letters. Calculating number of occurrences will take O(1) time, by simply calculating pref1[r] - pref1[l-1]. However, updating the prefix array can take O(n) time.

A better method to do this is using Fenwick Tree. In Fenwick tree we can update the array in O(logn) time, and the prefix sums can also be calculated in O(1) time. You can view this link for a better understanding of Fenwick Tree. In this problem, if we want to update the array, for the letter we want to remove, we update that letter's array by subtracting 1 from the position we want to update (and hence all positions such that g(j) <= i <= j, using the fenwick update method), and to add a letter, we just add 1 in the same manner.

Fenwick Tree Implementation

void add_fenwick(int idx, int i, vector < vector < int > > &fenwick, int val)
{       
     int n = fenwick[0].size();
    while(i < n)
    {
         fenwick[idx][i] += val;
         i = i | (i+1);
    }
    return;
}
int calc_sum(int idx, int i, vector < vector < int > > &fenwick_tree)
{
  int ans = 0;
  while(i > 0)
  {
     ans += fenwick_tree[idx][i];
     i = (i & (i+1)) - 1;
  }
  return ans;
}
// Here idx refers to the character we want to update
// i refers to the position
// In calculate sum function I have kept terminating condition as i > 0, since I am using 1 based indexing

4 months ago

Akshay Sharma 940

Delhi

Question 4

Overview

• We are given a string s we need to find the lexicographically smallest string possible that has all distinct characters.
  • Mean the string we are going to print is the smallest possible for each s[i] and no two characters repeat in that string.

Solution

• We will be going to maintain a hashmap or frequency array and start traversing the string.
  • one we get to any position we are going to check if that character is already present in the frequency array or not.
  • If the character is already present we can skip it else we will mark it true in the frequency array.
  • Once we reach to end we start traversing the frequency array and check if freq[i] is not false so that we can print that character at once.
  • Time complexity : O(N)

4 months ago

Akshay Sharma 940

Delhi

Question 5

Overview

• We are given strings S and T.
  • We need to find a string such that every character in string T is included in string S (Including duplicates)
  • Let's assume the size of strings S and T would be less than 10^4.
  • Also complete string S could be the answer for our given solution.
  • There can be multiple solutions to this question but we need to return that substring which has minimum length among all.
  • if string T did not exist in string S we need to return empty string.

Solution

• Here we’re storing all the characters from string t to an unordered_map mp or use hashing.
• We are taking 3 variables, ans(to store the size of the minimum substring), start(to store the start index) & count(to store the map size, if it became 0 that means we got a substring)
• Now taking 2 pointers i & j, we’ll iterate using j & will decrement the element count in the map in c++ or hash map in java.
• if at any point the value became 0 that means we got all the elements of that char till now, so we’ll decrement the size of the count.
• In this way, we will decrement and once the count will be 0 if there is a substring with all the elements present.
• Now we’ll increment i and check if there is possible to remove any more characters and get smaller substrings.
• We’ll store the smaller length to ans & store the ith index in the start variable. Also, we’ll add the element to our map and increment the count variable if it became greater than 0.
• Now if the ans have some length except int_max, then return the substring from the start index to the length of ans. Else return the empty string.
• Time complexity: O(m), where m is the length of string s.

10 months ago

Gurankit Pal Singh 160

Solution for Question 2

This problem can be solved by binary searching on the answer. Let n be the length of the string and x be the number of operations performed. Make a prefix sum frequency array freq[n][26] from x+1 to n. Now, frequency from L to R for a letter j can be calculated by freq[R][j] - freq[L-1][j] in O(1). If the frequency of each letter in each range is less than 2, then the string would be a good string. Perform the binary search on x, so, the time complexity is O(nlogn26), and space complexity is O(n*26).

Pseudo Code:

check(operations, str, arr, ranges)
    freq[n][26]
    for i from operations to n
        ++freq[arr[i]][str[arr[i]]]

    for i from 1 to n
        for j from 0 to 25
            freq[i][j] += freq[i-1][j]

    for i from 0 to ranges.size
        L = ranges[i][0], R = ranges[i][1]
        for j from 0 to 25
            if freq[R][j]-freq[L-1][j] > 1
                return false

    return true

goodString(str, arr, ranges)
    n=arr.size
    start = 0, end = n, mid, ans
    while start < = end
        mid = (start + end)/2
        if check(mid, str, ranges)
            ans = mid
            end = mid-1
        else
            start = mid+1

    return ans