시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.
차례
문제 설명
"스택을 사용하여 배열 정렬"문제는 데이터 구조가 제공됨을 나타냅니다. 정렬 크기 n의 a []. 종류 주어진 배열의 요소 스택 데이터 구조.
예
2 30 -5 43 100
-5 2 30 43 100
설명 : 요소는 오름차순으로 정렬됩니다.
2 3 1 8 6
1 2 3 6 8
스택을 사용하여 배열을 정렬하는 방법
주어진 입력 배열 a []의 모든 요소를 저장할 스택 데이터 구조를 만듭니다. 그런 다음 원본을 정렬하기 위해 다른 임시 스택을 만듭니다. 원래 스택을 반복하고 각 요소에 대해 상단을 팝하고 임시 변수에 저장합니다. 마찬가지로 임시 스택의 맨 위에있는 요소가 원래 스택의 팝된 맨 위에있는 요소보다 작은 동안 임시 스택을 반복합니다. 임시 스택의 맨 위 요소를 원래 스택에 삽입하고 임시 스택에서 제거합니다. 임시 스택에서 원래 스택의 튀어 나온 상단을 밉니다. 결국 임시 스택에는 정렬 된 순서로 요소가 포함됩니다. 이 문제는 정렬보다 약간의 수정입니다. 임시 스택을 사용하여 스택.
암호알고리즘
- n 크기의 배열 a []를 초기화합니다.
- 스택 데이터 구조를 만듭니다. 배열 a []를 가로 질러 스택에있는 배열 a []의 모든 요소를 밀어 넣습니다.
- 마찬가지로 다른 임시 스택을 만듭니다.
- 원래 스택의 크기가 0이 아닌 동안 트래버스합니다. 변수 tmp를 만들고 원래 스택의 맨 위에 요소를 저장하고 원래 스택에서 팝합니다.
- 임시 스택이 비어 있지 않은 동안 다시 트래버스하고 변수 tmp보다 적을 때까지 임시 스택의 맨 위에있는 요소를 팝합니다. 임시 스택에서 튀어 나오는 동안 원래 스택에서 임시 스택의 맨 위 요소를 푸시합니다.
- 임시 스택에 변수 tmp를 푸시합니다.
- 0에서 n-1로 이동하고 임시 스택의 최상위 요소를 현재 인덱스의 배열 a []에 저장하고 임시 스택에서 요소를 팝 / 삭제합니다.
- 마지막으로 0에서 n-1로 이동하고 a [] 배열을 인쇄합니다.
암호
스택을 사용한 배열 정렬을위한 C ++ 프로그램
#include <iostream>
#include <stack>
using namespace std;
stack<int> sortStack(stack<int> input){
stack<int> tmpStack;
while(!input.empty()){
int tmp = input.top();
input.pop();
while (!tmpStack.empty() && tmpStack.top() < tmp){
input.push(tmpStack.top());
tmpStack.pop();
}
tmpStack.push(tmp);
}
return tmpStack;
}
void sortUsingStack(int arr[], int n){
stack<int> input;
for(int i=0; i<n; i++){
input.push(arr[i]);
}
stack<int> tmpStack = sortStack(input);
for(int i=0; i<n; i++){
arr[i] = tmpStack.top();
tmpStack.pop();
}
}
int main(){
int a[] = {2, 30, -5, 43, 100};
int n = sizeof(a)/sizeof(a[0]);
sortUsingStack(a, n);
for(int i=0; i<n; i++)
cout << a[i] << " ";
return 0;
}
-5 2 30 43 100
스택을 사용한 배열 정렬을위한 Java 프로그램
import java.io.*;
import java.util.*;
class SortArrayWithStack{
static Stack<Integer> sortStack(Stack<Integer> input){
Stack<Integer> tmpStack = new Stack<Integer>();
while(!input.empty()){
int tmp = input.peek();
input.pop();
while(!tmpStack.empty() && tmpStack.peek() < tmp){
input.push(tmpStack.peek());
tmpStack.pop();
}
tmpStack.push(tmp);
}
return tmpStack;
}
static void sortUsingStack(int []arr, int n){
Stack<Integer> input = new Stack<Integer>();
for(int i = 0; i < n; i++){
input.push(arr[i]);
}
Stack<Integer> tmpStack = sortStack(input);
for(int i = 0; i < n; i++){
arr[i] = tmpStack.peek();
tmpStack.pop();
}
}
public static void main(String args[]){
int []a = {2, 30, -5, 43, 100};
int n = a.length;
sortUsingStack(a, n);
for(int i = 0; i < n; i++){
System.out.print(a[i] + " ");
}
}
}
-5 2 30 43 100
복잡성 분석
시간 복잡성
O (n ^ 2) 여기서 n은 스택의 요소 수입니다. 임시 스택의 맨 위가 푸시 할 요소보다 작은 경우 임시 스택에서 원래 스택으로 요소를 다시 푸시하기 때문입니다. 더 나은 이해를 위해 내림차순 순서를 고려하고 알고리즘을 실행 해보십시오.
공간 복잡성
O (N) n 개의 요소에 임시 스택 공간을 사용했기 때문입니다. 원래 스택에서 사용한 공간은 알고리즘에 포함되지 않습니다.
