Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.
Mündəricat
Problem bəyanat
Bu problemdə bir sinif dizayn etməliyik KthLargest () əvvəlcə k və an tam ədədi var array tam ədədi. Tam bir k və sıra olduqda bunun üçün parametrləşdirilmiş bir konstruktor yazmalıyıq nömrə arqument kimi qəbul edilir. Sinifin də bir funksiyası var əlavə et (val) dəyəri olan yeni bir element əlavə edir val tam ədəd axınına. Hər biri üçün əlavə et () çağırırıq, axındakı axındakı ən böyük element olan bir tam ədədi qaytarmalıyıq.
misal
["KthLargest", "add", "add", "add", "add", "add"] [[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]]
4 5 5 8 8
Explanation:
Yanaşma (Min yığınlar)
Kth ən kiçik / ən böyük elementi tapmağa gəldikdə, demək olar ki, hər dəfə maks / min yığınlar məqsədə xidmət edir. Bunun səbəbi elementləri sıralanmış (prioritetli) bir şəkildə tutmaq üçün çevik təbiətidir. Burada bir sorğu edildikdə elementləri ehtiva edən bir sıra istifadə edə bilərik. Ancaq tapmaq üçün Dizidəki ən böyük element, hər bir sorğu üçün O (N) vaxtından istifadə etməliyik. Buna görə də, O (1) vaxtında k ən böyük elementi tapmaq üçün k ölçüsündə bir min yığın saxlaya bilərik. Diqqət yetirin ki, bir yığın istifadə etdiyimiz üçün, ən üst element yığındakı ən kiçik olardı. Yığın ölçüsünü hər sorğudan sonra k-yə bərabər tutduğumuzdan, bu üst element ümumi axındakı K ən böyük olacaqdır (yığın yalnız k ən böyük elementi saxlayacağı üçün).
Bir Axın Leetcode həllində Kth Ən Böyük Elementin tətbiqi
C ++ Proqramı
#include <bits/stdc++.h>
using namespace std;
class KthLargest {
public:
priority_queue <int , vector <int> , greater <int> > pq;
int K;
KthLargest(int k, vector<int>& nums) {
K = k;
for(int &x : nums) {
pq.push(x);
if(pq.size() > k) {
pq.pop();
}
}
}
int add(int val) {
pq.push(val);
if(pq.size() > K)
pq.pop();
return pq.top();
}
};
int main() {
vector <int> nums = {4 , 5 , 8 , 2};
int k = 3;
KthLargest stream(k , nums);
cout << stream.add(3) << " ";
cout << stream.add(5) << " ";
cout << stream.add(10) << " ";
cout << stream.add(9) << " ";
cout << stream.add(4) << " ";
cout << endl;
return 0;
}
Java Proqramı
import java.util.*;
import java.io.*;
class comp implements Comparator<Integer> {
public int compare(Integer a , Integer b) {
if(a > b)
return 1;
if(a < b)
return -1;
return 0;
}
}
class KthLargest {
int K;
PriorityQueue <Integer> pq;
public KthLargest(int k, int[] nums) {
K = k;
pq = new PriorityQueue <Integer> (new comp());
for(int x : nums) {
pq.add(x);
if(pq.size() > k) {
pq.remove();
}
}
}
int add(int val) {
pq.add(val);
if(pq.size() > K)
pq.remove();
return pq.peek();
}
}
class KthLargestInStream {
public static void main(String args[]) {
int k = 3;
int[] nums = {4 , 5 , 8 , 2};
KthLargest stream = new KthLargest(k , nums);
System.out.print(stream.add(3) + " ");
System.out.print(stream.add(5) + " ");
System.out.print(stream.add(10) + " ");
System.out.print(stream.add(9) + " ");
System.out.print(stream.add(4) + " ");
System.out.println();
}
}
4 5 5 8 8
Bir Axın Leetcode həllində Kth Ən Böyük Elementin Mürəkkəblik Analizi
Zamanın mürəkkəbliyi
O (N + Q), Harada N = ilkin massivin ölçüsü (konstruktoru çağırarkən). Q = Sorğuların sayı. Bunun səbəbi serialı bir dəfə keçdiyimiz və hər bir sorğuya O (1) vaxtında cavab verdiyimizdir.
Kosmik Mürəkkəblik
TAMAM), Harada K verilmiş arqumentdir (konstruktoru çağırarkən). Bunun səbəbi, hər hansı bir əməliyyatdan sonra yığın ölçüsünü tam olaraq k olaraq saxlamağımızdır.
