시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.
차례
문제 정책
“Length of Longest valid Substring”에서 우리는 현 여는 괄호와 닫는 괄호 만 포함합니다. 가장 오래 유효한 프로그램을 작성하십시오. 괄호 부분 문자열.
입력 형식
문자열 s를 포함하는 첫 번째 및 유일한 행.
출력 형식
가장 긴 유효한 괄호 하위 문자열의 길이를 나타내는 정수 n을 포함하는 첫 번째 및 유일한 행입니다.
제약
- 1 <= | s | <= 10 ^ 5
- s [i]는 '('또는 ')'여야합니다.
예
(())())
6
설명 : "(()) ()"는 위에 주어진 문자열에서 가장 긴 유효한 괄호 하위 문자열입니다. 그래서 우리의 답은 6입니다.
유효한 가장 긴 부분 문자열의 길이에 대한 알고리즘
1. 빈 스택을 만들고 여기에 -1을 푸시합니다. -1은 다음 유효한 문자열에 대한 기본 케이스를 제공하는 것입니다.
2. 출력을 저장할 변수 'res'생성
3. 모든 문자를 처음부터 끝까지 순회
a. 문자가 '('이면 현재 인덱스를 스택으로 푸시합니다.
b. 그밖에,
- 스택에서 요소를 팝합니다.
- 스택이 비어 있지 않은 경우 현재 인덱스와 스택 맨 위의 차이를 사용하여 현재 유효한 하위 문자열의 길이를 찾습니다. 현재 길이가 결과보다 긴지 확인한 다음 결과를 업데이트하십시오.
- 스택이 비어 있으면 현재 인덱스를 다음 유효한 하위 문자열의 기준으로 푸시합니다.
4. 'res'반환
알고리즘 구현-
s =“(())”
-1을 스택에 넣고 res = 0을 초기화합니다.
i = 0, s [0] = '(', 0을 스택으로 푸시, 이제 스택 = [-1,0]
i = 1, s [1] = '(', 1을 스택으로 푸시, 이제 스택 = [-1,0,1]
i = 2, s [2] = ')', pop ()이므로 이제 스택 = [-1,0]
res = max (res, i – stack.top ()) = max (0, 2-0) = max (0,2) = 2
i = 3, s [3] = ')', pop () 이제 스택 = [-1]
res = max (res, i – stack.top ()) = max (2, 3-(-1)) = max (2,4) = 4
따라서 가장 긴 길이는 = res = 4입니다.
실시
유효한 가장 긴 부분 문자열의 길이에 대한 C ++ 프로그램
#include<bits/stdc++.h>
using namespace std;
int maxLength(string s)
{
int n = s.length();
// Create a stack and push -1 as initial index to it.
stack<int> stck;
stck.push(-1);
// Initialize res
int res = 0;
// Traverse all characters of given string
for (int i=0; i<n; i++)
{
// If opening bracket, push index of it
if (s[i] == '(')
stck.push(i);
else // If closing bracket, i.e.,s[i] = ')'
{
// Pop the previous opening bracket's index
stck.pop();
// Check if this length formed with base of
// current valid substring is more than max
// so far
if (!stck.empty())
res = max(res, i - stck.top());
// If stack is empty. push current index as
// base for next valid substring (if any)
else stck.push(i);
}
}
return res;
}
int main()
{
string s;
cin>>s;
cout<<maxLength(s)<<endl;
return 0;
}
가장 긴 유효한 하위 문자열 길이를위한 Java 프로그램
import static java.lang.Math.max;
import java.util.Scanner;
import java.util.Stack;
class sum
{
public static int maxLength(String s)
{
int n = s.length();
// Create a stack and push -1 as initial index to it.
Stack<Integer> stck = new Stack<Integer>();
stck.push(-1);
// Initialize res
int res = 0;
// Traverse all characters of given string
for (int i=0; i<n; i++)
{
// If opening bracket, push index of it
if(s.charAt(i) == '(')
stck.push(i);
else // If closing bracket, i.e.,s[i] = ')'
{
// Pop the previous opening bracket's index
stck.pop();
// Check if this length formed with base of
// current valid substring is more than max
// so far
if(stck.size()>0)
res = max(res, i - (Integer) stck.peek());
// If stack is empty. push current index as
// base for next valid substring (if any)
else stck.push(i);
}
}
return res;
}
public static void main(String[] args)
{
Scanner sr = new Scanner(System.in);
String s = sr.next();
System.out.println(maxLength(s));
}
}
(()())((
6
가장 긴 유효 부분 문자열의 길이에 대한 복잡성 분석
시간 복잡성
O (N) 어디에 n 주어진 문자열의 크기입니다. 여기서 우리는 char 단위로 string char을 탐색하고 일정한 시간에 몇 가지 작업을 수행합니다.
공간 복잡성
O (N) 스택을 사용하기 때문입니다. 여기서 스택의 최대 크기는 n입니다.
