스트림에서 회문을 확인하기위한 온라인 알고리즘

난이도 중급
자주 묻는 질문 수행자 어도비 벽돌 Zenefits
팔린 드롬 패턴 검색 조회수 545

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

문제 정책

“스트림에서 회문을 확인하기위한 온라인 알고리즘”문제에서 우리는 문자 스트림을 제공했습니다 (문자는 하나씩 수신됩니다). 지금까지 수신 된 문자가 A를 형성하면 매번 '예'를 인쇄하는 프로그램을 작성하십시오. 회문.

입력 형식

첫 번째이자 하나 뿐인 s.

출력 형식

현재 문자열 (이 문자까지 모든 문자로 구성됨)이 회문이면 "YES"를 인쇄하고 그렇지 않으면 "NO"를 인쇄합니다.

제약

  • 1 <= | s | <= 10 ^ 5
  • s [i]는 소문자 영어 알파벳이어야합니다.

bcdcb
YES  
NO 
NO 
NO   
YES

설명 : i = 0의 경우 "b"가 회문이므로 YES를 인쇄합니다. i = 1이면 "bc"가 회문이 아니므로 NO를 인쇄하십시오. i = 2의 경우 "bcd"가 회문이 아니므로 NO를 인쇄하십시오. i = 3이면 "bcdc"가 회문이 아니므로 NO를 인쇄하십시오. i = 4 인 경우 "bcdcb"가 회문이므로 YES를 인쇄하십시오.

스트림에서 회문을 확인하기위한 온라인 알고리즘에 대한 접근 방식

기본 아이디어는 입력 문자열의 모든 문자에 대해 s [0..i]가 회문인지 여부를 확인하는 것입니다. 또 다른 방법 (최적)에서는 O (1) 시간 이전부터 다음 해시 값을 계산할 수 있으므로 Rabin Karp 알고리즘에서 사용하는 Rolling 해시의 아이디어를 사용하는 것이 주된 아이디어입니다. 모든 인덱스에 대해 전반 및 후반의 반전 추적

암호알고리즘

1. 첫 번째 문자는 항상 회문이므로 첫 번째 문자에 대해 yes를 인쇄하십시오.

2. 전반을 첫 번째 문자로, 후반을 두 번째 문자로 초기화합니다. 전반전의 해시 값을 'FR'로하고 후반의 해시 값을 'S'로 지정합니다.

3. 두 번째 문자에서 문자열 순회

  • 'FR'과 'S'가 같으면 s [0..i]가 간단한 문자 별 일치를 사용하는 회문인지 확인합니다.
  • 다음 반복을 위해 'FR'및 'S'를 업데이트합니다.
  • 'i'가 짝수이면 'FR'의 시작과 후반의 끝에 다음 문자를 추가하고 해시 값을 업데이트합니다.
  • 'i'가 홀수이면 'FR'을 그대로 유지하고 두 번째 문자에서 선행 문자를 제거하고 끝에 다음 문자를 추가합니다.

위 알고리즘의 실제 구현

s =“bcdcb”
FR 및 S를 초기화합니다. FR = hash ( "b"), S = hash ( "c")
두 번째 문자에서 트래버스
i = 1, FR과 S는 같지 않으므로 NO를 인쇄하십시오.
FR과 S를 업데이트하면 i는 홀수이므로 FR은 변경되지 않고 S는 해시 ( "d")가됩니다.
i = 2, FR과 S는 같지 않으므로 NO를 인쇄하십시오.
FR과 S를 업데이트하면 i는 FR이 해시 ( "cb")가되고 S가 해시 ( "dc")가됩니다.
i = 3, FR과 S는 같지 않으므로 NO를 인쇄하십시오.
FR 및 S 업데이트, i는 홀수이므로 FR은 변경되지 않고 S는 해시 ( "cb")가됩니다.
i = 4, FR 및 S가 일치하므로 YES를 인쇄하십시오.
마지막 색인이므로 업데이트 할 필요가 없습니다.

실시

스트림에서 회문을 확인하기위한 온라인 알고리즘 용 C ++ 프로그램

#include <bits/stdc++.h>
using namespace std;
#define NO_OF_CHARS 256
// p is a prime number used for evaluating Rabin Karp's Rolling hash
#define p 103
 
void isPalindrome(string s)
{
    // Length of input string
    int N = s.length();
 
    // first character is a palindrome
    cout<<"YES"<<endl;
 
    // Return if string has only one character
    if (N == 1) return;
 
    // Initialize first half reverse and S half for 
    // as FR and S characters
    int FR  = s[0] % p;
    int S = s[1] % p;
 
    int h = 1, i, j;
 
    // Now check for palindromes from S character
    // onward
    for (i=1; i<N; i++)
    {
        // If the hash values of 'FR' and 'S' 
        // match, then only check individual characters
        if (FR == S)
        {
            //check if s[0..i] is a palindorme
            for (j = 0; j < i/2; j++)
            {
                if (s[j] != s[i-j])
                    break;
            }
            if((j == i/2))
            {
                cout<<"YES"<<endl;
            }
            else
            {
                cout<<"NO"<<endl;
            }
        }
        else
        { 
            cout<<"NO"<<endl;
        }

        //update hash values
        if (i != N-1)
        {
            // If i is even (next i is odd) 
            if (i%2 == 0)
            {
                // Add next character after first half at beginning 
                // of 'FR'
                h = (h*NO_OF_CHARS) % p;
                FR  = (FR + h*s[i/2])%p;
                 
                // Add next character after S half at the end
                // of S half.
                S = (S*NO_OF_CHARS + s[i+1])%p;
            }
            else
            {
                // If i is odd (next i is even) then we
                // need not update FR, we need to remove
                // first character of S and append a
                // character to it.
                S = (NO_OF_CHARS*(S + p - s[(i+1)/2]*h)%p
                          + s[i+1])%p;
            }
        }
    }
}
 
int main()
{
    string s;
    cin>>s;
    isPalindrome(s);
    return 0;
}

스트림에서 회문을 확인하는 온라인 알고리즘 용 Java 프로그램

import java.util.Scanner;
class sum
{
    private static int p=103;
    private static int NO_OF_CHARS = 256;
    public static void isPalindrome(String s)
    {
        // Length of input string
        int N = s.length();

        // first character is a palindrome
        System.out.println("YES");

        // Return if string has only one character
        if (N == 1) return;

        // Initialize first half reverse and S half for 
        // as FR and S characters
        int FR  = s.charAt(0) % p;
        int S = s.charAt(1) % p;

        int h = 1, i, j;

        // Now check for palindromes from S character
        // onward
        for (i=1; i<N; i++)
        {
            // If the hash values of 'FR' and 'S' 
            // match, then only check individual characters
            if (FR == S)
            {
                //check if s[0..i] is a palindorme
                for (j = 0; j < i/2; j++)
                {
                    if (s.charAt(j) != s.charAt(i-j))
                        break;
                }
                if((j == i/2))
                {
                    System.out.println("YES");
                }
                else
                {
                    System.out.println("NO");
                }
            }
            else
            { 
                System.out.println("NO");
            }

            //update hash values
            if (i != N-1)
            {
                // If i is even (next i is odd) 
                if (i%2 == 0)
                {
                    // Add next character after first half at beginning 
                    // of 'FR'
                    h = (h*NO_OF_CHARS) % p;
                    FR  = (FR + h*s.charAt(i/2))%p;

                    // Add next character after S half at the end
                    // of S half.
                    S = (S*NO_OF_CHARS + s.charAt(i+1))%p;
                }
                else
                {
                    // If i is odd (next i is even) then we
                    // need not update FR, we need to remove
                    // first character of S and append a
                    // character to it.
                    S = (NO_OF_CHARS*(S + p - s.charAt((i+1)/2)*h)%p
                              + s.charAt(i+1))%p;
                }
            }
        }
    }
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        String s = sr.next();
        isPalindrome(s);
    }
    
}
abacbca
YES
NO
YES
NO
NO
NO
NO

스트림에서 회문을 확인하기위한 온라인 알고리즘의 복잡성 분석

시간 복잡성

O (n * n) 어디에 n 주어진 문자열의 크기입니다. 여기서 n * n은 최악의 시간 복잡도입니다. 그러나 일반적으로 기본 간단한 접근 방식보다 훨씬 잘 작동합니다. 대부분의 경우 해시 값을 먼저 비교하여 완전한 부분 문자열 비교를 피합니다. 최악의 경우는 "zzzzzzzzz"와 같은 문자가 모두 동일한 입력 문자열에 대해 발생합니다.

공간 복잡성

O (1) 여기에는 보조 공간이 없기 때문입니다.

균열 시스템 설계 인터뷰
Translate »