Najmniejsza podtablica ze wszystkimi wystąpieniami najczęstszego elementu

Poziom trudności Średni
Często zadawane pytania Citrix Coursera Pokoje OYO Qualtrics Synopsys Taxi4Sure
Szyk Haszyszodwiedzajacy 88

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.

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ę.

najmniejsza podtablica z najczęściej występującym elementemszpilka

Algorytm dla najmniejszej podtablicy z najczęściej występującym elementem

  1. Zadeklaruj dwie HashMapy.
  2. Ustaw maxfreq, minlen, winindex na 0.
  3. Podczas gdy 0 <n
    1. Policz i zapisz częstotliwość numerów tablic na mapie w każdej iteracji.
    2. 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]];
    3. 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]];
  4. 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.

Referencje

Wywiady dotyczące projektowania systemu pękania
Translate »