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.
Üst-üstə düşməyən 3 subarrays probleminin maksimum cəmində bir verdik array müsbət tam ədədin sayı, maksimum cəmi olan k uzunluğunun üst-üstə düşməyən üç subarasını tapın və başlanğıc indekslərini qaytarın.
Mündəricat
misal
Input:
saylar [] = {1, 2, 1, 2, 6, 7, 5, 1}
k = 2
Çıxış:
{0, 3, 5}
Üst-üstə düşməyən 3 alt cədvəlin maksimum cəmi üçün alqoritm
Fikir bütün uzunluqlu fasiləsiz subrayların cəmini saxlayan bir cəm massivi qurmaqdır. İ indeksi üçün ondan alınan maksimum cəm [i] + indeksdən 0-a (i -k) qədər cəmin maksimum dəyəri + cəmin uzunluğuna qədər (i + k) cəmin maksimum dəyəridir.
Soldan və sağdan daha 2 massiv yaradın, burada sol, indeksə qədər bitişik bir uzunluqlu bir massivin maksimum cəminin indeksini saxlayır və sağ da eyni, lakin sondan başlayaraq saxlayır.
Dizin k-dən indeksə (cəmi uzunluğu - k) qədər olan sıra cəmini keçin, hər bir indeks üçün ondan alınan maksimum cəm cəm [i] + cəm [sol [i - k]] + cəm [sağ [i + k]].
Bütün mümkün cəmlər üçün maksimum cəmi və müvafiq indeksləri tapın.
Üst-üstə düşməyən 3 subarraysın maksimum cəminin izahı
Yuxarıdakı nümunədəki massivi nəzərdən keçirin,
nums [] = {1, 2, 1, 2, 6, 7, 5, 1} və k = 2
Nums array üçün 2 uzunluğunda bitişik alt məcmuların bütün mümkün cəmlərini saxlayan cəmi array.
cəmi [] = {3, 3, 3, 8, 13, 12, 6}
Alqoritmdə təsvir olunduğu kimi sola və sağa massivlər yaradın
sol [] = {0, 0, 0, 3, 4, 4, 4}
sağ [] = {4, 4, 4, 4, 4, 5, 6}
İndeks 2-dən indeks 4-ə qədər başlayan cəmi cərgəsində keçin,
- i = 2, cəmi [i] = 3
indeksdən alınan cəm 2 = 3 + (cəmi [sol [2 - 2]]) + (cəmi [sağ [2 + 2]]) = 19 - i = 3, cəmi [i] = 8
indeksdən alınan cəm 3 = 8 + (cəmi [sol [3 - 2]]) + (cəmi [sağ [3 + 2]]) = 23 - i = 4, cəmi [i] = 13
indeksdən alınan cəm 4 = 13 + (cəmi [sol [4 - 2]]) + (cəmi [sağ [4 + 2]]) = 22
Alınan maksimum məbləğ = 23 və başlanğıc göstəriciləri {0, 3, 5}
Üst üstə düşməyən 3 subarraysin maksimum cəmi üçün JAVA kodu
public class MaximumSumOfThreeNonOverlappingIntervals {
private static int[] findInicies(int[] nums, int k) {
int n = nums.length;
// build sum array that stores the sum of all k length continuous subarrays
int sum[] = new int[n - k + 1];
int currSum = 0;
for (int i = 0; i < k; i++) {
currSum += nums[i];
}
sum[0] = currSum;
for (int i = k;i < n; i++) {
currSum -= nums[i - k];
currSum += nums[i];
sum[i - k + 1] = currSum;
}
// Create left array that stores the index of maximum sum of contiguous array of length k upto that index
int left[] = new int[sum.length];
int best = 0;
for (int i = 0; i < sum.length; i++) {
if (sum[i] > sum[best]) {
best = i;
}
left[i] = best;
}
best = sum.length - 1;
// Create right array that stores the index of maximum sum of contiguous array of length k upto that index
// starting from end
int right[] = new int[sum.length];
for (int i = sum.length - 1; i >= 0; i--) {
if (sum[i] >= sum[best]) {
best = i;
}
right[i] = best;
}
// Initialise ans array as -1
int ans[] = new int[] {-1, -1, -1};
// Traverse in sum array from index k to (sum length - k)
for (int i = k; i < sum.length - k; i++) {
// Maximum sum obtained from this index is sum[i] + sum[left[i -k]] + sum[right[i + k]]
int l = left[i - k];
int r = right[i + k];
if (ans[0] == -1 ||
(sum[l] + sum[i] + sum[r]) > (sum[ans[0]] + sum[ans[1]] + sum[ans[2]])) {
// Update the indices if the max sum is greater than the actual max sum
ans[0] = l;
ans[1] = i;
ans[2] = r;
}
}
// return ans array
return ans;
}
public static void main(String[] args) {
// Example
int nums[] = new int[] {1,2,1,2,6,7,5,1};
int k = 2;
int indices[] = findInicies(nums, k);
for (int i = 0; i < 3; i++)
System.out.print(indices[i] + " ");
System.out.println();
}
}
Üst-üstə düşməyən 3 subarraysin maksimum cəmi üçün C ++ kodu
#include <iostream>
#include <vector>
using namespace std;
void findIndices(int *nums, int k, int n, vector<int> &ans) {
// build sum array that stores the sum of all k length continuous subarrays
int sum[n- k + 1];
int currSum = 0;
for (int i = 0; i < k; i++) {
currSum += nums[i];
}
sum[0] = currSum;
for (int i = k;i < n; i++) {
currSum -= nums[i - k];
currSum += nums[i];
sum[i - k + 1] = currSum;
}
// Create left array that stores the index of maximum sum of contiguous array of length k upto that index
int left[n - k + 1];
int best = 0;
for (int i = 0; i < n - k + 1; i++) {
if (sum[i] > sum[best]) {
best = i;
}
left[i] = best;
}
best = n - k;
// Create right array that stores the index of maximum sum of contiguous array of length k upto that index
// starting from end
int right[n - k + 1];
for (int i = n - k; i >= 0; i--) {
if (sum[i] >= sum[best]) {
best = i;
}
right[i] = best;
}
// Initialise ans array as -1
ans.push_back(-1);
ans.push_back(-1);
ans.push_back(-1);
// Traverse in sum array from index k to (sum length - k)
for (int i = k; i < (n - k + 1 - k); i++) {
// Maximum sum obtained from this index is sum[i] + sum[left[i -k]] + sum[right[i + k]]
int l = left[i - k];
int r = right[i + k];
if (ans[0] == -1 ||
(sum[l] + sum[i] + sum[r]) > (sum[ans[0]] + sum[ans[1]] + sum[ans[2]])) {
// Update the indices if the max sum is greater than the actual max sum
ans[0] = l;
ans[1] = i;
ans[2] = r;
}
}
}
int main() {
int nums[] = {1,2,1,2,6,7,5,1};
int k = 2;
int n = sizeof(nums) / sizeof(nums[0]);
vector<int> ans;
findIndices(nums, k, n, ans);
for (int i = 0; i < ans.size(); i++) {
cout<<ans[i]<<" ";
}
cout<<endl;
return 0;
}
0 3 5
Mürəkkəblik təhlili
Zaman Mürəkkəbliyi = O (n)
Kosmik Mürəkkəblik = O (n)
burada n - verilən massivdə mövcud olan elementlərin sayı.
