## Microsoft Interview Question for Software Engineer in Tests

Comment hidden because of low score. Click to expand.
2
of 2 vote

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

Comment hidden because of low score. Click to expand.
0

Thanks Rayden. So it means the buckets dont have to be sorted. i.e.
given input - aA1B23Cbc4
the output can be bcaABC2134... doesn't have to be abcABC1234 (in the latter case buckets are also sorted)

Comment hidden because of low score. Click to expand.
0
of 0 vote

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?

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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++;
}``````

Comment hidden because of low score. Click to expand.
0
of 2 vote

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++;

}

Comment hidden because of low score. Click to expand.
0

Comment hidden because of low score. Click to expand.
0

really appreciable :)

Comment hidden because of low score. Click to expand.
0

need add another constraint for loop while, or it will fail.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````/* 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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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++;
}

}
}

Comment hidden because of low score. Click to expand.
0

//small correction req.

while(i <=e) //required as not working in case of {0, 'A', 'c', 'a'

Comment hidden because of low score. Click to expand.
0

//small correction req.

while(i <=e) //required as not working in case of {0, 'A', 'c', 'a' }

Comment hidden because of low score. Click to expand.
0
of 0 vote

Dutch National Flag Algorithm

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.

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