We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Reorder Data in Log Files

Difficulty: Medium

Problem Description

You are given an array of logs. Each log is a space-delimited string of words, where the first word is the identifier. There are two types of logs: Letter-logs and Digit-logs. Reorder these logs so that the Letter-logs come before all Digit-logs, the Letter-logs are sorted lexicographically by their contents, and the Digit-logs maintain their relative ordering.

Key Insights

  • Identify the two types of logs: Letter-logs and Digit-logs.
  • Letter-logs need to be sorted by their contents and then by their identifiers if contents are the same.
  • Digit-logs should retain their original order.
  • Efficient sorting and classification of logs is crucial for solving this problem.

Space and Time Complexity

Time Complexity: O(n log n), where n is the number of logs (due to sorting). Space Complexity: O(n), since we may need additional space to store the sorted logs.

Solution

To solve the problem, we can use a two-step approach:

  1. Separate the logs into Letter-logs and Digit-logs.
  2. Sort the Letter-logs based on their contents and identifiers.
  3. Concatenate the sorted Letter-logs with the original list of Digit-logs to maintain their order.

This can be efficiently implemented using lists and custom sorting mechanisms.

Code Solutions

def reorderLogs(logs):
    # Separate the logs into letter-logs and digit-logs
    letter_logs = []
    digit_logs = []
    
    for log in logs:
        if log.split()[1].isdigit():
            digit_logs.append(log)
        else:
            letter_logs.append(log)
    
    # Sort the letter-logs by content and identifier
    letter_logs.sort(key=lambda x: (x.split()[1:], x.split()[0]))
    
    # Concatenate letter-logs and digit-logs
    return letter_logs + digit_logs
← Back to All Questions