Shopping Patterns Solution Amazon OA 2023

Shopping Patterns Minimum Degree of a Connected Trio in a Graph

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:

Shopping Patterns Solution Amazon OA 2023

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:

Shopping Patterns Solution Amazon OA 2023

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.

Also See: Nth Ugly numbers puesudo code using min heap

Shopping Patterns Amazon Online Assessment
Shopping Patterns Amazon Online Assessment

SOLUTION

Program: Shopping Patterns Solution in C++

class Solution {
public:
    
    bool visited[401][401];
    int minTrioDegree(int n, vector<vector<int>>& edges) {
        vector<unordered_set<int>>adj(n+1);
        
        memset(visited,false,sizeof(visited));
        
        int degree[n+1];
        for(int i=0;i<n+1;i++)
            degree[i]=0;
        
        for(int i=0;i<edges.size();i++){
            int start = edges[i][0];
            int end = edges[i][1];
            visited[start][end]=true;
            visited[end][start]=true;
            
            degree[start]++;
            degree[end]++;
        }
        
        int result = INT_MAX;
        
        for(int i=1;i<=n-2;i++){
            for(int j=i+1;j<=n-1;j++){
                for(int k=j+1;k<=n;k++){
                    if(connected(i,j,k)){
                        int count = 0;
                        count+=degree[i]-2;
                        count+=degree[j]-2;
                        count+=degree[k]-2;
                        result=min(result,count);
                    }
                }
            }
        }
        
        return result==INT_MAX ? -1: result;
    }
    
    bool connected(int i,int j,int k){
        if(!visited[i][j] || !visited[i][k])
            return false;
        
        if(!visited[j][i] || !visited[j][k])
            return false;
        
        if(!visited[k][i] || !visited[k][j])
            return false;
        
        return true;
    }
};

Program: Shopping Patterns Solution in Python

class Solution:
    def minTrioDegree(self, n: int, edges: List[List[int]]) -> int:
        g = defaultdict(set)
        for a, b in edges:
            g[a].add(b)
            g[b].add(a)
            
        d = {n:len(g[n]) for n in g}
            
        res = inf
        for n in g:
            for m in g[n]:
                for o in g[n] & g[m]:
                    res = min(res, d[n]+d[m]+d[o]-6)
                    g[o].discard(n)
                g[m].discard(n)
                        
        return res if res < inf else -1

Program: Shopping Patterns Solution in Java

Explanation:

  • The HashMap degrees keeps track of the degree for each vertex.
  • boolean[][] isEdge keeps track of whether (i, j) is an edge.
  • Then we just iterate through all edges (i, j), and for each edge, iterate through all nodes k, if (i, k) and (j, k) are also edges, then this is a trio. We just use the degrees we stored in the hashmap to calculate the total degrees.
  • The complexity is O(E * V), where E is the number of edges, and V is the number of vertices (which is N). In worst case scenario, there would be ~N^2 edges, so the time complexity is O(N^3).
class Solution {
    public int minTrioDegree(int n, int[][] edges) {
        int min = Integer.MAX_VALUE;
        Map<Integer, Integer> degrees = new HashMap<>(); // vertex, degree
        boolean[][] isEdge = new boolean[n + 1][n + 1];
        
        for (int[] edge : edges) {
            degrees.put(edge[0], degrees.getOrDefault(edge[0], 0) + 1);
            degrees.put(edge[1], degrees.getOrDefault(edge[1], 0) + 1);
            isEdge[edge[0]][edge[1]] = true;
            isEdge[edge[1]][edge[0]] = true;
        }
        
        for (int[] edge : edges) {
            for (int i = 1; i <= n; i++) {
                if (isEdge[i][edge[0]] && isEdge[i][edge[1]]) {
					// subtract 6 because we do not count inner edges of a trio
                    int degree = degrees.get(i) + degrees.get(edge[0]) + degrees.get(edge[1]) - 6;
                    min = Math.min(min, degree);
                }
            }
        }
        
        if (min == Integer.MAX_VALUE)
            return -1;
        return min;
    }
}

Amazon OA 2023 Questions with Solution

  1. Reorder Data in Log Files 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