시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.
차례
문제 정책
“나누기 및 정복을 사용하는 가장 긴 공통 접두사”문제에서 정수 n과 n을 지정했습니다. 문자열. 가장 긴 공통 접두사를 인쇄하는 프로그램을 작성하십시오. 공통점이 없다면 접두사 그런 다음“-1”을 인쇄하십시오.
입력 형식
첫 번째 줄에는 정수 n이 포함됩니다.
각각 하나의 문자열을 포함하는 다음 n 줄.
출력 형식
주어진 문자열의 가장 긴 공통 접두사를 나타내는 문자열을 인쇄합니다. 그러한 접두사 문자열이 없으면“-1”을 인쇄하십시오.
제약
- 1 <= n <= 10 ^ 3
- 1 <= | s [i] | <= 10 ^ 3 여기서 i는 0에서 n-1까지입니다.
- s [i] [j]는 소문자 영어 알파벳이어야합니다. 여기서 i는 0에서 n-1까지, j는 0에서 | s [i] |까지입니다.
예
3 tutorial tutcup turnin
tu
설명 : 여기서 우리는 "tu"가 모든 문자열에 나타나는 접두사임을 볼 수 있습니다.
Divide and Conquer를 사용한 가장 긴 공통 접두사 알고리즘
이 알고리즘에서는 분할 및 정복 접근 방식에 대해 설명합니다. 먼저 문자열 배열을 두 부분으로 나눕니다. 그런 다음 왼쪽 부분과 오른쪽 부분에 대해 동일한 작업을 수행합니다. 모든 문자열의 길이가 1이되지 않을 때까지이를 수행 할 것입니다. 이제 그 후에 왼쪽 및 오른쪽 문자열의 공통 접두사를 반환하여 정복을 시작합니다.
1. 길이가 1이 될 때까지 문자열 배열을 두 부분으로 재귀 적으로 나눕니다.
2. 이제 왼쪽과 오른쪽 문자열의 공통 접두사를 반환하여 정복을 시작하십시오.
실시
Divide and Conquer를 사용하는 가장 긴 공통 접두사를위한 C ++ 프로그램
#include<bits/stdc++.h>
using namespace std;
string commonPrefixUtil(string str1, string str2)
{
string result;
int n1 = str1.length(), n2 = str2.length();
for (int i=0,j=0;i<n1&&j<n2;i++,j++)
{
if(str1[i]!=str2[j])
{
break;
}
result.push_back(str1[i]);
}
return result;
}
string commonPrefix(string s[], int x, int y)
{
if(x==y)
{
return s[x];
}
if(y>x)
{
int mid=x+(y-x)/2;
string s1 = commonPrefix(s, x, mid);
string s2 = commonPrefix(s, mid+1, y);
return commonPrefixUtil(s1, s2);
}
}
int main()
{
int n;
cin>>n;
string s[n];
for(int i=0;i<n;i++)
{
cin>>s[i];
}
string ans = commonPrefix(s,0,n-1);
if(ans.length()>0)
{
cout<<ans<<endl;
}
else
{
cout<<-1<<endl;
}
return (0);
}
Divide and Conquer를 사용하는 가장 긴 공통 접두사를위한 Java 프로그램
import java.util.Scanner;
class sum {
static String commonPrefixUtil(String str1, String str2) {
String result = "";
int n1 = str1.length(), n2 = str2.length();
for (int i = 0, j = 0; i <= n1 - 1 && j <= n2 - 1; i++, j++)
{
if(str1.charAt(i)!=str2.charAt(j))
{
break;
}
result += str1.charAt(i);
}
return result;
}
static String commonPrefix(String s[], int x, int y) {
if(x==y)
{
return s[x];
}
if(y>x)
{
int mid = x + (y-x)/2;
String s1 = commonPrefix(s, x, mid);
String s2 = commonPrefix(s, mid + 1, y);
return commonPrefixUtil(s1,s2);
}
return null;
}
public static void main(String[] args)
{
Scanner sr = new Scanner(System.in);
int n = sr.nextInt();
String s[] = new String[n];
for(int i=0;i<n;i++)
{
s[i]= sr.next();
}
String ans = commonPrefix(s,0,n-1);
if(ans.length()!=0)
{
System.out.println(ans);
}
else
{
System.out.println("-1");
}
}
}
3 car carrace caramazing
car
Divide and Conquer를 사용한 가장 긴 공통 접두사에 대한 복잡성 분석
시간 복잡성
O (n * m) 어디에 n 문자열의 수이며 m 최대 문자열의 길이입니다. 여기서 우리는 시간 복잡도가 O (n * m) 인 모든 캐릭터를 방문합니다.
공간 복잡성
O (m * logn) 결과 문자열 또는 가장 긴 접두사 문자열을 저장하기 때문에 O (m * logn) 인 공간을 할당합니다.
