# DE-SHAW interview question help!

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}

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

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.

What are the constraints??

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)

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

But bro this approach fails this test case.
NUMBERS: 3 9 6 9 2 2 4
FAVOURITE NUMBERS: 4 9

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

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

#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

Run this…it would pass all the test cases

1 Like

Sliding Window Approach. Thanks For Sharing code.

1 Like