CareerCup

#!/usr/bin/perl

$str = "This is a test";
$cnt = () = $str =~ m/\s/g;
@arr = split(/\s+/,$str); $txt = join('',@arr);
$newstr = " "x($cnt/2).$txt." "x($cnt/2);
print "$newstr\n";

# easily extendable to odd number of total spaces

O(1) means you do the fix in place.

say you are given a char buffer[100], Start form the beginning - Maintain two ptrs - tgt & src. Advance src until you hit a space. At this point, bring the tgt here. Now continue advancing src at the saem time incrementing a spafce count, until a non space is encountered. Now, copy *src to *tgt, and advance both src & tgt. Do this for tgt -src -1 times. Repeating this process until src touches the end of string will have compacted the whole array, except that spacecount spaces are on the right! So place src at tgt, and tgt at position end of string - spacecount/2. Copy *src to *tgt, src--, tgt--, until src hits the beginning of the string. This requires 2 traversals, but we did not have to use an extra buffer.

Here is my solution

Maintain a count variable = counts num of spaces
1. Scan the string, keep counting spaces and keep compacting the string. Basically by end of scan, all spaces are at the end of string - O(n)
2. Let say total spaces is 2c. So c spaces have to come in front and c in end.
for(i=0;i<c;i++)
{
j = i;
currLoc = arr[j];
while(j<n && arr[j]!= ' ')
{ temp = arr[j+c];
arr[j+c] = currLoc;
currLoc = temp;
j= j + c;
}
arr[j] = currLoc;
}
If you see carefully, this is also O(n) so in total -> O(n)

I haven't covered edge cases in the code, leave it to you. Hope you guys got my basic idea!

int main(void) {
char T[100] ;
printf("Enter Text to be compacted\n") ;
fgets(T,100,stdin) ;
int len = strlen(T) - 2 ;
T[len+1] = '\0' ;
char *p, *q ;
p = q = T ;
int spc = 0 ;
while(*p != '\0') {

while( *p != ' ' && *p != '\0'){
*q++ = *p++ ;
}
p++ ;
spc++ ;
}
p = p-2;q--; spc-- ;
int i = spc/2 ;
while (i > 0) {
*p = '1' ;
i-- ;
p-- ;
}

while (q != T){
*p-- = *q-- ;
}
*p = *q ;
i = (spc - spc/2) ;
while (i > 0 ){
*q = '2' ;
i-- ;
q++ ;
}
printf("Compact Text: %s\n",T) ;

return 0 ;

}

'1' is padded at the end '2' at the beggining instead of spaces.

'1' is padded at the end '2' at the beggining instead of spaces,for debugging..put spaces in those places & u have the answer

may be this can be of O(1) space complexity.

public static String prePostSpace(String s){
int count = 0;
StringBuffer sb = new StringBuffer();
for(int i = 0; i < s.length(); i ++){
if(s.charAt(i) == ' '){
count++;
if(count % 2 == 0)
sb.replace( 0, 0, "*");
}
else
sb.append(s.charAt(i));
}

sb.append(sb.substring(0, count/2));

return sb.toString();
}

#include<stdio.h>
#include<conio.h>
#include<string.h>
void swap(char *a,char *b)
{char x;
x=*a;*a=*b;
*b=x; }
int main()
{char st[]=" this is n ";
int l=strlen(st),j,i,p;
for(j=0,i=l-1;j<=i;j++,i--)
{
if(st[j]==' '&&st[j-1]!=' ' &&j!=0)
{p=j;
while(st[p-1]!=' ')
{swap(&st[p],&st[p-1]);
p=p-1;
}
}
else if(st[i]==' '&&st[i+1]!=' '&&i!=l-1)
{p=i;
while(st[p+1]!=' ')
{swap(&st[p],&st[p+1]);
p=p+1;
}
}
}
printf("%s",st);
getch();
}

This is the code -
1. No error checking though.
2. The spaces are replaced by '*' just for readability


public static void compactSpaces() {
final char SPACE = ' ';
String str = " This is a test of the spaces in the string ";
char[] a = str.toCharArray();

int j = 0;
for(int i = 0; i < a.length; i++) {
if(a[i] != SPACE) {
a[j] = a[i];
j++;
}
}
for(int i = 0; i < a.length - j; i++) {
a[j+i] = '*';
}
for(int i = j; i >=0 ; i--) {
a[i + ((a.length - j)/2)] = a[i];
}
for(int i = 0; i < ((a.length - j)/2); i++) {
a[i] = '*';
}

for(int i = 0; i < a.length; i++) {
System.out.print(a[i]);
}
}