시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.
차례
문제 정책
“k 크기의 모든 하위 배열의 최소 및 최대 요소의 합”문제는 양의 정수와 음의 정수를 포함하는 배열이 주어지고 크기가 k 인 모든 하위 배열의 최소 및 최대 요소의 합을 찾습니다.
예
arr[] = {5, 9, 8, 3, -4, 2, 1, -5}
k = 4
17
설명
크기 4의 모든 하위 배열은 다음과 같습니다.
{5, 9, 8, 3} : 최소 + 최대 = 9 + 3 = 12
{9, 8, 3, -4} : 최소 + 최대 = -4 + 9 = 5
{8, 3, -4, 2} : 최소 + 최대 = -4 + 8 = 4
{3, -4, 2, 1} : 최소 + 최대 = -4 + 3 = -1
{-4, 2, 1, -5} : 최소 + 최대 = -5 + 2 = -3
arr[] = {1, -1, 2, -2, 3, -3}
k = 2
2
설명
크기 2의 모든 하위 배열은 다음과 같습니다.
{1, -1} : 최소 + 최대 = -1 + 1 = 0
{-1, 2} : 최소 + 최대 = -1 + 2 = 1
{2, -2} : 최소 + 최대 = -2 + 2 = 0
{-2, 3} : 최소 + 최대 = -2 + 3 = 1
{3, -3} : 최소 + 최대 = -3 + 3 = 0
접근
순진한 접근
크기 k의 모든 하위 배열을 가로 질러 최소 및 최대 요소를 찾고 합계를 인쇄합니다.
- 변수 합계를 0으로 초기화합니다.
- i에 대해 루프를 실행하면 0에서 (n – k)까지입니다. 여기서 n은 주어진 요소의 총 수입니다. 정렬. 각각의 i는 크기가 k 인 하위 배열의 시작점 역할을합니다.
- j = i ~ (i + k) (포함되지 않음)에 대해 중첩 루프를 실행합니다.이 루프는 크기 k의 하위 배열을 나타냅니다. 이 하위 배열을 가로 질러 최소 및 최대 요소를 찾아 각각 최소 및 최대 요소로 설정합니다.
- 합계에 (최소 + 최대)를 더합니다.
- 순회가 끝나면 합계를 반환합니다.
여기서 n은 주어진 배열의 총 요소 수입니다.
크기가 k 인 모든 하위 배열의 최소 및 최대 요소의 합계를 찾는 Java 코드
class SumOfMinimumAndMaximumElementsOfAllSubarraysOfSizeK {
private static int sumOfMinMax(int[] arr, int k) {
int n = arr.length;
// initialize sum as 0
int sum = 0;
// Traverse all the subarray of size k one by one
for (int i = 0; i <= n - k; i++) {
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
// traverse the current subarray and find the min and max
for (int j = i; j < i + k; j++) {
min = Math.min(min, arr[j]);
max = Math.max(max, arr[j]);
}
// add (min + max) to the sum
sum += (min + max);
}
return sum;
}
public static void main(String[] args) {
// Example 1
int arr1[] = new int[]{5, 9, 8, 3, -4, 2, 1, -5};
int k1 = 4;
System.out.println(sumOfMinMax(arr1, k1));
// Example 2
int arr2[] = new int[]{1, -1, 2, -2, 3, -3};
int k2 = 2;
System.out.println(sumOfMinMax(arr2, k2));
}
}
17 2
크기가 k 인 모든 하위 배열의 최소 및 최대 요소의 합계를 찾는 C ++ 코드
#include<bits/stdc++.h>
using namespace std;
int sumOfMinMax(int *arr, int k, int n) {
// initialize sum as 0
int sum = 0;
// Traverse all the subarray of size k one by one
for (int i = 0; i <= (n - k); i++) {
int min = INT_MAX;
int max = INT_MIN;
// traverse the current subarray and find the min and max
for (int j = i; j < i + k; j++) {
min = std::min(min, arr[j]);
max = std::max(max, arr[j]);
}
// add (min + max) to the sum
sum += (min + max);
}
return sum;
}
int main() {
// Example 1
int arr1[] = {5, 9, 8, 3, -4, 2, 1, -5};
int k1 = 4;
cout<<sumOfMinMax(arr1, k1, sizeof(arr1) / sizeof(arr1[0]))<<endl;
// Example 2
int arr2[] = {1, -1, 2, -2, 3, -3};
int k2 = 2;
cout<<sumOfMinMax(arr2, k2, sizeof(arr2) / sizeof(arr2[0]))<<endl;
return 0;
}
17 2
복잡성 분석
시간 복잡성 = O (n * k)
공간 복잡성 = O (1)
여기서 시간 복잡도는 각 하위 배열의 문제를 독립적으로 해결하기 때문에 다항식입니다. 최대 및 최소에 대한 두 개의 변수 만 저장했기 때문에 필요한 공간은 일정합니다.
최적의 접근 방식
두 개 만들기 데케 d1 및 d2, 두 deques 모두 하위 배열의 최소 및 최대에 기여할 수있는 요소의 인덱스를 저장합니다. Deque d1은 앞쪽에서 뒤쪽으로 내림차순으로 요소를 포함하고 d2는 앞쪽에서 뒤쪽으로 오름차순으로 요소를 포함합니다.
- 변수 합계를 0으로 초기화합니다. 두 개의 deques d1과 d2를 만듭니다. 크기 k의 첫 번째 하위 배열을 고려하십시오.
- 크기가 k 인 하위 배열의 현재 요소가 d1의 인덱스 뒷면에있는 요소보다 크거나 같지만 Deque d1의 뒷면 요소를 제거합니다.
- 크기가 k 인 하위 배열의 현재 요소가 d2의 인덱스 후면에있는 요소보다 작거나 같지만 Deque d2의 후면 요소를 제거합니다.
- 두 deques 뒤에 현재 색인을 추가합니다.
- deque d1의 후면은 서브 어레이의 최대 요소 인덱스이고 deque d2의 후면은 서브 어레이의 최소 요소 인덱스입니다. 최대 및 최소 요소의 합계를 변수 합계에 더합니다.
- 크기 k의 나머지 하위 배열을 횡단하고 2 ~ 5 단계를 반복합니다. 나머지 모든 하위 배열에 대해 슬라이딩 윈도우 기술 이전 하위 배열에없는 요소 만 처리합니다.
- 모든 하위 배열을 탐색 한 후 합계를 반환합니다.
크기가 k 인 모든 하위 배열의 최소 및 최대 요소의 합계를 찾는 Java 코드
import java.util.Deque;
import java.util.LinkedList;
class SumOfMinimumAndMaximumElementsOfAllSubarraysOfSizeK {
private static int sumOfMinMax(int[] arr, int k) {
int n = arr.length;
// initialize sum as 0
int sum = 0;
// create 2 deques d1 and d2
Deque<Integer> d1 = new LinkedList<>();
Deque<Integer> d2 = new LinkedList<>();
// first subarray
for (int i = 0; i < k; i++) {
// only push the elements that may contribute to maximum
while (!d1.isEmpty() && arr[d1.peekLast()] <= arr[i])
d1.removeLast();
// only push the elements that may contribute to minimum
while (!d2.isEmpty() && arr[d2.peekLast()] >= arr[i])
d2.removeLast();
// add the current elememt's index
d1.addLast(i);
d2.addLast(i);
}
// sum of min and max for first subarray
sum += arr[d2.peekFirst()] + arr[d1.peekFirst()];
// traverse the remaining subarray
for (int i = k; i < n; i++) {
// remove the previous element (sliding window technique)
while (!d2.isEmpty() && d2.peekFirst() <= i - k)
d2.removeFirst();
while (!d1.isEmpty() && d1.peekFirst() <= i - k)
d1.removeFirst();
// only push the elements that may contribute to maximum
while (!d1.isEmpty() && arr[d1.peekLast()] <= arr[i])
d1.removeLast();
// only push the elements that may contribute to minimum
while (!d2.isEmpty() && arr[d2.peekLast()] >= arr[i])
d2.removeLast();
// add the current element's index
d1.addLast(i);
d2.addLast(i);
// sum of min and max for current subarray
sum += arr[d2.peekFirst()] + arr[d1.peekFirst()];
}
// return total sum
return sum;
}
public static void main(String[] args) {
// Example 1
int arr1[] = new int[]{5, 9, 8, 3, -4, 2, 1, -5};
int k1 = 4;
System.out.println(sumOfMinMax(arr1, k1));
// Example 2
int arr2[] = new int[]{1, -1, 2, -2, 3, -3};
int k2 = 2;
System.out.println(sumOfMinMax(arr2, k2));
}
}
17 2
크기가 k 인 모든 하위 배열의 최소 및 최대 요소의 합계를 찾는 C ++ 코드
#include<bits/stdc++.h>
using namespace std;
int sumOfMinMax(int *arr, int k, int n) {
// initialize sum as 0
int sum = 0;
// create 2 deques d1 and d2
deque<int> d1;
deque<int> d2;
// first subarray
for (int i = 0; i < k; i++) {
// only push the elements that may contribute to maximum
while (!d1.empty() && arr[d1.back()] <= arr[i]) {
d1.pop_back();
}
// only push the elements that may contribute to minimum
while (!d2.empty() && arr[d2.back()] >= arr[i]) {
d2.pop_back();
}
// add the current element's index
d1.push_back(i);
d2.push_back(i);
}
// sum of min and max for first subarray
sum += (arr[d2.front()] + arr[d1.front()]);
// traverse the remaining subarray
for (int i = k; i < n; i++) {
// remove the previous element (sliding window technique)
while (!d1.empty() && d1.front() <= (i -k)) {
d1.pop_front();
}
while (!d2.empty() && d2.front() <= (i - k)) {
d2.pop_front();
}
// only push the elements that may contribute to maximum
while (!d1.empty() && arr[d1.back()] <= arr[i]) {
d1.pop_back();
}
// only push the elements that may contribute to minimum
while (!d2.empty() && arr[d2.back()] >= arr[i]) {
d2.pop_back();
}
// add the current element's index
d1.push_back(i);
d2.push_back(i);
// sum of min and max for current subarray
sum += (arr[d1.front()] + arr[d2.front()]);
}
// return total sum
return sum;
}
int main() {
// Example 1
int arr1[] = {5, 9, 8, 3, -4, 2, 1, -5};
int k1 = 4;
cout<<sumOfMinMax(arr1, k1, sizeof(arr1) / sizeof(arr1[0]))<<endl;
// Example 2
int arr2[] = {1, -1, 2, -2, 3, -3};
int k2 = 2;
cout<<sumOfMinMax(arr2, k2, sizeof(arr2) / sizeof(arr2[0]))<<endl;
return 0;
}
17 2
복잡성 분석
시간 복잡성 = O (N)
공간 복잡성 = O (N)
여기서 n은 주어진 배열의 총 요소 수입니다.
감소 및 증가 순서로 숫자를 나타내는 큐를 사용 했으므로 요소를 한 번 저장합니다. 따라서 알고리즘은 선형 시간이 걸리므로 필요한 공간도 선형입니다.
