CareerCup

Iterative Program logic explaination of function: alternateLettersAndNums()

initial: 1 2 3 4 5 6 7 8 | a b c d e f g h
				  
step 1a: 1 [2] 3 [4] 5 [6] 7 [8] | [a] b [c] d [e] f [g] h
leaving 1 element from start, elements selected from step 1a in [] are swapped respectively with elements after the bar: '|', resulting in:
Step 1b: 1 [a] 3 [c] 5 [e] 7 [g] | [2] b [4] d [6] f [8] h

Step 2a: 1 [a] {3 [c]} 5 [e] {7 [g]} | {[2] b} [4] d {[6] f} [8] h
leaving 2 element from start, elements in group of 2 with in {} are swapped with elements with in {} after bar, resulting in:
step 2b: 1 [a] [2] b 5 [e] [6] f | 3 [c] [4] d 7 [g] [8] h

Step 3a: 1 [a] [2] b {5 [e] [6] f} | {3 [c] [4]} d 7 [g] [8] h
leaving 4 element from start, elements in group of 4 with in {} are swapped with elements with in {} after bar, resulting in:
Step 3b: 1 [a] [2] b {3 [c] [4] d} | {5 [e] [6] f} 7 [g] [8] h

Final o/p: 1 a 2 b 3 c 4 d 5 e 6 f 7 g 8 h
/////////////////////////////////////////
Program:
/*
Constraints met:
Space complexity: In-Place, O(1)
Time Complexity: O(N): 
*/

#include<stdio.h>
#include<math.h>

static void swap(char a[], int s, int e, int len)
{
	int i=s, j=e, temp=0;
	for(i=s; (i-s+1<=len)&&(i); i++, j++)
	{
		temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}
}

void alternateLettersAndNums(char arr[], int len)
{
	int jumps, i, k, no, ch, temp;
	int c = (len + 1)/2;

	for(jumps=0; (i = (int)pow((double)2, jumps))<(int)len/2; jumps++)
	{
		i = (int)pow((double)2, jumps);
		for(k=0; k < c; k+=i*2)
		{
			no = i+k;
			ch = c+k;
			swap(arr, no, ch, i);
		}
	}
	return;
}

void alternateLettersAndNumsDriver()
{
	int i;
	char A[] = {'1', '2', '3', '4', '5', '6', '7', '8', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H'};
	
	printf("\nGiven array:\n");
	for(i=0; i<sizeof(A)/sizeof(char); i++)
		printf("%c  ", A[i]);
	
	alternateLettersAndNums(A, sizeof(A)/sizeof(char));
	
	printf("\nAfter alternating:\n");
	for(i=0; i<sizeof(A)/sizeof(char); i++)
		printf("%c  ", A[i]);
	return;
}
/////////////////////////////////////////////

/*Recursive solution*/
void Alter(char *arr, int mid, int len)
{
	if(!arr || (len == 0) || (mid == 0))
		return;

	int tmp = arr[mid];
	int k = mid;
	
	Alter(arr, --k, len);

	arr[mid + k] = arr[len/2 + k];
	arr[mid + k + 1] = tmp;

	return;
}

void AlterNumCharArray()
{
	char arr[10] = {'1', '2', '3', '4', '5', 'a', 'b', 'c', 'd', 'e'};
	int mid, len;

	len = 10;
	mid = len/2;
	
	printf("\n Array before Alternation = ");
	for(int i = 0; i < len; i++)
		printf("%c ", arr[i]);

	Alter(arr, mid-1, len);
	
	printf("\n Array after Alternation  = ");
	for(int i = 0; i < len; i++)
		printf("%c ", arr[i]);

	return;

}

o(n) is impossible. Did you mean O(n)?

And are you just posting a puzzle or was this really asked in an interview? (with the O(n) time and O(1) space restriction).

python

def inorder(a):
	N = len(a)
	startpos = 1
	cpos = startpos
	curelem = a[cpos]
	while True:
		npos = 0
		if cpos < N/2:
			npos = cpos * 2
		else:
			npos = (cpos - N/2)*2 + 1

		tmp = a[npos]
		a[npos] = curelem
		cpos = npos
		
		if cpos == startpos:			
			cpos += 2
			if cpos > N /2:
				break
			startpos = cpos
			tmp = a[cpos]

		curelem = tmp

// From www DOT ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs;action=display;num=1094241218
   
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
 
  
void Inshuffle(int *A, int N);
void follow_cycle(int *A, int N, int seed);
void cyclic_shift(int *A, int size, int distance);
void reverse(int *A, int size);
int Inverseof2(int M);
  
   
/***************************
Main Insuffle Algorithm.
Shuffle a1 a2 ..an b1 b2 ...bn
to
b1 a1 b2 a2 .... bn an
 
Parameters: A = the array
N = 2n, size of the array.
 
The permutation is given by
i -> 2i mod (N + 1)
 
We shuffle the array starting  
from A[1] for easier coding.
****************************/
   
void Inshuffle(int *initialA, int initialN)
{
    
      int m =1;
      int i;
      int power3 = 1;
      int seed = 1;
      int k = 1;
      int n = initialN/2; //N is assumed to be even.
      int *A = initialA;
      int N = initialN;
      
      while (N > 0){
    
              
            //Reset Values.
            m = 1;
            i = 0;
            power3 = 1;
            seed = 1;
            k = 1;
            n = N/2;
    
           //Step 1: Find an m such that 2m+1 is the largest power of 3 <= N+1
            for (i = 0; i <= N+1; i ++){
                  if (3*power3 > N+1){
                        break;
                  }
                  power3 = 3*power3;
            }
            k = i;
  
            m = (power3 - 1)/2;
           //Step 2: Cyclic Right Shift A[m+1, n+m] by m
            cyclic_shift(A+m+1,n,m);
 
           // Step3: Do inshuffle of A[1....2m] by 'following cycle'.
      
            for (i = 0 ; i < k; i ++)
            {
                  follow_cycle(A,2*m,seed);
                  seed = 3*seed;
            }
// Step 4: Recurse on A[2m+1...,2n]
    
//Could have made a recursive call here:
//Inshuffle(A+2*m,2*(n-m));
// But to make it O(1) space, convert tail recursion to iteration and put in a while loop.
      
            A = A + 2*m;
            N = 2*(n-m);
            // Reset Values.
      } //End of while loop.
}
    
/****************************************
Follow the cycle starting at seed.
For example: insuffle of 1 2 3 4 5 6 7 8
1 -> 2 -> 4 -> 8 -> 7 -> 5 -> 1
We follow this cycle in reverse order.
We look at 1. Save A[1].
Then look at what goes to 1, i.e 5 = 1*x
where x is inverse of 2.
Now fill A[1] with A[5].
Now look at what goes into A[5]. 7 = 5*x  
(x is inverse of 2)
So fill A[5] with A[7].
And so on.
*****************************************/
   
void follow_cycle(int *A, int N, int seed)
{
      int cur;
      int inverse2 = Inverseof2(N+1);
      int tmp;
      int prev;
 
      cur = (seed*inverse2 % (N+1));
      
      tmp = A[seed];
      prev = seed;
      while (cur != seed){
            A[prev] = A[cur];
            prev = cur;
            cur = (cur*inverse2 % (N+1));
      }
      A[prev] = tmp;
}
/*******************************
cyclic right shift an array by a given amount.
********************************/
void cyclic_shift(int *A, int sz, int k)
{
      reverse(A,sz - k);  
      reverse(A+sz-k,k);
      reverse(A,sz);
}
  
/******************************
reverse an array
*******************************/
void reverse(int *A, int sz)
{
      int i;
      int tmp;
      for (i = 0; i < sz/2; i++)
      {
            tmp = A[i];
            A[i] = A[sz-i-1];
            A[sz-i-1] = tmp;
      }
}
  
/***************************
 
find x such that 2x = 1 (mod M)
M is assumed to be an odd integer.
x = (M+1)/2
***************************/
int Inverseof2(int M)
{
      return (M+1)/2;
}
  
  
int main()
{
      int n;
      int i;
      int *A;
      printf("Enter the value of n, (total size of array = 2n): ");
      scanf("%d",&n);
      A = (int *)malloc((2*n+1)*sizeof(int));
      for (i = 0; i <= 2*n; i++){
            A[i] = i;
      }
      
      Inshuffle(A,2*n);
      
      printf("\n[");
      for (i = 1; i <= 2*n; i ++){
            printf(" %d",A[i]);
      }
      printf(" ]\n");
      free(A);
      return 1;
}

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

char* func(char arr[])
{
      int start,cpos,npos,i,N;
      char temp,cur_ele;
      N=strlen(arr);
      start=1;
      cpos=start;
      cur_ele=arr[cpos];
      for(i=1;i<N-1;i++)
      {
          npos=0;
          if(cpos<N/2)
             npos=cpos*2;
             
          else
             npos=(cpos-N/2)*2+1;
             
          temp=arr[npos];
          arr[npos]=cur_ele;
          cpos=npos;
          
          if(cpos==start)
          {
               cpos=cpos+2;
               start=cpos;
               temp=arr[cpos];               
          }                   
          cur_ele=temp;         
      }
      return arr;
}

int main()
{
    char str[20],*p;
    gets(str);
    p=func(str);
    puts(p);
}

#include<iostream>
using namespace std;

char *str(char *s);
char *str(char *s)
{
int i=0,j=0,k=0;
char tmp1=s[k],temp2=s[++k];
while(s[i]<97)
i++;
while(s[i]!='\0')
{
s[j++]=tmp1;
tmp1=temp2;
temp2=s[++k];
s[j++]=s[i++];

}
s[j]='\0';
return s;
}
int main()
{
char *s;
cin>> s;
cout<<str(s);
return 0;
}

#include<stdio.h>
#include<string.h>
int main()
{
        char str[10000];
        char str1[10000];
        int arr[10000];
        scanf("%s",str);
        int i,j=0,k,a,m=0;
        k=strlen(str);
        for(i=0;i<k;i++)
        {
                a=str[i]-'0';
                if(a>=0&&a<=9)
                {
                        arr[j]=a;
                        j=j+1;
                }
                else{
                str1[m]=str[i];
                m=m+1;
                }
        }
        for(i=0;i<j;i++)
        {
                printf("%d%c",arr[i],str1[i]);
        }
        return 0;
}

This might be work for all the cases...

#define SIZE 8

void exchange(char arr[], int x, int y)
{

int i =x;
while( x!=0 || y != SIZE-1)
{
if ( i<= y)
{
int t = arr[i];
arr[i] = arr[i+1];
arr[i+1] = t;
i = i+2;
}else{
i = x= x-1;
y = y+1;
}
}
}
int _tmain(int argc, _TCHAR* argv[])
{
char arr[8] = {'1','2','3','4','a','b','c','d'};
exchange(arr, (SIZE/2 -1), SIZE/2);
return 0;
}

Get the length of the string first (Say its n)... then divide the length by 2... use 2 variables i and j where i starts from 1 and j from n/2+1... Increment i by 2 every-time and j by 1 and swap them... that is it...

the question is not clear... do we just need to show the pattern on console,(since it is given output),or we have to modify the array as well..?? and the array should contain the pattern,please do post

None of the posted answers is right.

this is In-place matrix transposition problem, you can google it, its a famous algo.

void specialSort(char arr[], int len)
{
	if(!arr || len < 3)
		return;

	int i = (len-1)/2, j = i+1;

	while(i>0 && j<(len-1))
	{
		int m = i, n = j;
		while(m < n)
		{
			swap(arr[m],arr[m+1]);
			m+=2;
			if(m<n)
			{
				swap(arr[n],arr[n-1]);
				n-=2;
			}
		}
		i--;
		j++;
	}
}

void specialSort(char arr[], int len)
{
	if(!arr || len < 3)
		return;

	int i = (len-1)/2, j = i+1;

	while(i>0 && j<(len-1))
	{
		int m = i, n = j;
		while(m < n)
		{
			swap(arr[m],arr[m+1]);
			m+=2;
			if(m<n)
			{
				swap(arr[n],arr[n-1]);
				n-=2;
			}
		}
		i--;
		j++;
	}
}

//
// This assumes that the string sent in is properly formatted as "123456abcdef"
// and handles if this is not the case
//
static void PermutationsCombinations(string s)
{
int alpha = 0;
StringBuilder sb = new StringBuilder();

// Assuming that the string has to have equal number of digits and characters
if (s.Length % 2 != 0)
{
Console.WriteLine("The string is not even numbered - 1-digit to be paired with 1-character");
return;
}

// Parse the string and determine the exact position where the alphabets start within
for (int i = 0; i < s.Length; i++)
if (char.ToLower(s[i]) >= 'a' && char.ToLower(s[i]) <= 'z')
{
alpha = i;
break;
}
// Verify that the position is exactly half of the provided string
if (alpha != (s.Length/2))
{
Console.WriteLine("There are not equal digits and characters in the string!");
return;
}

// Use a stringBuilder class to collect the different digits and alphabets
for (int i = 0; i < alpha ; i++)
{
sb.Append(s[i]);
sb.Append(s[i + alpha]);
}
Console.WriteLine(sb);
}

There is one importnant from my perspective thing (which I was not familar with previously): if the algo uses n additional bits it is considered to use O(1) additional space anyway. (Since a representation of at least number 'n' requires log(n) bits.)
So we could just mark already swapped numbers in the array doing cycles and do not start the cycle for those numbers which are already marked. Result: O(n) times (for n-2 swaps) and O(1) space (for n bits).

Here is my solutions in C#

static void Main(string[] args)
{
string[] arr = new string[] { "1","2","3","4", "a","b","c","d",};
int arrayLength = arr.Length;
if (arr.Length / 2 % 2 != 0)
{
arrayLength = arrayLength - 2;
int startIndex = (arr.Length / 2)-1;
while (startIndex < arr.Length - 2)
{
string temp = arr[startIndex];
arr[startIndex] = arr[startIndex + 1];
arr[startIndex + 1] = temp;
startIndex++;
}
}

for (int i = 1, j = arrayLength / 2; i < arrayLength && j < arrayLength; i++, j++)
{
string temp = arr[j];
arr[j] = arr[i];
arr[i] = temp;
i++; j++;
}

int movesRequired = (arrayLength - 4) / 2;
int numPointer = arrayLength / 2;
int charPointer = numPointer + 1;
string nextIntValue = arr[numPointer];
string nextCharValue = arr[charPointer];
while (movesRequired > 0)
{
movesRequired--;
int newIntPos = GetNewPositionForInt(numPointer, arrayLength);
int newCharPos = GetNewPositionForChar(charPointer, arrayLength);
string tempInt = arr[newIntPos];
string tempChar = arr[newCharPos];
arr[newIntPos] = nextIntValue;
arr[newCharPos] = nextCharValue;
numPointer = newIntPos;
charPointer = newCharPos;
nextIntValue = tempInt;
nextCharValue = tempChar;
}
}

private static int GetNewPositionForChar(int charPointer, int arrayLength)
{
int mid = arrayLength / 2;
if (charPointer >= mid)
{
int diff = (charPointer - mid - 1);
int pow = GetPowerOf2(diff);
return diff == 0 ? 2 + 1 : 2 + pow + 1;
}
else
{
return (2 * (charPointer-1)) + 1;
}
}

private static int GetNewPositionForInt(int numPointer, int arrayLength)
{
int mid= arrayLength/2;
if (numPointer >= mid)
{
int diff = (numPointer - mid);
int pow = GetPowerOf2(diff);
return diff == 0 ? 2 : (2 + pow);
}
else
{
return 2 * numPointer;
}
}

private static int GetPowerOf2(int diff)
{
int powOf2 = 1;
while (diff > 0)
{
diff--;
powOf2 *= 2;
}
return powOf2;
}

MERGE SORT!!!!
I REALLY UNDERSTAND THE DIFFERENCES BETWEEN MICROSOFT AND GOOGLE!!!

My observation:

correct position of i if i belongs to 1st half of the array will be j=2*i, or if i belongs to 2nd half then it will be j=2*i-len+1
if length is not power of 2:

say

12345abcde


start from i=1;
then try to place s[i] to its correct poition j which is 2;
then take s[j] and try to place it in proper place which is 4. So new j is 4.
next j=8.
and go on like this..

Now if lenth is not power of 2, then in one round it gets over..
But if its power of 2,

eg:
1234abcd

0->0
1->2
2->4
4->1
5->3
6->5
7->7

so starts with i=1;
1->2
2->4
4->1
one cycle ended.. new cycle starts from 3...

so for length len where len=power of 2...

one cycle starts from 1
next cycle from 3
next from 5
then 7
........until its <len/2


code is

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

int ispowerof2(int len){
	if(len==1)
		return 1;
	if(len%2==1)
		return 0;
	return ispowerof2(len/2);
}


char *change(char *str){
	int i=1,j,k;
	int flag=0;
	char t,t1;
	int len=strlen(str);
	if(ispowerof2(len))
		flag=1;
		
	if(flag==0){
		t=str[1];
		while(1){
			if(i<len/2)
				j=2*i;
			else
				j=2*i-len+1;
			if(str[j]==t)
				return str;
			t1=str[j];
			str[j]=t;
			t=t1;
			i=j;
		}
	}
	else{
		k=1;
		i=1;
		t=str[1];
		while(k<len/2){
			if(i<len/2)
				j=2*i;
			else
				j=2*i-len+1;
			if(str[j]==t){
				k+=2;
				t=str[k];
				i=k;
				//continue;
			}
			else{
				t1=str[j];
				str[j]=t;
				t=t1;
				i=j;
			}
		}
		return str;
	}
	
}

main(){
	char *s;
	s=malloc(100*sizeof(char));
	strcpy(s,"123456789abcdefghi");
	s=change(s);
	printf("%s",s);
}

Assume char for i position is ch.
If it is a digit, its right position should be (ch - '0') * 2 - 1.
If it is not a digit, its right position should be (ch - 'a') * 2.
Can be solved by circle sort, O(n) time, O(1) space.

position for alphabet: (ch - 'a') * 2
position for digit: (ch - '0') * 2 - 1
Can be solved by circle sort in O(n) time, O(1) space.

position for alphabet: (ch - 'a') * 2
position for digit: (ch - '0') * 2 - 1
Can be solved by circle sort in O(n) time, O(1) space.

void SwapFromMid(char *str, int start, int mid, int end)
{
	if(end -start <1) return;
	int i= start; 
	int j= mid;
	char temp;
	while(i<=mid-1 && j<=end)
	{
		temp = str[i]; str[i] = str[j]; str[j]=temp;
		i++;j++;
	}

	return;
}

int main()
{
	char str[MAX_SIZE];
	cout<<"Enter the string"<<endl;
	cin>>str;

	int len = strlen(str);
	int i=1;
	int j = len/2;
	while(i<=(len/2-1))
	{
		SwapFromMid(str,i,j,len-i-1);
		i++;
	}
	cout<<"String after swap: ";
	cout<<str<<endl;
	return 1;
}

Assuming that numbers and letters are always a continuous sequence, we can get the expected position of any element in O(1).

Position of any digit D = (D - 1) * 2
Position of any letter L = (L - 1) * 2 + 1

Input --> 1 [2] 3 4 5 6 [a] b c d e f

Initially we maintain two pointers on the elements between [] that gives us
1 a [3] 4 5 6 [2] b c d e f
Now that we have one element in the correct position and another (2) in a faulty position, we maintain the pointer pointing to [2] and move the other pointer to the correct position of (2) using the equation above. and repeat that until both elements pointed to are in their correct positions.

O(n) time and in place.

I assumed the input was characters since no guidance was given.

C#

public char[] Answer(char[] input)
{
	var expected = new char[]{'1', '2', '3', '4', 'a', 'b', 'c', 'd'};
	if(input == null || !input.SequenceEqual(expected))
	{
		throw new ArgumentException("input array did not match what was expected.");
	}
	input[0] = '1';
	input[1] = 'a';
	input[2] = '2';
	input[3] = 'b';
	input[4] = '3';
	input[5] = 'c';
	input[6] = '4';
	input[7] = 'd';
	return input;
}

If this does not meet some mystery criteria which you left out of the question, please update it with more complete information.