시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.
차례
문제 정책
정렬 된 배열이 주어지면 정렬 된 배열에서 주요 요소를 찾아야합니다. 대다수 요소 : 크기의 절반 이상이 발생하는 수 정렬. 여기에서 우리는 그것이 major_element인지 아닌지 확인해야하는 x를 제공했습니다.
예
입력
5 2
1 2 2 2 4
산출
2는 주요 요소입니다.
과반수 요소를 찾기위한 접근법 1
우리는 이진 검색의 개념을 사용하지만 까다로운 방식으로 사용합니다. 이진 검색은 주어진 숫자 x의 첫 번째 발생을 확인하기 위해 쉽게 수정할 수 있습니다.
암호알고리즘
1. 배열의 중간 요소가 x인지 아닌지 확인하십시오 .N / 2 회 이상 발생하면 major_element가 배열의 중간에 있어야하기 때문입니다.
2. 있는 경우 사용자 지정 이진 검색을 수행하여 x의 첫 번째 항목을 찾습니다.
3. 얻은 인덱스는 k라고 말하고 (k + N / 2) 번째 인덱스에도 x가 있는지 확인합니다. 그렇다면 x는 다수 요소입니다.
알림: 작업을 쉽게 수행하려면 lower_bound 및 higher_bound STL 함수를 사용하십시오.
실시
과반수 요소를 찾기위한 C ++ 프로그램
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,x;
cin>>n>>x;
int arr[n];
for(int i=0;i<n;i++)
{
cin>>arr[i];
}
int low=lower_bound(arr,arr+N,x)-arr; //index of first occurence of the element
int high=upper_bound(arr,arr+N,x)-arr; //index of the last occurenece of element
if(high-low>N/2)
cout<<x <<" is a majority element\n";
else
cout<<x <<" is not a majority element\n";
return 0;
}
과반수 요소 찾기를위한 Java 프로그램
import java.util.Scanner;
class sum
{
public static int first(int arr[], int low, int high, int x, int n)
{
if (high >= low) {
int mid = low + (high - low) / 2;
if ((mid == 0 || x > arr[mid - 1]) && arr[mid] == x)
return mid;
else if (x > arr[mid])
return first(arr, (mid + 1), high, x, n);
else
return first(arr, low, (mid - 1), x, n);
}
return -1;
}
public static int last(int arr[], int low, int high, int x, int n)
{
if (high >= low) {
int mid = low + (high - low) / 2;
if ((mid == n - 1 || x < arr[mid + 1]) && arr[mid] == x)
return mid;
else if (x < arr[mid])
return last(arr, low, (mid - 1), x, n);
else
return last(arr, (mid + 1), high, x, n);
}
return -1;
}
public static void main(String[] args)
{
Scanner sr = new Scanner(System.in);
int n = sr.nextInt();
int x = sr.nextInt();
int a[] = new int[n];
for(int i=0;i<n;i++)
{
a[i] = sr.nextInt();
}
int low=first(a,0,n-1,x,n); //index of first occurence of the element
int high=last(a,0,n-1,x,n); //index of the last occurenece of element
if((high-low+1)>n/2)
System.out.println(x+" is a majority element");
else
System.out.println(x+" is not a majority element");
}
}
5 2 1 2 2 2 4
2 is a majority element
복잡성 분석
시간 복잡성 : O (logN) 우리는 이진 검색의 개념을 사용하고 이진 검색 알고리즘이 O (긴) 시간 복잡성을 가지고 있음을 알고 있기 때문입니다.
공간 복잡성 : O (1) 왜냐하면 우리는 O (1) 또는 일정한 공간 복잡도에 속하는 일부 변수를 사용하기 때문입니다.
과반수 요소를 찾기위한 접근법 2
암호알고리즘
배열의 절반이 될 때까지 반복합니다.
a. 현재 요소가 x이면 (현재 인덱스 + N / 2) 번째 인덱스에 x가 포함되어 있는지 확인합니다.
b. 그렇다면 x는 다수 요소입니다.
c. 그렇지 않으면 x는 major_element가 아닙니다.
실시
C ++ 프로그램
#include <bits/stdc++.h>
using namespace std;
int main()
{
int N,x;
cin>>N>>x;
int arr[N];
for(int i=0;i<N;i++)
{
cin>>arr[i];
}
int end;
if(N%2)
end = N/2+1;
else
end = N/2;
for(int i=0;i<end;i++)
{
if(arr[i] ==x and x == arr[i+N/2])
{
cout << x <<" is a mojority element " <<endl;
return 0;
}
}
cout<<x<<" is not a majority element\n";
}
자바 프로그램
import java.util.Scanner;
class sum
{
public static void main(String[] args)
{
Scanner sr = new Scanner(System.in);
int n = sr.nextInt();
int x = sr.nextInt();
int a[] = new int[n];
for(int i=0;i<n;i++)
{
a[i] = sr.nextInt();
}
int end;
if(n%2==1)
end = n/2+1;
else
end = n/2;
int temp=0;
for(int i=0;i<end;i++)
{
if(a[i] ==x && x == a[i+n/2])
{
System.out.println(x+" is a mojority element");
i=end;
temp=1;
}
}
if(temp==0)
System.out.println(x+" is not a majority element");
}
}
5 2 1 2 3 3 6
2 is not a majority element
복잡성 분석
시간 복잡성: O (N) 왜냐하면 우리는 O (n) 시간 복잡성으로 이끄는 절반 하위 배열을 횡단하기 때문입니다.
공간 복잡성 : O (1) 여기에서는 보조 공간을 사용하지 않기 때문입니다.
