Təkrarlanan Arraydan İtən Elementi tapın

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Akkolit Çiy kərpic Amazon alma Bloomberg Capital One Cisco eBay Facebook Goldman Sachs google IBM JP Morgan microsoft Nvidia Kahin PayPal XidmətNow Yandex
Arista Networks Geyim Sükut HashingBaxılıb 253

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Problem bəyanat

İki A və B massivi verildikdə, bir massiv bir element xaricində digərinin təkrarıdır. Bir element A ya da B-də yoxdur, itkin elementi çoxaldıb tapmaq lazımdır array.

misal

5
1 6 4 8 9
6 4 8 9
1

Yanaşma 1

Alqoritm

Elementlər eyni sıradadırsa,

1. A ölçüsünün B ölçüsündən böyük olduğu bir FindMissingInB funksiyası yaradın, yəni elementin B-də itkin olduğunu göstərir.

2. FindMissingInB funksiyasında:

  1. A massivində yalnız bir element varsa, o element B-də yoxdur, elementi qaytarın.
  2. Birinci element A və B-də bərabər deyilsə, onda birinci elementin özü yoxdursa, A-nın ilk elementini qaytarın.
  3. Başqa bir vəziyyətdə, A massivinin künc nöqtələri kimi orta və aşağı başlanğıc edin və A massivində ikili axtarışa başlayın və orta = (yüksək + aşağı) / 2 alın.
  4. A [orta] = B [orta] olarsa, sağ hissədə ortanı endirərək bir element axtarın.
  5. Başqa bir vəziyyətdə, sol hissədə orta səviyyəyə qədər bir element axtarın.
  6. Düşük = yüksək olduqda - 1 döngəsini bitirin və itkin element olan A [orta] qayıdın.

3. Şərtlərlə yeni bir FindMissing funksiyası yaradın:

  1. A ölçüsü = B ölçüsü + 1 olarsa, FindMissingInB (A, B) yazdırın
  2. B ölçüsü = A + 1 ölçüsüdürsə, FindMissingInB (B, A) yazdırın
  3. Başqa, etibarsız giriş.

4. itkin nömrəni çap etmək üçün verilən iki giriş massivindəki funksiyanı çağırın.

Həyata keçirilməsi

Təkrarlanan Dizidən İtmiş Elementi Tapmaq üçün C ++ Proqramı

#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

Qeyd: Həm A, həm də B massivlərində elementləri eyni qaydada götürsək.

Təkrarlanan Dizidən İtmiş Elementi Tapmaq üçün Java Proqramı

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

Təkrarlanan Arraydan İtən Elementi Tapmaq üçün Mürəkkəblik Analizi

Zamanın mürəkkəbliyi

O (logn) burada n massivin ölçüsüdür. Burada tətbiq edirik ikili axtarış bizi logn zaman mürəkkəbliyinə aparır.

Kosmik Mürəkkəblik

O (1) çünki bir neçə dəyişəndən yalnız həll yolu tapmaq üçün istifadə edirik.

Yanaşma 2

Alqoritm

Massivlərdəki elementlər eyni qaydada deyilsə,

1. biz yaradırıq funksiyası Eksik elementi tapmaq üçün tapın.

2. Bu funksiyada:

  1. Eksik_elementi başladın = 0
  2. Missing_element ilə massivdəki bütün elementlərdə XOR istifadə edin
  3. Missing_element = Missing_element ^ A [i] və ya B [i] bütün elementlər üçün.

3. Missing_element-in son dəyəri itkin itmiş elementdir.

4. itkin elementi çap etmək üçün verilən massivlərdəki funksiyanı çağırın.

Təkrarlanan Dizidən İtmiş Elementi Tapmaq üçün C ++ Proqramı

#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

Təkrarlanan Dizidən İtmiş Elementi Tapmaq üçün Java Proqramı

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

Təkrarlanan Arraydan İtən Elementi Tapmaq üçün Mürəkkəblik Analizi

Zamanın mürəkkəbliyi

O (n) burada n serialın ölçüsüdür. Burada zamanın mürəkkəbliyinin O (n) olacağını ifadə edən bir sıra düz bir dəfə keçirik.

Kosmik Mürəkkəblik

O (1) çünki bir neçə dəyişəndən yalnız həll yolu tapmaq üçün istifadə edirik.

References

Crack Sistemi Dizayn Müsahibələri
Translate »