시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 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 함수에서 :
- 배열 A에 요소가 하나만있는 경우 해당 요소가 B에서 누락 된 경우 해당 요소를 반환합니다.
- A와 B에서 첫 번째 요소가 같지 않은 경우 첫 번째 요소 자체가 누락 된 경우 A의 첫 번째 요소를 반환합니다.
- 그렇지 않으면 배열 A의 코너 포인트로 mid 및 low를 초기화하고 배열 A에서 이진 검색을 시작하고 mid = (high + low) / 2를 얻습니다.
- A [mid] = B [mid]이면 low를 mid로 만들어 오른쪽 부분의 요소를 찾습니다.
- 그렇지 않으면 높음을 중간으로 만들어 왼쪽 부분의 요소를 검색합니다.
- low = high – 1 일 때 루프를 종료하고 누락 된 요소 인 A [mid]를 반환합니다.
3. 조건이있는 새 함수 FindMissing을 만듭니다.
- A의 크기 = B의 크기 + 1이면 FindMissingInB (A, B)를 인쇄합니다.
- B의 크기 = A의 크기 + 1이면 FindMissingInB (B, A)를 인쇄합니다.
- 그렇지 않으면 잘못된 입력입니다.
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. 이 기능에서 :
- Missing_element = 0 초기화
- Missing_element가있는 배열의 모든 요소에 XOR 사용
- 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) 해를 찾기 위해 몇 가지 변수 만 사용하기 때문입니다.
