Mantı Parantezləşdirmə Problemi

Çətinlik səviyyəsi Ağır
Tez-tez soruşulur Amazon LinkedIn microsoft
Dinamik proqramlaşdırmaBaxılıb 66

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Problem bəyanat

"Boolean Parenthesization Problem" bizə doğru və yalan bir sıra verildiyini və aralarında bəzi mantıksal operatorların (AND, OR, XOR) verildiyini bildirir. Verilən ardıcıllığı parantezləşdirmə yollarının sayını tapmalıyıq ki, bütün ardıcıllıqla DOĞRU ilə nəticələnək. Verilən Boole Parenthesization problemində “T” istifadə edərək True, “F” ilə False müraciət edəcəyik.

misal

Symbol Sequence = {T,T}

Operator Sequence = {|}
1

İzahat: Bu, problemin nədən ibarət olduğuna başlamaq üçün burada göstərilən əhəmiyyətsiz bir nümunədir. Beləliklə, ardıcıllığı parantezləşdirməyin yalnız bir yolu var. (Y | T).

Mantı Parantezləşdirmə ProblemiPin

Symbol Sequence = {T, F, F}

Operator Sequence = {^, |}
2

İzahat: Burada verilmiş simvol ardıcıllığının iki yoludur. İki yol (T ^ (F | F)) və ((T ^ F) | F) dir.

Mantı Parantezləşdirmə Probleminə yanaşma

"Boolean Parenthesization Problem" bildirir ki, verilmiş operatorlardan istifadə edərək simvol ardıcıllığını mötərizə halına gətirmə yollarının sayını tapmalıyıq ki, ardıcıllıqla onu doğrudur. Beləliklə, bunun üçün i ilə j arasındakı ardıcıllıq seqmentini mötərizələşdirmə yollarının sayının saxlanılması üçün iki ədəd 2D massivi yaradacağıq. Eynilə, başqa bir 2D massivi eyni işarəni verir, lakin seqment səhv olur. Həll edərkən alt problemləri dəfələrlə həll etməliyik. Buna görə istifadə etməyə çalışırıq Dinamik proqramlaşdırma bu problemin həlli üçün.

Problem, bənzərdir Matris Zəncirinin Çarpılması Problemi, əvvəlcə daha kiçik alt problemləri (i, e, daha kiçik seqmentlər) həll edirik. Nəticəni birləşdirərək ilkin problemin cavabını tapırıq. Biz istifadə etdiyimiz üçün Dinamik proqramlaşdırma yanaşma, bəzi baza hallarına sahib olmalıyıq, burada əsas hallar uzunluq seqmentləri = 1. Beləliklə, T matrisini və F matrisini müvafiq olaraq dolduracağıq. Kiçik olanları birləşdirərək daha böyük alt problemləri həll etdikdə. Aşağıdakılardan müəyyən qaydalara əməl edəcəyik.

Mantı Parantezləşdirmə ProblemiPin

Kodu

Boolean Parenthesization Problemi üçün C ++ kodu

#include<bits/stdc++.h>
using namespace std; 

int waysToParenthesize(string symbolSequence, string operatorSequence) 
{
    int n = symbolSequence.size();
  int T[n][n], F[n][n];
  memset(T, 0 ,sizeof T);
  memset(F, 0, sizeof F);
  
  //base case 
  for(int i=0;i<n;i++)
        if(symbolSequence[i] == 'T')
            T[i][i] = 1, F[i][i] = 0;
        else
            T[i][i] = 0, F[i][i] = 1;

    // Now solve the subproblems in bottom up manner
  for(int len=2;len<=n;len++)
  {
    for(int i=0;i<=n-len;i++) 
    {
        int j = i+len-1;
      T[i][j] = F[i][j] = 0;
      
      //Index of placing brackets
      for(int k=i;k<j;k++)
      {
        int waysik = T[i][k] + F[i][k]; 
        int wayskj = T[k+1][j] + F[k+1][j]; 
        if(operatorSequence[k] == '&') 
        { 
          T[i][j] += T[i][k]*T[k+1][j]; 
          F[i][j] += (waysik*wayskj - T[i][k]*T[k+1][j]); 
        } 
        else if(operatorSequence[k] == '|')
        { 
          F[i][j] += F[i][k]*F[k+1][j]; 
          T[i][j] += (waysik*wayskj - F[i][k]*F[k+1][j]); 
        } 
        else if(operatorSequence[k] == '^') 
        { 
          T[i][j] += F[i][k]*T[k+1][j] + T[i][k]*F[k+1][j]; 
          F[i][j] += T[i][k]*T[k+1][j] + F[i][k]*F[k+1][j]; 
        }
      } 
    } 
  }
  return T[0][n-1]; 
} 

int main() 
{
    string symbolSequence="";
    string operatorSequence="";
    cin>>symbolSequence>>operatorSequence;
    cout<<waysToParenthesize(symbolSequence, operatorSequence)<<endl;
} 
TTFT
|&^
4

Boolean Parenthesization Problemi üçün Java Kodu

import java.util.*;

class Main{
    
    static int waysToParenthesize(String symbolSequence, String operatorSequence) 
    {
        int n = symbolSequence.length();
    	int T[][] = new int[n][n];
    	int F[][] = new int[n][n];
    	for(int i=0;i<n;i++){
    	    for(int j=0;j<n;j++){
    	        T[i][j] = 0;
    	        F[i][j] = 0;
    	    }
    	}
    	
    	//base case
    	for(int i=0;i<n;i++){
            if(symbolSequence.charAt(i) == 'T'){
                T[i][i] = 1;
                F[i][i] = 0;
            }
            else{
                T[i][i] = 0;
                F[i][i] = 1;   
            }
    	}
    
        // Now solve the subproblems in bottom up manner
    	for(int len=2;len<=n;len++)
    	{
    		for(int i=0;i<=n-len;i++) 
    		{
    		    int j = i+len-1;
    			T[i][j] = 0;
    			F[i][j] = 0;
    			
    			//Index of placing brackets
    			for(int k=i;k<j;k++)
    			{
    				int waysik = T[i][k] + F[i][k]; 
    				int wayskj = T[k+1][j] + F[k+1][j]; 
    				if(operatorSequence.charAt(k) == '&') 
    				{ 
    					T[i][j] += T[i][k]*T[k+1][j]; 
    					F[i][j] += (waysik*wayskj - T[i][k]*T[k+1][j]); 
    				} 
    				else if(operatorSequence.charAt(k) == '|')
    				{ 
    					F[i][j] += F[i][k]*F[k+1][j]; 
    					T[i][j] += (waysik*wayskj - F[i][k]*F[k+1][j]); 
    				} 
    				else if(operatorSequence.charAt(k) == '^') 
    				{ 
    					T[i][j] += F[i][k]*T[k+1][j] + T[i][k]*F[k+1][j]; 
    					F[i][j] += T[i][k]*T[k+1][j] + F[i][k]*F[k+1][j]; 
    				}
    			} 
    		} 
    	}
    	return T[0][n-1]; 
    } 
    
    
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        String symbolSequence = sc.next();
        String operatorSequence = sc.next();
    	int ans = waysToParenthesize(symbolSequence, operatorSequence);
    	System.out.println(ans);
    }
}
TTFT
|&^
4

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi: O (N ^ 3)

Matris Zənciri Çarpma problemində gördüklərimizə bənzəyir. Problem o birinə bənzər olduğundan, zamanın mürəkkəbliyi də eynidır.

Kosmik Mürəkkəblik: O (N ^ 2)

Burada alt seqmentin mötərizələşdirmə üsullarının sayının saxlanılması üçün 2 2D Dp massivdən birini istifadə etdik ki, nəticəsi doğrudur. O biri False üçün. Beləliklə bizə O (N ^ 2) polinom məkan mürəkkəbliyi verir.

Crack Sistemi Dizayn Müsahibələri
Translate »