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.
In Maksimum sürüşmə pəncərə problem verdik array nums, k ölçülü hər bitişik pəncərə üçün pəncərədə maksimum elementi tapın.
Mündəricat
misal
Input
nums [] = {1,3, -1, -3,5,3,6,7} k = 3
Buraxılış
3,3,5,5,6,7 {}
Izahat
Maksimum sürüşən pəncərə üçün sadəlövh yanaşma
K ölçülü hər bitişik pəncərə üçün pəncərədən keçin və maksimum elementi tapın.
- İndeks 0-dan bir döngə işlədin (massivin ölçüsü - k - 1)
- İndeksdən (i + k) başqa bir iç içə döngə işlədin
- İç içə dönmə bir pəncərəni təmsil edir, iç içə döngənin içərisində maksimum dəyəri tapın
- Yuxarıda tapılan maksimum dəyər cari pəncərənin maksimum dəyəridir.
- Bütün maksimumları tapmaq üçün yuxarıdakı addımları təkrarlayın
Zaman Mürəkkəbliyi = O (n * k)
Kosmik Mürəkkəblik = O (1)
JAVA Kodu
public class Naive {
private static int[] maxSlidingWindow(int[] nums, int k) {
int ans[] = new int[nums.length - k + 1];
// Traverse all the windows one by one
for (int i = 0; i < nums.length - k + 1; i++) {
// Initialise max as -infinite
int max = Integer.MIN_VALUE;
// Traverse the current window and find the maximum
for (int j = i; j < i + k; j++) {
max = Math.max(max, nums[j]);
}
// assign the current ans as maximum
ans[i] = max;
}
return ans;
}
public static void main(String[] args) {
// Example
int nums[] = new int[]{1, 3, -1, -3, 5, 3, 6, 7};
int k = 3;
int max[] = maxSlidingWindow(nums, k);
// Print the maximums
for (int i = 0; i < max.length; i++) {
System.out.print(max[i] + " ");
}
}
}
3 3 5 5 6 7
C ++ kodu
#include<bits/stdc++.h>
using namespace std;
vector<int> maxSlidingWindow(int *nums, int k, int n) {
vector<int> ans;
// Traverse all the windows one by one
for (int i = 0; i < n - k + 1; i++) {
// Initialise max as -infinite
int max = INT_MIN;
// Traverse the current window and find the maximum
for (int j = i; j < i + k; j++) {
max = std::max(max, nums[j]);
}
// assign the current ans as maximum
ans.push_back(max);
}
return ans;
}
int main() {
// Example
int nums[] = {1, 3, -1, -3, 5, 3, 6, 7};
int k = 3;
vector<int> ans = maxSlidingWindow(nums, k, sizeof(nums) / sizeof(nums[0]));
// Print the maximums
for (int i = 0; i < ans.size(); i++) {
cout<<ans[i]<<" ";
}
return 0;
}
3 3 5 5 6 7
Maksimum sürüşmə pəncərəsi üçün optimal yanaşma
İlk k elementlərini özünüzü balanslaşdıran BST-də saxlayın, BST-də ən böyük element ilk pəncərə üçün maksimum element verir.
Qalan alt cədvəllər üçün əvvəlki pəncərənin ilk elementini öz balanslaşdırma BST-dən çıxarın və cari elementi əlavə edin, ən böyük element yenidən cari pəncərədəki maksimum elementi qaytarır.
Təkrarlanan elementlərin işini idarə etmək üçün BST-də elementə nisbətən tezliyi saxlayın.
Zaman Mürəkkəbliyi = O (n log (k))
Kosmik Mürəkkəblik = Tamam)
JAVA Kodu
import java.util.TreeMap;
public class Optimal {
private static int[] maxSlidingWindow(int[] nums, int k) {
int ans[] = new int[nums.length - k + 1];
TreeMap<Integer, Integer> map = new TreeMap<>();
// Store the first k elements and their frequencies in a self balancing BST
for (int i = 0; i < k; i++) {
if (map.containsKey(nums[i])) {
map.put(nums[i], map.get(nums[i]) + 1);
} else {
map.put(nums[i], 1);
}
}
// Largest value of BST gives the first maximum
ans[0] = map.lastKey();
int index = 1;
// Traverse the remaining elements
for (int i = k; i < nums.length; i++) {
// Remove first element of previous window from BST
int freq = map.get(nums[i - k]);
if (freq == 1) {
map.remove(nums[i - k]);
} else {
map.put(nums[i - k], freq - 1);
}
// Add current element to BST
if (map.containsKey(nums[i])) {
map.put(nums[i], map.get(nums[i]) + 1);
} else {
map.put(nums[i], 1);
}
// Current asnwer is maximum value in BST
ans[index++] = map.lastKey();
}
return ans;
}
public static void main(String[] args) {
// Example
int nums[] = new int[]{1, 3, -1, -3, 5, 3, 6, 7};
int k = 3;
int max[] = maxSlidingWindow(nums, k);
// Print the maximums
for (int i = 0; i < max.length; i++) {
System.out.print(max[i] + " ");
}
}
}
3 3 5 5 6 7
C ++ kodu
#include<bits/stdc++.h>
using namespace std;
vector<int> maxSlidingWindow(int *nums, int k, int n) {
vector<int> ans;
map<int, int> eleFreq;
// Store the first k elements and their frequencies in a self balancing BST
for (int i = 0; i < k; i++) {
std::map<int, int>::iterator itr;
itr = eleFreq.find(nums[i]);
if (itr == eleFreq.end()) {
eleFreq.insert(make_pair(nums[i], 1));
} else {
itr->second++;
}
}
ans.push_back(eleFreq.rbegin()->first);
for (int i = k; i < n; i++) {
// Remove first element of previous window from BST
std::map<int, int>::iterator itr = eleFreq.find(nums[i - k]);
if (itr->second > 1) {
itr->second--;
} else {
eleFreq.erase(itr->first);
}
// Add current element to BST
itr = eleFreq.find(nums[i]);
if (itr == eleFreq.end()) {
eleFreq.insert(make_pair(nums[i], 1));
} else {
itr->second++;
}
// Current answer is maximum value in BST
ans.push_back(eleFreq.rbegin()->first);
}
return ans;
}
int main() {
// Example
int nums[] = {1, 3, -1, -3, 5, 3, 6, 7};
int k = 3;
vector<int> ans = maxSlidingWindow(nums, k, sizeof(nums) / sizeof(nums[0]));
// Print the maximums
for (int i = 0; i < ans.size(); i++) {
cout<<ans[i]<<" ";
}
return 0;
}
3 3 5 5 6 7
