시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.
차례
문제 정책
An 정렬 n 개의 정수가 우리에게 주어집니다. 우리는 최대 합계 비트 배열 하위 배열. 비 토닉 하위 배열은 요소가 특정 순서로 배열되는 하위 배열 일뿐입니다. 첫 번째 요소는 오름차순이되고 내림차순이됩니다. 따라서 a, a + 1, a + 4, a + 7, a-9, a-11과 같은 것입니다. 여기서 상수는 배열에 부과 된 조건을 만족하는 난수 일뿐입니다. 이것은 단지 그들의 순서를 보여주는 것입니다.
예
Size of array = 7
Array = {1 2 5 4 10 20 1}
25
설명 : 가능한 두 개의 비트 배열이 있습니다. 하나의 서브 어레이는 {1 2 5 4}이고 다른 하나는 {4 10 20 1}입니다. 최대 합이 필요하므로 두 번째 하위 배열을 선택합니다. 그리고 우리의 답은 4 + 10 + 20 + 1 = 25입니다.
Size of array = 4
Array = { 100 200 300 10}
610
설명 : 전체 배열이 우리의 조건을 만족하기 때문에. 답은 610입니다.
최대 합 바이 토닉 부분 배열 문제에 대한 접근 방식
순진한 접근
하위 배열의 왼쪽 및 오른쪽 경계에 두 개의 포인터를 사용할 수 있습니다. 하위 배열을 수정 한 후이 시퀀스가 비트인지 여부를 확인합니다. 이것이 bitonic subarray이면 합계를 취하고 그에 따라 답변을 업데이트합니다. 이 접근 방식을 따르면 XNUMX 개의 중첩 된 루프 확실히 가능한 최선의 방법은 아닙니다.
효율적인 접근
이 문제를 선형 시간 복잡성으로 해결할 수 있습니다. 두 개의 하위 배열을 생성하면 왼쪽 (left) 및 권리, 이는 피크가 현재 요소인지, 왼쪽 방향으로 얼마나 멀리 갈 수 있고 그 합계를 왼쪽 배열의 i 번째 인덱스에 저장할 수 있는지를 나타냅니다. 우리는 속성까지 왼쪽 방향으로 갈 수 있습니다 arr [i-1] 왼쪽 방향의 모든 요소에 대해 만족합니다. 마찬가지로 올바른 하위 배열에 대해서도 수행합니다. 이제 원래 배열을 탐색하여 현재 요소가 비트 배열의 피크 일 때 만들 수있는 비트 배열의 최대 합을 찾습니다. 각 색인에서 우리는 답변을 계속 업데이트합니다.
최대 합 비트 토닉 부분 배열을 찾는 코드
C ++ 코드
#include <bits/stdc++.h>
using namespace std;
int main(){
int testCases;cin>>testCases;
while(testCases--){
int inputSize;cin>>inputSize;
long long int input[inputSize];
for(int i=0;i<inputSize;i++){
cin>>input[i];
}
long long int leftSum[inputSize], rightSum[inputSize];
for(int i=0;i<inputSize;i++)
leftSum[i] = rightSum[i] = input[i];
leftSum[0] = input[0];
for(int i=1;i<inputSize;i++){
if(input[i-1] < input[i])
leftSum[i] += leftSum[i-1];
}
rightSum[inputSize-1] = input[inputSize-1];
for(int i=inputSize-2;i>=0;i--){
if(input[i] > input[i+1])
rightSum[i] += rightSum[i+1];
}
long long int answer = LLONG_MIN;
for(int i=0;i<inputSize;i++){
answer = max(answer, leftSum[i] + rightSum[i] - input[i]);
}
cout<<answer<<endl;
}
return 0;
}
2 5 1 2 5 3 10 5 10 50 10 90 10
13 110
자바 코드
import java.util.*;
import java.lang.*;
import java.io.*;
class Main {
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int testCases = sc.nextInt();
while(testCases-- > 0){
int inputSize = sc.nextInt();
long input[] = new long[inputSize];
for(int i=0;i<inputSize;i++){
input[i] = sc.nextInt();
}
long leftSum[] = new long[inputSize];
long rightSum[] = new long[inputSize];
for(int i=0;i<inputSize;i++) {
leftSum[i] = input[i];
rightSum[i] = input[i];
}
leftSum[0] = input[0];
for(int i=1;i<inputSize;i++){
if(input[i-1] < input[i])
leftSum[i] += leftSum[i-1];
}
rightSum[inputSize-1] = input[inputSize-1];
for(int i=inputSize-2;i>=0;i--){
if(input[i] > input[i+1])
rightSum[i] += rightSum[i+1];
}
long answer = Long.MIN_VALUE;
for(int i=0;i<inputSize;i++){
answer = Math.max(answer, leftSum[i] + rightSum[i] - input[i]);
}
System.out.println(answer);
}
}
}
2 5 1 2 5 3 10 5 10 50 10 90 10
13 110
복잡성 분석
시간 복잡성: 의 위에)
배열을 한두 번 통과하고 중첩 루프가 없었기 때문에. 선형 시간 복잡성이 있습니다.
공간 복잡성: 의 위에)
여기서 우리는 size = inputSize의 leftSum 및 rightSum이라는 두 개의 임시 배열을 만들었습니다. 1 차원 배열이기 때문에 선형 공간 복잡성도 있습니다.
