Question

Amazon | FAANG | OA Coding Questions and Solutions | Set - 28 | 2022

Answer 1

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.

public String[] reorderLogFiles(String[] logs) {
        
        Comparator<String> myComp = new Comparator<String>() {
            @Override
            public int compare(String s1, String s2) {
                int s1SpaceIndex = s1.indexOf(' ');
                int s2SpaceIndex = s2.indexOf(' ');
                char s1FirstCharacter = s1.charAt(s1SpaceIndex+1);
                char s2FirstCharacter = s2.charAt(s2SpaceIndex+1);
                
                if (s1FirstCharacter <= '9') {
                    if (s2FirstCharacter <= '9') return 0;
                    else return 1;
                }
                if (s2FirstCharacter <= '9') return -1;
                
                int preCompute = s1.substring(s1SpaceIndex+1).compareTo(s2.substring(s2SpaceIndex+1));
                if (preCompute == 0) return s1.substring(0,s1SpaceIndex).compareTo(s2.substring(0,s2SpaceIndex));
                return preCompute;
            }
        };
        
        Arrays.sort(logs, myComp);
        return logs;
    }

 

Answer 2

You are given an undirected graph. You are given an integer n which is the number of nodes in the graph and an array edges, where each edges[i] = [ui, vi] indicates that there is an undirected edge between ui and vi.

A connected trio is a set of three nodes where there is an edge between every pair of them.

The degree of a connected trio is the number of edges where one endpoint is in the trio, and the other is not.

Return the minimum degree of a connected trio in the graph, or -1 if the graph has no connected trios.

 

Example 1:

Input: n = 6, edges = [[1,2],[1,3],[3,2],[4,1],[5,2],[3,6]]
Output: 3
Explanation: There is exactly one trio, which is [1,2,3]. The edges that form its degree are bolded in the figure above.

Example 2:

Input: n = 7, edges = [[1,3],[4,1],[4,3],[2,5],[5,6],[6,7],[7,5],[2,6]]
Output: 0
Explanation: There are exactly three trios:
1) [1,4,3] with degree 0.
2) [2,5,6] with degree 2.
3) [5,6,7] with degree 2.

 

Constraints:

• 2 <= n <= 400
• edges[i].length == 2
• 1 <= edges.length <= n * (n-1) / 2
• 1 <= ui, vi <= n
• ui != vi
• There are no repeated edges.

 

Code : 

int minTrioDegree(int n, vector<vector<int>>& edges) {
    vector<set<int>> al(n + 1);
    vector<int> cnt(n + 1);
    int res = INT_MAX;
    for (auto &e: edges) {
        al[min(e[0], e[1])].insert(max(e[0], e[1]));
        ++cnt[e[0]];
        ++cnt[e[1]];
    }
    for (auto t1 = 1; t1 <= n; ++t1)
        for (auto it2 = begin(al[t1]); it2 != end(al[t1]); ++it2)
            for (auto it3 = next(it2); it3 != end(al[t1]); ++it3)
                if (al[*it2].count(*it3))
                    res = min(res, cnt[t1] + cnt[*it2] + cnt[*it3] - 6);
    return res == INT_MAX ? -1 : res;
}