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.
Mündəricat
Problem bəyanat
“Word by Word Matching istifadə edərək ən uzun yayılmış prefiks” problemində N strings. Verilən simlərin ən uzun ümumi prefiksini tapmaq üçün bir proqram yazın.
Giriş Formatı
Sətirlərin sayını ifadə edən tam bir N dəyəri olan ilk sətir.
Sonra bir simli olan N sətir.
Çıxış formatı
Verilən N simli ən uzun ümumi prefiksimiz olan "ans" simli olan ilk və tək sətir. Əgər belə bir önək yoxdursa, onda -1 yazdırın.
Məhdudiyyətlər
- 1 <= | N | <= 10 ^ 3
- 1 <= | s [i] | <= 10 ^ 3 burada i 0-dan N-1-ə
- s [i] [j], 0-dan N-1-ə, j-dən 0-dan | s [i] | -ə qədər olan kiçik bir İngilis əlifbası olmalıdır.
misal
5 abcde abba abaa abbbbb ababab
ab
Explanation: Burada 1-ci və XNUMX-ci simlərin ümumi prefiksinin “ab” olduğunu görə bilərik. İndi hər bir simli ilə bu prefiksiyanı bir-bir yoxlayın və “ab” olan son prefiksi əldə edin.
Alqoritm
Burada assosiasiya xüsusiyyətindən istifadə edirik - LCP (s1, s2, s3) = LCP (LCP (s1, s2), s3). Bu fikri tətbiq etmək üçün alqoritm simlər vasitəsilə təkrarlanır [S1… Sn], hər təkrarda tapmaq simlərin ən uzun yayılmış prefiksi Zaman boş bir sətirdir, alqoritm sona çatır. Əks təqdirdə, sonra n təkrarlamalar, alqoritm qayıdır .
1. İki simli üçün ümumi bir prefiks tapmaq üçün bir funksiya yaradırıq.
- Simli simvolları müqayisə edin.
- Eynidirsə, nəticəyə gətirin.
- Son nəticəni qaytarın.
2. Giriş sətirinin ilk elementi olaraq başlanğıc output_prefix olun.
3. Onu ikinci ilə müqayisə edin və ouput_prefix-də saxlayın və s.
4. Son output_prefix-i qaytarın.
Həyata keçirilməsi
Word uyğunluğu ilə ən uzun yayılmış prefiks sözü üçün C ++ proqramı
#include <bits/stdc++.h>
using namespace std;
string prefix(string s, string t)
{
string res;
int n = s.length();
int m = t.length();
for(int i=0,j=0;(i<=n-1)&&(j<=m-1);i++,j++)
{
if(s[i]!=t[j])
{
break;
}
res.push_back(s[i]);
}
return res;
}
string common_prefix(vector<string> v)
{
string res=v[0];
for(int i=1;i<=v.size()-1;i++)
{
res=prefix(res,v[i]);
}
return res;
}
int main()
{
int n;
cin>>n;
vector<string> v;
for(int i=0;i<n;i++)
{
string x;
cin>>x;
v.push_back(x);
}
string ans = common_prefix(v);
if(ans.length())
{
cout<<ans<<endl;
}
else
{
cout<<-1<<endl;
}
return 0;
}
Word Eşleme ilə Ən Uzun Ümumi Prefiks Word üçün Java Proqramı
import java.util.Scanner;
import java.util.Vector;
class sum
{
public static String prefix(String s, String t)
{
String res="";
int n = s.length();
int m = t.length();
for(int i=0,j=0;(i<n)&&(j<m);i++,j++)
{
if(s.charAt(i)!=t.charAt(j))
{
j=m;
}
else
{
res+=(s.charAt(i));
}
}
return res;
}
public static String common_prefix(Vector<String> v)
{
String res=v.get(0);
for(int i=1;i<=v.size()-1;i++)
{
res=prefix(res, v.get(i));
}
return res;
}
public static void main(String[] args)
{
Scanner sr = new Scanner(System.in);
int n=sr.nextInt();
Vector<String> v = new Vector<String>(n+1);
for(int i=0;i<n;i++)
{
String x = sr.next();
v.add(x);
}
String ans = common_prefix(v);
if(ans.length()!=0)
{
System.out.println(ans);
}
else
{
System.out.println("-1");
}
}
}
5 abcde abba abaa abbbbb ababab
ab
Word Eşleme ilə Ən Uzun Ümumi Prefiks Sözü üçün Mürəkkəblik Təhlili
Zamanın mürəkkəbliyi
O (n * m) hara n simlərin ümumi sayı və m maksimum sətrin uzunluğudur.
Kosmik Mürəkkəblik
O (m) iki sim arasında bir əməliyyat həyata keçirildikdən sonra ümumi prefiksi saxlamaq üçün.
