Rearrange words in a sentence
You are given a sentence 'TEXT'. Each word of 'TEXT' is separated by a single space and the first letter of 'TEXT' is capital. You need to rearrange the words of Text in increasing order of their length.

Note:

If two words have the same length then the word which comes first in 'TEXT' also comes first in the rearranged sentence.

Input format:

The first line of input contains an integer 'T' denoting the number of test cases. The first line of each test case contains a single sentence 'TEXT'.

Output Format:

For each test case, return the rearranged sentence.

Constraints:

1

Question

Rearrange words in a sentence

You are given a sentence 'TEXT'. Each word of 'TEXT' is separated by a single space and the first letter of 'TEXT' is capital. You need to rearrange the words of Text in increasing order of their length.

Note:

If two words have the same length then the word which comes first in 'TEXT' also comes first in the rearranged sentence.

Input format:

The first line of input contains an integer 'T' denoting the number of test cases. 

The first line of each test case contains a single sentence 'TEXT'.

Output Format:

For each test case, return the rearranged sentence.

Constraints:

1 <= T <= 5
1 <= | TEXT | <= 10^5

Where | 'TEXT' | denotes the length of the 'TEXT' sentence.

Time limit: 1 sec

Accepted Answer

Step 1 : Remove the capital letter (first letter of the sentence) and the full stop at the end.
Step 2 : I made use of the C++ STL library. I made a pair of strings and int where the string is the word and int is the position of the word in the sentence. These pairs were stored in a vector. I sorted the vector using the sort function of C++ STL and utilizing a custom comparison function to arrange the pairs according to string.length and if string.length was equal, arrange according to the second element of the pair.
Step 3 : The sorted vector contains the order of words in the sentence. Join all the words and capitalize the first letter and add full stop.

Accepted Answer

Using Sorting

The idea is to create an array of pairs, ‘WORD’, of size ‘N’. Where the first element of pair is word length and the second element is the starting index of word.

Now, start iterating over ‘TEXT’ starting from index 0 and maintain a variable ‘currentStart’ to store the starting index of the current word. Whenever you encounter space(“ “) say at index ‘C’, it means your current word starting from index ‘currentStart’ ends at index ‘C’ - 1 and its length is c - ‘currentStart’. Insert the pair { ‘C’ - ‘currentStart’, ‘currentStart' } in your 'WORD' array and update 'currentStart' with ‘C’ + 1 ( the starting index of next word). Repeat steps till the string ends.

Now, sort the 'WORD' array in increasing order of word length, if word length is the same for two words then sort them in increasing order of their starting index.

For example: Consider the Text is “Coding is fun”.
Now the Word array for this Text is = [{6,0}, {2,7}, {3,10}]. After sorting it becomes [{2,7}, {3,10}, {6,0}].

Now iterate over the 'WORD' array and for each ‘WORD[i]’ with value {a ,b}, start inserting characters of original text starting from index b and till index a + b - 1 ( as word length is a ) in your answer sentence say 'ANS'.

Make the first character of 'ANS' capital and return ‘ANS’.

Space Complexity: O(1)Explanation:

O(N), Where ‘N’ is the length of Text.

Since we are creating a Word array of size N / 2 (when the length of each word is 1). Thus the space complexity will be O(N).

Time Complexity: O(nlogn)Explanation:

O( N * logN ), Where ‘N’ is the length of Text.

Since we are traversing the input text once which takes O(N) time and we are sorting the Word array of size L which takes O(L * log(L)) time where L is the number of words in Text.In the worst case, number of words can be N / 2 so sorting Word array takes O(N * logN). Thus the final time complexity is O(N) + O(N * log(N)) = O(N * log(N)).

You are given a sentence 'TEXT'. Each word of 'TEXT' is separated by a single space and the first letter of 'TEXT' is capital. You need to rearrange the words of Text in increasing order of their length.

Note:

Input format:

Output Format:

Constraints:

Top JPMorgan Chase & Co. Software Developer Intern interview questions & answers

Popular interview questions of Software Developer Intern

Top HR questions asked in JPMorgan Chase & Co. Software Developer Intern