Question from a Sprinklr interview

→ Обратите внимание

До соревнования
Codeforces Round 941 (Div. 1)
4 дня
Зарегистрироваться »

*есть доп. регистрация

До соревнования
Codeforces Round 941 (Div. 2)
4 дня
Зарегистрироваться »

*есть доп. регистрация

→ Трансляции

CodeChef Starters 131 Solution Discussion

aryanc403

До начала 23:53:04

Всё →

→ Лидеры (рейтинг)

№	Пользователь	Рейтинг
1	ecnerwala	3650
2	Benq	3582
3	Geothermal	3570
3	orzdevinwang	3570
5	cnnfls_csy	3569
6	tourist	3565
7	maroonrk	3532
8	Radewoosh	3522
9	Um_nik	3483
10	jiangly	3468

Страны | Города | Организации

Всё →

→ Лидеры (вклад)

№	Пользователь	Вклад
1	maomao90	174
2	awoo	164
3	adamant	163
4	TheScrasse	159
5	nor	158
6	maroonrk	156
7	-is-this-fft-	151
8	SecondThread	147
9	orz	146
10	pajenegod	145

Всё →

→ Найти пользователя

→ Прямой эфир

Детальнее →

Блог пользователя guptaji30

Question from a Sprinklr interview

Автор guptaji30, история, 2 года назад, По-английски

Given an array, arr[] of integers. The task is to sort the elements of the given array in the increasing order of their modulo with 3 maintaining the order of their appearance.

Expect time complexity O(N) and the interviewer said that it can be done in only one/two traversal(s)(sorry I don't remember it clearly, it was quite sometime ago).

Expected space complexity O(1).

array, sorting, interview

guptaji30
2 года назад
24

Комментарии (17)

Показать архивные | Написать комментарий?

Actium

2 года назад, # |

← Rev. 3 →

-22

https://en.wikipedia.org/wiki/Dutch_national_flag_problem

However, stability requirement is not achievable in the given constraints.

→ Ответить

atarax

2 года назад, # |

-23

We can use dutch national flag as modulo with 3 will leave us with an array of 0, 1, 2. So the problem will boil down to something like this.

→ Ответить

tanmay.raj.29

2 года назад, # ^ |

The task is to sort the elements of the given array in the increasing order of their modulo with 3 maintaining the order of their appearance.

How to maintain the order of their appearance in one traversal?

→ Ответить

whynotremainsilent

2 года назад, # ^ |

If you push the elements in a vector, the order will be maintained.

→ Ответить

tanmay.raj.29

2 года назад, # ^ |

← Rev. 2 →

nvm

→ Ответить

m_patel

2 года назад, # ^ |

Space Complexity is O(1) mate. You can't use another vector. Somehow you have to think of a way while using only swapping.

→ Ответить

m_patel

2 года назад, # ^ |

In that way the original order will not be maintained.

→ Ответить

tiasmondal

2 года назад, # |

Can do it in 2 traversals with no extra space. In one traversal you can get number of 0s,1s and 2s. So in the second traversal, if you encounter a number, you know its exact position (from the previous traversal). Just swap with its exact position and continue the process.

→ Ответить

guptaji30

2 года назад, # ^ |

← Rev. 2 →

can you please elaborate I had though of the same thing but wasn't sure if it will maintain the order of the elements

→ Ответить

tiasmondal

2 года назад, # ^ |

okay, I just gave a thought and found out that the order will not be maintained. If you allow one more traversal then it is possible definitely. In the second traversal replace each value with its original position in the sorted array, this can be done using the number of 0,1,2. Finally, in the 3rd traversal, swap it i.e place everything in the positions stored. Maybe this swapping can be done in the 2nd traversal only efficiently but I guess it's tricky.

→ Ответить

guptaji30

2 года назад, # ^ |

Can you write the code for this ??

→ Ответить

tiasmondal

2 года назад, # ^ |

Code

ll n,i;
cin>>n;
vector<ll> v(n);
for(i=0;i<n;++i)
cin>>v[i];
ll cnt[3];
memset(cnt,0,sizeof(cnt));

for(i=0;i<n;++i)
{
    cnt[v[i]%3]++;
}
cnt[2]=cnt[0]+cnt[1];
cnt[1]=cnt[0];
cnt[0]=0;

ll con=1e9+7;
for(i=0;i<n;++i)
{ll x=v[i]%3;
    
    v[i]=cnt[v[i]%3]+v[i]*con; 
    cnt[x]++;
}


i=0;
while(i<n)
{
    while(i!=v[i]%con)
    {
        swap(v[i],v[v[i]%con]);
    }
    v[i]=v[i]/con;
    ++i;
}

for(auto x:v)
cout<<x<<" ";

→ Ответить

xinyster

2 года назад, # |

← Rev. 2 →

-13

→ Ответить

tanmay.raj.29

2 года назад, # ^ |

Order is not maintained here

→ Ответить

_Enginor_

2 года назад, # |

I think below code will work assuming input can be modified It uses two passes one to count the number of 0,1,2's and second for modifying the input to make it sorted by starting three pointers from 0,cnt[0],cnt[0]+cnt[1].

code

#include<bits/stdc++.h>

using namespace std;



#define fastio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define MOD 1000000007
#define MOD1 998244353
#define INF 1e18
#define nline "\n"
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define ff first
#define ss second
#define PI 3.141592653589793238462
#define set_bits __builtin_popcountll
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()

typedef long long ll;
typedef unsigned long long ull;
typedef long double lld;
// typedef tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update > pbds; // find_by_order, order_of_key

#ifndef ONLINE_JUDGE
#define debug(x) cerr << #x <<" "; _print(x); cerr << endl;
#else
#define debug(x)
#endif

void _print(ll t) {cerr << t;}
void _print(int t) {cerr << t;}
void _print(string t) {cerr << t;}
void _print(char t) {cerr << t;}
void _print(lld t) {cerr << t;}
void _print(double t) {cerr << t;}
void _print(ull t) {cerr << t;}

template <class T, class V> void _print(pair <T, V> p);
template <class T> void _print(vector <T> v);
template <class T> void _print(set <T> v);
template <class T, class V> void _print(map <T, V> v);
template <class T> void _print(multiset <T> v);
template <class T, class V> void _print(pair <T, V> p) {cerr << "{"; _print(p.ff); cerr << ","; _print(p.ss); cerr << "}";}
template <class T> void _print(vector <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(set <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(multiset <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void _print(map <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}

int main() {
#ifndef ONLINE_JUDGE
   freopen("Error.txt", "w", stderr);
#endif
   ll n;
   cin>>n;
   ll a[n];
   ll i;
   for(i=0;i<n;i++)
   {
      cin>>a[i];
   }
   ll cnt[3]={0};
   for(i=0;i<n;i++)
   {
      cnt[a[i]%3]++;
   }
   ll zeroindx=0;
   ll oneindx=cnt[0];
   ll twoindx=cnt[0]+cnt[1];
   //let us suppose maximum value not present in array is 1000000000
   ll mxv=10000000;
   for(i=0;i<n;i++)
   {
      ll v=a[i]%mxv;
      if(v%3==0)
      {
         a[zeroindx]+=mxv*v;
         zeroindx++;
      }
      else if(v%3==1)
      {  
         a[oneindx]+=mxv*v;
         oneindx++;
      }
      else
      {
         a[twoindx]+=mxv*v;
         twoindx++;
      }
   }
   for(i=0;i<n;i++)
   {
      cout<<a[i]/mxv<<" ";
   }
   cout<<"\n";
}

→ Ответить

pankaz_20

2 года назад, # ^ |

I have a doubt.... for example you are changing value of a[oneindx], but you are not storing its previous value i mean it's previous value would be diminshed?

→ Ответить

_Enginor_

2 года назад, # ^ |

This is very standard technique in which we can store information about two numbers using a single number.
let us say some n 
n=4
and now i want to somehow store 50 also.
So first we require some number that is bigger than both 4 and 50 so let us say 51 is one such number
so new modified number will be n=4+51*50;
now if we need to get information of both number 
so original number = n%51=(4+51*50)%51=(4%51+(50*51)%51)%51=4%51=4(original number)
if we want new number then it is equal to= n/51(integer division)=(4+51*50)/51=0+50=50(second number).
so in this we are storing information of two numbers in a single number.

→ Ответить

Соревнования по программированию 2.0

Время на сервере: 23.04.2024 19:51:56 (i2).

Десктопная версия, переключиться на мобильную.

При поддержке