시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.
주어진 정렬 크기 n의 a []. 위치의 각 요소에 대해 L [i] 및 R [i]를 찾습니다. 여기서 – L [i] = i에 가장 가까운 인덱스, 여기서 L [가장 가까운 인덱스]> L [i] 및 가장 가까운 인덱스 <i. R [i] = i에 가장 가까운 인덱스, 여기서 R [가장 가까운 인덱스]> R [i] 및 가장 가까운 인덱스> i. L [i] 또는 R [i]에 대해 이러한 인덱스가 없으면 0으로 업데이트합니다. L과 R의 최대 곱을 찾으십시오. 여기서 – LR Product [i] = L [i] * R [i].
차례
예
입력 : a [] = {5, 4, 3, 4, 5}
출력 : 8
입력 : a [] = {1, 1, 1, 1, 0, 1, 1, 1, 1, 1}
출력 : 24
암호알고리즘
- n 크기의 배열 a []를 초기화합니다.
- 가장 가까운 큰 요소의 왼쪽 및 오른쪽 인덱스를 저장하기 위해 두 개의 다른 배열을 초기화합니다.
- 만들기 스택. n-1에서 0으로 트래버스하고 스택이 비어 있지 않고 a [current index]가 a [stack.top () – 1])보다 크면 인덱스 stack.top () – 1에서 현재 인덱스로 왼쪽 배열을 업데이트합니다. + 1. 상단을 팝니다.
- 스택에 현재 index + 1을 삽입합니다.
- 올바른 배열의 경우 스택을 만듭니다. 0에서 n-1로 이동하고 스택이 비어 있지 않고 a [현재 인덱스]가 a [stack.top () – 1])보다 크면 인덱스 stack.top () – 1에서 현재 인덱스로 오른쪽 배열을 업데이트합니다. +1. 상단을 팝니다.
- 스택에 현재 index + 1을 삽입합니다.
- 답변을 저장할 변수를 만들고 -1로 초기화합니다. 0에서 n-1로 이동하고 왼쪽 배열과 오른쪽 배열의 현재 인덱스에있는 값의 곱과 응답 변수의 최대 값으로 응답 변수를 업데이트합니다.
- 답 변수를 반환합니다.
왼쪽과 오른쪽에서 다음으로 큰 인덱스의 최대 곱을 찾는 C ++ 프로그램
#include <bits/stdc++.h>
using namespace std;
#define MAX 1000
vector<int> nextGreaterInLeft(int a[], int n){
vector<int> left_index(MAX, 0);
stack<int> s;
for(int i = n - 1; i >= 0; i--){
while(!s.empty() && a[i] > a[s.top() - 1]){
int r = s.top();
s.pop();
left_index[r - 1] = i + 1;
}
s.push(i + 1);
}
return left_index;
}
vector<int> nextGreaterInRight(int a[], int n){
vector<int> right_index(MAX, 0);
stack<int> s;
for(int i = 0; i < n; ++i){
while(!s.empty() && a[i] > a[s.top() - 1]){
int r = s.top();
s.pop();
right_index[r - 1] = i + 1;
}
s.push(i + 1);
}
return right_index;
}
int Product(int a[], int n){
vector<int> left = nextGreaterInLeft(a, n);
vector<int> right = nextGreaterInRight(a, n);
int ans = -1;
for(int i = 1; i <= n; i++){
ans = max(ans, left[i] * right[i]);
}
return ans;
}
int main(){
int a[] = {5, 4, 3, 4, 5};
int n = sizeof(a)/sizeof(a[1]);
cout<<Product(a, n);
return 0;
}
8
왼쪽과 오른쪽에서 다음으로 큰 인덱스의 최대 제품을 찾는 Java 프로그램
import java.io.*;
import java.util.*;
class LRProduct{
static int MAX = 1000;
static int[] nextGreaterInLeft(int []a, int n){
int []left_index = new int[MAX];
Stack<Integer> s = new Stack<Integer>();
for(int i = n-1; i >= 0; i--){
while (s.size() != 0 && a[i] > a[s.peek() - 1]){
int r = s.peek();
s.pop();
left_index[r - 1] = i + 1;
}
s.push(i + 1);
}
return left_index;
}
static int[] nextGreaterInRight(int []a, int n){
int []right_index = new int[MAX];
Stack<Integer> s = new Stack<Integer>();
for(int i = 0; i < n; ++i){
while (s.size() != 0 && a[i] > a[s.peek() - 1]){
int r = s.peek();
s.pop();
right_index[r - 1] = i + 1;
}
s.push(i + 1);
}
return right_index;
}
static int Product(int []a, int n){
int []left = nextGreaterInLeft(a, n);
int []right = nextGreaterInRight(a, n);
int ans = -1;
for(int i = 1; i <= n; i++){
ans = Math.max(ans, left[i] * right[i]);
}
return ans;
}
public static void main(String args[]){
int []a = new int[]{5, 4, 3, 4, 5};
int n = a.length;
System.out.print(Product(a, n));
}
}
8
왼쪽과 오른쪽에서 다음으로 큰 인덱스의 최대 곱을 찾기위한 복잡성 분석
시간 복잡성 : O (n * n) 여기서 n은 배열 a []의 요소 수입니다.
보조 공간 : O (n) n 개의 추가 공간을 사용했기 때문입니다.
