Üç simli LCS (Ən Uzun Ortaq Nəticə)

Çətinlik səviyyəsi Ağır
Tez-tez soruşulur Amazon Kod milləti Expedia google Über Zoho
Dinamik proqramlaşdırma SimBaxılıb 82

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.

"Üç simli LCS (Ən Uzun Ortaq Nəticə)" problemi sizə 3 sim verildiyini bildirir. Bu 3 telin ən uzun yayılmış ardıcıllığını tapın. LCS, 3 sətir arasında yayılmış və verilən 3 sətrin hamısında eyni qaydada olan simvollardan ibarət olan sətirdir.

misal

Üç simli LCS (Ən Uzun Ortaq Nəticə)Pin

"gxtxayb" 
"abgtab" 
"gyaytahjb"
Length of LCS: 4("gtab")

Yanaşma

Problem bizə giriş olaraq 3 simli verir və bunlardan ən uzun yayılmış ardıcıllığı tapmağımızı xahiş etdi. Bir ardıcıllıq, bəzi simvolları orijinal sətirdən sildikdə qalan bir sətirdir. Beləliklə, verilmiş 3 sətirdə maksimum uzunluğa malik ortaq ardıcıllığı tapmaq lazımdır.

Problemə sadəlövh yanaşma normal Ən Uzun Ortaq Nəticə probleminə bənzəyir. Artıq ən uzun yayılmış sonrakı problemi müzakirə etmişdik. Ancaq sadəlövh yanaşmanın problemi vaxt məhdudiyyəti altında həll edəcək qədər səmərəli olmadığını da müzakirə etdik. Beləliklə, problemi vaxt həddini aşmadan həll etmək. İstifadə edəcəyik dinamik proqramlaşdırma sualın həlli üçün. Vəziyyət 2 simli LCS vəziyyətinə bənzəyir. Burada 3 satırdakı indekslərə istinad edəcək 3 vəziyyətimiz olacaq. Beləliklə, dp dizimiz, 3-ün içərisindəki hər hansı bir göstəricinin 0 olduğu 3-ı saxladığımız 0B bir sıra olacaqdır. Əgər 3 indeksdəki simvol varsa, alt problemin cavabına 1 əlavə edirik (LCS substrings from from uzunluq indekslərin hər birindən 0-dan 1-ə qədər). İki sətirdən hər hansı biri eyni xarakter daşımırsa, indeksin hər birini bir-bir azaldacağı alt problemlərin maksimumunu saxlayırıq.

Kodu

3 simli LCS tapmaq üçün C ++ kodu

#include<bits/stdc++.h> 
using namespace std; 
  
int main() 
{ 
  string x = "gxtxayb"; 
  string y = "abgtab"; 
  string z = "gyaytahjb"; 
  int n = x.length(), m = y.length(), l = z.length();
  
  int dp[n][m][l];
  memset(dp, 0, sizeof dp);
  for (int i=0; i<n; i++){ 
    for (int j=0; j<m; j++){ 
      for (int k=0; k<l; k++){
        if (x[i] == y[j] && x[i] == z[k])
          dp[i][j][k] = ((i>0 && j>0 && k>0) ? dp[i-1][j-1][k-1] : 0) + 1;
        else
          dp[i][j][k] = max({i>0 ? dp[i-1][j][k] : 0, j>0 ? dp[i][j-1][k] : 0, k>0 ? dp[i][j][k-1] : 0}); 
      } 
    } 
  } 
  cout<<dp[n-1][m-1][l-1];
  return 0; 
}
4

3 simli LCS tapmaq üçün Java kodu

import java.util.*;
class Main{
  public static void main(String[] args)
  {
    String x = "gxtxayb"; 
    String y = "abgtab"; 
    String z = "gyaytahjb"; 
    int n = x.length(), m = y.length(), l = z.length();
    
    int dp[][][] = new int[n][m][l];
    for (int i=0; i<n; i++){ 
      for (int j=0; j<m; j++){ 
        for (int k=0; k<l; k++){
          dp[i][j][k] = 0;
          if (x.charAt(i) == y.charAt(j) && x.charAt(i) == z.charAt(k))
            dp[i][j][k] = ((i>0 && j>0 && k>0) ? dp[i-1][j-1][k-1] : 0) + 1;
          else
            dp[i][j][k] = Math.max(Math.max(i>0 ? dp[i-1][j][k] : 0, j>0 ? dp[i][j-1][k] : 0), k>0 ? dp[i][j][k-1] : 0); 
        } 
      } 
    } 
    System.out.println(dp[n-1][m-1][l-1]);
  }
}
4

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (N * M * K), çünki uzunluğu olan 3 ipin hamısını keçməliyik N, MK. İstifadəyə görə Dinamik proqramlaşdırma eksponent zamanın mürəkkəbliyini polinoma endirə bilərik.

Kosmik Mürəkkəblik

O (N * M * K), çünki nəticəni daha kiçik alt problem üçün saxlamaq və nəticəni ilk problemin cavabını almaq üçün birləşdirmək üçün bir 3D DP massivi yaratmalıyıq. Beləliklə, üç simli LCS (Ən Uzun Ortaq Nəticə) tapmaq polinom boşluğu mürəkkəbliyinə malikdir.

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