시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.
차례
문제 설명
”Can Make Arithmetic Progression From Sequence”문제에서 배열이 주어 졌는데, 이제 우리는 산술 진행 순서를 재정렬하여.
예
arr = [3,1,5]
true
설명 : 우리는 배열을 {1,3,5 / 2}로 재 배열 할 수 있으며, 이는 공통 차이가 XNUMX 인 산술 진행을 형성하므로 출력이 참입니다.
시퀀스 Leetcode 솔루션에서 Can Make Arithmetic Progression에 대한 접근 방식
산술 시리즈는 인접한 숫자의 차이가 일정한 시리즈입니다. 매우 기본적인 접근 방식은 배열을 정렬하고 인접한 요소 간의 차이를 확인하는 것입니다. 차이가 모든 연속 쌍에 대해 동일하면 산술 진행이고 그렇지 않으면 산술 진행이 아닙니다.
정렬을위한 시간 복잡성은 nlogn입니다. 배열에 대한 조회 테이블을 만들어 시간 복잡성을 개선 할 수 있습니다.
AP의 n 번째 항은 = a + (n-1) * d이며, 여기서 a는 시리즈의 첫 번째 요소, n은 요소의 수, d는 공통 차이입니다.
AP의 최소 요소는 = a이고
AP의 최대 요소는 = a + (n-1) * d이므로
d = (최대-최소) / (n-1).
- 배열의 최소 및 최대 요소를 찾을 수 있습니다. 이를 사용하여 d (공통 차)를 계산할 수 있습니다.
- 배열에 대한 조회 테이블을 만듭니다.
- 이제 우리는 첫 번째 요소와 공통 차이점을 알고 있습니다.
- a와 d로 구성된 산술 시리즈의 모든 n 요소가 룩업 테이블에 있는지 확인합니다.
- 모든 요소가 룩업 테이블에 있으면 시퀀스에서 산술 진행을 만들 수 있습니다. 그렇지 않으면 시퀀스에서 산술 진행을 만들 수 없습니다.
실시
시퀀스에서 산술 진행을 만들 수있는 C ++ 코드
#include <bits/stdc++.h>
using namespace std;
bool canMakeArithmeticProgression(vector<int>& arr) {
unordered_set<int> seen;
int mi = INT_MAX, mx = INT_MIN, n = arr.size();
for (int a : arr) {
mi = min(mi, a);
mx = max(mx, a);
seen.insert(a);
}
int diff = mx - mi;
if (diff % (n - 1) != 0) {
return false;
}
diff /= n - 1;
while (--n > 0) {
if (seen.find(mi)==seen.end()) {
return false;
}
mi += diff;
}
return true;
}
int main()
{
vector<int> arr = {3,5,1};
cout <<boolalpha;
cout<<canMakeArithmeticProgression(arr)<<endl;
return 0;
}
true
시퀀스에서 산술 진행을 만들 수있는 Java 코드
import java.util.*;
public class Tutorialcup {
public static boolean canMakeArithmeticProgression(int[] arr) {
Set<Integer> seen = new HashSet<>();
int mi = Integer.MAX_VALUE, mx = Integer.MIN_VALUE, n = arr.length;
for (int a : arr) {
mi = Math.min(mi, a);
mx = Math.max(mx, a);
seen.add(a);
}
int diff = mx - mi;
if (diff % (n - 1) != 0) {
return false;
}
diff /= n - 1;
while (--n > 0) {
if (!seen.contains(mi)) {
return false;
}
mi += diff;
}
return true;
}
public static void main(String[] args) {
int [] arr = {3,5,1};
System.out.println( canMakeArithmeticProgression(arr));
}
}
true
시퀀스 Leetcode 솔루션에서 산술 진행을 만들 수있는 복잡성 분석
시간 복잡성
위 코드의 시간 복잡성은 O (N) 배열을 순회하여 조회 테이블을 만들고 산술 시리즈의 모든 요소가 조회 테이블에 있는지 확인하기 때문입니다. 여기서 n은 입력 배열의 크기입니다.
공간 복잡성
위 코드의 공간 복잡성은 다음과 같습니다. O (N) 배열에 대한 조회 테이블을 만들고 있기 때문입니다. 여기서 n은 입력 배열의 크기입니다.
