Directi Interview Question
SDE-2sCountry: India
#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;
}
#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;
}
}
#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;
}
}
#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;
}
}
#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;
}
#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;
}
#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;
}
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