Reorder Data in Log Files

Medium
1211.

Reorder Data in Log Files

Reorder Data in Log Files is a medium coding problem on arrays, strings and sorting, asked in Amazon and Microsoft interviews.

Each log is a string of space-separated words; the first word is the log's identifier (lowercase letters and digits). There are two kinds of logs:

  • letter-logs — every word after the identifier consists of lowercase letters;
  • digit-logs — every word after the identifier consists of digits.

Reorder the logs so that:

  1. all letter-logs come before all digit-logs;
  2. letter-logs are sorted by their contents (everything after the identifier); logs with equal contents are sorted by identifier — both by plain character comparison;
  3. digit-logs keep their original relative order.

Return the reordered list.

Example 1

Input
logs = ["k1 duel won","x9 7 3 1","a2 pair mode","b4 0 2","c3 duel won"]
Output
["c3 duel won","k1 duel won","a2 pair mode","x9 7 3 1","b4 0 2"]
Explanation
The two `duel won` logs tie on contents and are ordered by identifier.

Example 2

Input
logs = ["g1 act car","g2 act","z0 9 9"]
Output
["g2 act","g1 act car","z0 9 9"]
Explanation
`act` is a prefix of `act car`, so it sorts first.

Constraints

  • 1 <= logs.length <= 100
  • 3 <= logs[i].length <= 100
  • Words in a log are separated by single spaces
  • Every log has an identifier and at least one word after it
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string[]} logs
 * @return {string[]}
 */
var reorderLogFiles = function(logs) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Reorder Data in Log Files — Solution in Python, Java & C++

Reorder Data in Log Files solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Reorder Data in Log Files is a medium coding problem on arrays, strings and sorting, asked in Amazon and Microsoft interviews.

  • Difficulty: Medium
  • Topics: Arrays, Strings, Sorting
  • Asked at: Amazon, Microsoft
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Each log is a string of space-separated words; the first word is the log's identifier (lowercase letters and digits). There are two kinds of logs:

  • letter-logs — every word after the identifier consists of lowercase letters;
  • digit-logs — every word after the identifier consists of digits.

Reorder the logs so that:

  1. all letter-logs come before all digit-logs;
  2. letter-logs are sorted by their contents (everything after the identifier); logs with equal contents are sorted by identifier — both by plain character comparison;
  3. digit-logs keep their original relative order.

Return the reordered list.

Example 1

Input: logs = ["k1 duel won","x9 7 3 1","a2 pair mode","b4 0 2","c3 duel won"]
Output: ["c3 duel won","k1 duel won","a2 pair mode","x9 7 3 1","b4 0 2"]
Explanation: The two `duel won` logs tie on contents and are ordered by identifier.

Example 2

Input: logs = ["g1 act car","g2 act","z0 9 9"]
Output: ["g2 act","g1 act car","z0 9 9"]
Explanation: `act` is a prefix of `act car`, so it sorts first.

Constraints

  • 1 <= logs.length <= 100
  • 3 <= logs[i].length <= 100
  • Words in a log are separated by single spaces
  • Every log has an identifier and at least one word after it

Hints for Reorder Data in Log Files

  1. Hint 1

    The kind of a log is decided by the first character after the first space.

  2. Hint 2

    Split the logs into two lists, keeping the digit-logs in input order.

  3. Hint 3

    Sort the letter-logs with a comparator on (contents, identifier), then append the digit-logs.

How to solve Reorder Data in Log Files

Partition the logs by kind, sort only the letter-logs with the two-level key, and append the untouched digit-logs.

Approach

  1. For each log find its first space; the character after it tells whether it is a digit-log.
  2. Collect digit-logs in input order and letter-logs separately.
  3. Sort the letter-logs by contents (text after the first space) and break ties by identifier (text before it).
  4. Return the sorted letter-logs followed by the digit-logs.

Why it works

The required order is exactly the concatenation of the two groups, the letter group being a total order on (contents, identifier) and the digit group being the input order; keeping digit-logs out of the sort avoids depending on sort stability.

Complexity

  • Time — O(n log n · L) for n logs of length up to L
  • Space — O(n · L)

Pitfalls

  • Comparing whole log strings sorts by identifier first — the contents must come first.
  • Digit-logs must keep their original order; an unstable sort over everything can scramble them.
  • An identifier may contain digits (x9); only the first content word decides the kind.

Reference solution

Python

from typing import List

def reorderLogFiles(logs: List[str]) -> List[str]:
    letters = []
    digits = []
    for log in logs:
        ident, body = log.split(" ", 1)
        if body[0].isdigit():
            digits.append(log)
        else:
            letters.append((body, ident, log))
    letters.sort()
    return [t[2] for t in letters] + digits

Java

public static String[] reorderLogFiles(String[] logs) {
    List<String> letters = new ArrayList<>();
    List<String> digits = new ArrayList<>();
    for (String log : logs) {
        char c = log.charAt(log.indexOf(' ') + 1);
        if (c >= '0' && c <= '9') digits.add(log);
        else letters.add(log);
    }
    letters.sort((a, b) -> {
        int sa = a.indexOf(' '), sb = b.indexOf(' ');
        int cmp = a.substring(sa + 1).compareTo(b.substring(sb + 1));
        if (cmp != 0) return cmp;
        return a.substring(0, sa).compareTo(b.substring(0, sb));
    });
    letters.addAll(digits);
    return letters.toArray(new String[0]);
}

C++

vector<string> reorderLogFiles(vector<string>& logs) {
    vector<string> letters, digits;
    for (const string& log : logs) {
        char c = log[log.find(' ') + 1];
        if (c >= '0' && c <= '9') digits.push_back(log);
        else letters.push_back(log);
    }
    sort(letters.begin(), letters.end(), [](const string& a, const string& b) {
        size_t sa = a.find(' '), sb = b.find(' ');
        string ba = a.substr(sa + 1), bb = b.substr(sb + 1);
        if (ba != bb) return ba < bb;
        return a.substr(0, sa) < b.substr(0, sb);
    });
    letters.insert(letters.end(), digits.begin(), digits.end());
    return letters;
}

JavaScript

var reorderLogFiles = function(logs) {
    var letters = [], digits = [];
    for (var i = 0; i < logs.length; i++) {
        var sp = logs[i].indexOf(" ");
        var c = logs[i].charCodeAt(sp + 1);
        if (c >= 48 && c <= 57) digits.push(logs[i]);
        else letters.push({ id: logs[i].substring(0, sp), body: logs[i].substring(sp + 1), log: logs[i] });
    }
    letters.sort(function(a, b) {
        if (a.body !== b.body) return a.body < b.body ? -1 : 1;
        if (a.id !== b.id) return a.id < b.id ? -1 : 1;
        return 0;
    });
    var res = [];
    for (var k = 0; k < letters.length; k++) res.push(letters[k].log);
    return res.concat(digits);
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Strings