Jobs

Interviews

Discussions

Sorting the Sentence

Easy

Google

2 views

Topics:

StringsArrays

A sentence is a list of words separated by single spaces with no leading/trailing spaces. Each word consists of lowercase and uppercase English letters.

A sentence can be shuffled by appending the 1-indexed word position to each word and rearranging the words in the sentence. For example, "This is a sentence" can be shuffled as "sentence4 a3 is2 This1" or "is2 sentence4 This1 a3".

Given a shuffled sentence s containing no more than 9 words, reconstruct and return the original sentence.

Example:

Input: s = "is2 sentence4 This1 a3" Output: "This is a sentence"

Explanation: Sort the words in s to their original positions "This1 is2 a3 sentence4", then remove the numbers.

Constraints:

2 <= s.length <= 200
s consists of lowercase and uppercase English letters, spaces, and digits from 1 to 9.
The number of words in s is between 1 and 9.
The words in s are separated by a single space.
s contains no leading or trailing spaces.

Sorting the Sentence

Easy

Google

2 views

Topics:

StringsArrays

A sentence is a list of words separated by single spaces with no leading/trailing spaces. Each word consists of lowercase and uppercase English letters.

Given a shuffled sentence s containing no more than 9 words, reconstruct and return the original sentence.

Example:

Input: s = "is2 sentence4 This1 a3" Output: "This is a sentence"

Explanation: Sort the words in s to their original positions "This1 is2 a3 sentence4", then remove the numbers.

Constraints:

2 <= s.length <= 200
s consists of lowercase and uppercase English letters, spaces, and digits from 1 to 9.
The number of words in s is between 1 and 9.
The words in s are separated by a single space.
s contains no leading or trailing spaces.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the input string be empty or null?
Will the words in the input string always contain numbers from 1 to 9 indicating their position, and will those numbers always be at the end of the words?
Is it guaranteed that the numbers indicating word positions will be unique and within the valid range of word count?
Besides spaces and numbers, can the input string contain any other special characters or punctuation?
If the input string is malformed (e.g., missing a number, invalid number, or incorrect format), what should I return?

Brute Force Solution

Approach

The brute force way to sort a sentence involves figuring out the correct order by trying every single possible arrangement. We extract all the words from the sentence and then explore every way to put them back together based on the numbers attached to them.

Here's how the algorithm would work step-by-step:

First, separate each word from the sentence.
For each word, identify its position from the number located at the end of the word.
Now, arrange all the words based on the identified position.
Finally, put these arranged words back together to form the sorted sentence.

Code Implementation

def sort_the_sentence_brute_force(sentence):
    words = sentence.split()

    word_positions = {}
    for word in words:
        # Extract the number and the word without the number
        position = int(word[-1])
        actual_word = word[:-1]
        word_positions[position] = actual_word

    sorted_words = []
    # Arrange the words based on their identified positions
    for position_index in range(1, len(words) + 1):
        sorted_words.append(word_positions[position_index])

    #Join the sorted words to form the sorted sentence
    sorted_sentence = " ".join(sorted_words)
    return sorted_sentence

Big(O) Analysis

Time Complexity

O(n!) – Extracting words and identifying positions takes O(n) time, where n is the number of words. However, the brute force approach involves trying every possible arrangement of the words. There are n! (n factorial) possible permutations of n words. Constructing the sorted sentence from each permutation takes O(n) time. Therefore, the overall time complexity is dominated by the permutation generation, resulting in O(n * n!). Since n! grows much faster than n, we can simplify it to O(n!).

Space Complexity

O(N) – The space complexity is determined by the auxiliary space required to store the extracted words and their positions. Specifically, we need an array or list (of size N, where N is the number of words in the sentence) to hold each word in its correct sorted position after identifying the position from the trailing number. As the input sentence grows (more words), the array/list used to store the sorted words will grow linearly with it. Thus, the space complexity is O(N).

Optimal Solution

Approach

The sentence is jumbled, but each word contains a clue about its correct position. We can use these clues to directly place each word in its proper spot, building the sorted sentence efficiently.

Here's how the algorithm would work step-by-step:

Break the jumbled sentence into individual words.
For each word, look at the number at the end of it; this tells you its correct position in the sentence.
Put each word directly into its correct slot based on the number.
Once all the words are in their place, remove the numbers from each word.
Join the words back together with spaces in between, to form the sorted sentence.

Code Implementation

def sort_the_sentence(jumbled_sentence):
    words = jumbled_sentence.split()
    number_of_words = len(words)
    sorted_words = [""] * number_of_words

    # Place each word in its correct position based on the trailing number.
    for word in words:
        index = int(word[-1]) - 1
        sorted_words[index] = word[:-1]

    # Remove the numbers and build the sorted sentence.
    result = " ".join(sorted_words)

    return result

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the jumbled sentence to split it into n words, where n is the number of words. Then, it iterates through each word to extract the position number and place the word in its correct location in a new array. Finally, it iterates through the ordered words array to remove the number and join the words. Because each of these iterations is proportional to the number of words n and are done sequentially and not nested, the overall time complexity is O(n).

Space Complexity

O(N) – The algorithm creates an array of size N (where N is the number of words in the input sentence) to store the sorted words. This array acts as temporary storage to place each word at its correct index as determined by the number at the end of the word. Additionally, although not explicitly stated, string operations such as removing the trailing number can create temporary copies of strings, which in the worst case contributes to space proportional to N. Therefore the overall space complexity is O(N).

Edge Cases

Case	How to Handle
Empty input string	Return an empty string as there's nothing to sort.
Input string with only spaces	Trim the string first, then return an empty string if it becomes empty.
Missing number at the end of one or more words	Return the original potentially malformed string or throw an IllegalArgumentException.
Words with duplicate position numbers	The last word with the given number should overwrite any previous words with that number, resolving conflicts.
Out-of-order position numbers (e.g., 1 3 2)	The algorithm should correctly sort based on the numbers regardless of the initial order.
Large input string (performance considerations)	Utilize efficient string splitting and sorting algorithms to maintain acceptable performance for large inputs.
Numbers with leading zeros (e.g., word01)	Parse the number as an integer, which automatically removes the leading zeros.
Input string containing non-ASCII characters	The solution should correctly handle UTF-8 encoded characters.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the input string be empty or null?
Will the words in the input string always contain numbers from 1 to 9 indicating their position, and will those numbers always be at the end of the words?
Is it guaranteed that the numbers indicating word positions will be unique and within the valid range of word count?
Besides spaces and numbers, can the input string contain any other special characters or punctuation?
If the input string is malformed (e.g., missing a number, invalid number, or incorrect format), what should I return?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, separate each word from the sentence.
For each word, identify its position from the number located at the end of the word.
Now, arrange all the words based on the identified position.
Finally, put these arranged words back together to form the sorted sentence.

Code Implementation

def sort_the_sentence_brute_force(sentence):
    words = sentence.split()

    word_positions = {}
    for word in words:
        # Extract the number and the word without the number
        position = int(word[-1])
        actual_word = word[:-1]
        word_positions[position] = actual_word

    sorted_words = []
    # Arrange the words based on their identified positions
    for position_index in range(1, len(words) + 1):
        sorted_words.append(word_positions[position_index])

    #Join the sorted words to form the sorted sentence
    sorted_sentence = " ".join(sorted_words)
    return sorted_sentence

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

The sentence is jumbled, but each word contains a clue about its correct position. We can use these clues to directly place each word in its proper spot, building the sorted sentence efficiently.

Here's how the algorithm would work step-by-step:

Break the jumbled sentence into individual words.
For each word, look at the number at the end of it; this tells you its correct position in the sentence.
Put each word directly into its correct slot based on the number.
Once all the words are in their place, remove the numbers from each word.
Join the words back together with spaces in between, to form the sorted sentence.

Code Implementation

def sort_the_sentence(jumbled_sentence):
    words = jumbled_sentence.split()
    number_of_words = len(words)
    sorted_words = [""] * number_of_words

    # Place each word in its correct position based on the trailing number.
    for word in words:
        index = int(word[-1]) - 1
        sorted_words[index] = word[:-1]

    # Remove the numbers and build the sorted sentence.
    result = " ".join(sorted_words)

    return result

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty input string	Return an empty string as there's nothing to sort.
Input string with only spaces	Trim the string first, then return an empty string if it becomes empty.
Missing number at the end of one or more words	Return the original potentially malformed string or throw an IllegalArgumentException.
Words with duplicate position numbers	The last word with the given number should overwrite any previous words with that number, resolving conflicts.
Out-of-order position numbers (e.g., 1 3 2)	The algorithm should correctly sort based on the numbers regardless of the initial order.
Large input string (performance considerations)	Utilize efficient string splitting and sorting algorithms to maintain acceptable performance for large inputs.
Numbers with leading zeros (e.g., word01)	Parse the number as an integer, which automatically removes the leading zeros.
Input string containing non-ASCII characters	The solution should correctly handle UTF-8 encoded characters.