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.

Advertisements

Pages: 1 2

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

  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

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: