두 배열의 교차점

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

두 배열의 교차 문제에서 두 개의 배열, 우리는 교차점 (공통 요소)을 인쇄해야합니다.

예

입력
arr1 [] = {1, 2, 2, 1}
arr2 [] = {2, 2}
산출
{2, 2}

입력
arr1 = {4, 9, 5}
arr2 = {9, 4, 9, 8, 4}
산출
{4, 9}

두 배열의 교차 알고리즘

두 배열에있는 모든 요소의 빈도를 계산하고 두 배열의 교차점을 나타내는 공통 부분을 선택합니다.

즉,

예를 고려하십시오.
arr1 [] = {1, 2, 2, 1}
arr2 [] = {2, 2}
arr1에서 1의 주파수는 2이고 arr2에서 1의 주파수는 2입니다.
arr2에서 2의 주파수는 2입니다.
따라서 교차점은 {2, 2}

위에서 사용한 공간은 다음과 같이 최적화 할 수 있습니다.

1. arr1에 대한 빈도 맵을 작성합니다. 즉, 각 요소의 빈도를 계산합니다.
2. arr2의 각 요소를 하나씩 이동합니다.
3. 1 단계에서 만든지도에 요소가있는 경우 해당 요소의 빈도를 1 씩 줄이고 요소를 인쇄하고 빈도가 0이되면지도에서 요소를 제거합니다.
4. arr3의 모든 요소에 대해 2 단계를 반복합니다.

두 배열의 교차에 대한 설명

예를 들어,
arr1 = {4, 9, 5}
arr2 = {9, 4, 9, 8, 4}

1단계

빈도 = {}
반복 1
arr1 [0] = 4이므로 freq = {(4-> 1)}
반복 2
arr1 [1] = 9, 따라서 freq = {(4-> 1), (9-> 1)}
반복 3
arr1 [2] = 5이므로, freq = {(4-> 1), (5-> 1), (9-> 1)}

2, 3, 4 단계

반복 1
arr2 [0] = 9, 따라서 freq = {(4-> 1), (5-> 1)} 및 ans = {9}
반복 2
arr2 [1] = 4, 따라서 freq = {(5-> 1)} 및 ans = {9, 5}
반복 3
arr2 [2] = 9, 따라서 freq = {(5-> 1)} 및 ans = {9, 5}
반복 4
arr2 [3] = 8, 따라서 freq = {(5-> 1)} 및 ans = {9, 5}
반복 5
arr2 [4] = 4, 따라서 freq = {(5-> 1)} 및 ans = {9, 5}

핀

두 배열의 교차에 대한 JAVA 코드

import java.util.HashMap;

public class IntersectionOfTwoArrays {
    private static void printIntersection(int[] arr1, int[] arr2) {
        HashMap<Integer, Integer> map = new HashMap<>();
        // Build the frequency map for arr1
        for (int i = 0; i < arr1.length; i++) {
            if (map.containsKey(arr1[i])) {
                map.put(arr1[i], map.get(arr1[i]) + 1);
            } else {
                map.put(arr1[i], 1);
            }
        }

        // Traverse the elements of arr2 one by one
        for (int i = 0; i < arr2.length; i++) {
            // If the map contains current element
            if (map.containsKey(arr2[i])) {
                // Reduce the frequency by 1
                int freq = map.get(arr2[i]);
                freq--;
                // If freq becomes 0, remove the element from the map
                if (freq == 0) {
                    map.remove(arr2[i]);
                } else {
                    map.put(arr2[i], freq);
                }
                // Print the element
                System.out.print(arr2[i] + " ");
            }
        }

        System.out.println();
    }

    public static void main(String[] args) {
        // Example 1
        int arr1[] = new int[] {1, 2, 2, 1};
        int arr2[] = new int[] {2, 2};

        printIntersection(arr1, arr2);

        // Example 2
        int arr3[] = new int[] {4, 9, 5};
        int arr4[] = new int[] {9, 4, 9, 8, 4};

        printIntersection(arr3, arr4);
    }
}

2 2 
9 4

두 배열의 교차에 대한 C ++ 코드

#include<bits/stdc++.h> 
using namespace std;

void printIntersection(int *arr1, int *arr2, int n, int m) {
    unordered_map<int, int> map;
    // Build the frequency map for arr1
    for (int i = 0; i < n; i++) {
        auto it = map.find(arr1[i]);
        if (it != map.end()) {
            it->second = it->second + 1;
        } else {
            map.insert(make_pair(arr1[i], 1));
        }
    }
    
    // Traverse the elements of arr2 one by one
    for (int i = 0; i < m; i++) {
        auto it = map.find(arr2[i]);
        // If the map contains current element
        if (it != map.end()) {
            // Reduce the frequency by 1
            it->second = it->second - 1;
            // If freq becomes 0, remove the element from the map
            if (it->second == 0) {
                map.erase(arr2[i]);
            }
            // Print the element
            cout<<arr2[i]<<" ";
        }
    }
    cout<<endl;
}

int main() {
    // Example 1
    int arr1[] = {1, 2, 2, 1};
    int arr2[] = {2, 2};
    
    printIntersection(arr1, arr2, sizeof(arr1)/ sizeof(arr1[0]), 
            sizeof(arr2) / sizeof(arr2[0]));
            
    // Example 2
    int arr3[] = {4, 9, 5};
    int arr4[] = {9, 4, 9, 8, 4};
    
    printIntersection(arr3, arr4, sizeof(arr3) / sizeof(arr3[0]), 
            sizeof(arr4) / sizeof(arr4[0]));
}

2 2 
9 4

복잡성 분석

시간 복잡성 = O (n + m)
공간 복잡성 = O (N)
여기서 n은 arr1의 길이이고 m은 arr2의 길이입니다.

참조