가장 빈번한 요소가 모두 발생하는 최소 하위 배열

난이도 중급
자주 묻는 질문 시트릭스 Coursera 오요 룸 Qualtrics Synopsys 택시4슈어
배열 해시조회수 87

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

가장 빈번한 요소 문제가 모두 발생하는 가장 작은 하위 배열에서 정렬. 최대 주파수를 가진 배열에서 숫자 "m"을 가져옵니다. 문제 설명은 가장 작은 하위 배열에서 숫자 "m"이 모두 나오는 가장 작은 하위 배열을 찾아야한다고 말합니다.

입력

[3]

산출

[5, 4, 5]

설명

이와 같이 빈도가 같은 두 개의 빈번한 요소가 있으므로 처음 발생한 요소를 가져와 가장 작은 하위 배열을 만듭니다.

가장 빈번한 요소가있는 가장 작은 부분 배열

가장 빈번한 요소가있는 가장 작은 부분 배열에 대한 알고리즘

  1. 두 개의 HashMap을 선언하십시오.
  2. maxfreq, minlen, winindex를 0으로 설정합니다.
  3. 0 <n 동안
    1. 모든 반복에서 배열 번호의 빈도를 계산하고 맵에 저장합니다.
    2. 현재 요소의 주파수가 maxfreq보다 큰지 확인하고 참이면 다음을 수행합니다.
      • maxFreq = 개수 [a [i]];
      • minlen = i – freqCount [a [i]] + 1;
      • winindex = freqCount [a [i]];
    3. 그렇지 않으면 최대 주파수가 현재 요소 주파수와 같고 이렇게 형성된 서브 어레이의 길이가 minlen보다 작 으면 다음을 수행하십시오.
      • minlen = i – freqCount [a [i]] + 1;
      • winindex = freqCount [a [i]];
  4. winindex에서 winindex + minlen으로 배열 인쇄

가장 빈번한 요소가있는 가장 작은 부분 배열에 대한 설명

우리는 가장 빈번한 요소의 모든 발생을 가져야하는 가장 작은 하위 배열을 찾아야한다는 문제 진술을 제공했습니다. 요소의 최대 주파수를 인덱스로 저장하기 위해 maxFreq를 선언합니다. "minlen" 서브 어레이의 최소 길이를 결정하고 "winindex" 가장 작은 부분 배열을 위해. 요소가 처음 발견 된 경우 두 맵을 모두 삽입하고 맵에서 반복되는 요소 인 경우 카운트 맵에 저장합니다.

각 반복에 대한 요소와 색인을 저장하기 시작하고 맵에 저장 한 다음 현재 요소가 다음보다 큰 값을 가지고 있는지 확인합니다. "maxfreq" maxFreq의 값을 업데이트하고 "minlen".

요소의 빈도가 "maxfreq" 하위 배열의 길이를 확인하고 조건이 충족되면 업데이트합니다.

가장 빈번한 요소가 모두 나타나는 가장 작은 하위 배열의 예를 고려해 보겠습니다.

arr = {1, 2, 2, 2, 1}

i = 0 => arr [i] = 1

freqCount = [1 : 0] 개수 = [1 : 1]

maxfreq = 1, minlen = i – freqCount [a [i]] + 1 = 1, winindex = 0

maxfreq, minlen 및 windex를 업데이트합니다.

i = 1 => arr [i] = 2

freqCount = [1 : 0,2 : 1] count = [1 : 1, 2 : 1], 예외 없음

i = 2 => arr [i] = 2

freqCount = [1 : 0,2 : 1] count = [1 : 0, 2 : 2], 개수 만 업데이트합니다.

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], 개수 만 업데이트합니다.

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], 개수 만 업데이트합니다.

maxfreq = 3, minlen = i – freqCount [a [i]] + 1 = 3, winindex = 1

minlen = 3 및 winindex = 1 인 값이 있습니다.

루프가 열리고 winindex에서 minlen + winindex, 즉 1에서 4 미만으로 진행됩니다.

그러면 [2 2 2]가 출력됩니다. 이것이 필수 답변입니다.

가장 빈번한 요소로 가장 작은 하위 배열 구현

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

자바 프로그램

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

가장 빈번한 요소가있는 가장 작은 부분 배열에 대한 복잡성 분석

시간 복잡성

O (N) 어디에 "엔" 배열의 요소 수입니다.

공간 복잡성

O (N) 어디에 "엔" 배열의 요소 수입니다.

참조

균열 시스템 설계 인터뷰
Translate »