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.
Verilmiş bir array n ölçülü bir []. Vəziyyətdəki hər bir element üçün mən L [i] və R [i] tapıram, burada - L [i] = L-ə ən yaxın göstərici olduğu L [ən yaxın göstərici]> L [i] və ən yaxın göstərici <i. R [i] = i-yə ən yaxın göstərici, burada R [ən yaxın göstərici]> R [i] və ən yaxın göstərici> i. L [i] və ya R [i] üçün belə bir indeks yoxdursa, onu 0-da yeniləyin. L və R-nin məhsulunun maksimumunu tapın - LR Məhsulu [i] = L [i] * R [i].
Mündəricat
misal
Giriş: a [] = {5, 4, 3, 4, 5}
Çıxış: 8
Giriş: a [] = {1, 1, 1, 1, 0, 1, 1, 1, 1, 1}
Çıxış: 24
Alqoritm
- N ölçülü bir [] massivi başladın.
- Ən yaxın elementin sol və sağ indeksini saxlamaq üçün iki başqa massivi işə salın.
- Bir yaradın qalaq. N-1-dən 0-a keçin və yığın boş deyilsə və [cari indeks] [stack.top () - 1]) -dən böyükdürsə, stack.top () - 1 indeksindəki sol dizini cari indeks olaraq yeniləyin. + 1. Üstü açın.
- Hazırkı indeks + 1-i yığına daxil edin.
- Sağ sıra üçün bir yığın yaradın. 0-dan n-1-ə keçin və yığın boş deyilsə və [cari indeks] [stack.top () - 1]) -dən böyük olarsa, indiki stack.top () - 1 indeksindəki sağ cərgəni yeniləyin. +1. Üstü açın.
- Hazırkı indeks + 1-i yığına daxil edin.
- Cavabları saxlamaq üçün dəyişən yaradın və onu -1 olaraq başladın. 0-dan n-1-ə keçin və cavab dəyişənini maksimum cavab dəyişəni və sol dizidəki və sağ cərgədəki indeksdəki dəyərlərin məhsulu kimi yeniləyin.
- Cavab dəyişənini qaytarın.
C ++ proqramı, soldan və sağdan yuxarıdakı indekslərin maksimum məhsulunu tapmaq üçün
#include <bits/stdc++.h>
using namespace std;
#define MAX 1000
vector<int> nextGreaterInLeft(int a[], int n){
vector<int> left_index(MAX, 0);
stack<int> s;
for(int i = n - 1; i >= 0; i--){
while(!s.empty() && a[i] > a[s.top() - 1]){
int r = s.top();
s.pop();
left_index[r - 1] = i + 1;
}
s.push(i + 1);
}
return left_index;
}
vector<int> nextGreaterInRight(int a[], int n){
vector<int> right_index(MAX, 0);
stack<int> s;
for(int i = 0; i < n; ++i){
while(!s.empty() && a[i] > a[s.top() - 1]){
int r = s.top();
s.pop();
right_index[r - 1] = i + 1;
}
s.push(i + 1);
}
return right_index;
}
int Product(int a[], int n){
vector<int> left = nextGreaterInLeft(a, n);
vector<int> right = nextGreaterInRight(a, n);
int ans = -1;
for(int i = 1; i <= n; i++){
ans = max(ans, left[i] * right[i]);
}
return ans;
}
int main(){
int a[] = {5, 4, 3, 4, 5};
int n = sizeof(a)/sizeof(a[1]);
cout<<Product(a, n);
return 0;
}
8
Java proqramı, soldan və sağdan yuxarıdakı indekslərin maksimum məhsulunu tapmaq üçün
import java.io.*;
import java.util.*;
class LRProduct{
static int MAX = 1000;
static int[] nextGreaterInLeft(int []a, int n){
int []left_index = new int[MAX];
Stack<Integer> s = new Stack<Integer>();
for(int i = n-1; i >= 0; i--){
while (s.size() != 0 && a[i] > a[s.peek() - 1]){
int r = s.peek();
s.pop();
left_index[r - 1] = i + 1;
}
s.push(i + 1);
}
return left_index;
}
static int[] nextGreaterInRight(int []a, int n){
int []right_index = new int[MAX];
Stack<Integer> s = new Stack<Integer>();
for(int i = 0; i < n; ++i){
while (s.size() != 0 && a[i] > a[s.peek() - 1]){
int r = s.peek();
s.pop();
right_index[r - 1] = i + 1;
}
s.push(i + 1);
}
return right_index;
}
static int Product(int []a, int n){
int []left = nextGreaterInLeft(a, n);
int []right = nextGreaterInRight(a, n);
int ans = -1;
for(int i = 1; i <= n; i++){
ans = Math.max(ans, left[i] * right[i]);
}
return ans;
}
public static void main(String args[]){
int []a = new int[]{5, 4, 3, 4, 5};
int n = a.length;
System.out.print(Product(a, n));
}
}
8
Solda və sağda daha böyük indekslərin məhsulunu tapmaq üçün mürəkkəblik analizi
Zamanın mürəkkəbliyi: O (n * n), burada n - a [] massivindəki elementlərin sayı.
Köməkçi məkan: O (n), çünki n əlavə yer istifadə etdik.
