Reorder Data in Log Files Solution Amazon OA 2023

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:

  1. The letter-logs come before all digit-logs.
  2. The letter-logs are sorted lexicographically by their contents. If their contents are the same, then sort them lexicographically by their identifiers.
  3. 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
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

Amazon OA 2023 Questions with Solution

  1. Shopping Patterns Solution Amazon OA 2023
  2. Top K Frequent Words Solution Amazon OA 2023
  3. Trees Height Solution Amazon OA SDE 2023
  4. Counting Binary Substrings Amazon OA 2023
  5. Grid Connections Amazon OA 2023
  6. Shipment Imbalance Amazon OA 2023
  7. Max Profit Amazon OA 2023
  8. Find Lowest Price Amazon OA 2023
  9. Decode String Frequency Amazon OA 2023
  10. Simple Cipher Amazon OA 2023
  11. Valid Discount Coupons Amazon OA 2023 Solution
  12. Count Maximum Teams Amazon OA 2023
  13. Minimum Coin Flips Amazon OA 2023
  14. Max Average Stock Price Amazon OA 2023 Solution
  15. Robot Bounded In Circle Amazon OA 2023
  16. Shopping Options Amazon OA 2023 Solution
  17. Fill The Truck Maximum Units on a Truck Amazon OA Solution
  18. Maximize Score After N Operations Number Game Solution Amazon OA 2023
  19. Slowest Key Amazon OA 2023 Solution
  20. Five Star Seller Maximum Average Pass Ratio Amazon OA 2023
  21. Split String Into Unique Primes Amazon OA 2023 Solution
  22. Storage Optimization Amazon OA 2023 Solution
  23. Minimum Difficulty of a Job Schedule Amazon OA 2023 Solution
  24. Autoscale Policy Utilization Check Amazon OA 2023
  25. Optimal Utilization Solution Amazon OA 2023
  26. Merge Two Sorted Lists Solution Amazon OA 2023
  27. Two Sum Unique Pairs Solution Amazon OA 2023
  28. Amazon Music Pairs Amazon OA 2023 Solution
  29. Class Grouping Amazon OA 2023 Solution
  30. Find Max products Amazon OA 2023 Solution
  31. Get encrypted number Amazon OA 2023 Solution
  32. Find Total Imbalance Amazon OA 2023 Solution
  33. Find Total Power Amazon OA 2023 Solution