k보다 크거나 같은 소수 주파수를 가진 숫자

난이도 쉽게
자주 묻는 질문 수행자 아마존 팩트 셋 포카이트 그레이 오렌지 클립 솜
배열 해시 소수조회수 86

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

링크드인버퍼레딧텀블러

문제 정책

문제“k보다 크거나 같은 소수 주파수를 가진 숫자”는 정수 크기 n과 정수 값 k의 배열이 주어 졌음을 나타냅니다. 그 안의 모든 숫자는 소수입니다. 문제 설명은 배열에 최소 k 번 나타나는 숫자와 배열의 소수를 찾아야합니다.

예

arr[] = {29, 11, 37, 53, 53, 53, 29, 53, 29, 53}, k = 2
29 and 53

설명 : 29 번과 53 번이 각각 3 번, 5 번 나오는 것으로 최소 k 번 나오는 조건을 만족합니다.

k보다 크거나 같은 소수 주파수를 가진 숫자를 찾는 알고리즘

1. Declare a map and store all the numbers of the array in the map with their frequencies.
2. Traverse the map.
    1. Check if the frequency of each element is at least k or greater than k.
    2. Find if that frequency is a prime number or not.
    3. If the frequency is a prime number then print that key else go for other numbers.

설명

정수 배열과 값 k를 제공했습니다. 주어진 모든 숫자도 기본입니다. 우리는 그 숫자가 배열에 적어도 k 번 나타나는지, 그리고 소수가 나오는지 알아 내고 그 숫자를 인쇄하도록 요청했습니다. 이를 해결하기 위해 우리는 해싱 방법. 우리는 지도. 우리의 임무는 숫자의 모양을 찾는 것입니다. 이는 각 요소의 발생을 찾아야 함을 의미합니다.이 문제를 해결하기 위해 Map을 사용할 것입니다.

배열을 탐색하고 각 요소와 해당 빈도를 계산하여지도에 저장합니다. 번호가지도의 새 항목 인 경우지도에 해당 위치를 만들고 빈도를 1로 표시합니다. 이미 존재하는 경우 빈도를 가져 와서 빈도를 1 씩 늘린 다음 해당 빈도와 함께 다시 삽입합니다. 그 번호. 이런 식으로 각 숫자의 모든 빈도를 계산할 수 있습니다. 이제 우리는 각 숫자의 빈도가 먼저 k 번 존재하는지 확인해야하며, 또한 나타나는 횟수도 소수 여야합니다.

이 경우지도의 각 키를 탐색하고 빈도를 가져옵니다. 주파수가 소수인지 아닌지를 확인하는 기능을 만들었습니다. 소수의 경우 1이 아니어야하며 자신이 아닌 다른 숫자로 나눌 수 없어야합니다. 숫자로 나눌 수 있으면 false를 반환합니다. 나눌 수있는 경우 해당 키는 해당 주파수의 숫자를 의미하고 다른 숫자를 위해 계속 진행합니다.

 

k보다 크거나 같은 소수 주파수를 가진 숫자핀

 

암호

k보다 크거나 같은 소수 주파수를 가진 숫자를 찾는 C ++ 코드

#include<iostream>
#include<unordered_map>

using namespace std;

bool checkIfPrime(int n)
{
    if (n <= 1)
        return false;

    for (int i = 2; i < n; i++)
        if (n % i == 0)
            return false;

    return true;
}
void numberWithPrimeFreq(int arr[], int k)
{
    unordered_map<int, int> MAP;

    for (int i = 0; i < 12; i++)
        MAP[arr[i]]++;

    for (auto x : MAP)
    {
        if (checkIfPrime(x.second) && x.second >= k)
            cout << x.first << endl;
    }
}
int main()
{
    int arr[] = { 29,11,37,53,53,53,29,53,29,53 };
    int k = 2;

    numberWithPrimeFreq(arr, k);
    return 0;
}

29
53

k보다 크거나 같은 소수 주파수를 갖는 숫자를 찾는 Java 코드

import java.util.HashMap;
import java.util.Map;

public class  Frequencies_PrimeNumber
{
  public static void numberWithPrimeFreq(int[] arr, int k)
  {
    Map<Integer, Integer> MAP = new HashMap<>();

    for (int i = 0; i < arr.length; i++)
    {
      int val = arr[i];

      int freq;
      if (MAP.containsKey(val))
      {
        freq = MAP.get(val);
        freq++;
      }
      else
        freq = 1;
      MAP.put(val, freq);
    }
    for (Map.Entry<Integer, Integer> entry :MAP.entrySet())
    {
      int TEMP = entry.getValue();
      if (checkIfPrime(TEMP) && TEMP >= k)
        System.out.println(entry.getKey());
    }
  }
  private static boolean checkIfPrime(int n)
  {
    if ((n > 2 && n % 2 == 0) || n == 1)
      return false;

    for (int i = 2 ; i <n;	i ++)
    {
      if (n % i == 0)
        return false;
    }
    return true;
  }
  public static void main(String[] args)
  {
    int[] arr = { 29,11,37,53,53,53,29,53,29,53 };
    int k = 2;

    numberWithPrimeFreq(arr, k);
  }
}

53
29

복잡성 분석

시간 복잡성

여기서 우리는 주파수 k를 가진 n / k 요소를 가지고 있다고 생각해 보면 매번 소수성이 확인 될 것입니다. 그러나 소수성 검사는 O (n) 시간 만 걸립니다. 여기서 n은 주파수입니다. 따라서 최악의 경우에도 전체 알고리즘이 선형 시간으로 실행될 수 있습니다. 의 위에) 어디에 "엔"  배열의 요소 수입니다.

공간 복잡성

입력을 저장하는 데 필요한 공간 때문에 의 위에) 어디에 "엔"  배열의 요소 수입니다.

링크드인버퍼레딧텀블러
균열 시스템 설계 인터뷰
Translate »