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.
Mündəricat
misal
"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, Mvə K. İ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.
