Sort Big List Dates

Moderate
0/80
Average time to solve is 20m
8 upvotes
Asked in companies
Morgan StanleyJosh Technology Group

Problem statement

Mary is a party-loving girl of the 21st Generation. She loves to attend parties and events with her family and friends. But she is terrible at remembering the dates of these events.

Mary has a list of dates of these events. Can you help her sort the list of dates to be easier for Mary to track the parties?

You are given an array ‘dates’ consisting of ‘N’ dates. You have to sort this array and print the array in sorted order.

For example: 
If dates= [ [13,6,2007] , [2,6,2001] , [10,8,2019] , [1,6,2007] ]
Sorted Order of Dates will be :
dates = [ [ 2,6,2001] , [1,6,2007] , [13,6,2007] ]
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of the input contains an integer, 'T,’ denoting the number of test cases.
The first line of each test case contains a single integer, 'N,’ denoting the number of dates in the array.
The Next ‘N’ lines of each test case have three integers corresponding to date, month, and year.
Output Format: 
For each test case, print ‘N’ lines for the sorted list elements, each line has three integers corresponding to date, month, and year.

Print the output of each test case in a separate line.
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 <= 10^6
1 <= dates[i][0] <= 31
1 <= dates[i][1] <=12
2000 <= dates[i][2] <=2099


Time limit: 1 sec
Sample Input 1:
2
3    
21 6 2011
11 4 2009
17 8 2009 
3
1 1 2002
31 10 2005
10 8 2003
Sample Output 1:
11 4 2009
17 8 2009
21 6 2011
1 1 2002
10 8 2003
31 10 2005
Explanation of sample input 1:
For the first test case, 
The sorted list of the dates of events will be: [‘11 April 2009’, ‘17 August 2009’, ‘21 June 2011’]. Hence, the answer of this testcase is  [ [ 11,4,2009] , [17,8,2009] , [21,6,2011] ].

For the second test case,
The sorted list of the dates of events will be: [‘1 January 2002’, ‘10 August 2003’, ‘31 October 2011’]. Hence, the answer of this testcase is  [ [ 1,1,2002] , [10,8,2003] , [31,10,2005] ].
Sample Input 2:
2
3
14 5 2008
16 1 2001
23 3 2098
4
15 7 2000
21 4 2005
29 2 2004
30 12 2001
Sample Output 2:
16 1 2001
14 5 2008
23 3 2098
15 7 2000
30 12 2001
29 2 2004
21 4 2005
Hint

Can you use an inbuilt sort function to solve this problem?

Approaches (2)
Using Inbuilt Sort function

In this approach, we will sort the array using Inbuild Sort with the help of a Comparator. 

A Comparator is a custom compare function that decides the order of sorting by conditions defined by the programmer. It takes two arguments of the same datatype as the list element and returns a value whether the first argument will appear in the sorted array first or the second parameter. The Comparator will help us decide the relative positioning of elements in the sorted array. 

 

Algorithm:

 

  • We will define a comparator function with two dates, date1 and date2, as parameters.
    • First, we will compare by year, and if date1[2] is less than date2[2], then in the sorted list, date2 should appear after date1.
    • If date1[2] is greater than date2[2], then in the sorted list, date1 should appear after date2. 
    • If the year is equal, we will compare by month, and if date1[1] is less than date2[1], then in the sorted list, date2 should appear after date1.
    • If date1[1] is greater than date2[1], then in the sorted list, date1 should appear after date2.
    • If the month is equal, we will compare by day, and if date1[0] is less than date2[0], then in the sorted list, date2 should appear after date1.
    • If date1[0] is greater than date2[0],then in sorted list date1 should appear after date2.
  • Call the inbuilt sort function with the comparator and sort the list.
  • In the end, we will return the sorted array.
Time Complexity

O(N*log(N)), where N is the number of elements in the array.

 

The implementation of the Inbuilt Sorting function is Merge Sort, and its time complexity is O(N*log(N)). Hence, the overall time complexity is O(N*log(N)).

Space Complexity

O(N), where N is the number of elements in the array.

 

The O(N) space is used in Merge sort while merging the array. Hence, the overall space complexity is O(N).

Code Solution
(100% EXP penalty)
Sort Big List Dates
Full screen
Console