1

We are given a sentence text (A sentence is a string of space-separated words) in the following format:

First letter is in upper case. Each word in text are separated by a single space. Our task is to rearrange the words in text such that all words are rearranged in an increasing order of their lengths. If two words have the same length, we arrange them in their original order.

Example:

Input: text = "Keep calm and code on"
Output: "On and keep calm code"
Explanation: Output is ordered as follows:
"On" 2 letters.
"and" 3 letters.
"keep" 4 letters in case of tie order by position in the original text.
"calm" 4 letters.
"code" 4 letters.

The solution is:

class Solution {
    
    public String arrangeWords(String inputText) {
        String text = inputText.toLowerCase();
        String[] allWords = text.split("\\s+");

        Map<Integer, List<String>> lengthToWordsMap = new HashMap<>();

        for (int i = 0; i < allWords.length; i++) {
            lengthToWordsMap.computeIfAbsent(allWords[i].length(), k -> new ArrayList<>());
            lengthToWordsMap.get(allWords[i].length()).add(allWords[i]);
        }

        StringBuilder answerStringBuilder = new StringBuilder();

        for (int length : lengthToWordsMap.keySet()) {
            for (String word : lengthToWordsMap.get(length)) {
                answerStringBuilder.append(answerStringBuilder.length() == 0 ? "" : " ").append(word);
            }
        }

        String firstLetterInUppercase = answerStringBuilder.toString().substring(0, 1).toUpperCase();
        String restOfSentenceInLowercase = answerStringBuilder.toString().substring(1);
        
        String answer = firstLetterInUppercase + restOfSentenceInLowercase;
        
        return answer;
    }
}

I understand that after splitting the text and storing it in a String array, we are using a HashMap to store the length of words as the key and the words of that length as the length's values. But keys are not sorted in HashMaps so the length is not sorted either. So, after appending the words of each key (length of each word) to "sb", how are we ensuring that the words are rearranged in increasing order of their length?

Edit:

Okay, this is not my code. This was one of the solutions posted on the discussion board. This question is posted on Leetcode and the link to the question is here.

This solution passes all the 75 test cases too so I don't think this is working just by chance.

coderfromhell
  • 435
  • 1
  • 4
  • 13
  • The point I am trying to make is that this solution works. I want to know how it is working. – coderfromhell Jul 10 '20 at 07:48
  • Did you try the solution for some bigger input? `HashMap` doesn't guarantee anything about key order. It might happen that they are ordered but it won't always. – Amongalen Jul 10 '20 at 07:51
  • 1
    I think it's working by chance. (Also note that you seem to have reinvented `String.join(" ", map.get(i))`, and you should generally prefer to iterate over `entrySet` if you need both key and value.) – chrylis -cautiouslyoptimistic- Jul 10 '20 at 07:52
  • 1
    Possibly related: [Are the HashMap entries always sorted by key, if the key is of type Integer?](https://stackoverflow.com/questions/43871017/) and [Is the order of values retrieved from a HashMap the insertion order](https://stackoverflow.com/questions/2144776/). – Slaw Jul 10 '20 at 07:53
  • But the important thing is that `HashMap` has no order, even when it _appears_ to. If you need a map ordered by the keys you need to use a `SortedMap` implementation (e.g. `TreeMap`). – Slaw Jul 10 '20 at 07:56
  • 1
    Btw you could achieve the same using Streams: `List original = Arrays.asList(t.split("\\s+")); return IntStream.range(0, original.size()).boxed().sorted(Comparator.comparing(i -> original.get(i).length()).thenComparing(i -> i)).map(original::get).collect(Collectors.joining(" "));` – Lino Jul 10 '20 at 07:59
  • 1
    Part of the difficulty understanding this code are the horrible 1 and 2-letter variable names - this is really bad practice in writing code. I refactored the code, only changing the variable names and introducing 2 new variables at the end for clarity. It should be easier to understand now, – kenny_k Jul 10 '20 at 08:02
  • @Amongalen Yes, this solution passed all the 75 test cases. I've posted the link to the problem in my latest edits to this question. – coderfromhell Jul 10 '20 at 08:11

2 Answers2

5

HashMap stores keys in a map by first converting the key to an integer called the hash value. This is done by calling the hashCode() method on the object. Then finding a bin in the hash table depending on this hash value.

If you are using Oracle or OpenJDK, chances are that hashCode() of integer returns the int itself (because the hash value is also just an int):

/**
 * Returns a hash code for a {@code int} value; compatible with
 * {@code Integer.hashCode()}.
 *
 * @param value the value to hash
 * @since 1.8
 *
 * @return a hash code value for a {@code int} value.
 */
public static int hashCode(int value) {
    return value;
}

The default implementation of HashMap seems heavily java-version dependent. The principle (the naïve implementation) is to take the modulus of the hash value and the table length to get the index:

index = hash % table.length; // Don't try this, it breaks for negative hash values.

Java 11's implementation seems to do some array-of-trees trickery where it walks the table to find the hash.

At the very least, I could reproduce your example with Java 11, and I could break your example by changing this line:

    Map<Integer, List<String>> lengthToWordsMap = new HashMap<>(4);

Note how even the Integer.hashCode() method doesn't specify how it calculates the hash value, so the fact that it happens to calculate it with the identity function is undocumented and as such should never be relied on.

The answer to your question is, it happens because favorable conditions conspire (and specific implementation details), and not because of defined logic.

Mark Jeronimus
  • 9,278
  • 3
  • 37
  • 50
  • The problem with the negative index due to [how modulus works](https://stackoverflow.com/questions/4412179/best-way-to-make-javas-modulus-behave-like-it-should-with-negative-numbers) can be overcome using this: `(hash % table.length + table.length) % table.length` – Lino Jul 10 '20 at 08:39
  • I was about to add `Math.floorMod()` to the answer but I chose not to for clarity sake – Mark Jeronimus Jul 10 '20 at 08:44
1

This is just another approach to solve the problem, with O(N Log N) time complexity and O(N) space.

public class Solution {
    public static final String arrangeWords(String text) {
        String[] s = text.toLowerCase().split(" ");
        Arrays.sort(s, (a, b) -> a.length() - b.length());
        String rearranged = String.join(" ", s);
        return Character.toUpperCase(rearranged.charAt(0)) + rearranged.substring(1);
    }
}

You question set aside, I guess your method might be O(N ^ 2) time and O(N) space, but I might be totally wrong though.

References

  • For additional details, you can see the Discussion Board. There are plenty of accepted solutions with a variety of languages and explanations, efficient algorithms, as well as asymptotic time/space complexity analysis1, 2 in there.

If you are preparing for interviews:

Emma
  • 27,428
  • 11
  • 44
  • 69