Reorder Data In Log Files Solution Amazon OA 2023

Contents

1 Reorder Data in Log Files Solution
- 1.1 SOLUTION
2 Amazon OA 2023 Questions with Solution

Reorder Data in Log Files Solution

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: All words (except the identifier) consist of lowercase English letters.
Digit-logs: All words (except the identifier) consist of digits.

Reorder these logs so that:

The letter-logs come before all digit-logs.
The letter-logs are sorted lexicographically by their contents. If their contents are the same, then sort them lexicographically by their identifiers.
The digit-logs maintain their relative ordering.

Return the final order of the logs.

Example 1:

Input: logs = [“dig1 8 1 5 1″,”let1 art can”,”dig2 3 6″,”let2 own kit dig”,”let3 art zero”]

Output: [“let1 art can”,”let3 art zero”,”let2 own kit dig”,”dig1 8 1 5 1″,”dig2 3 6″]

Explanation:

The letter-log contents are all different, so their ordering is “art can”, “art zero”, “own kit dig”.
The digit-logs have a relative order of “dig1 8 1 5 1”, “dig2 3 6”.

Example 2:

Input: logs = [“a1 9 2 3 1″,”g1 act car”,”zo4 4 7″,”ab1 off key dog”,”a8 act zoo”]

Output: [“g1 act car”,”a8 act zoo”,”ab1 off key dog”,”a1 9 2 3 1″,”zo4 4 7″]

Constraints:

1 <= logs.length <= 100
3 <= logs[i].length <= 100
All the tokens of logs[i] are separated by a single space.
logs[i] is guaranteed to have an identifier and at least one word after the identifier.

Also See: Nth Ugly numbers puesudo code using min heap

Reorder Data in Log Files Amazon Online Assessment

SOLUTION

Program: Reorder Data in Log Files Solution in C++

Explanation:

Create a vector of strings to store digitslogs, another vector of pair of strings to store the letterlogs.
Start processing the string in logs one by one, initialise i=0 and increment until it hits first space (i.e. the first word(identifier)).
Now check if the first character after space is digit or alphabet, if digit, directly store string in diglogs, if letters, then split the string with identifier and without identifiers and place it in letterlogs.
Now sort the letterlogs, with a custom constructore, i.e. check if string without identifier is equal or not, if equal sort according to identifer (stored in first), if not sort according to remaining part of the string.
Now just copy all digitlogs to letterlogs as their relative order is same as before. Finally return the answer.

class Solution {
public:
    vector<string> reorderLogFiles(vector<string>& logs) {
        vector<string> diglog;
        vector<pair<string, string>> letlog;
        for(string &s:logs)
        {
            int i = 0;
            while(s[i]!=' ')
                i++;
            if(isalpha(s[i+1]))
                letlog.emplace_back(s.substr(0, i), s.substr(i+1));
            else
                diglog.push_back(s);
        }
        sort(letlog.begin(), letlog.end(), [&](auto& a, auto& b) //comparator to check if second part of string, i.e. the string 
             //without identifier equal then compare identifier, or else compare second half and decide sorting on that
             {
                 return a.second==b.second? a.first<b.first : a.second<b.second;
             });
        vector<string> ret;
        for(auto &p:letlog) ret.push_back(p.first + " " + p.second);
        for(string &s:diglog) ret.push_back(s);
        return ret;
    }
};

Program: Reorder Data in Log Files Solution in Java

Explanation:

Assuming there is m letter logs and n digit logs. and the average length of a log is N.
The idea is, given we only need to keep the relative order of the digit logs, we can just partition the digit logs to the right while keeping the relative order of the digit logs, this only takes O(n * N) time.
And then we just need to sort the left most m logs, which are all letter logs.
So I think the total complexity would be O(M * LogM + n) * N ?

private static final Comparator<String> COMP = (a, b) -> {
        int idA = a.indexOf(" ");
        int idB = b.indexOf(" ");
        int comp = a.substring(idA + 1).compareTo(b.substring(idB + 1));
        
        if (comp == 0) {
            comp = a.substring(0, idA).compareTo(b.substring(0, idB));    
        }
        
        return comp;
    };
    
    public String[] reorderLogFiles(String[] logs) {
        int pivot = partition(logs, logs.length);
        
        if (pivot >= 0) {
            Arrays.sort(logs, 0, pivot + 1, COMP);
        }
        
        return logs;
    }
    
    private int partition(String[] logs, int n) {
        int pivot = n - 1;
        
        for (int i = n - 1; i >= 0; i--) {
            if (isDigit(logs[i])) {
                String tmp = logs[pivot];
                logs[pivot] = logs[i];
                logs[i] = tmp;
                pivot--;
            }
        }
        
        return pivot;
    }
    
    private boolean isDigit(String log) {
        int i = 0;
        
        while (log.charAt(i) != ' ') {
            i++;
        }
        
        i++;
        
        return Character.isDigit(log.charAt(i));
    }

Program: Reorder Data in Log Files Solution in Python

class Solution:
def reorderLogFiles(self, logs: List[str]) -> List[str]:
    text=[]
    dig=[]
    res=[]
    for i in logs:
        l=[]
        items=i.split(" ")
        if items[1].isdigit():
            dig.append(' '.join(items))
        else:
            text.append((items[0],' '.join(items[1:])))
    text.sort(key=lambda x:(x[1],x[0]))
    # res=' '.join(text)
    res = [' '.join(tups) for tups in text]
    res.extend(dig)
    return res

Reorder Data in Log Files Solution

SOLUTION

Amazon OA 2023 Questions with Solution