Sort Big List Dates
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] ]

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

Question

Sort Big List Dates

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] ]

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

Accepted Answer

Custom sorting can be used here. Extract the days, months and years as sub-strings from the string then compare two strings by years, if years for two dates are equal then compare their months. If months are also equal than the days will decide which date appears earlier in the calendar.

Time Complexity: O(N * log(N))
Auxiliary Space: O(1)

Accepted Answer

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.

Space Complexity: O(n)Explanation:

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).

Time Complexity: O(nlogn)Explanation:

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)).

Java (SE 1.8)


/*
	Time Complexity: O(N*(log(N)))
	Space Complexity: O(N)
	
	Where N is the number of elements in array
*/
import java.util.Arrays;

public class Solution {
	public static int[][] sortBigListDates(int[][] dates) {
		// Sort the array dates based on comp as comparator

		Arrays.sort(dates, new java.util.Comparator() {
			public int compare(int date1[], int date2[]) {
				// Comparing by year
				if (date1[2] != date2[2]) {

					if (date1[2] < date2[2]) {
						return -1;
					} else {
						return 1;
					}
				}

				// Comparing by month
				if (date1[1] != date2[1]) {
					if (date1[1] < date2[1]) {
						return -1;
					} else {
						return 1;
					}
				}

				// Comparing by Day
				if (date1[0] < date2[0]) {
					return -1;
				} else {
					return 1;
				}
			}
		});
		return dates;
	}

}

C++ (g++ 5.4)

/*

    Time Complexity: O(N*(log(N)))

    Space Complexity: O(N)



    Where N is the number of elements in array

*/



#include 



bool comp(vector const &date1, vector const &date2) 

{

    // Comparing by year

    if (date1[2] != date2[2]) 

    {

        return date1[2] < date2[2];

    }



    // Comparing by month    

    if (date1[1] != date2[1]) 

    {

        return date1[1] < date2[1];

    }



    // Comparing by Day    

    return date1[0] < date2[0];

}



vector> sortBigListDates(vector> &dates)

{

    // Sort the array dates based on comp as comparator

    sort(dates.begin(), dates.end(), comp);



    return dates;

}

Python (3.5)

"""

    Time Complexity: O(N*(log(N)))

    Space Complexity: O(N)



    Where N is the number of elements in array

"""



from functools import cmp_to_key



def comp(date1, date2):



    # Comparing by year

    # Check if date1 year is less than date2 year,return -1

    if(date1[2] < date2[2]):

        return -1



    # Check if date1 year is greater than date2 year,return 1

    elif(date1[2] > date2[2]):

        return 1



    # Comparing by month

    if(date1[1] < date2[1]):

        return -1



    elif(date1[1] > date2[1]):

        return 1



    # Comparing by Day

    if(date1[0] < date2[0]):

        return -1

        

    elif(date1[0] > date2[0]):

        return 1



    return 1





def sortBigListDates(dates):



    # Sort the array dates based on comp as comparator

    dates = sorted(dates, key=cmp_to_key(comp))



    return dates

Accepted Answer

Using Counting Sort

In this approach, we will use Counting Sort to sort the array. The Counting Sort is a non-comparison-based sorting method with linear time complexity. It is usually used with arrays whose values lie in a particular range. It simply counts each element's occurrences and then rearranges the array according to the frequencies.

Algorithm:

Counting Sort:
- Make a function for implementing countSort(dates, par, maxVal), where dates are the given array, par is the parameter used for sorting, and maxValue is the maximum value of the parameter.
- Initialize an array to store the frequency of all elements in the array.
- For each element in the array, do freq[i]=freq[i]+freq[i-1] to find the index of the element in the sorted array.
- Initialize a Sorted Array and use this frequency array to build up our sorted array.
- Copy the sorted array to the original array.
We will first sort by day by updating dates as countSort(dates, 0, 31) using this counting sort function.
We will now sort by month by updating dates as countSort(dates, 1, 12).
We will now sort by year by updating dates as countSort(dates, 2, 2100).

In the end, we will return the sorted array dates.

Space Complexity: O(n)Explanation:

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

The space complexity O(N) is used to store the output array in the counting sort function. Hence, the overall space complexity is O(N).

Time Complexity: O(n)Explanation:

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

We are traversing the whole array while storing the frequency and copying the sorted array to the original array that takes O(N) time. So the overall time complexity is O(N).

C++ (g++ 5.4)

/*

    Time Complexity: O(N)

    Space Complexity: O(N)



    Where N is the number of elements in array

*/



// Counting Sort function

vector> countSort(vector> &dates, int par, int maxVal) 

{

    vector freq(maxVal + 1, 0);

    int n = dates.size();    

    vector> sortedDates(n, vector  (3, 0));



    for (int i = 0; i < n; i++) 

    {

        freq[dates[i][par]] += 1;

    }



    // Update freq array to find the actual position of elements in sorted array.

    for (int i = 1; i < maxVal + 1; i++) 

    {

        freq[i] += freq[i - 1];

    }



    for (int i = n - 1; i >= 0; i--) 

    {

        // Buliding up the sorted array using freq array.

        sortedDates[freq[dates[i][par]] - 1] = dates[i];



        // Decrementing Frequency.

        freq[dates[i][par]] -= 1;

    }



    // Copying the array to the original array.

    for (int i = 0; i < n; i++) 

    {

        dates[i] = sortedDates[i];

    }



    return dates;

}



vector> sortBigListDates(vector> &dates) 

{

    // Sorting by day.

    dates = countSort(dates, 0, 31);



    // Sorting by month.

    dates = countSort(dates, 1, 12);



    // Sorting by year.

    dates = countSort(dates, 2, 2100);



    return dates;

}

Java (SE 1.8)


/*
	Time Complexity: O(N)
	Space Complexity: O(N)
	
	Where N is the number of elements in array
*/
import java.util.Arrays;

public class Solution {
	public static int[][] countSort(int[][] dates, int par, int maxVal) {
		int[] freq = new int[maxVal + 1];
		Arrays.fill(freq, 0);
		int n = dates.length;
		int sortedDates[][] = new int[n][3];

		for (int i = 0; i < n; i++) {
			freq[dates[i][par]] += 1;
		}

		// Update freq array to find the actual position of elements in sorted array.
		for (int i = 1; i < maxVal + 1; i++) {
			freq[i] += freq[i - 1];
		}

		for (int i = n - 1; i >= 0; i--) {

			// Buliding up the sorted array using freq array.
			sortedDates[freq[dates[i][par]] - 1] = dates[i];

			// Decrementing Frequency.
			freq[dates[i][par]] -= 1;
		}

		// Copying the array to the original array.
		for (int i = 0; i < n; i++) {
			dates[i] = sortedDates[i];
		}

		return dates;

	}

	public static int[][] sortBigListDates(int[][] dates) {

		// Sorting by day.
		dates = countSort(dates, 0, 31);

		// Sorting by month.
		dates = countSort(dates, 1, 12);

		// Sorting by year.
		dates = countSort(dates, 2, 2100);

		return dates;
	}

}

Python (3.5)

"""

    Time Complexity: O(N)

    Space Complexity: O(N)



    Where N is the number of elements in array

"""



# Counting Sort function

def countSort(dates, par, maxVal):



    freq = [0 for i in range(maxVal + 1)]

    n = len(dates)

    sortedDates = [[0, 0, 0] for i in range(n)]



    for i in range(n):

        freq[dates[i][par]] += 1



    # Update freq array to find the actual position of elements in sorted array.

    for i in range(1, maxVal + 1):

        freq[i] += freq[i - 1]



    for i in range(n - 1, -1, -1):



        # Buliding up the sorted array using freq array.

        sortedDates[freq[dates[i][par]] - 1] = dates[i]



        # Decrementing Frequency.

        freq[dates[i][par]] -= 1



    # Copying the array to the original array.

    for i in range(n):

        dates[i] = sortedDates[i]



    return dates





def sortBigListDates(dates):



    # Sorting by day.

    dates = countSort(dates, 0, 31)



    # Sorting by month.

    dates = countSort(dates, 1, 12)



    # Sorting by year.

    dates = countSort(dates, 2, 2100)



    return dates

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:

Input Format:

Output Format:

Note:

Constraints:

Top Morgan Stanley Software Developer interview questions & answers

Popular interview questions of Software Developer

Top HR questions asked in Morgan Stanley Software Developer