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.
Sıralanmış verilmişdir array(artan sırada), dizinin 1-dən daha çox uzunluqlu 3 və ya daha çox alt sıraya bölünə biləcəyini yoxlayın, belə ki, hər alt ardıcıllıqla ardıcıl ədədlər olsun.
Mündəricat
Nümunələr
Input:
arr [] = {1,2,3,3,4,5}
Çıxış:
doğru
Explanation:
Dizini 2 ardıcıllığa bölmək olar,
alt1 [] = {1, 2, 3}
alt2 [] = {3, 4, 5}
Input:
arr [] = {Z1, 2, 3, 3, 4, 4, 5, 5}
Çıxış:
doğru
Explanation:
Ardıcıl ardıcıllıqlar,
alt1 [] = {1, 2, 3, 4, 5}
alt2 [] = {3, 4, 5}
Ardıcıl Sonralara Ayrılan Array üçün sadəlövh yanaşma
Verilən massivin arr [i] elementi üçün ya yeni bir altlıq meydana gətirə bilər və ya (arr [i] - 1) ilə bitən bir ardıcıllığa əlavə edilə bilər.
Həmişə daha yaxşıdır yox yeni bir ardıcıllıq meydana gətirdiyi üçün yeni bir ardıcıllıq yaratmaq üçdən az uzunluqlu bəzi alt ardıcıllıqla nəticələnə bilər. (Arr [i] - 1) ilə bitən bir ardıcıllıq yoxdursa, yeni bir alt ardıcıllıq yaratmaqdan başqa bir seçim yoxdur.
Mövcud elementi yerləşdirə bilən birdən çox ardıcıllıq varsa, hər zaman cari elementi ən az element olan ardıcıllığa əlavə edin, bu 3-dən az uzunluqlu altlıqların minimuma endirilməsini təmin edəcəkdir.
Alqoritm
- Massivin birinci elementi həmişə yeni bir altlıq meydana gətirir.
- Dizini 1-dən başlayaraq (0 əsaslı indeksləşdirmə) massivi keçin.
- Mövcud elementi yerləşdirə bilən bəzi ardıcıllığın olub olmadığını yoxlayın (arr [i] - 1) ilə bitən bir ardıcıllığa arr [i] elementi əlavə edilə bilər.
- Mövcud elementi yerləşdirə biləcək bir ardıcıllıq yoxdursa, yeni bir altlıq meydana gətirir.
- Başqası, mövcud elementi yerləşdirə biləcək minimum ölçülü altlığı seçin və cari elementi seçilmiş ardıcıllığa əlavə edin.
- Dizini keçdikdən sonra, uzunluğun 3-dən az bir ardıcıllığının olub olmadığını yoxlayın, bəli, saxta, əksinə qayıdın.
Ardıcıl Sonralara Ayrılan Array üçün JAVA Kodu
import java.util.ArrayList;
public class SplitTheArrayIntoConsecutievSubsequences {
private static boolean isPossible(int[] arr) {
// If the lenght of arr is less than 3, it is not possible to split the array
if (arr == null || arr.length < 3) {
return false;
}
int n = arr.length;
// List of subsequences
ArrayList<ArrayList<Integer>> al = new ArrayList<>();
// First element always forms a new subsequence
ArrayList<Integer> eles = new ArrayList<Integer>();
eles.add(arr[0]);
al.add(eles);
// Traverse the array starting from index 1
for (int i = 1; i < n; i++) {
// Required position of subsequence that can accommodate the current element
int pos = -1;
// Size of required subsequence
int size = -1;
// Check if there is some subsequence that can accommodate the current element
for (int j = 0; j < al.size(); j++) {
// A subsequence ending at (arr[i] - 1) can accommodate the element arr[i]
if (al.get(j).get(al.get(j).size() - 1) + 1 == arr[i]) {
if (pos == -1) {
pos = j;
size = al.get(j).size();
} else {
// Select the subsequence with minimum size
if (al.get(j).size() < size) {
pos = j;
size = al.get(j).size();
}
}
}
}
// If there is no subsequence that can accommodate the current element
// form a new subsequence
if (pos == -1) {
ArrayList<Integer> newAL = new ArrayList<>();
newAL.add(arr[i]);
al.add(newAL);
} else {
// else add it to the required subsequence
al.get(pos).add(arr[i]);
}
}
for (int i = 0; i < al.size(); i++) {
// if there is some subsequence of length less than 3, return false
if (al.get(i).size() < 3) {
return false;
}
}
// No subsequence of length less than 3, return true
return true;
}
public static void main(String[] args) {
// Example 1
int arr1[] = new int[]{1, 2, 3, 3, 4, 5};
System.out.println(isPossible(arr1));
// Example 2
int arr2[] = new int[]{1, 2, 3, 3, 4, 4, 5, 5};
System.out.println(isPossible(arr2));
// Example 3
int arr3[] = new int[]{1, 2, 3, 4, 4, 5};
System.out.println(isPossible(arr3));
}
}
true true false
Ardıcıl Növbələrə Artırılan Array üçün C ++ Kodu
#include<bits/stdc++.h>
using namespace std;
bool isPossible(int *arr, int n) {
if (n < 3) {
return false;
}
// List of subsequences
vector<vector<int>> v;
// First element always forms a new subsequence
vector<int> eles;
eles.push_back(arr[0]);
v.push_back(eles);
// Traverse the array starting from index 1
for (int i = 1; i < n; i++) {
// Required position of subsequence that can accommodate the current element
int pos = -1;
// Size of required subsequence
int size = -1;
// Check if there is some subsequence that can accommodate the current element
for (int j = 0; j < v.size(); j++) {
// A subsequence ending at (arr[i] - 1) can accommodate the element arr[i]
if (v[j][v[j].size() - 1] + 1 == arr[i]) {
if (pos == -1) {
pos = j;
size = v[j].size();
} else {
// Select the subsequence with minimum size
if (v[j].size() < size) {
size = v[j].size();
pos = j;
}
}
}
}
// If there is no subsequence that can accommodate the current element
// form a new subsequence
if (pos == -1) {
vector<int> newV;
newV.push_back(arr[i]);
v.push_back(newV);
} else {
v[pos].push_back(arr[i]);
}
}
for (int i = 0; i < v.size(); i++) {
if (v[i].size() < 3) {
return false;
}
}
return true;
}
int main() {
// Example 1
int arr1[] = {1, 2, 3, 3, 4, 5};
if(isPossible(arr1, sizeof(arr1) / sizeof(arr1[0]))) {
cout<<"true"<<endl;
} else {
cout<<"false"<<endl;
}
// Example 2
int arr2[] = {1, 2, 3, 3, 4, 4, 5, 5};
if (isPossible(arr2, sizeof(arr2) / sizeof(arr2[0]))) {
cout<<"true"<<endl;
} else {
cout<<"false"<<endl;
}
// Example 3
int arr3[] = {1, 2, 3, 4, 4, 5};
if (isPossible(arr3, sizeof(arr3) / sizeof(arr3[0]))) {
cout<<"true"<<endl;
} else {
cout<<"false"<<endl;
}
return 0;
}
true true false
Mürəkkəblik təhlili
Zaman Mürəkkəbliyi = O (n)2)
Kosmik Mürəkkəblik = O (n)
Ardıcıl Nəticələrə Split Array üçün optimal yanaşma
Arr [i] elementi üçün ya yeni bir ardıcıllıq yarada bilər və ya (arr [i] - 1) ilə bitən başqa bir ardıcıllığa əlavə edilə bilər, arr [i] -i yerləşdirə bilən birdən çox ardıcıllıq varsa, əlavə edin minimum uzunluğun ardıcıllığına.
Yalnız üç növ ardıcıllıq uzunluğu vacibdir, yəni p 1, c2, p3, c1, p1 və c2 kimi göstərilən uzunluq 2, uzunluq 3 və uzunluq 3-dən çox olan ardıcıllıqlar vacibdir, burada p əvvəlki və c cari deməkdir.
Hər bir rəqəm üçün əvvəlcə sıra içərisindəki meydana çıxma sayını sayın, 1 və 2 uzunluğundakı bütün alt ardıcıllıqlara yayıla biləcəyini yoxlayın, bacarmazsa dərhal yalan qaytarın, çünki cari sayı 1 uzunluqlu altlıqları uzada bilmirsə 2, sıra sıralanarkən heç bir nömrə olmaz. Beləliklə, sonunda 1 və ya 2 uzunluğunda bəzi ardıcıllıqlar qalacaq.
Başqa uzunluqdakı bütün alt ardıcıllıqlar 1 uzunluqdakı ardıcıllara, 2 uzunluq 2 uzunluğa çevrilir və qalan elementlər 3 və ya daha çox uzunluqdakı altlıqlara əlavə olunur, əgər hələ də bəzi elementlər paylanmırsa, onlar 3 uzunluğunun altlıqlarına kömək edirlər. yalnız 1 və ya daha çox uzunluğa töhfə verən elementlər yeni uzunluq 3 ardıcıllığına əlavə edir.
Sonda 1 uzunluq və 2 uzunluq ardıcıllığı yoxdursa, geriyə qayıdır, əks halda yalan qaytarır.
JAVA Kodu
public class SplitArrayIntoConsecutiveSubsequences {
private static boolean isPossible(int[] arr) {
int n = arr.length;
if (n < 3) {
return false;
}
int p1 = 0, p2 = 0, p3 = 0;
int c1 = 0, c2 = 0, c3 = 0;
int i = 0;
// prev denotes previous element
// curr denotes current element
int prev = 0, curr = 0;
// Traverse the array
while (i < n) {
// Current becomes previous
p1 = c1;
p2 = c2;
p3 = c3;
prev = curr;
curr = arr[i];
int count = 0;
// Count the frequency of current element
while (i < n && arr[i] == curr) {
i++;
count++;
}
if (prev + 1 == curr) {
// if element cannot be spread across subsequences of length 1 and 2
if (count < p1 + p2) {
// return false immediately
return false;
}
// Update c1, c2, c3 as described
c1 = Math.max(0, count - (p1 + p2 + p3));
c2 = p1;
c3 = p2 + Math.min(p3, count - (p1 + p2));
} else {
// this element cannot be spread across any subsequence
if (p1 != 0 || p2 != 0) {
// if there is any subsequence of length 1 or 2
// return false immediately
return false;
}
// Update c1, c2, c3 as described
c1 = count;
c2 = 0;
c3 = 0;
}
}
// if there are no length 1 and length 2 subsequences return true, else return false
return (c1 == 0 && c2 == 0);
}
public static void main(String[] args) {
// Example 1
int arr1[] = new int[]{1, 2, 3, 3, 4, 5};
System.out.println(isPossible(arr1));
// Example 2
int arr2[] = new int[]{1, 2, 3, 3, 4, 4, 5, 5};
System.out.println(isPossible(arr2));
// Example 3
int arr3[] = new int[]{1, 2, 3, 4, 4, 5};
System.out.println(isPossible(arr3));
}
}
true true false
C ++ kodu
#include<bits/stdc++.h>
using namespace std;
bool isPossible(int *arr, int n) {
if (n < 3) {
return false;
}
int p1 = 0, p2 = 0, p3 = 0;
int c1 = 0, c2 = 0, c3 = 0;
int i = 0;
// prev denotes previous element
// curr denotes current element
int prev = 0, curr = 0;
// Traverse the array
while (i < n) {
// Current becomes previous
p1 = c1;
p2 = c2;
p3 = c3;
prev = curr;
curr = arr[i];
int count = 0;
// Count the frequency of current element
while (i < n && arr[i] == curr) {
i++;
count++;
}
if (prev + 1 == curr) {
// if element cannot be spread across subsequences of length 1 and 2
if (count < p1 + p2) {
// return false immediately
return false;
}
// Update c1, c2, c3 as described
c1 = std::max(0, count - (p1 + p2 + p3));
c2 = p1;
c3 = p2 + std::min(p3, count - (p1 + p2));
} else {
// this element cannot be spread across any subsequence
if (p1 != 0 || p2 != 0) {
// if there is any subsequence of length 1 or 2
// return false immediately
return false;
}
// Update c1, c2, c3 as described
c1 = count;
c2 = 0;
c3 = 0;
}
}
// if there are no length 1 and length 2 subsequences return true, else return false
return (c1 == 0 && c2 == 0);
}
int main() {
// Example 1
int arr1[] = {1, 2, 3, 3, 4, 5};
if(isPossible(arr1, sizeof(arr1) / sizeof(arr1[0]))) {
cout<<"true"<<endl;
} else {
cout<<"false"<<endl;
}
// Example 2
int arr2[] = {1, 2, 3, 3, 4, 4, 5, 5};
if (isPossible(arr2, sizeof(arr2) / sizeof(arr2[0]))) {
cout<<"true"<<endl;
} else {
cout<<"false"<<endl;
}
// Example 3
int arr3[] = {1, 2, 3, 4, 4, 5};
if (isPossible(arr3, sizeof(arr3) / sizeof(arr3[0]))) {
cout<<"true"<<endl;
} else {
cout<<"false"<<endl;
}
return 0;
}
true true false
Mürəkkəblik təhlili
Zaman Mürəkkəbliyi = O (n)
Kosmik Mürəkkəblik = O (1)
