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)).

- Serge Aktanorovich October 28, 2015 | Flag Reply
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;	
}

- chinmay.rakshit March 11, 2016 | Flag Reply
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;

	}
}

- Shivman June 30, 2017 | Flag Reply
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;
  }
}

- avikalpakundu July 16, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Will this for sure not exceed time limit?

- pH August 21, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Will this exceed time limit?

- pH August 21, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

asasa

- shivman June 30, 2017 | Flag Reply
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;

	}
}

- ShivanshuJaiswal15 June 30, 2017 | Flag Reply
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;
}

- Deepak Yadav September 20, 2017 | Flag Reply
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;
}

- Deepak Yadav September 20, 2017 | Flag Reply
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;
}

- Deepak Yadav September 20, 2017 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More