CareerCup

Just another version of Dutch flag problem. Look it up on google.

Couple of questions,
when you say numbers that means digits from 0-9? or real numbers? because real numbers cannot be sorted in O(n) without any constraints.
Are there duplicates?
An array something like, a 1 b B A 11 a . is this allowed?

The numbers are from 0-9 and yes the array not necessarily be in sorted order.
Will look up the dutch flag problem.

using only one variable i don't think anyone can do it. For iteration to the length of string we need atleast one variable. so here is my thinking.

a = input string
s = 0;
e = n-1;
i = 0;
while(i<n){
if 'A' <= a[i] <= 'Z' ans i > s then
swap(a[s], a[i])                //swap using third variable
s++;
else if 'a'<=a[i]<='z' and i < e then
swap(a[i], a[e]);
e--;
else i++;
}

int l = a.length();
int s = 0;
int e = l-1;
int i =0;
while(i<l){
if('A' <= a[i] && a[i] <= 'Z' && i>s){
swap(a[i], a[s]);
s++;
}else if('a' <= a[i] && a[i] <= 'z' and i<e){
swap(a[i], a[e]);
e--;
}else i++;

}

/* A generic code implementing Dutch Flag Problem solution. Let me know if there are any bugs. Thanks*/
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
/*!
 * \fn void DFPBuckets(vector<T> &a, T bktBound1, T bktBound2)
 * \brief Rearrange the elements of an array into buckets 
 * \param  a   A vector containing the elements that need to be 
 * \param bktBound1 the value that separates lower buckets from mid bucket
 * \param bktBound2 the value that separates mid buckets from higher bucket
*/
template<typename T>
void DFPBuckets(vector<T> &a, T bktBound1, T bktBound2){
	int sz = a.size();
	int low=0,mid=0,high=sz-1;
	while(mid<=high){
		if(bktBound1 >= a[mid]){ //case 1st bucket
			swap(a[low],a[mid]);//cout<<"swap: "<< a[low] << " , " << a[mid]<<endl;
			++low; ++mid;
		}else if(bktBound2<=a[mid]){ //case 3rd bucket
			while(high>mid && a[high]>bktBound2)
				--high;
			swap(a[mid],a[high]);//cout<<"swap: "<<a[mid]<<" , "<<a[high]<<endl;
			--high;
		}else//case 2nd bucket
			++mid;	
	}
}
/*! 
 * \fn printVector(vector<T> &a);
 * \brief print contents of a vector
 */
template<typename T>
void printVector(vector<T> &a){
	int sz = a.size();
	for(int i=0;i<sz;++i)cout<<", "<<a[i];
}
int main(){
	vector<char> arrayC {'A','b','3','C','1','d','c','4','2','B','a'};
	vector<double> arrayF {11.2, 0.1, 15.4, 0.0, 3.2, 2.8, 6.2};
	cout<<"Input: ";printVector(arrayC);cout<<"\t\t\t\t";
	DFPBuckets(arrayC, '9','Z');
	cout<<"Output: ";printVector(arrayC);cout<<endl;
	cout<<"Input: ";printVector(arrayF);cout<<"\t\t\t";
	DFPBuckets(arrayF, 5.0,10.0);
	cout<<"Output: ";printVector(arrayF);cout<<endl;
}

If there is no constraint in memory than, we can do it in O(n) using three queue.
While traversing the array, check whether it is number or upper or lower case alphabet and enqueue it into corresponding queue.
When done. dequeue all the queue one by one.
space O(n).

void swap(char *a,int i,int j )
{
char temp= a[i];
a[i]=a[j];
a[j]=temp;
}

void move()
{
int s = 0,i = 0;

int e = size - 1;
while(i < e)
{
if(str[i]>= 'a' && str[i]<= 'z' && i>=s )
{swap(str,i++,s++); //i should be incremented for o(n) complexity
}
else if(str[i]>='A' && str[i] <='Z' && i < e)
{swap(str,i,e--);
}
else
{i++;
}

}
}

Dutch National Flag Algorithm