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.
W najmniejszej podtablicy ze wszystkimi wystąpieniami najczęściej występującego problemu z elementami daliśmy szyk. Weź liczbę „m” w tablicy z maksymalną częstotliwością. Stwierdzenie problemu mówi, że musisz znaleźć najmniejszą podtablicę, która również ma wszystkie wystąpienia liczby „m” w tej najmniejszej podtablicy.
Spis treści
Przykład
Wkład
[3, 5, 4, 5, 4]
Wydajność
[5, 4, 5]
Wyjaśnienie
Tak jak w tym przypadku, istnieją dwa częste elementy o tej samej częstotliwości, więc weźmie pierwszy występujący element i utworzy najmniejszą pod-tablicę.
Algorytm dla najmniejszej podtablicy z najczęściej występującym elementem
- Zadeklaruj dwie HashMapy.
- Ustaw maxfreq, minlen, winindex na 0.
- Podczas gdy 0 <n
- Policz i zapisz częstotliwość numerów tablic na mapie w każdej iteracji.
- Sprawdź, czy bieżący element ma częstotliwość większą niż maxfreq, jeśli prawda, wykonaj następujące czynności:
- maxFreq = count [a [i]];
- minlen = i - freqCount [a [i]] + 1;
- winindex = freqCount [a [i]];
- w przeciwnym razie, jeśli maksymalna częstotliwość jest taka sama jak częstotliwość bieżącego elementu, a także długość tak utworzonej podtablicy jest mniejsza niż minlen, wykonaj następujące czynności:
- minlen = i - freqCount [a [i]] + 1;
- winindex = freqCount [a [i]];
- wypisuje tablicę z winindex do winindex + minlen
Wyjaśnienie najmniejszej podtablicy z najczęściej występującym elementem
Podaliśmy stwierdzenie problemu, że musimy znaleźć najmniejszą podtablicę, która powinna zawierać wszystkie wystąpienia najczęściej występującego elementu. Zadeklarujemy maxFreq do przechowywania maksymalnej częstotliwości elementów jako indeksu, „Minlen” do określenia minimalnej długości podtablicy, i „Winindex” dla najmniejszej podtablicy. Jeśli element zostanie znaleziony po raz pierwszy, wstaw obie mapy, jeśli jest to powtarzający się element na mapie, zapisz go w mapie licznika.
Zaczniemy przechowywać element i jego indeks dla każdej iteracji i zapiszemy go do mapowania, a następnie sprawdzimy, czy bieżący element ma wartość większą niż „Maxfreq” zaktualizujemy wartość maxFreq i „Minlen”.
Jeśli częstotliwość elementu jest taka sama jak „Maxfreq” sprawdzimy długość podtablicy i zaktualizujemy ją, jeśli warunki są spełnione.
Rozważmy przykład najmniejszej podtablicy ze wszystkimi wystąpieniami najczęstszego elementu:
Przykład
arr = {1, 2, 2, 2, 1}
i = 0 => arr [i] = 1
freqCount = [1: 0] count = [1: 1]
maxfreq = 1, minlen = i - freqCount [a [i]] + 1 = 1, winindex = 0
zaktualizujemy maxfreq, minlen i windex
i = 1 => arr [i] = 2
freqCount = [1: 0,2: 1] count = [1: 1, 2: 1], nic nie jest wykonywane
i = 2 => arr [i] = 2
freqCount = [1: 0,2: 1] count = [1: 0, 2: 2], aktualizuje tylko liczbę.
maxfreq = 2, minlen = i - freqCount [a [i]] + 1 = 2, winindex = 1
i = 3 => arr [i] = 2
freqCount = [1: 0,2: 1] count = [1: 0, 2: 3], aktualizuje tylko liczbę.
maxfreq = 3, minlen = i - freqCount [a [i]] + 1 = 3, winindex = 1
i = 4 => arr [i] = 1
freqCount = [1: 0,2: 1] count = [1: 1, 2: 3], aktualizuje tylko liczbę.
maxfreq = 3, minlen = i - freqCount [a [i]] + 1 = 3, winindex = 1
mamy naszą wartość, czyli minlen = 3 i winindex = 1
Pętla się otwiera i przechodzi od winindex do minlen + winindex, czyli od 1 do mniej niż 4
I wypisze [2 2 2], to jest nasza wymagana odpowiedź
Implementacja dla najmniejszej podtablicy z najczęściej występującym elementem
Program w C ++
#include <unordered_map>
#include<iostream>
using namespace std;
void frequentSubArray(int a[], int n)
{
unordered_map<int, int> freqCount;
unordered_map<int, int> count;
int maxFreq = 0;
int minlen, winindex;
for (int i = 0; i < n; i++)
{
if (count[a[i]] == 0)
{
freqCount[a[i]] = i;
count[a[i]] = 1;
}
else
count[a[i]]++;
if (count[a[i]] > maxFreq)
{
maxFreq = count[a[i]];
minlen = i - freqCount[a[i]] + 1;
winindex = freqCount[a[i]];
}
else if (count[a[i]] == maxFreq && i - freqCount[a[i]] + 1 < minlen)
{
minlen = i - freqCount[a[i]] + 1;
winindex = freqCount[a[i]];
}
}
for (int i = winindex; i < winindex + minlen; i++)
{
cout << a[i] << " ";
}
}
int main()
{
int A[] = { 1, 2, 2, 2, 1 };
int n = sizeof(A) / sizeof(A[0]);
frequentSubArray(A, n);
return 0;
}
2 2 2
Program Java
import java.io.*;
import java.util.*;
class mostFrequentSubArray
{
public static void frequentSubArray(int a[], int n)
{
HashMap<Integer, Integer> freqCount= new HashMap<Integer, Integer>();
HashMap<Integer, Integer> count= new HashMap<Integer, Integer>();
int maxFreq = 0;
int minlen = -1, winindex = -1;
for (int i = 0; i < n; i++)
{
if (count.containsKey(a[i]))
{
count.put(a[i], count.get(a[i]) + 1);
}
else
{
freqCount.put(a[i], i) ;
count.put(a[i], 1);
}
if (count.get(a[i]) > maxFreq)
{
maxFreq = count.get(a[i]);
minlen = i - freqCount.get(a[i]) + 1;
winindex = freqCount.get(a[i]);
}
else if ((count.get(a[i]) == maxFreq) && (i - freqCount.get(a[i]) + 1 < minlen))
{
minlen = i - freqCount.get(a[i]) + 1;
winindex = freqCount.get(a[i]);
}
}
for (int i = winindex; i < winindex + minlen; i++)
System.out.print(a[i] + " ");
}
public static void main (String[] args)
{
int arr[] = { 1, 2, 2, 2, 1 };
int n = arr.length;
frequentSubArray(arr, n);
}
}
2 2 2
Analiza złożoności dla najmniejszej podtablicy z najczęściej występującym elementem
Złożoność czasowa
Na) gdzie „N” to liczba elementów w tablicy.
Złożoność przestrzeni
Na) gdzie „N” to liczba elementów w tablicy.
