시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.
2D가 주어지면 매트릭스 크기 (mxn)의 경우 행렬이 Toeplitz인지 여부를 확인합니다. Toeplitz 행렬은 왼쪽 상단에서 왼쪽 하단까지 동일한 대각선에있는 요소가 모든 대각선에 대해 동일한 행렬입니다.
차례
예
입력
1 2 3 4
5 1 2 3
9 5 1 2
산출
참된
설명
대각선은 [ "1", "1", "1"], [ "2", "2", "2"], [ "3", "3"], [ "4"], [ "5 ”,“5”], [“9”]
모든 대각선에서 모든 요소는 동일하므로 행렬은 Toeplitz입니다.
입력
1 2
2 2
산출
그릇된
설명
Dialgonals는 [ "1", "2"], [ "2"], [ "2"]입니다.
대각선 [ "1", "2"]에는 다른 요소가 있으므로 행렬은 토플 리츠가 아닙니다.
Check Toeplitz Matrix를위한 알고리즘
모든 대각선을 하나씩 횡단하고 모든 요소가 대각선에 대해 동일하지 않으면 행렬은 Toeplitz가 아니며 그렇지 않으면 Toeplitz입니다.
대각선은 아래 이미지와 같이 횡단해야합니다.
대각선의 시작점은 위의 예에서 [0, 0], [0, 1], [0, 2], [0, 3], [1, 0], [2, 0]입니다.
시작점에서 열 또는 행이 0이면 시작점에서 시작하여 행과 열의 값을 1 씩 증가시켜 모든 대각선을 횡단합니다.
Toeplitz 매트릭스에 대한 설명
예를 고려하십시오.
1 2 3 4
5 1 2 3
9 5 1 2
모든 대각선을 XNUMX 번째 행의 시작점.
대각선 1 : 시작점 = (0, 0)
요소 = {1, 1, 1}
모든 요소가 동일하므로 계속하십시오.
대각선 2 : 시작점 = (0, 1)
요소 = {2, 2, 2}
모든 요소가 동일하므로 계속하십시오.
대각선 3 : 시작점 = (0, 2)
요소 = {3, 3, 3}
모든 요소가 동일하므로 계속하십시오.
대각선 4 : 시작점 = (0, 3)
요소 = {4}
모든 요소가 동일하므로 계속하십시오.
모든 대각선을 XNUMX 번째 열의 시작점.
대각선 1 : 시작점 = (0, 0)
요소 = {1, 1, 1}
모든 요소가 동일하므로 계속하십시오.
대각선 2 : 시작점 = (1, 0)
요소 = {5, 5}
모든 요소가 동일하므로 계속하십시오.
대각선 3 : 시작점 = (2, 0)
요소 = {9}
모든 요소가 동일하므로 계속하십시오.
모든 대각선에는 동일한 요소가 있으므로 주어진 행렬은 Toeplitz입니다.
Toeplitz Matrix에 대한 JAVA 코드
public class ToeplitzMatrix {
private static boolean isToeplitz(int[][] matrix) {
boolean ans = true;
int n = matrix.length;
int m = matrix[0].length;
// First row diagonals
for (int i = 0; i < m; i++) {
int x = 0, y = i;
int curr = matrix[x][y];
x++; y++;
while (x < n && y < m) {
// If any element is not same, this can't be a toeplitz matrix
if (matrix[x][y] != curr) {
ans = false;
break;
}
// Increment row and column by 1
x++; y++;
}
if (!ans)
break;
}
// First column diagonals
for (int i = 1; i < n; i++) {
int x = i, y = 0;
int curr = matrix[x][y];
x++; y++;
while (x < n && y < m) {
// If any element is not same, this can't be a toeplitz matrix
if (matrix[x][y] != curr) {
ans = false;
break;
}
// Increment row and column by 1
x++; y++;
}
if (!ans)
break;
}
return ans;
}
public static void main(String[] args) {
// Example 1
int[][] matrix = new int[][] {
{1, 2, 3, 4},
{5, 1, 2, 3},
{9, 5, 1, 2}};
System.out.println(isToeplitz(matrix));
// Example 2
int[][] matrix2 = new int[][] {
{1, 2},
{2, 2}
};
System.out.println(isToeplitz(matrix2));
}
}
Toeplitz 매트릭스 용 C ++ 코드
#include<bits/stdc++.h>
using namespace std;
int matrix[4][4];
bool isToeplitz(int n, int m) {
bool ans = true;
// First row diagonals
for (int i = 0; i < m; i++) {
int x = 0, y = i;
int curr = matrix[x][y];
x++; y++;
while (x < n && y < m) {
// If any element is not same, this can't be a toeplitz matrix
if (matrix[x][y] != curr) {
ans = false;
break;
}
// Increment row and column by 1
x++; y++;
}
if (!ans)
break;
}
// First column diagonals
for (int i = 1; i < n; i++) {
int x = i, y = 0;
int curr = matrix[x][y];
x++; y++;
while (x < n && y < m) {
// If any element is not same, this can't be a toeplitz matrix
if (matrix[x][y] != curr) {
ans = false;
break;
}
// Increment row and column by 1
x++; y++;
}
if (!ans)
break;
}
return ans;
}
int main() {
// Example 1
matrix[0][0] = 1;
matrix[0][1] = 2;
matrix[0][2] = 3;
matrix[0][3] = 4;
matrix[1][0] = 5;
matrix[1][1] = 1;
matrix[1][2] = 2;
matrix[1][3] = 3;
matrix[2][0] = 9;
matrix[2][1] = 5;
matrix[2][2] = 1;
matrix[2][3] = 2;
if (isToeplitz(3, 4)) {
cout<<"true"<<endl;
} else {
cout<<"false"<<endl;
}
// Example 2
matrix[0][0] = 1;
matrix[0][1] = 2;
matrix[1][0] = 2;
matrix[1][1] = 2;
if (isToeplitz(2, 2)) {
cout<<"true"<<endl;
} else {
cout<<"false"<<endl;
}
return 0;
}
true false
복잡성 분석
시간 복잡성 = O (m * n)
공간 복잡성 = O (1)
여기서 m과 n은 2D 행렬의 행과 열 수입니다.
