1
\$\begingroup\$

A couple of weeks I had a coding interview and the problem to solve was very simple: reverse the words order of a string. What did I do wrong here?

public static String reverse(String phrase) {
        String[] words = phrase.split(" ");
        StringBuffer sb = new StringBuffer();
        for (String word : words) {
            String reversed = new String();
            for (int j = word.length() - 1; j >= 0; j--) {
                reversed += word.charAt(j);
            }
            sb = sb.append(reversed).append(" ");
        }

        return sb.toString().substring(0, sb.toString().length() - 1);
    }
\$\endgroup\$
  • \$\begingroup\$ String reversed = new String(); this doesn't look good. Why are you doing this when you're already using a StringBuffer (which should be a StringBuilder, by the way)? When is it ever appropriate to use new String()?? \$\endgroup\$ – Hovercraft Full Of Eels Jan 3 '18 at 22:32
  • \$\begingroup\$ Also, sb = sb.append(... it is unnecessary to assign the StringBuilder reference. Two unforced errors, makes it look like you don't understand objects and references. \$\endgroup\$ – markspace Jan 3 '18 at 22:36
  • \$\begingroup\$ In the StringBuffer API: As of release JDK 5, this class has been supplemented with an equivalent class designed for use by a single thread, StringBuilder. The StringBuilder class should generally be used in preference to this one, as it supports all of the same operations but it is faster, as it performs no synchronization. \$\endgroup\$ – Hovercraft Full Of Eels Jan 3 '18 at 22:36
  • \$\begingroup\$ One more thing: you extract a String from sb (at the return) and then immediately call substring() on that string. Strings are immutable, and this forces another buffer copy. You should have reduced the length of the string builder first, then called toString(). \$\endgroup\$ – markspace Jan 3 '18 at 22:40
0
\$\begingroup\$

The main reason why you fail may be because your code reverse the entire sentence while only the order of the words must be reversed; Hello the world should be world the hello. If you want to reverse the whole string, there is StringBuilder.html#reverse()

That put aside. Some problems I see is the usage of StringBuffer which is slower but synchronized. There is also this new String() in your loop which is useless because you can already use sb.append. And there is this ugly string building at the end where sb.toString() is abused while sb.delete can do it.


For the fun I made mine which revert the words by traversing the char sequence from the end and insert the character at a given index. The index is changed when a space is found to insert at the end of the new string : https://github.com/gervaisb/stackexchange-codereview/blob/q184229/src/main/java/q184229/Sentence.java

final StringBuilder target = new StringBuilder(value.length());
for (int i=value.length()-1, at=0; i>-1; i--) {
    char character = value.charAt(i);
    if ( Character.isWhitespace(character) ) {
        target.append(character);
        at = target.length();
    } else {
        target.insert(at, character);
    }
}
\$\endgroup\$
0
\$\begingroup\$

Thanks for your fast response guys, after reading your messages I tried to solve it different:

public static void reverse(String phrase, char delimiter) {
        char[] newPhrase = new char[phrase.length()];
        int start = 0, i = 0, currentPos = newPhrase.length;
        while (i < phrase.length()) {
            if (phrase.charAt(i) == delimiter || i == phrase.length() - 1) {
                char[] word = phrase.substring(start, i).toCharArray();
                currentPos = currentPos - word.length;
                System.arraycopy(word, 0, newPhrase, currentPos, word.length);
                if (i != phrase.length() - 1) {
                    newPhrase[--currentPos] = delimiter;
                }
                start = ++i;
            } else {
                i++;
            }
        }

        System.out.println(new String(newPhrase));
    }
\$\endgroup\$
  • \$\begingroup\$ This may be faster, but it's damn hard to read. Dealing with char[]s is pretty low level and better to be avoided unless really needed. Especially in interviews. \$\endgroup\$ – maaartinus Jan 4 '18 at 1:09
  • \$\begingroup\$ Also, if the String contains weird unicode characters, it might be the case that the character from the String does not fit in a char \$\endgroup\$ – RobAu Jan 4 '18 at 11:27
  • \$\begingroup\$ @maaartinus indeed I took the main Idea from apache StringUtils.reverse \$\endgroup\$ – Eliú Abisaí Díaz Vásquez Jan 4 '18 at 12:47
0
\$\begingroup\$

Your current solution looks to be too complex. If all you need to do is swap the order of words, Strings that are separated by white space, then why not simply do this:

  • Use String#split("\\s+") to split the input text into an array of words -- of Strings split greedily by white-space
  • Iterate through this array backwards in a simple for loop
  • Add these Strings to a StringBuilder (not a StringBuffer which has unnecessary overhead of thread-safety -- we're doing this in only one thread)
  • Avoiding use of new String(...), it's almost never necessary to use this, and there is a down-side to its use, including avoiding appropriate and efficient use of the String-pool.
  • And then return.

e.g., something as basic as:

public static String reverseWords(String inText) {
    StringBuilder sb = new StringBuilder();
    String[] tokens = inText.split("\\s+");
    for (int i = tokens.length - 1; i >= 0; i--) {
        sb.append(tokens);
        if (i != 0) {
            sb.append(" ");
        }
    }        
    return sb.toString();
}
\$\endgroup\$
  • \$\begingroup\$ I like your solution but what about String.split method? the interviewer didn't like it and asked me how can I avoid to create several copies of the same string when using String.split and I didn't know what to say \$\endgroup\$ – Eliú Abisaí Díaz Vásquez Jan 3 '18 at 23:11
  • \$\begingroup\$ @EliúAbisaíDíazVásquez: "didn't like it" how? why? What specifically were they concerned about, and what metrics are we to use here to measure the quality of an attempt? \$\endgroup\$ – Hovercraft Full Of Eels Jan 3 '18 at 23:14
  • \$\begingroup\$ I agreed with you 100% but maybe I am guessing they asked me to solve it different because I was using split instead of iterate throught the array because in their feed back the only mentioned that I didn't solve the problem as expected, but after reading all comments I have more issues like: using StringBuffer and toString \$\endgroup\$ – Eliú Abisaí Díaz Vásquez Jan 3 '18 at 23:22
  • \$\begingroup\$ Probably just one of those probing interview questions. "Does the interviewee know a second way of implementing this?" Ignore the /didn't like it/ part and just focus on a different way to parse the input string. \$\endgroup\$ – markspace Jan 4 '18 at 0:27
  • \$\begingroup\$ @HovercraftFullOfEels String.split is pretty crazy: github.com/google/guava/wiki/StringsExplained#splitter \$\endgroup\$ – maaartinus Jan 4 '18 at 1:02

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.