스트림에서 상위 K (또는 가장 빈번한) 번호 찾기

난이도 중급
자주 묻는 질문 수행자 아마존
배열 해시조회수 116

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

스트림 문제에서 상위 k (또는 가장 빈번한) 숫자 찾기에서 정수를 제공했습니다. 정렬 일부 숫자로 구성됩니다. 문제 설명은 배열에서 요소를 가져와야하며 상단에는 최대 k 개의 숫자 만 가질 수 있습니다. 빈도에 따라 점차적으로 정렬되는 상위 k 개 요소를 인쇄해야합니다.

입력

[3, 1, 4, 6, 1] k = 4

산출

3, 1, 3, 1, 3, 4, 1, 3, 4, 6, 1, 3, 4, 6

스트림의 상위 k (또는 가장 빈번한) 숫자에 대한 설명

  • 우리가 1을 읽을 때st 배열의 요소가 3이고 지금까지 주파수가 1 인 유일한 요소로 '3'을 인쇄합니다.
  • 배열의 두 번째 요소 인 2을 읽고 동일한 주파수를 가진 1과 3이 있습니다. 즉, 1이지만 1은 1보다 작으므로 3 1을 인쇄합니다.
  • 다음 단계에서 배열의 세 번째 요소 인 3를 읽고 동일한 주파수 즉, 4을 가진 3, 1, 4가 있지만 정렬 된 순서는 1 1 3 여야합니다.
  • 배열의 4 번째 요소 인 6을 읽고 동일한 주파수 즉, 3을 가진 1, 4, 6, 1이 있지만 정렬 된 순서는 1 3 4이어야합니다.
  • 배열의 5 번째 요소 인 1을 읽고 3, 1, 4, 6이 모두 같은 주파수를 가질 때 즉, 1이지만 1은 주파수가 1보다 크므로 주파수가 더 큰 요소가 먼저 와야합니다. 1 3 4이어야합니다.

스트림에서 상위 K (또는 가장 빈번한) 번호 찾기

입력

[1, 2, 2, 4, 5] k = 4

산출

1, 1, 2, 2, 1, 2, 1, 4, 2, 1, 4, 5

스트림의 상위 k (또는 가장 빈번한) 숫자에 대한 설명

  • 우리가 1을 읽을 때st 배열의 요소가 1이고 지금까지 주파수가 1 인 유일한 요소로 '1'을 인쇄합니다.
  • 2 인 배열의 두 번째 요소를 읽고 동일한 주파수를 가진 2와 2을 가지고 있습니다. 즉, 1이지만 1은 1보다 작으므로 2 1를 인쇄합니다.
  • 다음 단계에서는 배열의 세 번째 요소 인 3를 읽고 2는 주파수보다 더 큰 주파수를 가지므로 더 높은 주파수를 가진 요소가 먼저 오므로 2 2을 인쇄합니다.
  • 배열의 4 번째 요소 인 4를 읽고 주파수가 4 인 1와 1이 있으므로 2 1 4를 인쇄합니다.
  • 5 인 배열의 5 번째 요소를 읽고 1, 4, 5가 모두 같은 주파수를 가질 때 즉, 1이지만 2는 주파수가 1보다 크므로 주파수가 더 큰 요소가 먼저 와야합니다. 2 1 4 5.

암호알고리즘

  1. HashMap을 선언하십시오.
  2. 배열을 선언하십시오.
  3. 지도에 각 요소의 빈도를 계산하고 저장합니다.
  4. 요소를 k + 1 위치에 놓습니다.
  5. 상단 요소를 검색하고 위치를 가져옵니다.
  6. 얻은 위치에서 0까지 반복합니다.
  7. 더 높은 주파수의 요소가 i 옆에 저장되어 있으면 바꿉니다.
  8. 주파수가 같지만 다음 요소가 더 큰 경우 바꿉니다.
  9. 배열의 모든 반복에 대해 상위 k를 인쇄합니다.

에 대한 설명 스트림에서 상위 k (또는 가장 빈번한) 숫자 찾기

우리는 배열과 그 안에 몇 가지 숫자를 제공했습니다. 여기에서 각 반복마다 스트림에서 상위 k (또는 가장 빈번한) 숫자를 찾아야합니다. 우리는 그것에 대한 몇 가지 조건을 제공했습니다. 먼저해야 할 일은 각 요소와 그 빈도를 세는 것입니다. 그리고 우리는 그 빈도와 함께 그 요소를지도에 저장할 것입니다. 배열이 반복 될 때마다 요소와 빈도를 입력해야합니다.

빈도로 해당 맵에 넣은 첫 번째 요소를 반복 한 다음 해당 배열의 요소를 k 번째 위치의 임시 배열에 복사했다고 가정합니다. 그런 다음 임시 배열에서 해당 요소의 위치를 ​​찾아 임시 변수에 저장하고 해당 임시 변수를 카운트 1만큼 줄입니다.

반복 while 루프 해당 위치 (임시 변수)에서 0으로 설정하고 그 안에 세 가지 조건을 설정합니다. 해당 위치 값의 빈도가 다음 요소의 빈도보다 작 으면 두 요소를 모두 바꿉니다. 빈도가 비슷하지만 다음 요소가 그에 따라 교체하는 것보다 큰 경우. 그렇지 않으면 루프를 끊어야합니다.

기본 아이디어는 모든 상위 k 요소 쌍을 감소하지 않는 순서로 정렬해야한다는 것입니다. 그러나 해당 상위 k 요소 쌍의 요소 중 어떤 요소가 다른 요소의 주파수보다 더 큰 주파수를 갖는 경우이를 넣어야합니다. 요소를 순서대로 그래서 숫자 2가 주파수 2를 가지고 반복되기 때문에 우리 순서에서 가장 먼저 나오는 이유입니다. 그래서 그것은 우리 순서에서 가장 큰 주파수 숫자였습니다.

모든 상위 k 요소 쌍을 교환하고 배열 한 후에는 스트림에서 상위 k (또는 가장 빈번한) 숫자를 인쇄해야합니다.

스트림에서 상위 k (또는 가장 빈번한) 숫자 찾기 구현

C ++ 프로그램

#include <bits/stdc++.h>
using namespace std;

void kTop(int arr[], int n, int k)
{
  vector<int> topArray(k + 1);

  unordered_map<int, int> freq;

  for (int l = 0; l < n; l++)
    {
    freq[arr[l]]++;

    topArray[k] = arr[l];
    auto itr = find(topArray.begin(), topArray.end() - 1, arr[l]);

    for (int i = distance(topArray.begin(), itr) - 1; i >= 0; --i)
        {

      if (freq[topArray[i]] < freq[topArray[i + 1]])
        swap(topArray[i], topArray[i + 1]);

      else if ((freq[topArray[i]] == freq[topArray[i + 1]])
          && (topArray[i] > topArray[i + 1]))
        swap(topArray[i], topArray[i + 1]);
      else
        break;
    }
    for (int i = 0; i < k && topArray[i] != 0; ++i)
      cout << topArray[i] << ' ';
  }
  cout << endl;
}
int main()
{
  int k = 4;
  int arr[] = { 5, 2, 1, 3, 2 };
  int n = sizeof(arr) / sizeof(arr[0]);
  kTop(arr, n, k);
  return 0;
}
5 2 5 1 2 5 1 2 3 5 2 1 3 5

자바 프로그램

import java.io.*;
import java.util.*;
class topKElements
{
    public static int findTop(int[] arr, int ele)
    {
        for (int i = 0; i < arr.length; i++)
            if (arr[i] == ele)
                return i;
        return -1;
    }
    public static void printTopElements(int[] a, int n, int k)
    {
        int[] topArray = new int[k + 1];

        HashMap<Integer, Integer> freq = new HashMap<>();
        for (int i = 0; i < k + 1; i++)
            freq.put(i, 0);

        for (int l = 0; l < n; l++)
        {
            if (freq.containsKey(a[l]))
                freq.put(a[l], freq.get(a[l]) + 1);
            else
                freq.put(a[l], 1);

            topArray[k] = a[l];

            int i = findTop(topArray, a[l]);

            i -= 1;

            while (i >= 0)
            {
                if (freq.get(topArray[i]) < freq.get(topArray[i + 1]))
                {
                    int temp = topArray[i];
                    topArray[i] = topArray[i + 1];
                    topArray[i + 1] = temp;
                }
                else if ((freq.get(topArray[i]) == freq.get(topArray[i + 1])) && (topArray[i] > topArray[i + 1]))
                {
                    int temp = topArray[i];
                    topArray[i] = topArray[i + 1];
                    topArray[i + 1] = temp;
                }
                else
                {
                    break;
                }
                i -= 1;
            }
            for (int j = 0; j < k && topArray[j] != 0; j++)
            {
                System.out.print(topArray[j]+" ");
            }
        }
        System.out.println();
    }
    public static void main(String args[])
    {
        int k = 4;
        int[] arr = { 5, 2, 1, 3, 2 };
        int n = arr.length;
        printTopElements(arr, n, k);
    }
}
5 2 5 1 2 5 1 2 3 5 2 1 3 5

스트림에서 상위 k 개 (또는 가장 빈번한) 숫자 찾기에 대한 복잡성 분석

시간 복잡성

O (n * k)  각 순회에서 크기의 임시 배열이 "케이" 순회 "엔" 순회됩니다.

공간 복잡성

O (N) HashMap에 요소를 저장하면 "엔" 시간.

참조

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