Jobs

Interviews

Discussions

Reformat Date #3 Most Asked

Easy

Twilio

5 views

Topics:

Strings

Given a date string in the form Day Month Year, where:

Day is in the set {"1st", "2nd", "3rd", "4th", ..., "30th", "31st"}.
Month is in the set {"Jan", "Feb", "Mar", "Apr", "May", "Jun", "Jul", "Aug", "Sep", "Oct", "Nov", "Dec"}.
Year is in the range [1900, 2100].

Convert the date string to the format YYYY-MM-DD, where:

YYYY denotes the 4 digit year.
MM denotes the 2 digit month.
DD denotes the 2 digit day.

Example 1:

Input: date = "20th Oct 2052"
Output: "2052-10-20"

Example 2:

Input: date = "6th Jun 1933"
Output: "1933-06-06"

Example 3:

Input: date = "26th May 1960"
Output: "1960-05-26"

Constraints:

The given dates are guaranteed to be valid, so no error handling is necessary.

Try coding it in LeetCode

Reformat Date #3 Most Asked

Easy

Twilio

5 views

Topics:

Strings

Given a date string in the form Day Month Year, where:

Day is in the set {"1st", "2nd", "3rd", "4th", ..., "30th", "31st"}.
Month is in the set {"Jan", "Feb", "Mar", "Apr", "May", "Jun", "Jul", "Aug", "Sep", "Oct", "Nov", "Dec"}.
Year is in the range [1900, 2100].

Convert the date string to the format YYYY-MM-DD, where:

YYYY denotes the 4 digit year.
MM denotes the 2 digit month.
DD denotes the 2 digit day.

Example 1:

Input: date = "20th Oct 2052"
Output: "2052-10-20"

Example 2:

Input: date = "6th Jun 1933"
Output: "1933-06-06"

Example 3:

Input: date = "26th May 1960"
Output: "1960-05-26"

Constraints:

The given dates are guaranteed to be valid, so no error handling is necessary.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Is the input date string guaranteed to always be in the specified 'Day Month Year' format, and can I assume it's a valid date?
What should I return if the input date string is null or empty?
Is the year always a four-digit number within the range [1900, 2100], or could it have leading zeros or be outside this range?
Are there any locale considerations for the month names (e.g., will they always be in English)?
Is it acceptable to use built-in date parsing libraries, or should I implement the date conversion manually?

Brute Force Solution

Approach

The brute force method for reformatting a date involves checking all possible valid arrangements. We will have a way to convert the given date string into its components, and then create a valid output date string. We simply test every possible date combination that could be valid and pick the correct one.

Here's how the algorithm would work step-by-step:

First, separate the given date string into three parts: the day, the month, and the year.
Create a list containing all possible valid months (January, February, March, etc.).
Check if the month part of the original date matches one of the months in your list.
Convert the day part of the original date from a string to a number.
Check to make sure the day number is within the valid range of days for that month, considering leap years if needed.
Put the year, month (in numerical format), and day together in the required output format.
If all checks pass, you have a valid reformatting of the date and return that reformatted date.

Code Implementation

def reformat_date(date):
    day_string, month_string, year_string = date.split()
    
    month_list = ["January", "February", "March", "April", "May", "June", 
                  "July", "August", "September", "October", "November", "December"]
    
    # Find the month number corresponding to month_string
    month_number = month_list.index(month_string) + 1

    # Convert the day_string to an integer and remove suffix
    day_number = int(day_string[:-2])

    # Construct the reformatted date string
    reformatted_date = f"{year_string}-month_number:02}-day_number:02}"

    return reformatted_date

Big(O) Analysis

Time Complexity

O(1) – The algorithm parses the date string into day, month, and year. The month lookup uses a fixed-size list of 12 months, meaning the lookup is constant time. Converting the day string to a number and validating it also takes constant time. The final combination of year, numerical month, and day also takes constant time. Therefore, the overall time complexity is O(1) because the operations performed do not depend on the size of an input 'n'.

Space Complexity

O(1) – The algorithm uses a list of months, which has a fixed size of 12, independent of the input date string's length. It also uses a few variables to store the day, month, and year components, as well as the reformatted date, but the number of these variables remains constant. Therefore, the auxiliary space used does not scale with the input size N (where N is the length of the input date string), resulting in constant space complexity.

Optimal Solution

Approach

The optimal approach involves converting the given date string into a standardized format. We achieve this by extracting the day, month, and year components and then rearranging them into the desired format using a lookup for month names.

Here's how the algorithm would work step-by-step:

First, separate the date string into its three parts: the day, the month, and the year.
Create a way to convert the month name (like 'Jan', 'Feb', etc.) into its numerical representation (like '01', '02', etc.). This could be something that looks up the number when you provide the month name.
Remove any extra endings from the day (like 'st', 'nd', 'rd', 'th'). You want just the number.
If the day is a single digit, add a zero in front of it to make it two digits (for example, '1' becomes '01').
Finally, put the year, month (in number format), and day together in the correct order, separated by dashes. This new string is the reformatted date.

Code Implementation

def reformat_date(date):
    date_components = date.split()
    day = date_components[0]
    month = date_components[1]
    year = date_components[2]

    month_map = {
        'Jan': '01', 'Feb': '02', 'Mar': '03',
        'Apr': '04', 'May': '05', 'Jun': '06',
        'Jul': '07', 'Aug': '08', 'Sep': '09',
        'Oct': '10', 'Nov': '11', 'Dec': '12'
    }

    # Convert the month from name to numerical representation
    month_number = month_map[month]

    day_number = ''.join(filter(str.isdigit, day))

    # Add leading zero if the day is a single digit
    if len(day_number) == 1:
        day_number = '0' + day_number

    # Construct the reformatted date string
    reformatted_date = year + '-' + month_number + '-' + day_number

    return reformatted_date

Big(O) Analysis

Time Complexity

O(1) – The algorithm operates on a date string that always has a fixed format and length. Extracting day, month, and year involves constant-time string manipulation. The month lookup uses a fixed-size data structure. The day processing and final string construction also take constant time. Since the input size is bounded and operations are independent of a growing input, the time complexity is O(1).

Space Complexity

O(1) – The described solution uses a constant amount of extra space. The primary driver of space complexity is the month name lookup, which is a fixed-size mapping (e.g., a hash map or array) of 12 month names to their numerical representations; this size is independent of the input date string length. Additionally, constant space is used for storing the day, month, and year strings after splitting, as well as the final reformatted date string which at most depends on the characters already present in the input date, thus not scaling with a hypothetical input length N. Therefore, the space complexity is O(1).

Edge Cases

Case	How to Handle
Null or empty input string	Return an empty string or throw an IllegalArgumentException, depending on desired behavior.
Invalid Day format (e.g., '1th', '32nd')	Implement validation for correct day suffixes and valid day numbers, potentially throwing an exception.
Invalid Month format (e.g., 'Jann', 'Foo')	Use a map or a fixed array to validate the month string against a predefined set of valid month names, throwing an exception otherwise.
Invalid Year format (e.g., '1899', '2101', 'abc')	Check if the year is within the range [1900, 2100] and is a valid integer, throwing an exception if not.
Date string with extra spaces or leading/trailing spaces	Trim the input string and split the string into its parts based on a single space delimiter.
Incorrect number of components in the date string (more or less than three parts)	Check the number of parts after splitting the input string and return an appropriate error or handle the exception gracefully.
Leap year day handling (Feb 29th in non-leap years)	While this problem does not ask to validate if the date is a real date, this would be part of a production validation implementation to handle edge cases like invalid dates.
Day having single digit number (e.g., 1st).	Pad the day with a leading zero if it's a single digit number after removing the suffix.

Null or empty input string

How to Handle:

Return an empty string or throw an IllegalArgumentException, depending on desired behavior.

Invalid Day format (e.g., '1th', '32nd')

How to Handle:

Implement validation for correct day suffixes and valid day numbers, potentially throwing an exception.

Invalid Month format (e.g., 'Jann', 'Foo')

How to Handle:

Use a map or a fixed array to validate the month string against a predefined set of valid month names, throwing an exception otherwise.

Invalid Year format (e.g., '1899', '2101', 'abc')

How to Handle:

Check if the year is within the range [1900, 2100] and is a valid integer, throwing an exception if not.

Date string with extra spaces or leading/trailing spaces

How to Handle:

Trim the input string and split the string into its parts based on a single space delimiter.

Incorrect number of components in the date string (more or less than three parts)

How to Handle:

Check the number of parts after splitting the input string and return an appropriate error or handle the exception gracefully.

Leap year day handling (Feb 29th in non-leap years)

How to Handle:

While this problem does not ask to validate if the date is a *real* date, this would be part of a production validation implementation to handle edge cases like invalid dates.

Day having single digit number (e.g., 1st).

How to Handle:

Pad the day with a leading zero if it's a single digit number after removing the suffix.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Is the input date string guaranteed to always be in the specified 'Day Month Year' format, and can I assume it's a valid date?
What should I return if the input date string is null or empty?
Is the year always a four-digit number within the range [1900, 2100], or could it have leading zeros or be outside this range?
Are there any locale considerations for the month names (e.g., will they always be in English)?
Is it acceptable to use built-in date parsing libraries, or should I implement the date conversion manually?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, separate the given date string into three parts: the day, the month, and the year.
Create a list containing all possible valid months (January, February, March, etc.).
Check if the month part of the original date matches one of the months in your list.
Convert the day part of the original date from a string to a number.
Check to make sure the day number is within the valid range of days for that month, considering leap years if needed.
Put the year, month (in numerical format), and day together in the required output format.
If all checks pass, you have a valid reformatting of the date and return that reformatted date.

Code Implementation

def reformat_date(date):
    day_string, month_string, year_string = date.split()
    
    month_list = ["January", "February", "March", "April", "May", "June", 
                  "July", "August", "September", "October", "November", "December"]
    
    # Find the month number corresponding to month_string
    month_number = month_list.index(month_string) + 1

    # Convert the day_string to an integer and remove suffix
    day_number = int(day_string[:-2])

    # Construct the reformatted date string
    reformatted_date = f"{year_string}-month_number:02}-day_number:02}"

    return reformatted_date

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, separate the date string into its three parts: the day, the month, and the year.
Create a way to convert the month name (like 'Jan', 'Feb', etc.) into its numerical representation (like '01', '02', etc.). This could be something that looks up the number when you provide the month name.
Remove any extra endings from the day (like 'st', 'nd', 'rd', 'th'). You want just the number.
If the day is a single digit, add a zero in front of it to make it two digits (for example, '1' becomes '01').
Finally, put the year, month (in number format), and day together in the correct order, separated by dashes. This new string is the reformatted date.

Code Implementation

def reformat_date(date):
    date_components = date.split()
    day = date_components[0]
    month = date_components[1]
    year = date_components[2]

    month_map = {
        'Jan': '01', 'Feb': '02', 'Mar': '03',
        'Apr': '04', 'May': '05', 'Jun': '06',
        'Jul': '07', 'Aug': '08', 'Sep': '09',
        'Oct': '10', 'Nov': '11', 'Dec': '12'
    }

    # Convert the month from name to numerical representation
    month_number = month_map[month]

    day_number = ''.join(filter(str.isdigit, day))

    # Add leading zero if the day is a single digit
    if len(day_number) == 1:
        day_number = '0' + day_number

    # Construct the reformatted date string
    reformatted_date = year + '-' + month_number + '-' + day_number

    return reformatted_date

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input string	Return an empty string or throw an IllegalArgumentException, depending on desired behavior.
Invalid Day format (e.g., '1th', '32nd')	Implement validation for correct day suffixes and valid day numbers, potentially throwing an exception.
Invalid Month format (e.g., 'Jann', 'Foo')	Use a map or a fixed array to validate the month string against a predefined set of valid month names, throwing an exception otherwise.
Invalid Year format (e.g., '1899', '2101', 'abc')	Check if the year is within the range [1900, 2100] and is a valid integer, throwing an exception if not.
Date string with extra spaces or leading/trailing spaces	Trim the input string and split the string into its parts based on a single space delimiter.
Incorrect number of components in the date string (more or less than three parts)	Check the number of parts after splitting the input string and return an appropriate error or handle the exception gracefully.
Leap year day handling (Feb 29th in non-leap years)	While this problem does not ask to validate if the date is a real date, this would be part of a production validation implementation to handle edge cases like invalid dates.
Day having single digit number (e.g., 1st).	Pad the day with a leading zero if it's a single digit number after removing the suffix.

Null or empty input string

How to Handle:

Return an empty string or throw an IllegalArgumentException, depending on desired behavior.

Invalid Day format (e.g., '1th', '32nd')

How to Handle:

Implement validation for correct day suffixes and valid day numbers, potentially throwing an exception.

Invalid Month format (e.g., 'Jann', 'Foo')

How to Handle:

Use a map or a fixed array to validate the month string against a predefined set of valid month names, throwing an exception otherwise.

Invalid Year format (e.g., '1899', '2101', 'abc')

How to Handle:

Check if the year is within the range [1900, 2100] and is a valid integer, throwing an exception if not.

Date string with extra spaces or leading/trailing spaces

How to Handle:

Trim the input string and split the string into its parts based on a single space delimiter.

Incorrect number of components in the date string (more or less than three parts)

How to Handle:

Check the number of parts after splitting the input string and return an appropriate error or handle the exception gracefully.

Leap year day handling (Feb 29th in non-leap years)

How to Handle:

While this problem does not ask to validate if the date is a *real* date, this would be part of a production validation implementation to handle edge cases like invalid dates.

Day having single digit number (e.g., 1st).

How to Handle:

Pad the day with a leading zero if it's a single digit number after removing the suffix.

0/0 Twilio questions completed

0/0 completed