Author |
Topic: A problem of microsoft (Read 2295 times) |
|
bbskill
Newbie
Posts: 42
|
 |
A problem of microsoft
« on: Dec 10th, 2007, 7:12pm » |
 Quote  Modify
|
Assume you have a string that only contains capitals , blanks and lowercases, write a program to rearrange the string, letting all the lowercases be located at the beginning of the string, and the capitals be located at the last of the string, te blanks be located in the middle.
Note that the original sequence of capitals and lowercase could not be change?
For example, the original string is "aA b Dc Eef"
the result should be "abcef ADE"
Could any one raise a solution in O(n) time and O(1) spaces?
|
| « Last Edit: Dec 10th, 2007, 8:15pm by bbskill » |
 IP Logged |
|
|
|
GowriKumar
Junior Member
 
Gender: 
Posts: 55
|
|
Re: A problem of microsoft
« Reply #1 on: Dec 10th, 2007, 8:47pm » |
Quote Modify
|
This is called "Dutch National Flag" problem.
Have two pointers, one pointing to the beginning of the array (say begin) and the other pointing to the end of the array (say end).
Have a third pointer, for traversing the array.
- If you find a capital letter then move it to location where begin is pointing to and increment begin.
- If you find a small letter then move it to end and decrement end
- If it is space ignore.
Regards,
Gowri Kumar
|
|
IP Logged |
www.gowrikumar.com
|
|
|
GowriKumar
Junior Member
Gender:
Posts: 55
|
|
Re: A problem of microsoft
« Reply #2 on: Dec 10th, 2007, 8:55pm » |
Quote Modify
|
Here is the code. Replace the
- case 0 with islower
- case 1 with isspace and
- case 2 with isupper
Code:
<snip>
#include <stdio.h>
#define SIZEOF(arr) (sizeof(arr)/sizeof(arr[0]))
void swap(int* a,int* b)
{
int t;
t = *a;
*a = *b;
*b = t;
}
void printarr(int arr[],int len)
{
int i;
for(i=0;i<len;i++)
printf("%d ",arr[i]);
printf("\n");
}
int main()
{
int arr[] = {0,1,1,2,1,1,0,2,1,0,2,1,1,1};
int len = SIZEOF(arr);
int beg=0,end=len-1,index=0;
printf("Before : ");
printarr(arr,len);
while(index <= end)
{
switch(arr[index])
{
case 0:
swap(&arr[beg],&arr[index]);
beg++;
break;
case 1:
/* do nothing */
break;
case 2:
swap(&arr[index],&arr[end]);
end--;
}
index++;
}
printf("After : ");
printarr(arr,len);
return 0;
}
</snip>
|
|
|
|
IP Logged |
www.gowrikumar.com
|
|
|
bbskill
Newbie
Posts: 42
|
|
Re: A problem of microsoft
« Reply #3 on: Dec 11th, 2007, 1:42am » |
Quote Modify
|
on Dec 10th, 2007, 8:47pm, gowrikumar wrote:This is called "Dutch National Flag" problem.
Have two pointers, one pointing to the beginning of the array (say begin) and the other pointing to the end of the array (say end).
Have a third pointer, for traversing the array.
- If you find a capital letter then move it to location where begin is pointing to and increment begin.
- If you find a small letter then move it to end and decrement end
- If it is space ignore.
Regards,
Gowri Kumar |
|
I think that is incorrect and it doesn't reserve the original sequence of uppercase and lowercase.
For example, the original string is "aA F"
beg = 0, end = 3, index = 0
the string After each step become
"aA F" beg = 1, end = 3, index = 1
"aF A" beg = 1, end = 2, index = 2
"aF A" beg = 1, end = 2, index = 3
"aFA " beg = 1, end = 1, index = 4
|
| « Last Edit: Dec 11th, 2007, 1:51am by bbskill » |
IP Logged |
|
|
|
ThePriest
Newbie
Gender:
Posts: 16
|
|
Re: A problem of microsoft
« Reply #4 on: Dec 11th, 2007, 1:57am » |
Quote Modify
|
Given the constraints of constant space and O(n) time, i doubt that it can be done. Because preserving the order of alphabets and shifting within the array (to one side) will require O(n^2) in any case (consider a typical bubble sort kind of implementation where the upper case letters moves to one side of the array and the lower case to the other side). Either constraint must be changed. i.e if you want O(n), it cannot be in-place (no constant space) and vice-versa.
Correct me if i am wrong.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: A problem of microsoft
« Reply #5 on: Dec 11th, 2007, 5:37am » |
Quote Modify
|
We can easily shift the blanks to one side in one pass (since they're not distinguishable). This would give us some room to do the separation of the upper- and lowercase letters. Of course, when there aren't any blanks, this won't help us one bit.
So really that's the problem we need to solve (if there are blanks, we can shift them to the middle at the end just as easily).
I'm not sure yet whether O(N) can be attained, but I am fairly sure we can do better than O(N2). In particular O(n log n) should be possible.
|
| « Last Edit: Dec 11th, 2007, 5:41am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: A problem of microsoft
« Reply #6 on: Dec 11th, 2007, 6:39am » |
Quote Modify
|
If there is a O(n) solution, there must be a O(n) solution in the special case where there are no blanks.
And separating 2 colors with constant space looks difficult to me.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: A problem of microsoft
« Reply #7 on: Dec 11th, 2007, 7:22am » |
Quote Modify
|
on Dec 11th, 2007, 6:39am, Grimbal wrote:| And separating 2 colors with constant space looks difficult to me. |
|
At least if you also need to keep the order inside the two classes the same..
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: A problem of microsoft
« Reply #8 on: Dec 11th, 2007, 8:04am » |
Quote Modify
|
Ah... yes, that's what I meant.
|
|
IP Logged |
|
|
|
wanderer
Newbie
Posts: 34
|
|
Re: A problem of microsoft
« Reply #9 on: Dec 11th, 2007, 12:06pm » |
Quote Modify
|
Well...one way to do it in O(n) would be to hash the string, say using the Rabin Karp hash where we would hash the string to a long integer, and then reconstruct the string by overwriting on the previous string. But I agree that this kind of method would be heavily limited by the range of the integer type we are hashing to..
|
|
IP Logged |
|
|
|
GowriKumar
Junior Member
Gender:
Posts: 55
|
|
Re: A problem of microsoft
« Reply #10 on: Dec 11th, 2007, 5:54pm » |
Quote Modify
|
on Dec 11th, 2007, 1:42am, bbskill wrote:
I think that is incorrect and it doesn't reserve the original sequence of uppercase and lowercase.
|
|
My bad.
I didn't notice that condition of preserving the sequence. Thanks for pointing it out.
Regards,
Gowri Kumar
|
|
IP Logged |
www.gowrikumar.com
|
|
|
softhacker
Newbie
 
Gender:
Posts: 13
|
|
Re: A problem of microsoft
« Reply #11 on: Dec 17th, 2007, 8:50am » |
Quote Modify
|
on Dec 10th, 2007, 8:55pm, gowrikumar wrote:Here is the code. Replace the
- case 0 with islower
- case 1 with isspace and
- case 2 with isupper
|
|
int arr[]={0,2,1,0,1,2,0,1,2,0,0}
Run ur program for above test case
u will get wrong output ( 0 0 0 0 1 0 1 1 2 2 2 )
but I couldn't get flaw in the program. 
|
|
IP Logged |
|
|
|
xpectronum
Newbie
Gender:
Posts: 8
|
|
Re: A problem of microsoft
« Reply #12 on: Mar 10th, 2008, 9:38pm » |
Quote Modify
|
if i assume the string to be a linked list, with each node having a character each,i can keep freeing the current node to create a new node,which i insert in the proper position. Will that be called O(1) space?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: A problem of microsoft
« Reply #13 on: Mar 11th, 2008, 1:39am » |
Quote Modify
|
on Mar 10th, 2008, 9:38pm, xpectronum wrote:| if i assume the string to be a linked list, with each node having a character each,i can keep freeing the current node to create a new node,which i insert in the proper position. Will that be called O(1) space? |
|
Yes, that would be O(1) space.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: A problem of microsoft
« Reply #14 on: Mar 11th, 2008, 3:00am » |
Quote Modify
|
on Mar 11th, 2008, 1:39am, towr wrote:
Yes, that would be O(1) space.
|
|
I don't thing so. The problem will be forulated as a link list problem not as a string problem...
|
| « Last Edit: Mar 11th, 2008, 3:00am by Hippo » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: A problem of microsoft
« Reply #15 on: Mar 11th, 2008, 3:48am » |
Quote Modify
|
on Mar 11th, 2008, 3:00am, Hippo wrote:| I don't thing so. The problem will be forulated as a link list problem not as a string problem... |
|
He made the specific assumption that the string would be a linked list; under that assumption, he doesn't use extra space the way he treats it.
Whether that assumption is warranted or not is another issue.
In some programming language you don't have arrays (or other direct access datastructure equivalents), and so it might be entirely plausible to assume strings are linked lists (or equivalent).
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: A problem of microsoft
« Reply #16 on: Mar 11th, 2008, 10:53am » |
Quote Modify
|
OK, his solution is OK, but it does not help us in solving our problem.
This is the problem with O(1) space requirements ... it highly depends on data format.
|
|
IP Logged |
|
|
|
nothing_
Newbie
Posts: 22
|
|
Re: A problem of microsoft
« Reply #17 on: Mar 12th, 2008, 4:40pm » |
Quote Modify
|
O(n) solution in one pass ...
Logic: Keep three pointers , one for lowercase, one for uppercase and one for the space....
Code:
#include<iostream>
#include<string>
using namespace std;
int main()
{
string x = "aABC fddefgh";
int i=0;
int j=x.size()-1;
int k;
while(i<=j)
{
while(i<x.size() && x[i]>='a' && x[i]<='z')
i++;
while(j>=0 && x[j]>='A' && x[j]<='Z')
j--;
for(k=i+1;k<j;k++)
if(x[k]!=' ')
break;
if(x[i]==' ' && x[j]==' ')
{
if(x[k]>='a' && x[k]<='z')
swap(x[k],x[i]);
else
swap(x[k],x[j]);
}
else if(i<j)
swap(x[i],x[j]);
else if(k==j)
break;
}
cout<<x<<endl;
}
|
| « Last Edit: Mar 12th, 2008, 4:42pm by nothing_ » |
IP Logged |
|
|
|
m_aakash
Junior Member
Posts: 96
|
|
Re: A problem of microsoft
« Reply #18 on: Mar 13th, 2008, 10:45am » |
Quote Modify
|
on Mar 12th, 2008, 4:40pm, nothing_ wrote:O(n) solution in one pass ...
Logic: Keep three pointers , one for lowercase, one for uppercase and one for the space....
Code:
#include<iostream>
#include<string>
using namespace std;
int main()
{
string x = "aABC fddefgh";
int i=0;
int j=x.size()-1;
int k;
while(i<=j)
{
while(i<x.size() && x[i]>='a' && x[i]<='z')
i++;
while(j>=0 && x[j]>='A' && x[j]<='Z')
j--;
for(k=i+1;k<j;k++)
if(x[k]!=' ')
break;
if(x[i]==' ' && x[j]==' ')
{
if(x[k]>='a' && x[k]<='z')
swap(x[k],x[i]);
else
swap(x[k],x[j]);
}
else if(i<j)
swap(x[i],x[j]);
else if(k==j)
break;
}
cout<<x<<endl;
}
|
|
Is your code keeping the relative order of characters?
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print