Rearrange Sentences

Easy
0/40
Average time to solve is 10m
profile
Contributed by
22 upvotes
Asked in company
Ola

Problem statement

You are given an array of ‘N’ sentences. Each sentence is a space-delimited string of words. The first word in each sentence is an alphanumeric identifier. Then, at least one of the following conditions will hold true:

1. After identifier, each word will consist only of lowercase English letters
2. After the identifier, each word will consist only of numbers.

We will call these two types of sentences, letter – sentence and number– sentence. It is guaranteed that each sentence has at least one word after its identifier. Your task is to sort these sentences such that the following two conditions will hold.

1. All letter - sentences must come before number- sentences.
2. The letter - sentences must be ordered lexicographically ignoring identifiers. The identifier will be used in case of ties.
3. The number– sentence must be put in their original order of occurrence.
Detailed explanation ( Input/output format, Notes, Images )
Input format : 
The first line of input contains a single integer 'T', representing the number of test cases or queries to be run. 
Then the 'T' test cases follow. 
The first line of each test case contains an integer 'N'.    
Then 'N' lines follow.
Each line contains a single string, representing the sentence of the array.
Output format : 
For each test case, print 'N' lines.    
Then 'N' lines follow.
Each line will contain a single string, representing a sentence of the array in sorted order as mentioned in the description.

Print the output of each test case in a separate line
Constraints : 
1 <= T <= 10
0 <= N <= 1000  
3 <= |S| <= 100 

Where 'T' denotes the number of test cases, 'N' denotes the number of sentences, and |S| denotes the length of sentence, S.

Time Limit: 1 sec
Note: 
You do not need to print anything, it has already been taken care of. Just implement the given function.
Sample Input 1 :
2
3
d1 2 3
love8 coding world
a1 coding ninjas 
3 
rating1 2143 1706
g1 raone 
avengers1 assemble
Sample Output 1 :
a1 coding ninjas
love8 coding world
d1 2 3
avengers1 assemble
g1 raone
rating1 2143 1706
Explanation for sample input1:
For the first test case, 
Letter sentences are [“love8 coding world”,   “a1 coding ninjas”], and number sentences are [“d1 2 3”]
Sorted order of letter sentences = [“a1 coding ninjas”, “love8 coding world”]
The original order of number sentences =[“d1 2 3”]
So the answer is [“a1 coding ninjas”, “love8 coding world”, “d1 2 3”].

For the second test case:
Letter sentences are [“g1 raone”,  “avengers1 assemble”], and number sentences are [“rating1 2143 1706”]
Sorted order of letter sentences = [“avengers1 assemble”, “g1 raone”].
Original order of number sentences = [ “rating1 2143 1706”]
So the answer is [“avengers1 assemble” , “g1 raone” , “rating1 2143 1706”]
Sample Input 2 :
1
4
wait8 opportunity is coming
coding24 7 365
coding1 2 3 4 5
goodluck2 you my friend
Sample Output 2 :
wait8 opportunity is coming
goodluck2 you my friend
coding24 7 365 
coding1 2 3 4 5
Explanation for sample input2:
For the first test case:
Letter sentences are [“wait8 opportunity is coming”,  “goodluck2 you my friend”], and number sentences are [  “coding24 7 365”, “coding1 2 3 4 5”].
Sorted order of letter sentences = [“wait8 opportunity is coming”, “goodluck2 you my friend”].
Original order of number sentences =[“coding24 7 365”, “coding1 2 3 4 5”].
So the answer is [“wait8 opportunity is coming”, “goodluck2 you my friend”, “coding24 7 365”, “coding1 2 3 4 5”].
Hint

Think of a solution using brute force.

Approaches (2)
Brute force

In this solution, the idea is to always pick the smallest letter sentence which is currently available in our list/array and add it to the answer. If there is no letter sentence available in the current list/array then add remaining number sentences to answer.

Below is the implementation of the above approach :

  1. Declare an empty array of strings, say the answer.
  2. Pick the smallest available letter sentence from a given array of sentences. Let’s called it small.
  3. Add this small to answer.
  4. Remove small from the original list.
  5. Repeat steps 2,3 and 4 until there is no letter sentence left.
  6. Add remaining number sentences to answer.
  7. Finally, return the answer.
Time Complexity

O(N^2 * M), where N is the length of the given array of sentences and M is the maximum length of sentence available in an array.

 

Comparing two sentences takes M time and picking the smallest sentence takes O(N) time. In the worst case, we need to pick the smallest sentence O(N) times. So O(N) * O(N) *M = O(N^2 * M). Hence the overall complexity will be O(N^2 * M). 

Space Complexity

O(N), where N is the length of the given array of sentences.

 

In the worst case, extra space is required for the visited array. Hence the overall space complexity will be O(N).

Code Solution
(100% EXP penalty)
Rearrange Sentences
Full screen
Console