시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.
차례
문제 설명
”Check If N and Its Double Exist”문제에서 n 개의 요소 배열이 주어집니다. 배열 길이가 XNUMX보다 크거나 같습니다.
우리의 임무는 첫 번째 값이 두 번째 값의 두 배가되도록 배열에 쌍이 있는지 확인하는 것입니다.
좀 더 공식적으로 i, j가 존재하는지 확인해야합니다.
예
arr = [7,1,14,11]
true
설명 :
이 입력에 대한 출력은 true입니다. 질문은 주어진 배열에서 값과 이중 종료가 있는지 확인하도록 요청하기 때문입니다. 따라서 7과 14는 14가 7의 두 배이므로 이러한 기준을 충족합니다.
N과 그 이중 존재 Leetcode 솔루션에 대한 접근 방식
이 문제를 해결하는 첫 번째 방법은 브 루트 포스 접근하다. 배열의 각 요소에 대해 전체 배열을 탐색하고 이중이 있는지 확인합니다. 이 조건을 만족하는 요소를 찾으면 true를 반환하고, 그렇지 않으면 마지막에 false를 반환합니다. 이 접근법의 시간 복잡도는 O (n * n)입니다. 배열의 모든 요소에 대해 전체 배열을 순회하기 때문입니다.
순서가 지정되지 않은 맵 또는 순서가 지정되지 않은 집합을 사용하여 더 나은 시간 복잡성으로이 문제를 해결할 수 있습니다.
- 배열을 횡단합니다.
- 배열의 모든 요소에 대해 이중 또는 절반이 이미 존재하는지 확인하십시오.
- 조건이 true이면 true를 반환하고 그렇지 않으면 해당 요소를지도에 추가합니다.
- 배열 순회가 완료되고 이중 요소를 찾지 못한 경우 false를 반환합니다.
실시
N 및 이중 존재 여부 확인을위한 C ++ 코드
#include <bits/stdc++.h>
using namespace std;
bool checkIfExist(vector<int>& arr) {
unordered_map<int,bool>mp;
for(int i=0;i<arr.size();i++)
{
if(mp[arr[i]*2]==1||(mp[arr[i]/2]==1&&arr[i]%2==0))
return true;
mp[arr[i]]=1;
}
return false;
}
int main()
{
vector<int> arr = {7,1,14,11};
bool ans=checkIfExist(arr);
cout <<boolalpha;
cout<<ans<<endl;
return 0;
}
true
N 및 이중 존재 여부 확인을위한 Java 코드
import java.util.Arrays;
import java.util.Set ;
import java.util.HashSet;
public class Tutorialcup {
public static boolean checkIfExist(int[] arr) {
Set<Integer> seen = new HashSet<>();
for (int i : arr) {
if (seen.contains(2 * i) || (i % 2 == 0 && seen.contains(i / 2)))
return true;
seen.add(i);
}
return false;
}
public static void main(String[] args) {
int [] arr = {7,1,14,11};
boolean ans=checkIfExist(arr);
System.out.println(ans);
}
}
true
Check If N 및 이중 존재 Leetcode 솔루션의 복잡성 분석
시간 복잡성
위 코드의 시간 복잡성은 O (N) 정렬되지 않은 맵에서 검색하고 삽입하는 평균 시간 복잡성을 O (1)로 간주합니다.
공간 복잡성
위 코드의 공간 복잡성은 다음과 같습니다. O (N) 최악의 경우 모든 요소를 저장해야 할 수도 있기 때문입니다.
