시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.
K 명의 근로자를 고용하기위한 최소 비용 문제에서, 우리는 정확히 k 명의 근로자를 고용하여 유급 그룹을 형성 할 N 명의 근로자를 제공했습니다. i 번째 근로자는 품질 [i]과 최저 임금 기대 임금 [i]을 가지고 있습니다.
다음 규칙에 따라 급여가 지급됩니다.
- 유급 그룹의 모든 근로자는 유급 그룹의 다른 근로자에 비해 품질 비율로 급여를 받아야합니다.
- 유급 그룹의 모든 근로자는 최소 기대 임금을 받아야합니다.
차례
예
입력: 품질 = [50, 30, 10, 60, 70], 임금 = [100, 120, 130, 90, 140], K = 3
출력: 360
K 근로자를 고용하기위한 최소 비용 요점
품질 = [a, b, c, d] 및 임금 = [p, q, r, s]가 있다고 가정 해 보겠습니다.
- 첫 번째 요소에 대한 품질의 유효 비율은 다음과 같습니다. [1, b / a, c / a, d / a]
- 유효 임금 : [p, pb / a, pc / a, pd / a]
- 보장하기 위해 최저 임금 비율에 대해 j 번째 요소를 고려할 때 i 번째 요소를 선택하여 k 노동자의 유료 그룹을 형성합니다. B [i] <= (A [i] / A [j]) * B [j] == B [i] / A [i] <= B [j] / A [j] 즉, 조건을 만족하기 위해서는 품질 / 최저 임금 비율이 내림차순으로 정렬되어야하며, 이후의 모든 비율 j 번째 근로자는 고려시 자동으로 최저 임금 조건을 만족하게됩니다. i 번째 요소.
- 다음 최적의 솔루션: (b / cr + r + d / cr)은 다음과 같습니다. (b + c + d) * (r / c) 즉, 비례 인자를 곱한 품질의 최소 합이 해입니다. 우리는 이미 내림차순 O (nlogn)의 r / c를 가지고 있습니다.
- nk-1 요소에서 시작한다는 것은 마지막 k 요소가 (nk) 번째 요소의 관점에서 사용 가능한 최소 요소임을 의미합니다. 이 숫자의 최대 힙을 유지하십시오 (-min heap == max heap). 최소 k 요소의 최대 값보다 작은 숫자를 볼 수 있습니다. 최대 값을 제거하고 새 요소를 삽입하기 만하면됩니다.
- 더 작은 새 요소가 감지되는 즉시 힙이 업데이트되고 새로운 잠재적 최소 합계가 확인됩니다.
K 근로자 고용을위한 최소 비용 구현
C ++ 프로그램
#include<bits/stdc++.h>
using namespace std;
double hireKworkers(vector<int>& quality, vector<int>& wage, int K) {
int N = quality.size();
vector<pair<double, int>> vec;
for(int i = 0; i < N; i++) {
vec.push_back(make_pair(wage[i] * 1.0 / quality[i], quality[i]));
}
sort(vec.begin(), vec.end(), [](auto& a, auto& b){
return a.first < b.first;
});
int quality_cnt = 0;
priority_queue<int> q;
for(int i = 0; i < K; i++) {
quality_cnt += vec[i].second;
q.push(vec[i].second);
}
double ans = quality_cnt * vec[K - 1].first;
for(int i = K; i < N; i++) {
q.push(vec[i].second);
quality_cnt += vec[i].second;
quality_cnt -= q.top();
q.pop();
ans = min(ans, quality_cnt * vec[i].first);
}
return ans;
}
int main(){
int n=5;
vector<int> quality ={50, 30, 10, 60, 70};
vector<int> wages = {100, 120, 130, 90, 140};
int k=3;
cout<<"The least amount of money needed to form a paid group: "<<hireKworkers(quality,wages,k);
}
The least amount of money needed to form a paid group: 360
JAVA 프로그램
import java.util.*;
class Main {
public static double hireKworkers(int[] quality, int[] wage, int K) {
double[][] workers = new double[quality.length][2];
PriorityQueue<Double> heap = new PriorityQueue<>(Comparator.reverseOrder());
double sum = 0;
double result = Integer.MAX_VALUE;
for(int i = 0; i < quality.length; i++) {
workers[i][0] = (double) wage[i] / (double) quality[i];
workers[i][1] = quality[i];
}
Arrays.sort(workers, (o1, o2) -> {
if(o1[0] - o2[0] == 0) return 0;
if(o1[0] - o2[0] > 0) return 1;
return -1;
});
for(double[] worker : workers) {
if(heap.size() == K) {
sum -= heap.poll();
}
heap.add(worker[1]);
sum += worker[1];
if(heap.size() == K) {
result = Math.min(result, sum * worker[0]);
}
}
return result;
}
public static void main(String args[])
{
int n=4;
int[] quality = { 20, 40, 10, 50};
int[] wages = {70, 80, 30, 40};
int k=3;
System.out.println("The least amount of money needed to form a paid group: "+hireKworkers(quality,wages,k));
}
}
The least amount of money needed to form a paid group: 245.0
K 근로자 고용을위한 최소 비용에 대한 복잡성 분석
시간 복잡성
O (NlogN) 힙 / 우선 순위 큐에 삽입하는 데는 로그온 시간이 걸리며 전체를 순회합니다. 정렬 따라서 전체 시간 복잡도는 O (NlogN)가됩니다.
공간 복잡성
의 위에) 여기서 N은 입력 배열의 크기입니다.
