1 day ago

John 500

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

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.

9 weeks ago

Akshay Sharma 860

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;
      }`

12 days ago

Yash Sahijwani 670

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

9 weeks ago

Akshay Sharma 860

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)

9 weeks ago

Akshay Sharma 860

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.

3 months ago

Gurankit Pal Singh 140

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