Question

GoldMan Sachs | Recent Interview Experiences | SDE | Set-30

Answer 1

An array of numbers and favourite numbers are given. we have to find the number of sub arrays which includes all the favourite numbers atleast once.

Constraints:
Let size of NUMBERS array be N, and size of favourite numbers be K
1 <=N <= 10^6
1<=K<=N

EXAMPLE:
NUMBERS :{1,2,1,1,1,1}
Favourite Numbers: {1,1,2}

Answer: 7
Explanation:
(1,2,1) , (1,2,1,1), (1,2,1,1,1), (1,2,1,1,1,1), (2,1,1), (2,1,1,1), (2,1,1,1,1)

NUMBERS: 3 9 6 9 2 2 4
FAVOURITE NUMBERS: 4 9

ANSWER:
4
(3,9,6,9,2,2,4), (9,6,9,2,2,4) ,(6,9,2,2,4) , (9,2,2,4)

Any help would be highly appreciated.Sorry! I couldn't recall the every detail of the question

Answer 2

A similar problem like this is https://leetcode.com/problems/number-of-substrings-containing-all-three-characters/. In your case u can keep track of fav elements in hashmap and do the job as shown:
Here is simple solution for the problem I mentioned : class Solution {
public:
int numberOfSubstrings(string s) {

 

    int a=0,b=0,c=0;
    int i=0;
    int j=0;
    int ans=0;
    int n=s.size();
    for(int i=0;i<s.size();++i)
    {
        if(a>0 && b>0 && c>0)
        {
            ans+=n-j+1;
            
            if(s[i]=='a') a--;
            if(s[i]=='b') b--;
            if(s[i]=='c') c--;
            continue;
        }
        if(j==s.size()) break;
        
        while(j<s.size() && (a<=0 || b<=0 || c<=0))
        {
            if(s[j]=='a') a++;
            if(s[j]=='b') b++;
            if(s[j]=='c') c++;
            
            j++;
        }
        if(a>0 && b>0 && c>0) ans+=n-j+1;
        
        if(s[i]=='a') a--;
        if(s[i]=='b') b--;
        if(s[i]=='c') c--;
    }
    return ans;
}

 

};