시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.
"배열의 최고 주파수와 최소 주파수 간의 차이"문제는 정수 정렬. 문제 설명은 배열에있는 두 개의 고유 숫자 중 가장 높은 빈도와 가장 낮은 빈도 사이의 최대 차이를 알아 내도록 요청합니다.
차례
예
arr[] = {1, 2, 3, 1, 5, 2, 3, 1 }
2
설명
주파수 1 → 3 (가장 높은 주파수)
주파수 5 → 1 (최저 주파수)
arr[] = {5, 4, 5, 5, 5, 3, 4 }
3
설명
주파수 5 → 4 (가장 높은 주파수)
주파수 3 → 1 (최저 주파수)
암호알고리즘
- 선언 지도.
- 배열 요소의 빈도를 저장하고 계산합니다.
- 세트 최대 주파수 0 및 민프레크 에 n.
- 지도 횡단 :
- 지도에서 maxfreq와 주파수 사이의 최대 값을 찾아서 maxfreq에 저장합니다.
- 지도에서 minfreq와 주파수 사이의 최소값을 찾아서 minfreq에 저장합니다.
- 반환 (maxfreq-minfreq).
설명
정수 배열이 있습니다. 우리의 임무는 배열에 존재하는 두 개의 고유 한 숫자의 가장 높은 발생과 가장 낮은 발생 사이의 최대 차이를 찾는 것입니다. 우리는 사용할 것입니다 해싱. 해싱은이 질문을 해결하는 효율적인 방법을 제공합니다. 우리는 맵을 선언하고 각 배열 요소의 주파수를 계산하고 동시에 요소와 함께 주파수를 맵에 저장합니다.
그런 다음 값을 설정합니다. 최대 주파수 0 및 민프레크 즉, 주어진 배열의 크기보다 큰 주파수를 갖는 요소가 없기 때문에 배열의 길이. 우리는지도를 횡단하고 모든 요소를 하나씩 집어 들고 주파수가 가장 큰지 또는 가장 낮은 지 확인합니다. 최대 주파수를 다른 변수로, 최소 주파수를 다른 변수로 분리하십시오. 최대 주파수와 최저 주파수의 차이를 반환해야하므로 (maxfreq-minfreq)를 반환합니다.
예를 들어 보겠습니다.
예
arr [] = {1, 2, 3, 1, 5, 2, 3, 1}
배열을 처음 탐색 할 때 요소와 발생 횟수를지도에 배치하고, 탐색 후지도를 다음과 같이 갖게됩니다.
지도 : {1 : 3, 2 : 2, 3 : 2, 5 : 1}
이제 맵에 각 요소의 발생이 있습니다. 맵을 가로 지르고 맵에서 각 요소를 선택하여 더 큰 현재 주파수 또는 maxfreq이고 최소 전류 주파수 또는 minfreq를 저장하고 각각 maxfreq 및 minfreq에 저장합니다.
- 1 : 3 →
3은 maxfreq보다 크므로 maxfreq = 3
3은 minfreq보다 작으므로 minfreq = 3
- 2 : 2 →
maxfreq가 2보다 크므로 maxfreq = 3
2은 minfreq보다 작으므로 minfreq = 2
- 3 : 2 →
maxfreq가 2보다 크므로 maxfreq = 3
minfreq, minfreq = 2에서는 아무것도 변경되지 않습니다.
- 5 : 1 →
maxfreq가 1보다 크므로 maxfreq = 3
1은 minfreq보다 작으므로 minfreq = 1
그리고 maxfreq-minfreq → (3-1) = 2의 차이를 반환합니다.
암호
배열에서 가장 높은 빈도와 가장 낮은 빈도의 차이를 찾는 C ++ 코드
#include<iostream>
#include<unordered_map>
using namespace std;
int getMaximumDiff(int arr[], int n)
{
unordered_map<int, int> freq;
for (int i = 0; i < n; i++)
freq[arr[i]]++;
int maxfreq = 0, minfreq = n;
for (auto x : freq)
{
maxfreq = max(maxfreq, x.second);
minfreq = min(minfreq, x.second);
}
return (maxfreq - minfreq);
}
int main()
{
int arr[] = {1, 2, 3, 1, 5, 2, 3, 1 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << getMaximumDiff(arr, n) << "\n";
return 0;
}
2
배열에서 가장 높은 빈도와 가장 낮은 빈도의 차이를 찾기위한 Java 코드
import java.util.HashMap;
import java.util.Map;
class diffBWHighFLeastF
{
public static int getMaximumDiff(int arr[], int n)
{
HashMap<Integer,Integer> freq = new HashMap<>();
for (int i = 0 ; i < n; i++)
{
if(freq.containsKey(arr[i]))
{
freq.put(arr[i], freq.get(arr[i])+1);
}
else
{
freq.put(arr[i], 1);
}
}
int maxfreq = 0, minfreq = n;
for (Map.Entry<Integer,Integer> x : freq.entrySet())
{
maxfreq = Math.max(maxfreq, x.getValue());
minfreq = Math.min(minfreq, x.getValue());
}
return (maxfreq - minfreq);
}
public static void main(String[] args)
{
int arr[] = {1, 2, 3, 1, 5, 2, 3, 1 };
int n = arr.length;
System.out.println(getMaximumDiff(arr, n));
}
}
2
복잡성 분석
시간 복잡성
O (N) 어디에 "엔" 배열의 요소 수입니다. 여기서 우리는 단순히 주파수를 추적하면서 배열의 요소를 순회했습니다. 이 모든 비용은 O (N) 시간입니다.
공간 복잡성
O (N) 어디에 "엔" 배열의 요소 수입니다. 기껏해야 n 개의 요소가 모두 구별되는 경우 저장할 수 있습니다. 공간 복잡성은 선형입니다.
