CareerCup

i/p str: a 1 b 2 c 3 d 4 e 5
index: 0 1 2 3 4 5 6 7 8 9

o/p str: a b c d e 1 2 3 4 5
index: 0 1 2 3 4 5 6 7 8 9
here string length is L = 10/2 = 5
numbers are moving from i/p location to o/p location
1 to 5 => L+1/2
3 to 6 => L+3/2
5 to 7 => L+5/2
7 to 8 => L+7/2
and characters are moving from i/p location to o/p location
2 to 1 => 2/2
4 to 2 => 4/2
6 to 3 => 6/2
8 to 4 => 8/2
now traverse the string array and move the data according to above logic... if the location is odd then move to L+i/2 and if the location is even then move it to i/2 location

initially
1st location is 1 so move it to 5+1/2 = 5th location ----- a[5] = 1
5th location is 3 so move it to 5+5/2 = 7th location ------a[7] = 3
7th location is 4 so move it to 5+7/2 = 8th location ----- a[8] = 4
8th location is 'e' so move it to 8/2 = 4th location ----- a[4] = 'e'
4th location is 'c' so move it to 4/2 = 2nd location ----- a[2] = 'c'
2nd location is 'b' so move it to 2/2 = 1st location ----- a[1] = 'b'
at this point we started with 1st location and we reached again to 1st location...
now the array looks like
array: a b c 2 e 1 d 3 4 5
index: 0 1 2 3 4 5 6 7 8 9

now traverse the array till L-1 location and check there is any number is still present, if no we are done... else there is a number then continue the above operation...
here L-1 is 4 but at location 3 there is number '2' so move it to L+3/2 => 5+3/2 = 6 ----- a[6] = 2
6th location is 'd' so move it to 6/2 = 3rd location ----- a[3] = 'd'
final array is {a b c d e 1 2 3 4 5}
time complexity O(n) and space complexity O(1)

#include "stdafx.h"
#include <string.h>

size_t right_pos(char* p, size_t arr_len)
{
  return ('1' <= *p && '9' >= *p) ? (arr_len >> 1) + (*p - '1') : (*p - 'a');
}

void swap(char* arr, size_t i, size_t j)
{
  char tmp = arr[ i ];
  arr[ i ] = arr[ j ];
  arr[ j ] = tmp;
}

int sorter(char* arr, size_t i, size_t arr_len)
{
  size_t pos = right_pos(arr + i, arr_len);
  if (i != pos) swap(arr, i, pos);
  else return ++i;

  pos = right_pos(arr + i, arr_len);
  if (pos != right_pos(arr + pos, arr_len))
  return sorter(arr, pos, arr_len) + 1;
}

int _tmain(int argc, _TCHAR* argv[])
{
  char arr[] = "a1b2c3d4e5f6g7";

  for (size_t i = 0; i < strlen(arr); )
    i = sorter(arr, i, strlen(arr));

  return 0;
}

void spearate(input[])
{
	start = input[0];
	end = input[input.size() - 1];
  	while(start < end)
  	{
    		if(isNumber(input[start])) {
    			while(end > start && !isAlphabet(input[end])) {
    				end--;
    			}
    			if(end == start)
    				break;
    			swap(input[], start, end);
    			end--;
    		}
    		else
    		{
    			//	assume its an alphabet.
    			start++;
    		}
         
    
  	} 

}

Although we have a nested loop this runs in O(n). Inner loop and outer loop always visit mutually exclusive elements.

This is wrong.. It wont give {abcd1234} as result. I guess thats the reason Loler is LOLing..

for each character in the string, we actually can calculate its expected position from it.
so we traverse the string, if we find a character that is not supposed to be in i, we will swap it to its expected position, we keep on doing this until we get what should be in i.

def swap_char(str):
	array = [c for c in str]
	l = len(array)
	sh = l // 2
	for i in range(1, l):
		while True:
			if array[i].isdigit():
				expected_i = int(array[i]) - 1 + sh
			else:
				expected_i = ord(array[i]) - ord('a')
			if i == expected_i:
				break
			array[i], array[expected_i] = array[expected_i], array[i]
	return "".join(array)

No extra memory and o(n)


i=0; //alphabet index
j = 0; //numeric index
count = 0; //number of numerics to swap

while( i <= x.length())
{
if(alphabet(x[i])
{
if(j != i)
{
//Swap
temp = x[i];
x[i] = x[j];
x[j] = x[i];

//Decrease count due to swap
if(count != 0)
count--;

//Keep swapping as more numerics to swap
if(count > 0)
{
i = j
j = j - 1;
continue;
}
j++
}
i++;
}
else
{
if(j != i)
{
j = i;
count++;
}
i++;
}
}

Common guys, simple as

#include <stdio.h>
#include <string.h>
#include <ctype.h>

#define BIGGEST_ALPHA 122

char* theStr = "a1b2c3d4";

int main(int argc, char** argv)
{
char str[10];
strcpy(str, theStr);

int curPos = 0;
for(int i = 0; i < strlen(str) - 1; i++)
{
if((isdigit(str[i]) ? str[i] + BIGGEST_ALPHA : str[i]) >
(isdigit(str[i+1]) ? str[i+1] + BIGGEST_ALPHA : str[i+1]))
{
char temp = str[i+1];
str[i+1] = str[i];
str[i] = temp;
i = 0;

}
printf("%s\n", str);

}

return 0;
}

bool isInteger(char c)
{
	return c >= '0' && c <= '9';
}
void swap(char &a, char &b)
{
	char tmp = a;
	a = b;
	b = tmp;
}
void Arrangement(char arr[], int size)
{
	int i, j;
	for (i = 0; i < size / 2; ++i, j = i)
	{
		if (isInteger(arr[i]))
		{
			while (isInteger(arr[++j])) swap(arr[i], arr[j]);
			swap(arr[i], arr[j]);
		}
	}
}
void main()
{
	const int size = 10;
	char arr[size] = {'a', '1', 'b', '2', 'c', '3', 'd', '4', 'e', '5'};
	Arrangement(arr, size);
}

I think the required optimality can only be achieved if the array is implemented as Linked List.

#include<iostream>
#include<string>

void temp();

void temp()
{
    string str1;
    string str2;
    string arr[10]={"a","1","b","2","c","3","d","4","e","5"};
    string result;
    
    for(int ctr=0;ctr<10;ctr+=2)
    {
        str1+=arr[ctr];
        str2+=arr[ctr+1];
    }
    result=str1+str2;
    cout<<result;
}

int main()
{
temp();
return 1;
}

for i = 0 to N
    while a[i] not correct
        swap a[i] with the correct position

This is O(N) time as each position only needs maximum 1 swap. And each swap bring at least 1 incorrect position to a correct one.

#include<iostream>
#include<string.h>
using namespace std;
int main()
{
    char arr[]={"a1b2c3d4"};
    int n=strlen(arr);
    cout<<"Old array : "<<arr<<endl;
    int i,j,k;
    k=1;
    while(k<char(arr[n-1]))
    {
        i=k;
        j=n-1-k;
        while(i<j)
        {
            swap(arr[i],arr[i+1]);
            i+=2;
        }
        k++;
    }
    cout<<"New array : "<<arr<<endl;
    return 0;
}

I just have a question. What about z26? So in this case, there is 2 numbers at the end of it...

public static void swaps(char[] str){
		for(int i=1,j=str.length-2;i<j;i++,j--){
			for(int k=i;k<j;k+=2){
				char temp = str[k]; 
				str[k] = str[k+1]; 
				str[k+1] = temp; 
			}
		}
	}

#include<stdio.h>
#include<string.h>
rearrange(char *str, int len)
{
int i;
for(i=0;i<=len;i++)
{
if(str[i]>=97)
printf("%c",str[i]);

}
for(i=0;i<=len;i++)
{
if(str[i]<65)
printf("%c",str[i]);
}
}
int main()
{
char str[50];
printf("Enter string\n");
gets(str);
int l = strlen(str)-1;
rearrange(str,l);
}

#include<stdio.h>
#include<string.h>
rearrange(char *str, int len)
{
    int i;
    for(i=0;i<=len;i++)
    {
        if(str[i]>=97)
            printf("%c",str[i]);

    }
    for(i=0;i<=len;i++)
    {
        if(str[i]<65)
            printf("%c",str[i]);
    }
}
int main()
{
    char str[50];
    printf("Enter string\n");
    gets(str);
    int l = strlen(str)-1;
    rearrange(str,l);
}

#include<stdio.h>
#include<string.h>
rearrange(char *str, int len)
{
    int i;
    for(i=0;i<=len;i++)
    {
        if(str[i]>=97)
            printf("%c",str[i]);

    }
    for(i=0;i<=len;i++)
    {
        if(str[i]<65)
            printf("%c",str[i]);
    }
}
int main()
{
    char str[50];
    printf("Enter string\n");
    gets(str);
    int l = strlen(str)-1;
    rearrange(str,l);
}

}

#include<stdio.h>
#include<string.h>
rearrange(char *str, int len)
{
    int i;
    for(i=0;i<=len;i++)
    {
        if(str[i]>=97)
            printf("%c",str[i]);

    }
    for(i=0;i<=len;i++)
    {
        if(str[i]<65)
            printf("%c",str[i]);
    }
}
int main()
{
    char str[50];
    printf("Enter string\n");
    gets(str);
    int l = strlen(str)-1;
    rearrange(str,l);
}

shifting of array would do???

for i=0...n/2-1
tmp=array[i]
if tmp is a letter
continue // nothing to do, we have a letter already!
index=i
do
// we have the wrong think at index! Where is it supposed to be?
if (index is even) // the wrong thing is a letter
index=index/2
else // the wrong thing is a number
index=n/2+index/2
// we found where temp should go! Lets put it there!
// But we keep what was already there and look for its place next iteration
tmp2=array[index]
array[index]=tmp
tmp=tmp2
while index!=i


It might look like O(n2) but it isnt..Each element is being moved only once..

for i=0...n/2-1
tmp=array[i]
if tmp is a letter
continue // nothing to do, we have a letter already!
index=i
do
// we have the wrong think at index! Where is it supposed to be?
if (index is even) // the wrong thing is a letter
index=index/2
else // the wrong thing is a number
index=n/2+index/2
// we found where temp should go! Lets put it there!
// But we keep what was already there and look for its place next iteration
tmp2=array[index]
array[index]=tmp
tmp=tmp2
while index!=i

this looks like o(n2) but every element is moved only onnce. So, it is o(n).

This is like the Dutch National Flag problem