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.

Advertisements

Pages: 1 2

12 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)))

    (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”))

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

  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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: