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.
Mündəricat
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:
- A massivində yalnız bir element varsa, o element B-də yoxdur, elementi qaytarın.
- Birinci element A və B-də bərabər deyilsə, onda birinci elementin özü yoxdursa, A-nın ilk elementini qaytarın.
- 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.
- A [orta] = B [orta] olarsa, sağ hissədə ortanı endirərək bir element axtarın.
- Başqa bir vəziyyətdə, sol hissədə orta səviyyəyə qədər bir element axtarın.
- 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:
- A ölçüsü = B ölçüsü + 1 olarsa, FindMissingInB (A, B) yazdırın
- B ölçüsü = A + 1 ölçüsüdürsə, FindMissingInB (B, A) yazdırın
- 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:
- Eksik_elementi başladın = 0
- Missing_element ilə massivdəki bütün elementlərdə XOR istifadə edin
- 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.
