9
\$\begingroup\$

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();
  }
}
\$\endgroup\$
  • 1
    \$\begingroup\$ I like your variable and method names. Very sensible. \$\endgroup\$ – Floris Jul 27 '16 at 20:40
  • \$\begingroup\$ @Floris If you have any feedback on the code, whether positive or negative, short or long, please write an answer. Comments are for seeking clarification on the question, and may be deleted. \$\endgroup\$ – 200_success Jul 27 '16 at 20:46
  • \$\begingroup\$ Thanks @200_success. I will keep that in mind. Am writing on my phone so will rather just refrain from commenting or answering. :) \$\endgroup\$ – Floris Jul 27 '16 at 20:53
  • 1
    \$\begingroup\$ One basic limitation of your code is that it doesn't support unicode properly (in particular combining marks and UTF-16 surrogate pairs). \$\endgroup\$ – CodesInChaos Jul 28 '16 at 9:35
  • \$\begingroup\$ Interviewing is like a show business performance. Not only the final code matters, but also how you produce it: what clarification questions you ask (instead of going on with implicit assumptions), how many test cases you write, how quickly you produce the first correct code, how many mistakes (bugs) you make, and how easily you notice and fix them, how accurately and logically you can reason about the memory usage and speed of your code, how quickly you incorporate feedback and hints from the interviewer, how you consider and reject suboptimal solutions, how you communicate your confidence... \$\endgroup\$ – pts Jul 28 '16 at 13:27
11
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ By the way, I don't believe that your solution is so bad that I would reject a candidate based on it. A good interviewer would probe you a bit to see if you could either justify your answer or spot your own deficiencies. \$\endgroup\$ – 200_success Jul 27 '16 at 20:50
  • \$\begingroup\$ Thanks for the feedback. I see the stupidity of returning null, I should have just returned the input as is. Same with doing reversed.trim(), I ended up creating an extra string. And will keep my uses of final in check. The interviewer ran the solutions on CoderPad and just said works fine, looks good, I had no idea I will get reject on this :( \$\endgroup\$ – terminator Jul 27 '16 at 20:56
  • 1
    \$\begingroup\$ One could make a very strong argument that the code for reverseSentence() isn't correct. It's unclear what reversing a sentence means, and splitting on spaces to detect words only works on languages that use space strictly as a word delimiter. Not all languages have a word delimiter in text. \$\endgroup\$ – Leliel Jul 27 '16 at 22:52
  • 1
    \$\begingroup\$ @Leliel We can only speculate what the interviewer wanted. I hope this was a fizzbuzz-style question as a basic test of proficiency, because I can't see any practical application for reversing a sentence. It's also possible that the interviewer was looking for a dialogue about requirements, or hoping for an in-depth discussion about the intricacies of internationalization (capitalization, punctuation, bidi, hyphenation, combining characters, word segmentation,…). Only a mean-spirited interviewer would expect an interviewee to produce a solution handling all of those concerns on the spot. \$\endgroup\$ – 200_success Jul 27 '16 at 23:31
  • 1
    \$\begingroup\$ You should have gone all TDD and written private static String reverseString(String input) { return "world hello"; }. If that's not the implementation he's looking for, he should provide more test cases :P \$\endgroup\$ – CompuChip Jul 28 '16 at 8:54
6
\$\begingroup\$

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.

\$\endgroup\$
  • 2
    \$\begingroup\$ Hmm, I should have asked more questions. I was given sample inputs and outputs for both methods as reverse string : "abc" --> "cba", reverse sentence : "hello world" --> "world hello", and I just worked off these inputs \$\endgroup\$ – terminator Jul 27 '16 at 21:13
  • \$\begingroup\$ @terminator You should put that in your question as it clarifies the expected reversal result. \$\endgroup\$ – Mario Jul 28 '16 at 6:57
5
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Thanks for the feedback, will keep allocating required memory in mind wherever I can. Indentation actually went off while pasting the solution here, sorry about that \$\endgroup\$ – terminator Jul 27 '16 at 21:12
1
\$\begingroup\$

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();
}
\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ Constant differences and constant factors don't matter within the O(...) notation, thus O(5n) = O(4n) = O(4n+1). If you want to convey that implementation A is faster than implementation B by a constant factor, then don't use the O(...) notation. Especially not on an interview, because the interviewer will immediately notice that you don't understand the O(...) notation, and that can be a red flag. \$\endgroup\$ – pts Jul 28 '16 at 13:12
  • \$\begingroup\$ @pts ah-ha! Hoisted by my own petard! \$\endgroup\$ – Dai Jul 28 '16 at 16:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.