Move Spaces To Beginning Of String
August 8, 2017
Today’s exercise is a programming interview question from a programmer who very obviously didn’t get the job:
Given a C-style null-terminated string, move all the spaces in the string to the beginning of the string, in place, in one pass.
The candidate claimed it couldn’t be done, and apparently got into an argument with the interviewer, and took to the internet after the interview to vindicate himself about the “unfair question.”
Your task is to either write the requested program, or demonstrate that it cannot be done. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
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)))
(defun advance-by-one (array start end)
(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))
(advance-by-one str first-non-space cursor)
(incf first-non-space))
(incf cursor)))
str)
(move-spaces-to-front (null-terminate “a string with spaces”))
In Common Lisp, you can use stable-sort:
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.
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.
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.
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.
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).
Interesting. Not sure if my solution qualifies as “one pass”, but it definitely works in a timely manner.
Code: https://app.box.com/s/o3572j8a3jtag9pyh1yormme3o6jrsad
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…
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)))))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); }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(); } }Did they say what end to start at? Can you start at the last character, not the first?
“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.
Here’s a solution in x86 assembly. It loops over a null-terminated string, swapping spaces with the first non-space character.
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.
Correction: “Here’s a C program that calls the mvspaces function.”
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
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.