시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.
이 문제는“주식 스팬 문제”는 재정적 측면에서 발생합니다. 이 문제에서 우리는 매일의 주가에 대한 주식 스팬을 찾습니다. 전날의 주식 가격이 주식의 가격보다 작거나 같은 특정 일 직전의 최대 연속 일수를 스팬이라고합니다.
위의 재고 스팬 문제 이미지에서와 같이 –
1 일째, 주가 100 – 연속 된 전일의 더 작은 주가가 없으므로 범위 = 1
2 일, 주가 80 – 연속 된 전일의 주가가 더 작지 않으므로 범위 = 1
3 일, 주가 60 – 연속 된 전일의 주가가 더 작지 않으므로 범위 = 1
4 일차, 주가 70 – 3 일차의 주가가 더 작습니다. 즉, 60 일, 스팬 = 2
5 일, 주가 60 – 연속 된 전일의 주가가 더 작지 않으므로 범위 = 1
6 일, 주가 75 – 3 일, 4 일, 5 일은 주가가 더 작습니다 (예 : 각각 60, 70, 60), 따라서 범위 = 4
7 일차 주가 85 – 2 일차, 3 일차, 4 일차, 5 일차 및 6 일차는 주가가 더 작습니다 (예 : 각각 80, 60, 70, 60, 75), 따라서 범위 = 6
차례
예
입출력에 대한 이해를 위해 주식 스팬 문제의 몇 가지 예를 살펴 보겠습니다.
입력 : 가격 = {100, 80, 60, 70, 60, 75, 85}
출력 : 7 일 기간 : 1 1
입력 : 가격 = {10, 4, 5, 90, 120, 80}
출력 : 6 일의 기간 : 1 1 2 4
스택을 사용하지 않고
주식 스팬 문제에 대한 순진한 방법
암호알고리즘
- 초기화 정렬 n 일의 주가를 저장합니다.
- 범위를 저장하기 위해 크기가 n 인 또 다른 배열 S를 만듭니다.
- 1에서 n-1로 이동하고 S []의 현재 인덱스에있는 값을 1로 설정합니다. 외부 루프의 인덱스에있는 가격이 현재의 가격보다 크거나 같은 동안 외부 루프 -1에서 0까지 내부 루프를 초기화합니다. 내부 루프의 인덱스를 사용하고 내부 루프의 모든 단계에서 S []의 현재 인덱스를 증가시킵니다.
- 배열 S []를 인쇄합니다.
주식 스팬 문제에 대한 C ++ 프로그램
#include <bits/stdc++.h>
using namespace std;
void calculateSpan(int price[], int n, int S[]){
S[0] = 1;
for(int i = 1; i < n; i++){
S[i] = 1;
for (int j = i - 1; (j >= 0) &&
(price[i] >= price[j]); j--)
S[i]++;
}
}
void display(int arr[], int n){
cout<<"Span of "<<n<<" days : ";
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
}
int main(){
int price[] = {100, 80, 60, 70, 60, 75, 85};
int n = sizeof(price) / sizeof(price[0]);
int S[n];
calculateSpan(price, n, S);
display(S, n);
return 0;
}
Span of 7 days : 1 1 1 2 1 4 6
주식 스팬 문제를위한 자바 프로그램
Span of 7 days : 1 1 1 2 1 4 6
복잡성 분석
시간 복잡성 : O (n * n) 여기서 n은 주가가 제공되는 일수입니다.
보조 공간 : O (n) n 주가에 대해 스팬을 저장하기 위해 공간을 사용했기 때문입니다.
스택 사용
재고 스팬 문제를위한 효율적인 방법
암호알고리즘
- n 일의 주가를 저장하도록 배열을 초기화합니다.
- 스팬과 정수 유형의 스택 st를 저장하기 위해 크기가 n 인 또 다른 배열 S를 만듭니다.
- 1에서 n-1로 이동하는 동안 스택 비어 있지 않고 현재 인덱스의 가격이 스택 상단의 값과 동일한 인덱스의 가격보다 크거나 같으면 상단을 팝합니다.
- 현재 인덱스 + 1이 스택이면 S []의 현재 인덱스를 업데이트하고, 그렇지 않으면 현재 인덱스는 스택의 맨 위에 있고 스택에 현재 인덱스를 푸시 / 삽입합니다.
- 루프 후에 배열 S []를 인쇄합니다.
주식 스팬 문제에 대한 C ++ 프로그램
#include <bits/stdc++.h>
using namespace std;
void calSpan(int price[], int n, int S[]){
stack<int> st;
st.push(0);
S[0] = 1;
for(int i = 1; i < n; i++){
while ((!st.empty()) && (price[st.top()] <= price[i])){
st.pop();
}
S[i] = (st.empty()) ? (i + 1) : (i - st.top());
st.push(i);
}
}
void display(int arr[], int n){
cout<<"Span of "<<n<<" days : ";
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
}
int main(){
int price[] = {100, 80, 60, 70, 60, 75, 80 };
int n = sizeof(price) / sizeof(price[0]);
int S[n];
calSpan(price, n, S);
display(S, n);
return 0;
}
Span of 7 days : 1 1 1 2 1 4 6
주식 스팬 문제를위한 자바 프로그램
import java.util.Arrays;
import java.util.Stack;
class spanStock{
static void calSpan(int price[], int n, int S[]){
Stack<Integer> st = new Stack<>();
st.push(0);
S[0] = 1;
for(int i = 1; i < n; i++){
while((!st.empty()) && (price[st.peek()] <= price[i])){
st.pop();
}
S[i] = (st.empty()) ? (i + 1) : (i - st.peek());
st.push(i);
}
}
static void display(int arr[]){
System.out.print("Span of "+arr.length+" days : ");
for (int i = 0; i < arr.length; i++)
System.out.print(arr[i]+" ");
}
public static void main(String[] args){
int price[] = {100, 80, 60, 70, 60, 75, 85};
int n = price.length;
int S[] = new int[n];
calSpan(price, n, S);
display(S);
}
}
Span of 7 days : 1 1 1 2 1 4 6
복잡성 분석
시간 복잡성 : O (n) 여기서 n은 주가가 제공되는 일수입니다.
보조 공간 : O (n) n 주가에 대해 스팬을 저장하기 위해 공간을 사용했기 때문입니다.
