Interview solutions to reverse a string and reverse a sentence

Question

Recently in an interview I was asked to

1. Write a method to reverse a string. I used StringBuilder but was asked not to use reverse method of builder but iterate over the string. Sample input/output provided by interviewer : "abc" --> "cba"
2. Next was to reverse a sentence. Sample input/output provided by interviewer : "hello world" --> "world hello"

Total time spent on both the solutions : around 10-12 minutes to write and run

Following is the code I wrote and I got rejected from interview. Would appreciate any helpful feedback.

class Solution {

  public static void main(String[] args) {
    String input = "hello world";
    System.out.println(reverseString(input));
    System.out.println(reverseSentence(input));
  }

  private static String reverseString(final String input){
    if(input == null || input.length() == 0){
      return null;
    }
    StringBuilder sb = new StringBuilder();
      for(int i =input.length()-1; i  >= 0; i--){
      sb.append(input.charAt(i));
    }
    return sb.toString();
  }

  private static String reverseSentence(final String input){

    final String[] wordsInInput = input.split(" ");
    StringBuilder sb = new StringBuilder();
    for(int i = wordsInInput.length-1; i >=0; i--){
      sb.append(wordsInInput[i]);
      sb.append(" ");
    }
    final String reversed = sb.toString();
    return reversed.trim();
  }
}

Answer 1

The reverse of an empty string should be an empty string, not null.

In reverseSentence(), the reversed.trim() call inefficiently copies the entire string, less one final space. You would have been better off shortening the StringBuilder instead of trimming the string.

All of your uses of final are excessive, I think. The final keyword merely prevents reassignment, and doesn't make anything more immutable than it already is. For short functions like this, writing final just adds noise.

Answer 2

Try to reverse an actual sentence, e.g. this one. Your code will give

one. this e.g. sentence, actual an reverse to Try

I would expect something more like

.one this .g.e ,sentence actual an reverse to Try

or maybe

One this .g.e, sentence actual an reverse to try.

I've also spoken to at least one interviewer who would have downgraded someone for not asking for more details about what reversing a sentence means.

Answer 3

The methods and variables are properly named, the code is correct... I don't see why you would be rejected. In addition to 200_success's answer, a couple of notes:

• StringBuilder also has a constructor taking the initial size of the backing array. Since, in this case, you know in advance the right size (it will be same as the length of the input String), might as well initialize it correctly. Otherwise, either too much is allocated or too less (requiring StringBuilder to copy the current backing array into a new one).

• Take care of your indentation; some for constructs are off:

    for(int i =input.length()-1; i  >= 0; i--){
    sb.append(input.charAt(i));
  }
  

  In addition to the indentation, there are spurious spaces, like i >= 0, but no spaces where it could add to clarity, like after the for or after the operators. Consider this style instead:

  for (int i = input.length() - 1; i >= 0; i--) {
    sb.append(input.charAt(i));
  }
  

  which is technically the same, but reads easier.

Answer 4

This is the trick (if (i > 0)) to avoid the slow and memory-consuming .trim() call:

private static String reverseSentence(String input) {
  final String[] wordsInInput = input.split(" ");
  StringBuilder sb = new StringBuilder();
  for (int i = wordsInInput.length - 1; i >= 0; i--) {
    sb.append(wordsInInput[i]);
    if (i > 0) sb.append(' ');
  }
  return sb.toString();
}

You may also shave the last iteration off the loop to make it even faster:

private static String reverseSentence(String input) {
  final String[] wordsInInput = input.split(" ");
  StringBuilder sb = new StringBuilder();
  for (int i = wordsInInput.length - 1; i > 0; i--) {
    sb.append(wordsInInput[i]);
    sb.append(' ');
  }
  if (wordsInInput.length > 0) sb.append(wordsInInput[0]);
  return sb.toString();
}

Answer 5

main

You only provided a single test case (hello world). Assuming this was the code you gave to the interviewer and they expected you to give a few test-cases then this probably made you look bad. Functions like these are straightforward to develop testcase equivalence-classes for and you can implement an exhaustive test suite very quickly.

reverseString

Your reverseString implementation is inefficient: Using a StringBuilder without an initial capacity means reallocating the StringBuilder's internal buffer numerous times if you're dealing with a long string. There are a variety of approaches that offer improvements on your implementation.

Note that in Java, array allocation is O(n) because the JVM will zero-out all arrays, whereas in languages like C and C++ it's O(1) (though the host OS will probably zero-out pages before allocating them to your host process). Given that StringBuilder operations such as .toString() and the StringBuilder(String) constructor are both O(n) you're probably better-off using a char[] as working-space:

Also you should handle invalid input more predictably (e.g. return null only for null input, returning the input directly if it's an empty input or only 1 character long).

private static String reverseString(final String input) {

    if( input == null ) return null;
    final int len = input.length();
    if( len == 0 || len == 1 ) return input;

    final char[] chars = input.toCharArray(); // O(n)
    for( int i = 0; i < chars.length / 2; i++ ) { // O(n/2), but because it does 2 element assignments ops per loop, it works out as O(n) anyway.

        final char c = chars[i]; // or replace this with an XOR swap if you're feeling smartarsed.
        chars[i] = chars[ len - i ];
        chars[ len - i ] = c;
    }

    return new String( chars ); // O(n)
}

reverseSentence

Your reverseSentence is also suboptimal. When writing fast code you can always replace split with a simple finite-state-machine parser which iterates through an existing buffer without needing to reallocate strings - which is good for the GC as there will be a lot less objects to process.

You didn't provide an automated test case for reverseSentence so I don't know if the code is meant to reverse the order of words in a string (while maintaining in-word character order) or reverse the character-order but maintain the word order. I'm assuming it's the former. I don't know how the function should handle punctuation and other non-letter/digit characters.

static String reverseSentence(final String input) {

    final int len = input.length(); // O(1)
    StringBuilder sb = new StringBuilder( len  ); // O(n)

    int lastSpace = len;
    for( int i = len - 1; i >= 0; i-- ) { // O(n)
        char c = input.charAt( i );
        if( c == ' ' ) {
            // copy the last word into sb
            if( lastSpace < len ) sb.append(' '); // potentially O(n)
            for(int w = i; w < lastSpace; w++ ) {
                sb.append( input.charAt( w ) );
            }
            lastSpace = i;
        }
    }
    return sb.ToString(); // O(n)
}

This approach takes O(4n) time and at most O(n+2) space. Whereas your implementation is O(5n) time and O(4n+1) space in the best case, see my annotated comments for why:

private static String reverseSentence(final String input){

    final String[] wordsInInput = input.split(" "); // O(2n) time, O(n) space
    StringBuilder sb = new StringBuilder();
    for(int i = wordsInInput.length-1; i >=0; i--){ // O(n) time
        sb.append(wordsInInput[i]);
        sb.append(" ");
    }
    final String reversed = sb.toString(); // O(n) time, O(n) space
    return reversed.trim(); // O(n) time, O(n) space
}

String.split takes O(2n) time and O(n) space because it allocates a new character array/string ((On) space) for each split chunk, which requires zeroing by the JVM (O(n) time) and then populating with character data (O(n) time again). You also didn't preallocate your StringBuilder so you'll lose time if/when it reallocates internally.