시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.
차례
문제 정책
확장 가능한 어레이 기반 스택은 "스택이 가득 찬"경우에 사용됩니다. 여기서 이전 어레이는 더 큰 새 어레이로 대체됩니다. 새 어레이의 크기는 다음 두 가지 전략을 사용하여 결정됩니다.
- 엄격한 전략 –이 경우 일정한 양으로 c가 이미 존재하는 스택에 추가됩니다. 즉 n = n + c 여기서 n은 기존 스택의 크기입니다.
- 성장 전략 –이 경우 기존 스택의 크기를 두 배로 늘립니다. 즉 n = 2n입니다.
확장 가능한 어레이 기반 스택을 구현하는 프로그램을 작성하십시오.
예
push(100) push(200) push(300) display() push(400) display()
Stack: 100 200 300 Stack: 100 200 300 400
설명 : 스택의 기본 작업을 수행했습니다. 그래서 먼저 100, 200, 300을 푸시 한 다음 스택 콘텐츠를 표시했습니다. 400을 푸시 한 후 스택 콘텐츠를 다시 표시했습니다.
push(1) push(2) display() push(3) display()
Stack: 1 2 Stack: 1 2 3
성장 가능한 어레이 기반 스택을위한 알고리즘
1. Create three global variables bound, top, and length, and initialize them as 3, -1, and 0 respectively. 2. After that, create a function to create extra space for an array-based stack that accepts an integer array as it's parameter. 3. Initialize a new array inside the function of length equals the sum of the length of given array and the bound variable. 4. Traverse through the given array and update the value at the current index in the new array as the value at the current index in the given array. 5. Update the variable-length as the sum of variable length itself and the bound variable and return the new array. 6. Similarly, create a function to push/insert the elements which accept an integer array and an integer variable as it's parameter. 7. Check if the value of top is equal to the length - 1, call the function to create a new array. Store the integer variable in the array at index equals to top + 1 and return the array. 8. After that, create a function to pop/remove the top element from the array. Decrement the variable top by 1. 9. Similarly, create a function to print the elements in the array which accepts an integer array as it's a parameter. 10. Check if the top is equal to -1, print "Stack is Empty". 11. Else print the array.
여기서 우리는 타이트한 전략을 사용했습니다. 스택. 우리는 매번 동일한 BOUND를 계속 추가합니다. 따라서 추가 크기를 추가해야 할 때마다 정렬, 원래 배열을 새 배열에 복사 한 다음 새 요소를 추가해야합니다. 이 접근 방식은 우리가 더 적은 공간으로 묶여 있다면 좋습니다. 그러나 더 나은 시간 복잡성을 원한다면 성장 전략을 따라야합니다.
암호
확장 가능한 어레이 기반 스택을위한 C ++ 프로그램
#include <iostream>
using namespace std;
#define BOUND 3
int top = -1;
int length = 0;
int* create_new(int* a){
int* new_a = new int[length + BOUND];
for(int i = 0; i < length; i++){
new_a[i] = a[i];
}
length += BOUND;
return new_a;
}
int* push(int* a, int element){
if(top == length - 1){
a = create_new(a);
}
a[++top] = element;
return a;
}
void pop(int* a){
top--;
}
void display(int* a){
if(top == -1){
cout << "Stack is Empty" << endl;
}
else{
cout << "Stack: ";
for(int i = 0; i <= top; i++){
cout << a[i] << " ";
}
cout << endl;
}
}
int main(){
int *a = create_new(a);
a = push(a, 100);
a = push(a, 200);
a = push(a, 300);
display(a);
a = push(a, 400);
display(a);
return 0;
}
Stack: 100 200 300 Stack: 100 200 300 400
확장 가능한 어레이 기반 스택을위한 Java 프로그램
class GrowableStack{
static final int BOUND = 3;
static int top = -1;
static int length = 0;
static int[] create_new(int[] a){
int[] new_a = new int[length + BOUND];
for(int i = 0; i < length; i++){
new_a[i] = a[i];
}
length += BOUND;
return new_a;
}
static int[] push(int[] a, int element){
if(top == length - 1){
a = create_new(a);
}
a[++top] = element;
return a;
}
static void pop(int[] a){
top--;
}
static void display(int[] a){
if(top == -1){
System.out.println("Stack is Empty");
}
else{
System.out.print("Stack: ");
for(int i = 0; i <= top; i++){
System.out.print(a[i] + " ");
}
System.out.println();
}
}
public static void main(String args[]){
int []a = create_new(new int[length + BOUND]);
a = push(a, 100);
a = push(a, 200);
a = push(a, 300);
display(a);
a = push(a, 400);
display(a);
}
}
Stack: 100 200 300 Stack: 100 200 300 400
복잡성 분석
시간 복잡성
의 위에), 왜냐하면 우리는 단순히 요소를 스택으로 밀어 넣기 때문입니다. 여기서 N은 푸시되는 요소의 수입니다. 이러한 작업은 모두 O (1)이므로 일정 시간 작업입니다. 따라서 N 시간 동안 이러한 작업을 수행하면 선형 시간 복잡도 알고리즘이 생성됩니다.
공간 복잡성
의 위에), 여기서 N은 스택의 요소 수입니다. N 개의 요소를 저장하는 단일 스택을 사용했기 때문입니다. 따라서 알고리즘은 선형 공간 복잡성을 갖습니다.
