Pytania do rozmowy kwalifikacyjnej na temat projektowania systemu może być tak nieograniczona, że trudno jest określić właściwy sposób przygotowania. Teraz jestem w stanie złamać rundy projektowe Amazon, Microsoft i Adobe po zakupie ta książka. Codziennie poprawiaj jeden pytanie projektowe i obiecuję, że możesz złamać cały projekt.
Spis treści
Problem Statement
W zadaniu „Najdłuższy wspólny prefiks przy użyciu dzielenia i zwyciężania” podaliśmy liczbę całkowitą n i n smyczki. Napisz program, który wydrukuje najdłuższy wspólny prefiks. Jeśli nie ma wspólnego prefiks następnie wypisz „-1”.
Format wejściowy
W pierwszym wierszu znajduje się liczba całkowita n.
Następna linia n zawierająca po jednym ciągu.
Format wyjściowy
Wydrukuj ciąg, który reprezentuje najdłuższy wspólny prefiks podanych ciągów. Jeśli nie znaleziono takiego prefiksu, wypisz „-1”.
ograniczenia
- 1 <= n <= 10 ^ 3
- 1 <= | s [i] | <= 10 ^ 3 gdzie i od 0 do n-1
- s [i] [j] musi być alfabetem angielskim małą literą, gdzie i od 0 do n-1, a j od 0 do | s [i] |.
Przykład
3 tutorial tutcup turnin
tu
Wyjaśnienie: Tutaj widzimy „tu” to przedrostek występujący w każdym łańcuchu.
Algorytm najdłuższego wspólnego prefiksu przy użyciu funkcji Podziel i zwyciężaj
W tym algorytmie omówiono podejście dziel i rządź. Najpierw dzielimy tablice łańcuchów na dwie części. Następnie robimy to samo dla lewej części, a następnie dla prawej części. Będziemy to robić, dopóki wszystkie łańcuchy nie będą miały długości 1. Teraz zaczniemy podbijać, zwracając wspólny prefiks lewego i prawego łańcucha.
1. Rekurencyjnie podziel tablicę ciągów na dwie części, aż długość wyniesie 1
2. Teraz zacznij podbijać, zwracając wspólny prefiks lewego i prawego łańcucha
Realizacja
Program w C ++ dla najdłuższego wspólnego prefiksu przy użyciu dzielenia i zwyciężania
#include<bits/stdc++.h>
using namespace std;
string commonPrefixUtil(string str1, string str2)
{
string result;
int n1 = str1.length(), n2 = str2.length();
for (int i=0,j=0;i<n1&&j<n2;i++,j++)
{
if(str1[i]!=str2[j])
{
break;
}
result.push_back(str1[i]);
}
return result;
}
string commonPrefix(string s[], int x, int y)
{
if(x==y)
{
return s[x];
}
if(y>x)
{
int mid=x+(y-x)/2;
string s1 = commonPrefix(s, x, mid);
string s2 = commonPrefix(s, mid+1, y);
return commonPrefixUtil(s1, s2);
}
}
int main()
{
int n;
cin>>n;
string s[n];
for(int i=0;i<n;i++)
{
cin>>s[i];
}
string ans = commonPrefix(s,0,n-1);
if(ans.length()>0)
{
cout<<ans<<endl;
}
else
{
cout<<-1<<endl;
}
return (0);
}
Program w języku Java z najdłuższym wspólnym prefiksem przy użyciu funkcji Divide and Conquer
import java.util.Scanner;
class sum {
static String commonPrefixUtil(String str1, String str2) {
String result = "";
int n1 = str1.length(), n2 = str2.length();
for (int i = 0, j = 0; i <= n1 - 1 && j <= n2 - 1; i++, j++)
{
if(str1.charAt(i)!=str2.charAt(j))
{
break;
}
result += str1.charAt(i);
}
return result;
}
static String commonPrefix(String s[], int x, int y) {
if(x==y)
{
return s[x];
}
if(y>x)
{
int mid = x + (y-x)/2;
String s1 = commonPrefix(s, x, mid);
String s2 = commonPrefix(s, mid + 1, y);
return commonPrefixUtil(s1,s2);
}
return null;
}
public static void main(String[] args)
{
Scanner sr = new Scanner(System.in);
int n = sr.nextInt();
String s[] = new String[n];
for(int i=0;i<n;i++)
{
s[i]= sr.next();
}
String ans = commonPrefix(s,0,n-1);
if(ans.length()!=0)
{
System.out.println(ans);
}
else
{
System.out.println("-1");
}
}
}
3 car carrace caramazing
car
Analiza złożoności dla najdłuższego wspólnego prefiksu przy użyciu funkcji Podziel i zwyciężaj
Złożoność czasowa
O (n * m) gdzie n to liczba ciągów i m jest długością maksymalnego ciągu. Tutaj odwiedzamy każdą postać, dlatego złożoność czasowa wynosi O (n * m).
Złożoność przestrzeni
O (m * logn) ponieważ przechowujemy wynikowy ciąg lub najdłuższy prefiks, przydzielamy miejsce, które wynosi O (m * logn).
