## Directi Interview Question for SDE-2s

Country: India

Comment hidden because of low score. Click to expand.
1
of 1 vote

Hello. This problem can be solved in at least three different ways with the same approach. Assume L is sequence's length (in our case 10M). The main idea is to build data structure with two operations defined: 1) flip(start_index, end_index) -- flip bits from start_index to end_index; 2) query(index) -- get hexadecimal number corresponding to bits on positions [index, index+3]. The first approach is related to provided answer. The main issue is that the flip operation takes O(L) time in the worst case. The second idea is to divide our sequence on Sqrt(L) blocks and perform flip operation on blocks instead of on each element. In this case flip operation takes(O(Sqrt(L)) time in the worst case. The third approach is to build segment tree and implement each operation with complexity O(log(L)).

Comment hidden because of low score. Click to expand.
1
of 1 vote

``````#include <bits/stdc++.h>
using namespace std;
int a[10000007]={0};
int main(int argc, char const *argv[])
{
int t,x,y;
scanf("%d",&t);
while(t--)
{
int n,b[16]={0};
scanf("%d",&n);
while(n--)
{
scanf("%d %d",&x,&y);
a[x]++;
a[y+1]--;
}
for(int i=1;i<=10000000;i++)
a[i]+=a[i-1];
for(int i=1;i<=10000000;i++)
a[i]=a[i]&1;
int i=1,l=0,s=0;
while(i<=10000000)
{
s+=a[i]<<(3-l);
l++;
i++;
if(l==4)
{
b[s]++;
s=0,l=0;
}
}
for(i=0;i<=15;i++)
printf("%d ",b[i] );
printf("\n");
for(i=1;i<=10000000;i++)
a[i]=0;
}
return 0;
}``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

``````#include<bits/stdc++.h>
using namespace std;
int main()
{
long long t;
cin>>t;
while(t--)
{
int hex[16];
memset(hex,0,sizeof(hex));
vector<int> arr(10000000,0);
long long n;
cin>>n;
while(n--)
{
long long x,y;
cin>>x>>y;
arr[x]=1;
arr[y]=-1;
}
//for(int i=1;i<=16;i++)
//	cout<<arr[i]<<" ";
//cout<<endl;
int j=0;
int ans[4];
int count=0;
for(int i=1;i<=10000000;i++)
{
if(arr[i]==1 && count%2==0)
{
//cout<<"1 "<<i<<endl;
ans[j]=1;
j++;
count++;
}
else if(arr[i]==1 && count%2==1)
{
//cout<<"2 "<<i<<endl;
ans[j]=0;
j++;
count++;
}
if(arr[i]==-1 && count%2==0)
{
//cout<<"3 "<<i<<endl;
ans[j]=0;
j++;
count--;
}
else if(arr[i]==-1 && count%2==1)
{
//cout<<"4 "<<i<<endl;
ans[j]=1;
j++;
count--;
}
if(arr[i]==0 && count%2==0)
{
//cout<<"5 "<<i<<endl;
ans[j]=0;
j++;
}
else if(arr[i]==0 && count%2==1)
{
//cout<<"6 "<<i<<endl;
ans[j]=1;
j++;
}
if(j==4)
{
j=0;
//cout<<ans[0]<<ans[1]<<ans[2]<<ans[3]<<endl;
int num=8*ans[0]+4*ans[1]+2*ans[2]+ans[3];
ans[0]=ans[1]=ans[2]=ans[3]=0;
hex[num]++;
}

}
for(int i=0;i<16;i++)
cout<<hex[i]<<" ";
cout<<endl;

}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#include <iostream>
#define VERSION 0
#define ARRAY_SIZE 10000000

char *array= new char[ARRAY_SIZE]();
int *frequency;
int T,N;

inline void flip(int start, int end);
inline void init_array();
inline void show_output();

int main(int argc, char *argv[]){
int x,y;
//input
std::cin >> T; // number of test cases
frequency = new int [T*16]();
for(int count =0 ; count <T ; count++){
std::cin >> N; // number of operations
for(int i=0 ; i < N ; i++){
std::cin >>x;
std::cin >>y;
flip(x,y);
}
int hex;
for(int i=0; i <= ARRAY_SIZE - 4;i+=4){
hex= 8*array[i] + 4*array[i+1] + 2*array[i+2]
+ array[i+3];
frequency[16*count + hex]++;
}
init_array();
}
show_output();
return 0;
}

inline void flip(int start, int end){ // DONE
for (int i=start-1; i<end; i++){
(array[i]==0?array[i] =1 : array[i] =0);
}
}

inline void init_array(){ // DONE
for(int i=0;i < ARRAY_SIZE;i++){
array[i] = 0;
}
}

inline void show_output(){ // OK
for (int i=0; i < T ; i++){
for(int j=0; j < 15 ; j++){
std::cout << frequency[ i*16 + j ] << " ";
}
std::cout << frequency[i*16 + 15] << std::endl;
}
}``````

Comment hidden because of low score. Click to expand.
0

Will this for sure not exceed time limit?

Comment hidden because of low score. Click to expand.
0

Will this exceed time limit?

Comment hidden because of low score. Click to expand.
0
of 0 vote

asasa

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#include<bits/stdc++.h>
using namespace std;
int main()
{
long long t;
cin>>t;
while(t--)
{
int hex[16];
memset(hex,0,sizeof(hex));
vector<int> arr(10000000,0);
long long n;
cin>>n;
while(n--)
{
long long x,y;
cin>>x>>y;
arr[x]=1;
arr[y]=-1;
}
//for(int i=1;i<=16;i++)
//	cout<<arr[i]<<" ";
//cout<<endl;
int j=0;
int ans[4];
int count=0;
for(int i=1;i<=10000000;i++)
{
if(arr[i]==1 && count%2==0)
{
//cout<<"1 "<<i<<endl;
ans[j]=1;
j++;
count++;
}
else if(arr[i]==1 && count%2==1)
{
//cout<<"2 "<<i<<endl;
ans[j]=0;
j++;
count++;
}
if(arr[i]==-1 && count%2==0)
{
//cout<<"3 "<<i<<endl;
ans[j]=0;
j++;
count--;
}
else if(arr[i]==-1 && count%2==1)
{
//cout<<"4 "<<i<<endl;
ans[j]=1;
j++;
count--;
}
if(arr[i]==0 && count%2==0)
{
//cout<<"5 "<<i<<endl;
ans[j]=0;
j++;
}
else if(arr[i]==0 && count%2==1)
{
//cout<<"6 "<<i<<endl;
ans[j]=1;
j++;
}
if(j==4)
{
j=0;
//cout<<ans[0]<<ans[1]<<ans[2]<<ans[3]<<endl;
int num=8*ans[0]+4*ans[1]+2*ans[2]+ans[3];
ans[0]=ans[1]=ans[2]=ans[3]=0;
hex[num]++;
}

}
for(int i=0;i<16;i++)
cout<<hex[i]<<" ";
cout<<endl;

}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#include <bits/stdc++.h>
using namespace std;

int A[10000003];
int C[20];

int main() {
//freopen("input.in","r",stdin);
//freopen("output.out","w",stdout);

int T, N, a, b;
scanf("%d", &T);

while(T--) {
scanf("%d", &N);
for(int i = 1;i <= N;i++) {
scanf("%d %d", &a, &b);
A[a]++;A[b+1]--;
}

for(int i = 1;i <= 10000000;i++) {
A[i] += A[i-1];
}

for(int i = 1;i <= 10000000;i++) {
A[i] %= 2;
}

for(int i = 1;i <= 10000000;i += 4) {
C[8*A[i]+4*A[i+1]+2*A[i+2]+A[i+3]]++;
}

for(int i = 0;i < 16;i++) {
cout << C[i] << " ";
} cout << endl;

for(int i = 1;i <= 10000000;i++) A[i] = 0;
for(int i = 0;i < 16;i++) C[i] = 0;
}

return 0;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <bits/stdc++.h>
using namespace std;

int A[10000003];
int C[20];

int main() {
//freopen("input.in","r",stdin);
//freopen("output.out","w",stdout);

int T, N, a, b;
scanf("%d", &T);

while(T--) {
scanf("%d", &N);
for(int i = 1;i <= N;i++) {
scanf("%d %d", &a, &b);
A[a]++;A[b+1]--;
}

for(int i = 1;i <= 10000000;i++) {
A[i] += A[i-1];
}

for(int i = 1;i <= 10000000;i++) {
A[i] %= 2;
}

for(int i = 1;i <= 10000000;i += 4) {
C[8*A[i]+4*A[i+1]+2*A[i+2]+A[i+3]]++;
}

for(int i = 0;i < 16;i++) {
cout << C[i] << " ";
} cout << endl;

for(int i = 1;i <= 10000000;i++) A[i] = 0;
for(int i = 0;i < 16;i++) C[i] = 0;
}

return 0;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#include <bits/stdc++.h>
using namespace std;

int A[10000003];
int C[20];

int main() {
//freopen("input.in","r",stdin);
//freopen("output.out","w",stdout);

int T, N, a, b;
scanf("%d", &T);

while(T--) {
scanf("%d", &N);
for(int i = 1;i <= N;i++) {
scanf("%d %d", &a, &b);
A[a]++;A[b+1]--;
}

for(int i = 1;i <= 10000000;i++) {
A[i] += A[i-1];
}

for(int i = 1;i <= 10000000;i++) {
A[i] %= 2;
}

for(int i = 1;i <= 10000000;i += 4) {
C[8*A[i]+4*A[i+1]+2*A[i+2]+A[i+3]]++;
}

for(int i = 0;i < 16;i++) {
cout << C[i] << " ";
} cout << endl;

for(int i = 1;i <= 10000000;i++) A[i] = 0;
for(int i = 0;i < 16;i++) C[i] = 0;
}

return 0;
}``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.