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:
- all letter-logs come before all digit-logs;
- letter-logs are sorted by their contents (everything after the identifier); logs with equal contents are sorted by identifier — both by plain character comparison;
- 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 <= 1003 <= logs[i].length <= 100Words in a log are separated by single spacesEvery log has an identifier and at least one word after it
Hints for Reorder Data in Log Files
Hint 1
The kind of a log is decided by the first character after the first space.
Hint 2
Split the logs into two lists, keeping the digit-logs in input order.
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
- For each log find its first space; the character after it tells whether it is a digit-log.
- Collect digit-logs in input order and letter-logs separately.
- Sort the letter-logs by contents (text after the first space) and break ties by identifier (text before it).
- 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] + digitsJava
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.