시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.
당신이 정렬 of 정수, 문제 설명은 가장 긴 비트 시퀀스를 찾아야합니다. 배열의 비 토닉 시퀀스는 먼저 증가한 다음 감소하는 시퀀스로 간주됩니다.
차례
예
arr[] = {1,4,2,76,43,78,54,32,1,56,23}
7
설명
1 ⇒ 4 ⇒ 76 ⇒ 78 ⇒ 54 ⇒ 32 ⇒ 23 (먼저 78까지 증가한 다음 23까지 감소합니다.
암호알고리즘
- 배열 선언 incrementSeq [] 주어진 배열 길이의 길이와 같은 크기입니다.
- 모든 인덱스 요소를 생성 된 배열 incrementSeq []의 1로 초기화합니다.
- 왼쪽에서 오른쪽으로 incrementSeq []에 저장하여 가장 긴 증가 하위 시퀀스를 찾으십시오.
- 배열 선언 decreasingSeq [] 주어진 배열의 길이와 같은 크기.
- 오른쪽에서 왼쪽으로 이동하고 decreasingSeq []에 저장하여 가장 긴 감소하는 하위 시퀀스를 찾습니다.
- maxOutput이라는 변수를 incrementSeq [0] + decreasingSeq [0] – 1로 초기화하십시오.
- 최대 값 알아보기 incrementSeq [i] + decreasingSeq [i] – 1 maxOutput에 저장합니다.
- 반환 최대 출력.
설명
크기 n의 입력 배열은 양의 정수로 구성됩니다. 주어진 배열의 가장 긴 비 토닉 시퀀스를 찾아야합니다. 비 토닉 시퀀스는 먼저 증가하는 시퀀스로 정의 할 수 있으며, 이는 시퀀스의 숫자가 먼저 증가 함을 의미합니다. 그런 다음 시퀀스가 끝날 때까지 숫자가 감소합니다. 가장 긴 비 토닉 시퀀스의 길이를 결정해야합니다.
먼저 솔루션을 두 부분으로 분리하십시오. 두 개의 배열을 선언합니다. 첫 번째 배열은 incrementSeq 정렬. 가장 긴 증가 시퀀스는 증가 시퀀스에서 숫자가 첫 번째 여야하는 시퀀스입니다. 그래서 우리는 중첩 된 루프에서 배열을 순회 할 것입니다. 증가하는 하위 시퀀스를 계속 찾으십시오. 그런 다음 현재 요소가 다음 요소보다 작은 지 확인해야합니다. 또한 incrementSeq의 현재 요소는 incrementSeq []의 다음 요소보다 작습니다. 참이면 요소를 incrementSeq [j] + 1로 저장하십시오. 이것은 배열을 이미 1로 초기화했기 때문에 더해집니다.
둘째, 배열을 선언하고 decreasingSeq []. 이 decreasingSeq []에서 배열의 오른쪽에서 왼쪽으로 중첩 된 루프 방식으로 배열을 순회합니다. 현재 요소가 다음 요소보다 큰지 확인합니다. 우리는 오른쪽에서 왼쪽으로 횡단하고 있기 때문입니다. 그런 다음 decreasingSeq [i]를 decreasingSeq [j] +1로 업데이트합니다. 코드의 마지막 단계에서 maxOutput에 저장된 최대 incrementSeq [i] + decreasingSeq [i] – 1을 찾아야합니다.
암호
가장 긴 Bitonic 하위 시퀀스에 대한 C ++ 코드
#include<iostream>
using namespace std;
int BitonicSequence( int arr[], int n )
{
int i, j;
int *increasingSeq = new int[n];
for (i = 0; i < n; i++)
increasingSeq[i] = 1;
for (i = 1; i < n; i++)
for (j = 0; j < i; j++)
if (arr[i] > arr[j] && increasingSeq[i] < increasingSeq[j] + 1)
increasingSeq[i] = increasingSeq[j] + 1;
int *decreasingSeq = new int [n];
for (i = 0; i < n; i++)
decreasingSeq[i] = 1;
for (i = n-2; i >= 0; i--)
for (j = n-1; j > i; j--)
if (arr[i] > arr[j] && decreasingSeq[i] < decreasingSeq[j] + 1)
decreasingSeq[i] = decreasingSeq[j] + 1;
int maxOutput = increasingSeq[0] + decreasingSeq[0] - 1;
for (i = 1; i < n; i++)
if (increasingSeq[i] + decreasingSeq[i] - 1 > maxOutput)
maxOutput = increasingSeq[i] + decreasingSeq[i] - 1;
return maxOutput;
}
int main()
{
int arr[] = {1,4,2,76,43,78,54,32,1,56,23};
int n = sizeof(arr)/sizeof(arr[0]);
cout<<"Length of Longest Bitonic Sequence is "<< BitonicSequence(arr, n);
return 0;
}
Length of Longest Bitonic Sequence is 7
가장 긴 Bitonic 하위 시퀀스에 대한 Java 코드
class longestBitonicSequence
{
public static int BitonicSequence( int arr[], int n )
{
int i, j;
int[] increasingSeq = new int[n];
for (i = 0; i < n; i++)
increasingSeq[i] = 1;
for (i = 1; i < n; i++)
for (j = 0; j < i; j++)
if (arr[i] > arr[j] && increasingSeq[i] < increasingSeq[j] + 1)
increasingSeq[i] = increasingSeq[j] + 1;
int[] decreasingSeq = new int [n];
for (i = 0; i < n; i++)
decreasingSeq[i] = 1;
for (i = n-2; i >= 0; i--)
for (j = n-1; j > i; j--)
if (arr[i] > arr[j] && decreasingSeq[i] < decreasingSeq[j] + 1)
decreasingSeq[i] = decreasingSeq[j] + 1;
int maxOutput = increasingSeq[0] + decreasingSeq[0] - 1;
for (i = 1; i < n; i++)
if (increasingSeq[i] + decreasingSeq[i] - 1 > maxOutput)
maxOutput = increasingSeq[i] + decreasingSeq[i] - 1;
return maxOutput;
}
public static void main (String[] args)
{
int arr[] = {1,4,2,76,43,78,54,32,1,56,23};
int n = arr.length;
System.out.println("Length of longest bitonic sequence is "+ BitonicSequence( arr, n ));
}
}
Length of longest bitonic sequence is 7
복잡성 분석
시간 복잡성
의 위에2) 어디에 "엔" 배열의 요소 수입니다. 알고리즘이 다항식 시간에 실행되도록하는 중첩 루프를 사용했기 때문입니다.
공간 복잡성
O (N) 어디에 "엔" 배열의 요소 수입니다. 크기가 입력 배열에 따라 달라지는 두 개의 추가 배열을 사용했기 때문입니다. 공간 복잡성은 선형입니다.
