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
Sizə bir ədəd tam ədəd verilir. Problem ifadəsi ən böyük cəmi bitişik subarrayı tapmağı xahiş edir. Bu, verilmiş massivdəki digər subarrayslar arasında ən böyük cəmi olan subarray (davamlı elementlər) tapmaqdan başqa bir şey demək deyil.
misal
arr[] = {1, -3, 4, -2, 5, -6, 2}
[2, 4]
İzahat: İndeks 2-dən indeks 4-ə qədər başlayan alt sıra, massiv içərisində ən böyük cəmi 7-yə malikdir. Hər hansı bir subarray 7-dən kiçik bir məbləğ verəcəkdir.
arr[] = {1, -3, 4, -1, 4, -2, 5, -6, 2}
[2, 6]
İzahat: İndeks 2-dən indeks 6-ya qədər başlayan alt sıra, massiv içərisində ən böyük cəmi 10-a malikdir.
Ən böyük cəm bitişik subarray problemi üçün alqoritm
1. Set the maxValue to the minimum value an integer can hold (INT_MIN / Integer.MIN_VALUE) and maxPoint to 0.
2. Set start, end, s to 0.
3. Traverse the array starting from i=0 to i<size(length of the array).
1. Add the maxPoint and arr[i] and update it into the maxPoint.
2. Check if maxValue is less than maxPoint, then update the following:
1. maxValue = maxPoint
2. start=s
3. end=i
3. Check if the maxPoint is less than 0, then update
1. maxPoint=0
2. s=i+1
4. Print ‘start’ and ‘end’ as an index and the maxValue as the largest sum.
Izahat
Biz verdik array tam ədədi. Ən böyük cəmi bitişik subarrayı tapmağı xahiş etdik. Tərkibində mənfi və müsbət tam ədədlər də ola bilər. Bütün bu işlərin öhdəsindən gəlməliyik. Bunun üçün serialı yalnız bir dəfə keçəcəyik və bu səbəbdən də mürəkkəblik vaxtına sahibdir O (n). Xətti zaman mürəkkəbliyində maksimum bitişik subarray cəmini tapacağıq.
Kimi bəzi dəyərlər qurun maksimum dəyər Bir Tamsayı tuta biləcəyi minimum dəyərə, maxPoint 0-a və Başlamaq, sonvə s 0-a qədər. Dizini uzunluğa qədər keçməyə başlayın n. Cari array elementini cəmi maxPoint-ə əlavə edin. Hər zaman dəyəri olan maxPoint-də saxlayın i loopda artımlar, bu əməliyyatı edirik. Artıq dəyərini təyin etdik maksimum dəyər bir Tamsayı minimum dəyərinə və maxValue-nun maxPoint-dən az olub olmadığını yoxlayın. Bu doğrudursa, maxValue dəyərini maxPoint-dən yeniləyəcəyik, s-ə başlayın. Bu başlanğıc dəyişən bitişik alt dizinin başlanğıc aralığının dəyərini təyin edəcək və i (loop dəyişən) ilə yenilədiyimiz bir sonumuz var.
İndi yoxlayacağıq maxPoint 0-dan azdırsa, indiyə qədər sıra dəyərlərinin əlavə edilməsi mənfi deməkdir. Sonra yenidən maxPoint dəyərini 0-a, s-i isə i + 1-ə yeniləyirik. Bu s başlanğıc aralığının dəyərini təyin etməkdə bizə yenidən kömək edəcək və ən böyük cəm subarrayını tapmaqda bizə kömək edəcəkdir. Bu maxPoint sıfıra başlanacaq, çünki ən böyük cəmi tapmaq məcburiyyətindəyik və sonra başlanğıc və sonun dəyərini tələb olunan ən böyük cəmi alt serialın başlanğıc və bitmə göstəricisi olaraq çap edəcəyik. Bu yanaşmadan istifadə etsək, bir keçiddə ən böyük cəmi bitişik subarray tapa bilərik.
Ən böyük cəmi bitişik subarray problemi üçün kod
C ++ kodu
#include<bits/stdc++.h>
using namespace std;
// This Function prints the Largest Sum Contiguous Subarray
void getLargestSumContiguousSubarray(int arr[], int size)
{
// initialising variables with starting values
int maxValue = INT_MIN;
int maxPoint = 0;
int start =0, end = 0, s=0;
for (int i=0; i< size; i++ )
{
maxPoint += arr[i];
if (maxValue < maxPoint)
{
maxValue = maxPoint;
start = s;
end = i;
}
if (maxPoint < 0)
{
maxPoint = 0;
s = i + 1;
}
}
cout << "Sub-Array starting from "<< start<< " to "<< end<< " has a largest sum of " <<maxValue;
}
int main()
{
int arr[] = {1, -3, 4, -2, 5, -6, 2};
int n = sizeof(arr)/sizeof(arr[0]);
getLargestSumContiguousSubarray(arr, n);
return 0;
}
Sub-Array starting from 2 to 4 has a largest sum of 7
Java kodu
class LargestSumSubArray
{
// This Function prints Largest Sum Contiguous Subarray
public static void getLargestSumContiguousSubarray(int arr[], int size)
{
// initialising variables with starting values
int maxValue = Integer.MIN_VALUE;
int maxPoint = 0;
int start =0, end = 0, s=0;
for (int i=0; i< size; i++ )
{
maxPoint += arr[i];
if (maxValue < maxPoint)
{
maxValue = maxPoint;
start = s;
end = i;
}
if (maxPoint < 0)
{
maxPoint = 0;
s = i + 1;
}
}
System.out.println("Sub-Array starting from "+ start + " to "+ end + " has a largest sum of " + maxValue);
}
public static void main(String [] args)
{
int arr[] = {1, -3, 4, -2, 5, -6, 2};
int n = arr.length;
getLargestSumContiguousSubarray(arr, n);
}
}
Sub-Array starting from 2 to 4 has a largest sum of 7
Mürəkkəblik təhlili
Zamanın mürəkkəbliyi
N ölçülü giriş massivi üzərində tək bir döngə işlədirdiyimiz üçün. Beləliklə, ən böyük cəmi bitişik subarray üçün alqoritm xətti zaman mürəkkəbliyinə malikdir. O (n) hara "N" massivdəki elementlərin sayıdır.
Kosmik Mürəkkəblik
Tam ədədlərin saxlanması üçün tək bir 1D giriş massivindən istifadə etdik. Beləliklə, ən böyük cəmi bitişik subarray probleminə xətti bir kosmik mürəkkəblik vermək. O (n) hara "N" massivdəki elementlərin sayıdır.
