시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.
우리는 모두 인터뷰에서 어느 시점에서 하위 집합 문제로 어려움을 겪었습니다. 면접관들도 이러한 문제를 좋아합니다. 이러한 문제는 학생들의 이해와 사고 과정을 검토하는 데 도움이됩니다. 따라서 더 이상 고민하지 않고 문제로 바로 뛰어들겠습니다.
차례
섹션 1
문제 진술
숫자의 조합 / 배열이 제공되었습니다. 우리는 고유 한 짝수를 가질 수있는 서브 세트의 수를 등록해야합니다.
작은 예를 들어 보겠습니다.
입력:
[1,2,5,6,3,2,1,1,8]
가능한 하위 집합 :
[2,6]
[6,8]
[2,6,8]
참고 : 동일한 번호를 가진 부분 집합은 다른 것으로 간주되지 않습니다.
가능한 대답 하위 집합 중 하나를 강조 표시하여 동일한 내용을 설명하겠습니다.
섹션 2
분석
우리가 원하는 것을 찾을 수있는 다양한 방법이 있습니다. 그만큼 브 루트 포스 하나는 가능한 모든 하위 집합을 찾은 다음 규칙을 충족하는 하위 집합을 찾는 것입니다.
위의 방법은 머리를 벽에 두드리는 것 이상입니다. 따라서 어리석은 소리로 들리는 당혹감을 덜기 위해 가능한 가장 좋은 시간에 답을 얻을 수있는 가장 쉬운 방법을 찾았습니다.
우리는 짝수를 만날 때마다 두 가지 선택이 있습니다
- 하위 집합에 포함되도록 선택할 수 있습니다.
- 하위 집합에서 제외되도록 선택할 수 있습니다.
따라서 현재 우리가 가진 유일한 임무는 숫자가 고유한지 여부를 결정하는 것입니다. (앞서 언급 한 규칙 덕분에)
프로세스를 XNUMX으로 설정하겠습니다.
- 첫째, 해시셋 우리가 만난 짝수를 저장하기 위해
- 둘째, 루프 실행
- 숫자가 짝수인지 확인
- 숫자가 짝수이면 HashSet에 추가합니다.
- HashSet에는 고유 한 요소 만 들어오는 것을 보장하는 자체 순서가 있습니다.
- 그런 다음 HashSet에서 요소 수를 찾습니다.
- 이 수는 우리가 가진 고유 한 짝수 수를 나타냅니다.
- 이 개수를 사용하여 하위 집합의 수를 찾을 수 있습니다.
- 부분 집합 개수 = 2 ^ count-1
위의 프로세스는 다음과 같이 코드에 넣을 수 있습니다.
고유 한 짝수를 갖는 개수 하위 집합에 대한 Java 코드
public class Main
{
public static int evenSub(int arr[],int n)
{
HashSet<Integer>store=new HashSet<Integer>();
for(int i=0;i<arr.length;i++)
{
if(arr[i]%2==0)
store.add(arr[i]);
}
int p=store.size();
return (int)(Math.pow(2,p)-1);
}
public static void main(String[] args)
{
int arr[] = {2, 1, 9, 2, 6, 5, 3};
int n = arr.length;
System.out.println
("Number of subsets = "+ evenSub(arr, n));
}
}
2, 1, 9, 2, 6, 5, 3
3
고유 한 짝수를 갖는 개수 하위 집합에 대한 C ++ 코드
Java에서 C ++로 전환 할 때 HashSet 대신 Unordered Set를 사용하고 몇 가지 매개 변수를 사용하여 우리에게 적합합니다.
int evenSub(int arr[],int n)
{
unordered_set<int>store;
for(int i=0;i<n;i++)
{
if(arr[i]%2==0)
store.insert(arr[i]);
}
int p=store.size();
return (pow(2,p)-1);
}
int main()
{
int arr[] = {
4, 2, 1, 9, 2, 6, 5, 3
7
고유 한 짝수를 갖는 개수 하위 집합에 대한 복잡성 분석
시간 복잡성 = O (n)
공간 복잡성 = O (n)
시간 복잡성
- 배열을 통과 할 때 O (n)입니다.
- 하위 집합에 추가하기 전에 모든 요소를 살펴 봅니다.
공간 복잡성
- 최악의 경우 전체 배열을 저장하게 될 수 있으므로 O (n)입니다.
