Znajdź utracony element ze zduplikowanej tablicy

Poziom trudności Łatwo
Często zadawane pytania Accolita Adobe Amazonka Apple Bloomberg Capital One Cisco eBay Facebook Goldman Sachs Google IBM JP Morgan Microsoft Nvidia wyrocznia PayPal ServiceNow Yandex
Arista Networks Szyk Haszysz Hashingodwiedzajacy 253

Pytania do rozmowy kwalifikacyjnej na temat projektowania systemu może być tak nieograniczona, że ​​trudno jest określić właściwy sposób przygotowania. Teraz jestem w stanie złamać rundy projektowe Amazon, Microsoft i Adobe po zakupie ta książka. Codziennie poprawiaj jeden pytanie projektowe i obiecuję, że możesz złamać cały projekt.

Problem Statement

Biorąc pod uwagę dwie tablice A i B, jedna tablica jest duplikatem drugiej z wyjątkiem jednego elementu. Brakuje jednego elementu w A lub B. Musimy znaleźć utracony element z duplikatu szyk.

Przykład

5
1 6 4 8 9
6 4 8 9
1

Podejście 1

Algorytm

Jeśli elementy są w tej samej kolejności,

1. utwórz funkcję FindMissingInB, w której rozmiar A jest większy niż rozmiar B, co oznacza, że ​​brakuje elementu w B.

2. W funkcji FindMissingInB:

  1. Jeśli w tablicy A jest tylko jeden element, to brakuje tego elementu w B, zwróć element.
  2. Jeśli pierwszy element nie jest równy w A i B, to brakuje pierwszego elementu, zwróć pierwszy element z A.
  3. W przeciwnym razie zainicjuj środek i dół jako punkty narożne tablicy A i rozpocznij wyszukiwanie binarne w tablicy A i uzyskaj mid = (wysoki + niski) / 2.
  4. Jeśli A [środek] = B [środek], wyszukaj element w prawej części, wybierając nisko jako środek.
  5. W przeciwnym razie wyszukaj element w lewej części, określając wysokość jako środek.
  6. Zakończ pętlę, gdy low = high - 1 i zwróć A [mid], który jest brakującym elementem.

3. Utwórz nową funkcję FindMissing z warunkami:

  1. Jeśli Rozmiar A = Rozmiar B + 1, wypisz FindMissingInB (A, B)
  2. Jeśli Rozmiar B = Rozmiar A + 1, wypisz FindMissingInB (B, A)
  3. W przeciwnym razie nieprawidłowe dane wejściowe.

4. wywołaj funkcję na danych dwóch tablicach wejściowych, aby wypisać brakującą liczbę.

Realizacja

Program w C ++ do znajdowania utraconego elementu ze zduplikowanej tablicy

#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

Uwaga: Zakładając, że elementy są w tej samej kolejności w tablicach A i B.

Program Java do znajdowania utraconego elementu w zduplikowanej tablicy

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

Analiza złożoności w celu znalezienia utraconego elementu ze zduplikowanej tablicy

Złożoność czasowa

O (logn) gdzie n jest rozmiarem tablicy. Tutaj stosujemy wyszukiwanie binarne co prowadzi nas do złożoności czasu logowania.

Złożoność przestrzeni

O (1) ponieważ używamy tylko kilku zmiennych, aby znaleźć rozwiązanie.

Podejście 2

Algorytm

Jeśli elementy w tablicach nie są w tej samej kolejności,

1. tworzymy funkcjonować FindMissing, aby znaleźć brakujący element.

2. W tej funkcji:

  1. Zainicjuj Missing_element = 0
  2. Użyj XOR na wszystkich elementach tablicy z Missing_element
  3. Missing_element = Missing_element ^ A [i] lub B [i] dla wszystkich elementów.

3. Ostateczna wartość Missing_element to brakujący utracony element.

4. wywołaj funkcję na podanych tablicach, aby wypisać brakujący element.

Program w C ++ do znajdowania utraconego elementu ze zduplikowanej tablicy

#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

Program Java do znajdowania utraconego elementu w zduplikowanej tablicy

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

Analiza złożoności w celu znalezienia utraconego elementu ze zduplikowanej tablicy

Złożoność czasowa

Na) gdzie n jest rozmiarem tablicy. Tutaj przechodzimy przez tablicę dokładnie jeden raz, co oznacza, że ​​złożoność czasowa wyniesie O (n).

Złożoność przestrzeni

O (1) ponieważ używamy tylko kilku zmiennych, aby znaleźć rozwiązanie.

Referencje

Wywiady dotyczące projektowania systemu pękania
Translate »