Directi Interview Question
SDE-2sCountry: India
Interview Type: In-Person
#include <iostream>
using namespace std;
int main()
{
int T,n,l;
cin>>T;
for(int t=0;t<T;t++ )
{
cin>>n>>l;
int a[n];
for(int i=0;i<n;i++)
cin>>a[i];
for(int i=0;i<n;i++)
{
int pos=i;
for(int j=i+1;j<n;j++)
{
if(j-i>l)
break;
if(a[pos]>=a[j])
pos=j;
}
if(i!=pos)
{
for(int k=pos;k>i;k--)
swap(a[k],a[k-1]);
l-=(pos-i);
}
}
for(int i=0;i<n;i++)
cout<<a[i]<<" ";
cout<<"\n";
}
return 0;
}
#include<iostream>
using namespace std;
void quickSort(int a[],int b[],int start, int end)
{
if(start<=end)
{
int i=start,j=end;
int mid=(start+end)/2 ;
int pivot = a[mid];
while(i<=j)
{
while(a[i]<pivot)
i++;
while(a[j]>pivot)
j--;
if(i<=j)
{
swap(a[i],a[j]);
swap(b[i],b[j]);
i++;
j--;
}
}
quickSort(a,b,start,j);
quickSort(a,b,i,end);
}
}
void function(int a[], int size, int k)
{
int b[size];
for(int i=0;i<size;i++)
b[i]=i;
quickSort(a,b,0,size-1);
int counter=0;
for(int j=0; j<size; j++)
{
if(k>=(b[j]-counter))
{
k-=(b[j]+counter);
swap(a[j],a[counter]);
swap(b[j],b[counter]);
counter++;
}
}
quickSort(b,a,counter,size-1);
for(int i=0;i<size;i++)
cout<<a[i]<<" ";
}
int main()
{
int y;
cin>>y;
while(y)
{
int x,k;
cin>>x>>k;
int a[x];
for(int i=0;i<x;i++)
{
cin>>a[i];
}
function(a,x,k);
y--;
}
}
- Anonymous August 24, 2014