시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.
차례
문제 정책
"Palindrome Substring Queries"문제는 문자열과 일부 쿼리가 제공되었음을 나타냅니다. 이러한 쿼리를 사용하여 해당 쿼리에서 형성된 하위 문자열이 회문인지 여부를 확인해야합니다.
예
String str = "aaabbabbaaa"
Queries q[] = { {2, 3}, {2, 8},{5, 7}, {3, 7} }
The Substring [2 3] is not a palindrome The Substring [2 8] is a palindrome The Substring [5 7] is not a palindrome The Substring [3 7] is a palindrome
설명 : 하위 문자열 [2,8]은 회문이므로 결과는 YES입니다. 하위 문자열은 "abbabba"입니다.
접근
각 쿼리를 기반으로 문자열과 몇 가지 쿼리를 제공했습니다. 이렇게 형성된 부분 문자열을 결정해야합니다. 회문 또는 아닙니다. 문자열 사용 해싱 이것을 해결하기 위해. 원래 문자열에 대해 하나와 반전 된 문자열에 대해 하나씩 두 개의 배열을 사용할 것입니다. 그런 다음 String의 해시 값을 저장합니다. 여기서 해시 값은 서로 다를 수 있습니다. String []에 대해 해시 값을 취하고 반전 된 문자열에 대해 해시 값을 반대로한다고 가정합니다. 접두사와 접미사 배열을 사용할 것입니다.
String str :“aabbbababaaa”가 있다고 가정합니다.
str의 해시 값을 다음과 같이 저장합니다.
접두사 [i] = str [0] + str [1] * 101 + str [2] * 1012 + ………. + str [i-1] * 101 *I-1 .
접두사 [i]의 각 값에 대해. 다음과 같은 값을 갖게됩니다.
Prefix[0]=0, Prefix[1]= 97 + 97 *101, ( 0+ ASCII value of a) Prefix[2]= 97 + 97 *101 + 98 *101^2 Prefix[3]= 97 + 97 *101 + 98 *101^2 + 98 *101^3 ( 0 + ASCII value of a’s and ASCII value of b). . . . Prefix [12]= 97 + 97 *101 + 98 *101^2 + 98 *101^3 +…… +97 *101^11 as length of String is 12.
이제 많은 사람들이 왜 이것이 이런 방식으로 해시 값을 저장하는 방법인지 생각하고 있습니다. 답은 최소한의 시간 복잡성으로 간단한 공식을 사용하여 주어진 하위 문자열의 해시 값을 검색하는 방법입니다.
해시 값 (왼쪽, 오른쪽) = 접두사 [오른쪽 + 1] – 접두사 [왼쪽].
왼쪽과 오른쪽은 하위 문자열 시작 지점이 될 수 있습니다. 문자열 (2, 4) = "bbb"의 해시 값을 찾으려면 다음과 같이됩니다.
접두사 [5] – 접두사 [2] = 98 * 1013 + 98 * 1014 + 98 * 1015.
이 값은 회문을 찾는 데 도움이됩니다. 접미사 배열로도 똑같이 할 것이기 때문에 이번에는 마지막으로 방법을 살펴 보겠습니다.
문자열 str : "aabbbababaaa".
suffix[i] = str[n-1]+ str[n-2] *101 + str[n-3]*1022 + ……….+ str[n-i]*101*i-1 . suffix[0]=0, suffix [1]= 97 + 97 *101, ( 0+ ASCII value of a) suffix [2]= 97 + 97 *101 + 97 *101^2, suffix [3]= 97 + 97 *101 + 97 *101^2 + 98 *101^3 ( 0 + ASCII value of a’s and ASCII value of b). . . . . suffix [11]= 97 + 97 *101 + 97 *101^2 + 98 *101^3 +…… +97 *101^10 as length of String is 11.
이제 다음을 사용하여 역 해시 값의 값을 계산할 수 있습니다.
역 해시 값 (왼쪽, 오른쪽) : 해시 값 (오른쪽, 왼쪽) = 접미사 [n- 왼쪽] – 접미사 [n- 오른쪽 -1].
예
예 : 문자열 str : "aabbbababaaa".
역 해시 값 : substring (2,4) :
"bbba"의 값을 반대로하면 "abbb"가됩니다.
Suffix [11-1] – suffix [11-4-1] = suffix [10] -suffix [6].
그리고 지금 우리는 회문이 존재하는지 알아내는 방정식을 가지고 있습니다.
이제 우리는 접두사와 접미사로 두 개의 배열을 가지고 있으며, 그들 사이에 관계가 있습니다.
(접두사 [오른쪽 + 1] – 접두사 [왼쪽]) = (접미사 [n – 왼쪽] – 접미사 [n – 오른쪽-1])
(101좌회전) (101n – 오른쪽 – 1)
암호
회문 하위 문자열 쿼리에 대한 C ++ 코드
#include<iostream>
using namespace std;
#define p 101
#define MOD 1000000007
struct Queries
{
int left, right;
};
bool CheckPalindrome(string str, int left, int right)
{
while (right > left)
if (str[left++] != str[right--])
return (false);
return (true);
}
unsigned long long int moduloPower(unsigned long long int base,unsigned long long int exponent)
{
if (exponent == 0)
return 1;
if (exponent == 1)
return base;
unsigned long long int temp = moduloPower(base, exponent / 2);
if (exponent % 2 == 0)
return (temp % MOD * temp % MOD) % MOD;
else
return (((temp % MOD * temp % MOD) % MOD)* base % MOD)% MOD;
}
unsigned long long int ModuloMultiplicativeInverse(unsigned long long int n)
{
return moduloPower(n, MOD - 2);
}
void HashPrefix( string str, int n, unsigned long long int prefix[], unsigned long long int powerArr[])
{
prefix[0] = 0;
prefix[1] = str[0];
for (int i = 2; i <= n; i++)
prefix[i] = (prefix[i - 1] % MOD + (str[i - 1] % MOD * powerArr[i - 1] % MOD) % MOD) % MOD;
return;
}
void HashSuffix( string str, int n, unsigned long long int suffix[], unsigned long long int powerArr[])
{
suffix[0] = 0;
suffix[1] = str[n - 1];
for (int i = n - 2, j = 2; i >= 0 && j <= n; i--, j++)
suffix[j] = (suffix[j - 1] % MOD+ (str[i] % MOD* powerArr[j - 1] % MOD)% MOD)% MOD;
return;
}
void GetQueryOutput(string str, Queries q[], int m, int n, unsigned long long int prefix[], unsigned long long int suffix[], unsigned long long int powerArr[])
{
for (int i = 0; i <= m - 1; i++)
{
int left = q[i].left;
int right = q[i].right;
unsigned long long HashValue= ((prefix[right + 1] - prefix[left] + MOD) % MOD* ModuloMultiplicativeInverse(powerArr[left]) % MOD)% MOD;
unsigned long long reverseHashValue= ((suffix[n - left] - suffix[n - right - 1] + MOD) % MOD* ModuloMultiplicativeInverse(powerArr[n - right - 1]) % MOD)% MOD;
if (HashValue == reverseHashValue)
{
if (CheckPalindrome(str, left, right) == true)
cout<<"The Substring ["<< left <<" "<<right<<"] is a palindrome\n";
else
cout<<"The Substring ["<< left <<" "<<right<<"] is a palindrome\n";
}
else
cout<<"The Substring ["<< left <<" "<<right<<"] is not a palindrome\n";
}
return;
}
void assginedPowers(unsigned long long int powerArr[], int n)
{
powerArr[0] = 1;
for (int i = 1; i <= n; i++)
powerArr[i] = (powerArr[i - 1] % MOD * p % MOD) % MOD;
return;
}
int main()
{
string str = "aaabbabbaaa";
int n = str.length();
unsigned long long int powerArr[n + 1];
assginedPowers(powerArr, n);
unsigned long long int prefix[n + 1];
unsigned long long int suffix[n + 1];
HashPrefix(str, n, prefix, powerArr);
HashSuffix(str, n, suffix, powerArr);
Queries q[] = { {2, 3}, {2, 8},{5, 7}, {3, 7} };
int m = sizeof(q) / sizeof(q[0]);
GetQueryOutput(str, q, m, n, prefix, suffix, powerArr);
return (0);
}
The Substring [2 3] is not a palindrome The Substring [2 8] is a palindrome The Substring [5 7] is not a palindrome The Substring [3 7] is a palindrome
Palindrome 하위 문자열 쿼리를위한 Java 코드
public class PalindromeSubstringQuery
{
static int p = 101;
static int MOD = 1000000007;
public static class Queries
{
int left, right;
public Queries(int left, int right)
{
this.left = left;
this.right = right;
}
}
public static boolean CheckPalindrome(String str, int left, int right)
{
while (right > left)
{
if (str.charAt(left++) != str.charAt(right--))
return (false);
}
return (true);
}
public static int moduloPower(int base, int exponent)
{
if (exponent == 0)
{
return 1;
}
if (exponent == 1)
{
return base;
}
int temp = moduloPower(base, exponent / 2);
if (exponent % 2 == 0)
{
return (temp % MOD * temp % MOD) % MOD;
}
else
{
return (((temp % MOD * temp % MOD) % MOD) * base % MOD) % MOD;
}
}
public static int ModuloMultiplicativeInverse(int n)
{
return moduloPower(n, MOD - 2);
}
public static void HashPrefix(String str, int n,int prefix[], int powerArr[])
{
prefix[0] = 0;
prefix[1] = str.charAt(0);
for (int i = 2; i <= n; i++)
{
prefix[i] = (prefix[i - 1] % MOD+ (str.charAt(i - 1) % MOD * powerArr[i - 1] % MOD) % MOD) % MOD;
}
return;
}
public static void HashSuffix(String str, int n,int suffix[], int powerArr[])
{
suffix[0] = 0;
suffix[1] = str.charAt(n - 1);
for (int i = n - 2, j = 2; i >= 0 && j <= n; i--, j++)
{
suffix[j] = (suffix[j - 1] % MOD + (str.charAt(i) % MOD* powerArr[j - 1] % MOD) % MOD) % MOD;
}
return;
}
public static void GetQueryOutput( String str, Queries q[], int m, int n, int prefix[], int suffix[], int powerArr[])
{
for (int i = 0; i <= m - 1; i++)
{
int left = q[i].left;
int right = q[i].right;
long HashValue= ((prefix[right + 1] - prefix[left] + MOD) % MOD* ModuloMultiplicativeInverse(powerArr[left]) % MOD)% MOD;
long reverseHashValue= ((suffix[n - left] - suffix[n - right - 1] + MOD) % MOD* ModuloMultiplicativeInverse(powerArr[n - right - 1]) % MOD)% MOD;
if (HashValue == reverseHashValue)
{
if (CheckPalindrome(str, left, right) == true)
{
System.out.print("The Substring ["+left+" "+ right+"] is a palindrome\n");
}
else
{
System.out.print("The Substring ["+left+" "+ right+"] is not a palindrome\n");
}
}
else
{
System.out.print("The Substring ["+left+" "+ right+"] is not a palindrome\n");
}
}
return;
}
public static void assginedPowers(int powerArr[], int n)
{
powerArr[0] = 1;
for (int i = 1; i <= n; i++)
powerArr[i] = (powerArr[i - 1] % MOD * p % MOD) % MOD;
return;
}
public static void main(String[] args)
{
String str = "aaabbabbaaa";
int n = str.length();
int[] powerArr = new int[n + 1];
assginedPowers(powerArr, n);
int[] prefix = new int[n + 1];
int[] suffix = new int[n + 1];
HashPrefix(str, n, prefix, powerArr);
HashSuffix(str, n, suffix, powerArr);
Queries q[] = { new Queries(2, 3), new Queries(2, 8),new Queries(5, 7), new Queries(3, 7) };
int m = q.length;
GetQueryOutput(str, q, m, n, prefix, suffix, powerArr);
}
}
The Substring [2 3] is not a palindrome The Substring [2 8] is a palindrome The Substring [5 7] is not a palindrome The Substring [3 7] is a palindrome
복잡성 분석
시간 복잡성
O (N + Q) 어디에 "엔" 문자열의 크기이고 "큐" 수행 할 쿼리 수입니다. 따라서 알고리즘은 O (1) 시간에 각 쿼리에 응답하므로 선형 시간 복잡도를 갖습니다.
공간 복잡성
의 위에) 어디에 "엔" 주어진 문자열의 문자 수입니다. 문자열에 대한 해시 값을 저장했기 때문입니다. 추가 공간을 사용했습니다.
