시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.
차례
문제 정책
주어진 현 길이 / 크기 n의 s 및 여는 대괄호의 인덱스를 나타내는 정수 값. 식에서 주어진 여는 대괄호에 대한 닫는 대괄호의 색인을 찾습니다.
예
s = "[ABC[23]][89]" index = 0
8
s = "[C-[D]]" index = 3
5
s = "E-[FX]]" index = 0
-1
접근
사용하십시오 스택 데이터 구조 정수 주어진 문자열에서 여는 괄호의 인덱스를 저장하려면 type. 주어진 반복 시작 현 주어진 색인에서 시작합니다. 여는 괄호가 발견되면 스택에 밀어 넣습니다. 접하는 모든 닫는 대괄호에 대해 스택에서 여는 대괄호를 꺼냅니다. 스택이 비어있는 경우, 즉 스택의 크기가 일부 인덱스에서 0이면 인덱스를 인쇄합니다. 그렇지 않으면 -1을 인쇄하십시오.
암호알고리즘
- 길이 / 크기의 문자열 초기화 n 및 여는 대괄호의 인덱스를 나타내는 정수 값.
- 표현식을 나타내는 문자열 값과 주어진 문자열에서 여는 괄호의 인덱스를 나타내는 정수 값을 매개 변수로 받아들이는 주어진 문자열에서 주어진 여는 괄호에 대한 닫는 괄호의 인덱스를 찾는 함수를 만듭니다.
- 주어진 색인에있는 문자가 여는 괄호와 같지 않은지 확인하십시오. 즉 '[', -1을 인쇄하고 리턴하십시오.
- 그 후 정수 유형의 스택 데이터 구조를 생성하여 주어진 문자열의 여는 괄호 인덱스를 저장합니다.
- 주어진 색인에서 시작하여 주어진 문자열을 순회하고 문자열의 현재 색인에있는 문자가 여는 대괄호와 같은지 확인하고 스택의 문자열에서 현재 색인에있는 문자를 푸시 / 삽입합니다.
- 그렇지 않으면 문자열의 현재 색인에있는 문자가 닫는 대괄호, 즉 ']'와 같으면 스택 맨 위에있는 요소를 팝 / 제거합니다. 그 후 스택이 비어 있는지 확인합니다. 즉, 스택의 크기가 0과 같은지 확인하고 현재 인덱스를 인쇄하고 반환합니다.
- 인쇄 -1.
암호
여는 대괄호에 해당하는 닫는 대괄호를 찾는 C ++ 프로그램
#include <bits/stdc++.h>
using namespace std;
void test(string expression, int index){
int i;
if(expression[index]!='['){
cout << "-1\n";
return;
}
stack <int> st;
for(i = index; i < expression.length(); i++){
if(expression[i] == '['){
st.push(expression[i]);
}
else if(expression[i] == ']'){
st.pop();
if(st.empty()){
cout << i << "\n";
return;
}
}
}
cout << "-1\n";
}
int main() {
string s = "[ABC[23]][89]";
int index = 0;
test(s, index);
return 0;
}
8
여는 대괄호에 해당하는 닫는 대괄호를 찾는 Java 프로그램
import java.util.Stack;
class FindIndex{
static void test(String expression, int index){
int i;
if(expression.charAt(index) != '['){
System.out.print("-1\n");
return;
}
Stack<Integer> st = new Stack<>();
for(i = index; i < expression.length(); i++){
if(expression.charAt(i) == '['){
st.push((int) expression.charAt(i));
}
else if(expression.charAt(i) == ']'){
st.pop();
if(st.empty()){
System.out.print( i );
return;
}
}
}
System.out.print("-1\n");
}
public static void main(String[] args){
String s = "[ABC[23]][89]";
int index = 0;
test(s, index);
}
}
8
복잡성 분석
시간 복잡성
O (n) 여기서 n은 주어진 문자열 s의 길이입니다. 문자열에서 사용 가능한 모든 문자를 순회했기 때문에 시간 복잡도는 선형입니다.
공간 복잡성
O (n) 주어진 문자열의 문자를 저장하기 위해 공백을 사용했기 때문입니다. 공간 복잡성은 브래킷 수에 따라 다릅니다. 그러나 최악의 경우 모든 문자가 대괄호 일 수 있습니다. 따라서 공간 복잡성도 선형입니다.
