DE-SHAW interview question help!

help
1

Recently DESHAW came for oncampus intern ,there was a question which i couldn’t solve it.
Question gives this meaning:

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

Explanation:
(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.

2

What are the constraints??

4

take two pointer i = 0 and j = 0 and then find the value of j at which all the favourite number are present then add n - j to the answer and increment i and again find such j and add the n - j to the answer and keep this process going until j < n
time complexity would be O(n)

5

the idea behind this is that if for any i to j if the lucky number condition is fulfilled then it is obvious that this condition will also be fullfiled for i to j+1, i to j+2…i to n so we just to add n - j to the answer

6

But bro this approach fails this test case.
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)

7

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

8

#include<bits/stdc++.h>

using namespace std;

int main(){

int n = 7;

int arr[7] = {3, 9, 6, 9, 2, 2, 4};  //3 9 6 9 2 2 4

int luck[] = {4 , 9};

unordered_map<int, int> m;

for(int i=0; i<2; i++){

    m[luck[i]]++;

}



int count = m.size();

int left = 0, right = 0, ans = 0;

while(right < n){

    if(m.find(arr[right]) != m.end()){

        m[arr[right]]--;

        if(m[arr[right]] == 0){

            count--;

        }

    }

    while(count == 0){

        ans += (n - right);

        if(m.find(arr[left]) != m.end()){

            m[arr[left]]++;

            if(m[arr[left]] == 1){

                count++;

            }

        }

        left++;

    }

    right++;

}

cout<<ans;

}

4 Likes
9

Run this…it would pass all the test cases

1 Like
10

Sliding Window Approach. Thanks For Sharing code.

1 Like