Microsoft student Interview Question
StudentsCountry: India
step1:-taake two arrey a[],b[],k=0,m=0;
step2:-traverse the string , if isdigit() than a[k++]=s[i++];
else b[m++]=s[i++];
step3:- m=0;k=0;
for(int i=0;i<s.lenght();i++)
{ if(i%2==0)
s[i]=b[m++];
else
s[i]=a[m++];
}
step 4:- print s;
We can do it in a much simpler way I guess.. Take a look at below piece of code.
i=0;
for(int k-0;k<strlen(str);k++)
{
if(isChar(a[k]) {
continue;
}
if(isChar(a[i])) {
print a[i] a[k];
}
i++;
}
Edge cases(need requirements for below cases).
1. What if number of chars and number of numbers are not same in given string
2. What if no chars or no nums(above algo does not display anything)
3. What if numbers precede(should the output be same)
Above algo works if string starts with char and need minor modifications if above requirements are provided.
Java code.
Complexity: O(n) moves. Space O(1).
Assumptions: equal number of chars and digits and we should arrange (char||digit)*
Executions:
input: abcd1234ef56 modified string: a1b2c3d4e5f6
input: a1234bcdef56gh78 modified string: a1b2c3d4e5f6g7h8
input: a1 modified string: a1
input: a1234bcd modified string: a1b2c3d4
input: abcd1234 modified string: a1b2c3d4
public class OddEven {
public static void main(String[] args){
OddEven oe = new OddEven();
oe.classify("abcd1234ef56");
oe.classify("a1234bcdef56gh78");
oe.classify("a1");
oe.classify("a1234bcd");
oe.classify("abcd1234");
}
private void classify(String string) {
//Each position is touched at most once hence O(length of array)
int nn=0,nc=0,mx=-1;
char[] a = string.toCharArray();
int state = 0 ; //expect char
for(int i=0;i<string.length();i++){
if(state == 0){
if(ischar(a[i])){
if( i> mx){
nc++;
mx = Math.max(i, mx);
}
state = 1;
}
else{//expected char but got a number
boolean found = false;
int j=i+1;
while(!found){
if(ischar(a[j])){
found=true;
break;
}
j++;
}
if(!found || j >= string.length()){
//done with processing
return;
}
char t=a[i];
a[i]=a[j]; nc++; mx = Math.max(j, mx);
a[j]='-';
while(true){
char tt;
if(ischar(t)){
tt = a[nc*2]; mx = Math.max(nc*2, mx);
a[nc*2] = t; nc++;
t=tt;
}
else{
tt = a[nn*2+1]; mx = Math.max(nn*2+1, mx);
a[nn*2+1] = t;
nn++;
t=tt;
}
if(t=='-'){
break;
}
}
}
state=1;
}
else if(state == 1){
if(isdigit(a[i])){
if(i> mx){
nn++;
mx = Math.max(i, mx);
}
state = 0;
}
else{//expected number but got character
boolean found = false;
int j=i+1;
while(!found){
if(isdigit(a[j])){
found=true;
break;
}
j++;
}
if(!found || j >= string.length()){
//done with processing
return;
}
char t=a[i];
a[i]=a[j]; nn++; mx = Math.max(j, mx);
a[j]='-';
while(true){
char tt;
if(ischar(t)){
tt = a[nc*2]; mx = Math.max(nc*2, mx);
a[nc*2] = t; nc++;
t=tt;
}
else{
tt = a[nn*2+1]; mx = Math.max(nn*2+1, mx);
a[nn*2+1] = t;
nn++;
t=tt;
}
if(t=='-'){
break;
}
}
}
state=0;
}
}
System.out.print("input: " + string + " modified string: " ); System.out.println(a);
}
private static boolean isdigit(char c) {
return ( c>='0' && c<='9');
}
private static boolean ischar(char c) {
return ( c>='a' && c<='z');
}
}
We can map given string to a 4*4 matrix and problem will be solved by just printing the matrix in "Column major".
//pass a string to this function it will work
//C++
#include<string>
void arrange(string str)
{
int flag=0;
string::iterator it_c,it_n;
it_c=str.begin();
it_n=str.begin();
while( ( (int)*it_n >=97 ) && ( (int)*it_n <=122 ) )
{
it_n++;
if(it_n == str.end())
{
break;
}
}
while( ( (int)*it_c >=48 ) && ( (int)*it_c <=57 ) )
{
it_c++;
if(it_c == str.end())
{
break;
}
}
while ( ( it_c != str.end() ) || ( it_n != str.end() ) )
{
if ( (flag == 0) || ( it_n==str.end() ) )
{
if (it_c != str.end())
{
cout<<*it_c;
it_c++;
while( ( (int)*it_c >=48 ) && ( (int)*it_c <=57 ) )
{
it_c++;
}
}
flag=1;
}
if ( (flag == 1) || ( it_c==str.end() ) )
{
if (it_n != str.end())
{
cout<<*it_n;
it_n++;
while( ( (int)*it_n >=97 ) && ( (int)*it_n <=122 ) )
{
it_n++;
}
}
flag=0;
}
}
}
int main()
{
char str[] = "abcd1234defgh8965";
char *out;
int i;
int n = strlen(str);
int int_c = 1;
int char_c = 0;
out = malloc(sizeof(char) * (n+1));
for(i = 0; i < n; i++)
{
if((str[i]-'0') >= 0 && (str[i] - '0') <= 9)
{
*(out + int_c) = str[i];
int_c += 2;
}
else if((str[i] - 0) >= 65 && (str[i] - 0) <= 122)
{
*(out + char_c) = str[i];
char_c += 2;
}
}
*(out+n) = '\0';
printf("out:..%s\n",out);
}
- bluesky October 02, 2012