Author And Books

Easy
0/40
Average time to solve is 20m
profile
Contributed by
56 upvotes
Asked in companies
AdobeOptum

Problem statement

You are given a certain format of books and their authors.

For example -

NameOfAuthor1 Book1 Book2

NameOfAuthor2 Book1

Your task is to print the given information in the following manner:

1. NameOfAuthor1

    A. Book1

    B. Book2

2. NameOfAuthor2

    A. Book1

You are given a 2D array of strings ‘S’ where each vector is the information about the i-th author, the first index of this vector is the ‘NameOfAuthor’ and the other indexes are the ‘Books’ written by the author. You are supposed to print the Authors and their books in the above mentioned format.

Detailed explanation ( Input/output format, Notes, Images )

Input Format :

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

The first line of each test case contains one integer, ‘N’ denoting the number of authors. 

The next N’ lines contain a stream of strings, where the first token is an integer ‘M’ denoting the number of books, the second token is the ‘NameOfAuthor’ and the other space-separated strings are the ‘Books’ written by the author.

Output Format :

For each test case, you need to print an array of strings in which the first index of the array is the ‘NameOfAuthor1’ followed by the ‘Books’ written by this author(each book should be a separate string in the array) and the next index is the ‘NameOfAuthor2’ and the next indexes are the ‘Books’ written by this author and so on. 

Don’t care about indentation. It has been taken care of. But, the labels matter here.

Note :

You do not need to print anything. It has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 10
1 <= N <= 1000
1 <= |S| <= 100
1 <=  Number of books by each author <= 26

Time limit: 1 sec

Sample Input 1 :

2
2
4 ChetanBhagat TwoStates Revolution HalfGirlfriend OneIndianGirl
2 JKRowling HarryPotter FantasticBeasts
1
2 JeffreyArcher OldLove FalseImpression

Sample Output 1 :

1. ChetanBhagat
    A. TwoStates
    B. Revolution
    C. HalfGirlfriend
    D. OneIndianGirl 
2. JKRowling
    A. HarryPotter
    B. FantasticBeasts
1. JeffreyArcher
    A. OldLove 
    B. FalseImpression
Explanation for Sample Input 1 :
For, the first test case, the expected array to be returned is,
[“1. ChetanBhagat”, “B. Revolution”, “C. HalfGirlfriend”, “D. OneIndianGirl”,  “ 2. JKRowling
“, “A. HarryPotter”, “B. FantasticBeasts”]
For, the second test case the expected array to be returned is,
[“1. JeffreyArcher”, “A. OldLove”, “B. FalseImpression”].

Sample Input 2 :

2
1
2 RoaldDahl LambToTheSlaughter TheWitches
1
1 JhumpaLahiri ARealDurwan

Sample Output 2 :

1. RoaldDahl
    A. LambToTheSlaughter
    B. TheWitches
1. JhumpaLahiri
    A. ARealDurwan
Hint

Can you think of some pointers to take care of the labels.

Approaches (1)
Brute Force

The idea is to use an array of strings, which stores the information about the authors and the books written by them. Now, just iterate through the 2D array S and form the ans according to the rules mentioned.

 

The algorithm is as follows :

  • Declare an array of strings to store your ans.
  • Let N be the size of the given array S.
  • Iterate from i = 0 to N-1,
    • Declare a variable NameOfAuthor to string(i + 1).
    • Append, the string “. “ to NameOfAuthor.
    • Append, S[i][0] to NameOfAuthor.
    • Add NameOfAuthor to and.
    • Let M be the size of the current S[i].
    • Iterate from j = 1 to M-1,
      • Declare a string Book to (‘A’ + (j - 1)).
      • Append, the string “. “ to Book.
      • Append, S[i][j] to Book.
      • Append, Book to and.
  • Return the ans.
Time Complexity

O(N * |S|), where, N is the number of authors and |S| is the size of the 2D Array.

 

Here we are just iterating for each author, and traversing the books written by them. So, the overall time complexity is O(N * |S|).

Space Complexity

O(N * |S|), where, N is the number of authors and |S| is the size of the 2D Array.

 

We are using an array ans which can have a maximum space of order N * |S|. Hence, the overall space complexity is O(N * |S|).

Code Solution
(100% EXP penalty)
Author And Books
Full screen
Console