중복 배열에서 손실 된 요소 찾기

난이도 쉽게
자주 묻는 질문 수행자 어도비 벽돌 아마존 Apple 블룸버그 게시물에서 자본 하나 시스코 이베이 Facebook 골드만 삭스 구글 IBM JP 모건 Microsoft 엔비디아 신탁 페이팔 ServiceNow Yandex 주차
Arista Networks 배열 해시 해싱조회수 254

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

문제 정책

두 개의 배열 A와 B가 주어지면 한 배열은 하나의 요소를 제외하고 다른 배열의 복제본입니다. A 또는 B에서 하나의 요소가 누락되었습니다. 중복 된 요소에서 손실 된 요소를 찾아야합니다. 정렬.

5
1 6 4 8 9
6 4 8 9
1

접근법 1

암호알고리즘

요소의 순서가 같으면

1. A의 크기가 B의 크기보다 큰 FindMissingInB 함수를 만듭니다. 즉, B에서 요소가 누락되었음을 의미합니다.

2. FindMissingInB 함수에서 :

  1. 배열 A에 요소가 하나만있는 경우 해당 요소가 B에서 누락 된 경우 해당 요소를 반환합니다.
  2. A와 B에서 첫 번째 요소가 같지 않은 경우 첫 번째 요소 자체가 누락 된 경우 A의 첫 번째 요소를 반환합니다.
  3. 그렇지 않으면 배열 A의 코너 포인트로 mid 및 low를 초기화하고 배열 A에서 이진 검색을 시작하고 mid = (high + low) / 2를 얻습니다.
  4. A [mid] = B [mid]이면 low를 mid로 만들어 오른쪽 부분의 요소를 찾습니다.
  5. 그렇지 않으면 높음을 중간으로 만들어 왼쪽 부분의 요소를 검색합니다.
  6. low = high – 1 일 때 루프를 종료하고 누락 된 요소 인 A [mid]를 반환합니다.

3. 조건이있는 새 함수 FindMissing을 만듭니다.

  1. A의 크기 = B의 크기 + 1이면 FindMissingInB (A, B)를 인쇄합니다.
  2. B의 크기 = A의 크기 + 1이면 FindMissingInB (B, A)를 인쇄합니다.
  3. 그렇지 않으면 잘못된 입력입니다.

4. 주어진 두 입력 배열에서 함수를 호출하여 누락 된 숫자를 인쇄합니다.

실시

중복 배열에서 손실 된 요소를 찾기위한 C ++ 프로그램

#include <bits/stdc++.h>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
 
//Function:
//Using binary search approch in finding the missing element
//where A[] is bigger array than B
//Assuming the elements in same order in both A and B
int FindMissingInB(int A[], int B[], int N)
{
    //condition
    //only one element in A and B is empty
    if (N == 1)
        {
            return A[0];
        }
    //condition
    //First element is missing
    // special case, for first element missing
    if (A[0] != B[0])
        {
            return A[0];
        }
    //condition
    //element is in between  
    // Initialize low and high 
    int low = 0,high = N - 1;
    while (low < high)
    {
        int mid = (low + high) / 2;
        //mid elements are equal then search in right subarray
        if (A[mid] == B[mid])
            {
                low = mid;
            }
        else //mid elements are not eqaul 
            {
                high = mid;
            }
        // end when low = high -1
        if (low == high - 1)
            {
                break;
            }
    }
    //Missing element
    return A[high];
}
 
//Checking conditions Size A > Size B or 
void FindMissing(int A[], int B[], int M, int N)
{
    if (N == M-1)
    {
           cout << "Missing Element: "<< FindMissingInB(A, B, M) << endl;
    }
    else if (M == N-1)
    {
           cout << "Missing Element: "<< FindMissingInB(B, A, N) << endl;
    }
    else
    {
           cout << "Invalid!"<<endl;
    }
}
//Main Function
int main()
{
    int A[] = {1, 6, 4, 8, 9};
    int B[] = {6, 4, 8, 9};
    int M = sizeof(A)/sizeof(int);
    int N = sizeof(B)/sizeof(int);
    FindMissing(A, B, M, N);
    return 0;
}
Missing Element: 1

참고 : A 배열과 B 배열에서 같은 순서로 요소를 가정합니다.

중복 배열에서 손실 된 요소를 찾기위한 Java 프로그램

import java.util.Scanner;
class sum
{
    //Function:
    //Using binary search approch in finding the missing element
    //where A[] is bigger array than B
    //Assuming the elements in same order in both A and B
    public static int FindMissingInB(int A[], int B[], int N)
    {
        //condition
        //only one element in A and B is empty
        if (N == 1)
            {
                return A[0];
            }
        //condition
        //First element is missing
        // special case, for first element missing
        if (A[0] != B[0])
            {
                return A[0];
            }
        //condition
        //element is in between  
        // Initialize low and high 
        int low = 0,high = N - 1;
        while (low < high)
        {
            int mid = (low + high) / 2;
            //mid elements are equal then search in right subarray
            if (A[mid] == B[mid])
                {
                    low = mid;
                }
            else //mid elements are not eqaul 
                {
                    high = mid;
                }
            // end when low = high -1
            if (low == high - 1)
                {
                    break;
                }
        }
        //Missing element
        return A[high];
    }

    //Checking conditions Size A > Size B or 
    public static void FindMissing(int A[], int B[], int M, int N)
    {
        if(N == M-1)
        {
            System.out.println("Missing Element: " + FindMissingInB(A, B, M));
        }
        else if(M == N-1)
        {
            System.out.println("Missing Element: " + FindMissingInB(B, A, N));
        }
        else
        {
            System.out.println("Invalid!");
        }
    }
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int m = sr.nextInt();
        int a[] = new int[n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        int b[] = new int[m];
        for(int i=0;i<m;i++)
        {
            b[i] = sr.nextInt();
        }
        FindMissing(a,b,n,m); 
    }
}
5
1 6 7 3 2
1 6 7 2
3

중복 배열에서 손실 된 요소 찾기를위한 복잡성 분석

시간 복잡성

O (로그온) 여기서 n은 배열의 크기입니다. 여기서 우리는 이진 검색 이로 인해 로그온 시간이 복잡해집니다.

공간 복잡성

O (1) 해를 찾기 위해 몇 가지 변수 만 사용하기 때문입니다.

접근법 2

암호알고리즘

배열의 요소가 동일한 순서가 아닌 경우

1. 우리는 기능 FindMissing을 사용하여 누락 된 요소를 찾습니다.

2. 이 기능에서 :

  1. Missing_element = 0 초기화
  2. Missing_element가있는 배열의 모든 요소에 XOR 사용
  3. Missing_element = Missing_element ^ 모든 요소에 대해 A [i] 또는 B [i].

3. Missing_element의 최종 값은 누락 된 손실 요소입니다.

4. 주어진 배열에서 함수를 호출하여 누락 된 요소를 인쇄합니다.

중복 배열에서 손실 된 요소를 찾기위한 C ++ 프로그램

#include <bits/stdc++.h>
using namespace std;
 
//using XOR on all the elements.
void FindMissing(int A[], int B[], int M,int N)
{
    if (M != N-1 && N != M-1)
    {
        cout << "Invalid!";
        return;
    }
    int MissingElement = 0;
    for (int i=0; i<M; i++)
        {
            MissingElement = MissingElement^A[i];
        }
    for (int i=0; i<N; i++)
       {
            MissingElement = MissingElement^B[i];
       }
    cout << "Missing element: " << MissingElement;
}
 
//main function
int main()
{
    int A[] = {4, 1, 5, 9, 7};
    int B[] = {7, 5, 9, 4};
    int M = sizeof(A)/ sizeof(int);
    int N = sizeof(B)/ sizeof(int);
    FindMissing(A, B, M, N);
    return 0;
}
Missing element: 1

중복 배열에서 손실 된 요소를 찾기위한 Java 프로그램

import java.util.Scanner;
class sum
{
    public static void FindMissing(int A[], int B[], int M,int N)
    {
    if (M != N-1 && N != M-1)
    {
        System.out.println("Invalid!");
        return;
    }
    int MissingElement = 0;
    for (int i=0; i<M; i++)
        {
            MissingElement = MissingElement^A[i];
        }
    for (int i=0; i<N; i++)
       {
            MissingElement = MissingElement^B[i];
       }
    System.out.println("Missing element: " + MissingElement);
}
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int m = sr.nextInt();
        int a[] = new int[n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        int b[] = new int[m];
        for(int i=0;i<m;i++)
        {
            b[i] = sr.nextInt();
        }
        FindMissing(a,b,n,m); 
    }
}
3 2
1 2 3
1 2
3

중복 배열에서 손실 된 요소 찾기를위한 복잡성 분석

시간 복잡성

O (N) 여기서 n은 배열의 크기입니다. 여기서 우리는 정확히 한 번 배열을 횡단하므로 시간 복잡도가 O (n)이됩니다.

공간 복잡성

O (1) 해를 찾기 위해 몇 가지 변수 만 사용하기 때문입니다.

참조

균열 시스템 설계 인터뷰
Translate »