시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.
차례
문제 정책
"골롬 시퀀스"문제는 입력이 주어 졌다는 것을 나타냅니다. 정수 n 및 n 번째 요소까지 골롬 시퀀스의 모든 요소를 찾아야합니다.
예
n = 8
1 2 2 3 3 4 4 4
설명
Golomb 시퀀스의 처음 8 개 항을 찾아 인쇄합니다. 출력이 골롬 시퀀스의 처음 8 개 요소를 나타내므로 출력이 정확합니다.
접근
수학에서 주어진 시퀀스는 Silverman의 시퀀스라고도합니다. 시퀀스 이름은 Solomon W. Golomb의 이름을 따서 명명되었습니다. a (n)은 시퀀스에서 n이 발생하는 횟수 인 비 감소 정수 시퀀스입니다. Golomb 시퀀스의 첫 번째 요소는 1입니다. 예를 들어 a1 = 1은 시퀀스에서 1이 한 번만 발생한다는 것을 의미하므로 a2도 1 일 수는 없지만 2 일 수 있으므로 XNUMX 여야합니다.
시퀀스의 처음 몇 항은 1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 8, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 11, 11, 11, 11, 11, 12, 12, 12, 12, 12, 12.
우리는 Golomb 시퀀스의 요소를 생성하기위한 반복 관계를 알고 있습니다. 재귀 공식은 다음과 같습니다.
재귀 공식을 사용하여 문제를 해결할 것입니다. 한 가지 방법은 재귀를 사용하여 문제를 해결하는 것입니다. 그러나 동일한 값을 반복해서 계산하기 때문에 기하 급수적 인 시간 복잡성이 발생합니다. 반복 관계에서 볼 수 있듯이 시퀀스의 n 번째 요소는 이전에 계산 된 항에 의존하기 때문입니다. 따라서 동적 프로그래밍을 사용하여 문제를 해결합니다. 다른 값을 다시 계산할 필요가 없기 때문입니다.
암호
Golomb 시퀀스 용 C ++ 코드
#include <bits/stdc++.h>
using namespace std;
int main(){
// number of elements of Golomb sequence which are required
int n;cin>>n;
cout<<1<<" ";
int dp[n+1];
dp[1] = 1;
for(int i=2;i<=n;i++){
dp[i] = 1 + dp[i-dp[dp[i-1]]];
cout<<dp[i]<<" ";
}
}
10
1 2 2 3 3 4 4 4 5 5
Golomb 시퀀스 용 Java 코드
import java.util.*;
class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
// number of elements of Golomb sequence which are required
int n = sc.nextInt();
System.out.print("1 ");
int dp[] = new int[n+1];
dp[1] = 1;
for(int i=2;i<=n;i++){
dp[i] = 1 + dp[i-dp[dp[i-1]]];
System.out.print(dp[i]+" ");
}
}
}
10
1 2 2 3 3 4 4 4 5 5
복잡성 분석
시간 복잡성
O (N), n 번째 요소가 이전에 계산 된 단일 요소에 의존하기 때문에이 연산은 각 요소에 대해 O (1) 시간이 복잡해집니다. n 개의 요소가 있으므로 시간 복잡도는 선형입니다.
공간 복잡성
O (N), n 개의 요소를 저장하고 있으므로 공간 복잡도도 선형입니다.
