시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.
차례
문제 정책
합계가 2 인 2D 배열에서 최대 크기 부분 행렬을 찾습니다. 하위 행렬은 주어진 2D 배열 내부의 XNUMXD 배열에 불과합니다. 따라서 부호있는 정수로 구성된 행렬이 있으므로 부분 행렬의 합을 계산하고 합이 XNUMX 인 최대 크기의 행렬을 찾아야합니다.
예
Matrix = { 0 10 0
-20 10 100
10 -100 -10 }
9
설명 : 여기에 주어진 입력에는 가능한 답이 하나뿐입니다. 최대 크기 부분 행렬이 될 크기 9 (전체 행렬)의 부분 행렬을 선택할 수 있습니다. 그래서 우리는 답으로 전체 행렬을 선택할 것입니다.
Matrix = { 100
-100
100 }
2
설명 : 선택할 수있는 두 가지 옵션이 있습니다. 첫 번째와 두 번째 행 또는 두 번째와 세 번째 행을 선택합니다. 둘 다 합계 = 0이됩니다.
합계가 0 인 가장 큰 직사각형 부분 행렬을 찾는 방법
순진한 접근
간단한 배열을 활용하여이 문제를 해결할 수 있습니다. 다양한 셀에 대해 각각 XNUMX 개의 인덱스를 활용할 수 있습니다. 매트릭스. 이 인덱스 중 하나는 시작 행, 시작 열, 끝 행 및 끝 열에 대한 것입니다. 솔루션을 약간 개선하기 위해 2D 접두사 합계 접근 방식을 활용할 수 있습니다. 이 방법론은 간단한 솔루션을 약간 최적화 할 수 있지만 충분하지 않습니다.
효율적인 접근
따라서 우리는 문제에서했던 것과 유사한 접근 방식을 사용할 것입니다. 최대 합이있는 부분 행렬 찾기. 이제 두 개의 열을 수정합니다. 하나는 왼쪽 열용이고 다른 하나는 오른쪽 열용입니다. 0 번째 행에서 끝 행 (n-1 번째)까지 각 행에 대해이 열 사이의 합계를 저장하기 위해 임시 배열을 만듭니다. 이제 우리는 지금까지 만난 합계에 대한 인덱스를 저장하기 위해 맵 데이터 구조를 사용할 것입니다.
이 접근 방식을 이해하기 위해 다음과 같은 1D 배열을 고려할 수 있습니다. 접두사 합계, 접두사 합계 배열에서 두 개의 동일한 값을 찾으면. 즉, 요소의 합이 같을 때까지 두 개의 인덱스가 있습니다. 따라서 더 높은 지수의 합에서 더 작은 지수의 합을 빼면. 우리는 더 작은 지수와 더 높은 지수 사이의 합계를 얻습니다. 두 값이 모두 같았 기 때문입니다. 우리는 sum = 0으로 남습니다. 같은 일이 여기서 우리가하는 일입니다.
합계가 0 인 가장 큰 직사각형 부분 행렬을 찾기위한 코드
C ++ 코드
#include<bits/stdc++.h>
using namespace std;
int findMaximumSubMatrixWithZeroSum(vector<vector<int>> matrix, int n, int m){
// stores the prefixSum of rows
vector<vector<int>> prefixSum(n,vector<int>(m));
for(int i=0;i<n;i++){
for(int j=0;j<m;j++)
prefixSum[i][j] = matrix[i][j];
}
// calculation prefix sum for each row
for(int i=0;i<n;i++){
for(int j=1;j<m;j++)
prefixSum[i][j] += prefixSum[i][j-1];
}
// store indices of submatrix with maximum sum
int startCol = 0, endCol = 0, startRow = 0, endRow = 0;
int maxSize = 0;
// use a map to first store the row for sum if it was not present earlier
// else we calculate the result regarding the particular sum
for(int firstCol=0;firstCol<m;firstCol++){
for(int secondCol=firstCol;secondCol<m;secondCol++){
int tmp[n]; // stores the sum between two columns for each row
for(int row=0;row<n;row++)
tmp[row] = prefixSum[row][secondCol] - (firstCol>0 ? prefixSum[row][firstCol-1] : 0);
int curSum = 0;
unordered_map<int,int> rowSumMap;
rowSumMap[0] = -1;
for(int curRow=0;curRow<n;curRow++){
curSum += tmp[curRow];
if(rowSumMap.count(curSum)) {
int subMatrixSize = (secondCol - firstCol + 1)*(curRow - rowSumMap[curSum]);
if(subMatrixSize > maxSize){
maxSize = subMatrixSize;
startCol = firstCol;
endCol = secondCol;
startRow = rowSumMap[curSum] + 1;
endRow = curRow;
}
} else {
rowSumMap[curSum] = curRow;
}
}
}
}
if(maxSize == 0){
cout<<"There exists no sub-matrix with zero sum"<<endl;
return 0;
}
cout<<"Sub-matrix with zero Sum"<<endl;
for(int i=startRow;i<=endRow;i++){
for(int j=startCol;j<=endCol;j++){
cout<<matrix[i][j]<<" ";
}
cout<<endl;
}
return maxSize;
}
int main(){
int t;cin>>t;
while(t--){
int n,m;cin>>n>>m;
vector<vector<int>> matrix(n,vector<int>(m));
for(int i=0;i<n;i++){
for(int j=0;j<m;j++)
cin>>matrix[i][j];
}
int ans = findMaximumSubMatrixWithZeroSum(matrix, n, m);
if(ans != 0)
cout<<ans<<endl;
}
}
2 4 4 5 9 8 7 -9 -5 -4 -2 0 0 0 -9 1 8 8 4 4 4 5 9 8 7 -9 -5 -4 -2 0 0 0 9 1 8 8 4
Largest Sub-matrix with zero Sum 5 9 8 7 -9 -5 -4 -2 0 0 0 -9 12 Largest Sub-matrix with zero Sum 5 9 -9 -5 0 0 6
자바 코드
import java.util.*;
import java.lang.*;
import java.io.*;
class Main {
static int findMaximumSubMatrixWithZeroSum(int[][] matrix, int n, int m){
// stores the prefixSum of rows
int[][] prefixSum = new int[n][m];
for(int i=0;i<n;i++){
for(int j=0;j<m;j++)
prefixSum[i][j] = matrix[i][j];
}
// calculation prefix sum for each row
for(int i=0;i<n;i++){
for(int j=1;j<m;j++)
prefixSum[i][j] += prefixSum[i][j-1];
}
int startCol = 0, endCol = 0, startRow = 0, endRow = 0;
int maxSize = 0;
for(int firstCol=0;firstCol<m;firstCol++){
for(int secondCol=firstCol;secondCol<m;secondCol++){
int tmp[] = new int[n]; // stores the sum between two columns for each row
for(int row=0;row<n;row++)
tmp[row] = prefixSum[row][secondCol] - (firstCol>0 ? prefixSum[row][firstCol-1] : 0);
int curSum = 0;
HashMap<Integer, Integer> rowSumMap = new HashMap<Integer, Integer>();
rowSumMap.put(0,-1);
for(int curRow=0;curRow<n;curRow++){
curSum += tmp[curRow];
if(rowSumMap.containsKey(curSum)) {
int subMatrixSize = (secondCol - firstCol + 1)*(curRow - rowSumMap.get(curSum));
if(subMatrixSize > maxSize){
maxSize = subMatrixSize;
startCol = firstCol;
endCol = secondCol;
startRow = rowSumMap.get(curSum) + 1;
endRow = curRow;
}
} else {
rowSumMap.put(curSum,curRow);
}
}
}
}
if(maxSize == 0){
System.out.println("There exists no sub-matrix with zero sum");
return 0;
}
System.out.println("Largest Sub-matrix with zero Sum");
for(int i=startRow;i<=endRow;i++){
for(int j=startCol;j<=endCol;j++){
System.out.print(matrix[i][j]+" ");
}
System.out.println();
}
return maxSize;
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while(t-- > 0){
int n = sc.nextInt();
int m = sc.nextInt();
int matrix[][] = new int[n][m];
for(int i=0;i<n;i++){
for(int j=0;j<m;j++)
matrix[i][j] = sc.nextInt();
}
int ans = findMaximumSubMatrixWithZeroSum(matrix, n, m);
if(ans != 0)
System.out.println(ans);
}
}
}
2 4 4 5 9 8 7 -9 -5 -4 -2 0 0 0 -9 1 8 8 4 4 4 5 9 8 7 -9 -5 -4 -2 0 0 0 9 1 8 8 4
Largest Sub-matrix with zero Sum 5 9 8 7 -9 -5 -4 -2 0 0 0 -9 12 Largest Sub-matrix with zero Sum 5 9 -9 -5 0 0 6
복잡성 분석
시간 복잡성: O (N ^ 3)
3 개의 중첩 루프가 있기 때문에 다항식 시간 복잡도는 O (N ^ XNUMX)입니다. 하나의 루프는 접두사 Sum 및 맵 기술을 사용하여 제로 합계를 찾는 데 사용됩니다.
공간 복잡성: O (N ^ 2)
2D 접두사 Sum 배열을 만들었 기 때문에. 우리는 O (N ^ 2)의 공간 복잡도를 가지고 있습니다.
