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.
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.