## Move Spaces To Beginning Of String

### August 8, 2017

There’s more than one answer to this question.

If you know the length of the string in advance, you can work from back to front, copying non-space characters as you go:

```(define (spaces-to-front str)
(define (swap! a b)
(let ((temp (string-ref str a)))
(string-set! str a (string-ref str b))
(string-set! str b temp)))
(let ((len (- (string-length str) 1)))
(let loop ((i len) (j len))
(cond ((negative? i)
(do ((j j (- j 1)))
((negative? j) str)
(string-set! str j #\space)))
((char=? #\space (string-ref str i))
(loop (- i 1) j))
(else (swap! i j) (loop (- i 1) (- j 1)))))))```

Scheme strings are typically stored internally as a vector of characters paired with a length, so taking the length of the string is a constant-time operation that doesn’t require a pass through the string, but that’s not a C-style null-terminated string as the interview question requires.

```> (spaces-to-front "h e l l o")
"    hello"
> (spaces-to-front "hello    ")
"    hello"
> (spaces-to-front "    hello")
"    hello"```

If you don’t mind scrambling the non-space portion of the string (nothing in the problem description disallows it), the task is easy:

```(define (spaces-to-front str)
(define (swap! a b)
(let ((temp (string-ref str a)))
(string-set! str a (string-ref str b))
(string-set! str b temp)))
(set! str (string-append str (string #\nul)))
(let loop ((i 0) (j 0))
(cond ((char=? (string-ref str j) #\nul) str)
((char=? (string-ref str j) #\space)
(swap! i j) (loop (+ i 1) (+ j 1)))
(else (loop i (+ j 1))))))```

For a C-style string, we add a `#\nul` character to the end of `str`, which you see in the output below:

```> (spaces-to-front "h e l l o")
"    lelho\x0;"
> (spaces-to-front "hello    ")
"    ohell\x0;"
> (spaces-to-front "    hello")
"    hello\x0;"```

Otherwise, the candidate is correct and the interviewer is incorrect; there is no way to solve the problem. But that doesn’t seem to have gotten him the job.

You can run the program at http://ideone.com/FECXsR.

Pages: 1 2

### 16 Responses to “Move Spaces To Beginning Of String”

1. Fred said

I guess it sort of depends on the definition of “one pass”. Similar to the way you check for cycles in a linked list, you can use two cursors to move the spaces as you advance from the front of the string towards the null character. Here’s some common lisp code. In order to respect the spirit of the challenge I don’t use the length function.

(defun null-terminate (str)
(concatenate ‘string str ‘(#\null)))

(defun swap (array idx1 idx2)
(let ((tmp (aref array idx1)))
(setf (aref array idx1) (aref array idx2))
(setf (aref array idx2) tmp)))

(let ((dist (- end start)))
(loop for x from 0 to (1- dist) do
(swap array (- end x 1) (- end x)))))

(defun move-spaces-to-front (str)
(let ((first-non-space 0)
(cursor 0))
(loop while (not (char= (aref str cursor) #\null)) do
(when (char= #\space (aref str cursor))
(incf first-non-space))
(incf cursor)))
str)

(move-spaces-to-front (null-terminate “a string with spaces”))

2. In Common Lisp, you can use stable-sort:

```
(defun move-spaces-to-the-beginning (string)
(replace string (stable-sort string (lambda (x y) (char= #\space x)))))

(let ((string (copy-seq "Hello World !")))
(assert (eq string (move-spaces-to-the-beginning string)))
string)
;; --> "  HelloWorld!"

```

Notice that our comparison where non-space character are not ordered, implies they are equal, which combined with the stability property of stable-sort gives deterministic (conforming) results as per the Common Lisp specification.

3. If you want to argue that stable-sort could be O(nlogn) or worse, here is a O(n) solution:

```
(defun move-spaces-to-the-beginning (string)
(loop
:with d := (1- (length string))
:for s :from d :downto 0
:when (char/= #\space (aref string s))
:do (loop :while (and (char/= #\space (aref string d)) (< s d) )
:do (decf d))
(rotatef (aref string s) (aref string d))
:finally (fill string #\space :start 0 :end d)
(return string)))

(let ((string (copy-seq "FooBar")))
(assert (eq string (move-spaces-to-the-beginning string)))
string)
;; --> "FooBar"

(let ((string (copy-seq "Hello World !")))
(assert (eq string (move-spaces-to-the-beginning string)))
string)
;; --> "  HelloWorld!"

(let ((string (copy-seq "   Hello  World  !   ")))
(assert (eq string (move-spaces-to-the-beginning string)))
string)
;; --> "          HelloWorld!"

```

Note: we still ignore the null-termination aspect, which is irrelevant (just change (length string) with (position #\null string)); rotatef is the Common Lisp swap operator. Since we want to compact a unique value (#\space), we don’t need to store them during the loop, so we use the fill trick at the end.

4. John Cowan said

Here’s another approach:

```char *x = str;
char *y = str;
while (*x) {
if (*x == ' ') {
*y = ' ';
++y;
}
x++;
}
*y = 0;
```

That leaves the rest of the string a mess (“h␣e␣l␣l␣o” becomes “␣␣␣␣l␣l␣o”), and probably isn’t the semantics of “move” that the interviewer had in mind (but note the assembler mnemonic MOV for copy operations). Then again, the problem doesn’t state what should or shouldn’t be done to the rest of the string.

5. Oops, the final FILL is not necessary when we use ROTATEF. (It would be used only if we moved the non-space up, without using rotatef, but this would require more complex index updating to do it correctly.

6. Actually, it simplifies the processing of d:

```
(defun move-spaces-to-the-beginning (string)
(loop
:with d := (1- (length string))
:for s :from d :downto 0
:when (char/= #\space (aref string s))
:do (loop :while (and (char/= #\space (aref string d)) (< s d) )
:do (decf d))
(rotatef (aref string s) (aref string d))
:finally (return string)))

(defun move-spaces-to-the-beginning (string)
(loop
:with d := (1- (length string))
:for s :from d :downto 0
:when (char/= #\space (aref string s))
:do (setf (aref string d) (aref string s))
(decf d)
:finally (fill string #\space :start 0 :end (1+ d))
(return string)))

```

The first solution will store 2n times in the array (n x rotatef), while the second solution will store n+d times in the array (n x setf + d times in fill).
Also, the first solution reads 4n times the array (n times for s and n times for d, plus 2n times for rotatef), while the second solution reads only 2n times (n times for s, n times for d).

7. Zack said

Interesting. Not sure if my solution qualifies as “one pass”, but it definitely works in a timely manner.
Demonstration:
julia> a
“f fd ds f43df”

julia> MoveSpaces(a)
” ffddsf43df”

If I were the interviewer, I’d disqualify the candidate just because of his negative attitude…

8. Jussi Piitulainen said

Returning from a recursive pass does not count.

```(define (string0-frontspace! s)
(define (mov! t f)
(or (= t f) (begin (string-set! s t (string-ref s f))
(string-set! s f #\space)))
(- t 1)) ;!
(let loop ((k 0))
(case (string-ref s k)
((#\nul) (- k 1))
((#\space) (loop (+ k 1)))
(else (mov! (loop (+ k 1)) k)))))
```
9. Jussi Piitulainen said

Same in C.

```int mov(char *s, int t, int f) {
(t == f) || (s[t] = s[f], s[f] = ' ');
return t - 1;
}

int lop(char *s, int k) {
if (s[k] == '\0') return k - 1;
else if (s[k] == ' ') return lop(s, k + 1);
else return mov(s, lop(s, k + 1), k);
}

void frntspc(char *s) {
lop(s, 0);
}
```
10. Dustin Kieler said

Are we allowed to use the length function? If so, we can just do some simple string manipulation. Here’s a solution in Java.

```import java.util.Scanner;

public class Main {

public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String input = scanner.nextLine() + "\n"; // C-style string

int originalInputLength = input.length();
input = input.replaceAll(" ", "");
int lengthDifference = originalInputLength - input.length();

// This could be replaced with Apache Commons StringUtils.leftPad
for (int i = 0; i < lengthDifference; i++)
input = " " + input;

System.out.println(input);

scanner.close();
}

}
```
11. Brendan said

Did they say what end to start at? Can you start at the last character, not the first?

12. Python said

“Can you start at the last character, not the first” – this is all the question. If you’ll get index of last character, or pointer to it, there will be no problem to solve this. For example (Delphi):
procedure SpaceToFront(var S:string);
var
I,J:integer;
begin
I:=Length(S); // prime index
J:=I; // secondary index
while J>=1 do begin
while (J>1) and (S[J]=’ ‘) do
Dec(J);
S[I]:=S[J];
Dec(I);
Dec(J);
end;
while I>=1 do begin
S[I]:=’ ‘;
Dec(I);
end;
end;
But this is completely NOT a solution. Yes, the algorithm by itself is one-pass, but only due to pascal-strings has already length in it’s header. For PChar lstrlen should make one pass to find the null-character… and that’s all – we’ve done our pass, no chances to solve more. So, you are VERY RESTRICTED to use any of the embedded functions (because they may make one-pass inside them). Length/lstrlen or s.length() or something else are forbidden too.

13. Daniel said

Here’s a solution in x86 assembly. It loops over a null-terminated string, swapping spaces with the first non-space character.

```/* mvspaces.s */

.section .text

# void mvspaces(char* str);
.globl mvspaces
mvspaces:
# Save old base pointer and non-volatile registers
pushl %ebp
movl %esp, %ebp
pushl %ebx
pushl %esi
# %eax stores the current index
movl \$0, %eax
# %ecx stores the index of the next swap
movl \$0, %ecx
# %esi stores str
movl 8(%ebp), %esi
# %bl stores the current character
# %dl stores the swap character
loop:
movb (%esi,%eax,1), %bl
# Exit when we've reached the null character
cmpb \$0, %bl
je exit
# 32 is ascii code for space character
cmpb \$32, %bl
jne proceed
# Swap current character and swap character
movb (%esi,%ecx,1), %dl
movb %bl, (%esi,%ecx,1)
movb %dl, (%esi,%eax,1)
incl %ecx
proceed:
incl %eax
jmp loop
exit:
movl \$0, %eax
# Restore old base pointer and non-volatile registers
popl %esi
popl %ebx
popl %ebp
ret
```

Here’s a C program that calls the day-of-week function.

```/* main.c */

#include <stdio.h>

void mvspaces(char* str);

int main(int argc, char* argv[]) {
// this function modifies the contents pointed to by argv
if (argc != 2) return 0;
char* str = argv[1];
mvspaces(str);
printf("'%s'\n", str);
return 0;
}
```

Here’s example usage.

```\$ as --32 -o mvspaces.o mvspaces.s
\$ gcc -m32 -o main main.c mvspaces.o

\$ ./main 'Move Spaces To Beginning Of String'
'     SpacesoTovBeginningeOfMString'
```
14. Daniel said

“Here’s a C program that calls the day-of-week function.”

Correction: “Here’s a C program that calls the mvspaces function.”

15. Javascript(with built-in functions- may not count, if join/split built-in’s loop is a loop)

function moveSpaces(tex){
var s = [];
var sp = tex.split(”).forEach(function(a){
if (a === ‘ ‘){
s.unshift(a);
}else{
s.push(a);
}
});
return s.join(”);

}
moveSpaces(‘t t edd eas as1 1’); // _____tteddeasas11 _ -> denotes spaces

16. Richard A. O'Keefe said

Presumably the non-space characters must be preserved,
but nothing in the problem specification says their order must be.
Certainly the interviewee should have asked several questions
about what exactly the problem meant.