모든 오렌지를 썩는 데 필요한 최소 시간


자주 묻는 질문 어도비 벽돌 아마존 블룸버그 게시물에서 Microsoft
배열 폭 우선 검색 매트릭스조회수 81

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

문제 정책

“모든 오렌지를 썩는 데 필요한 최소 시간”이라는 문제는 2D 배열, 모든 셀에는 세 가지 가능한 값 0, 1 또는 2 중 하나가 있습니다.
0은 빈 셀을 의미합니다.
1은 신선한 오렌지를 의미합니다.
2는 썩은 오렌지를 의미합니다.
썩은 오렌지가 1 시간 단위로 인접한 신선한 오렌지를 썩을 수 있다면, 모든 오렌지를 썩는 데 걸리는 시간을 찾고, 모든 오렌지를 썩는 것이 불가능하다면 -1을 인쇄하십시오.

{
{0, 1, 1}
{2, 1, 2}
{1, 0, 1}
}
2
{
{0, 1, 0}
{2, 0, 2}
{1, 1, 1}
{1, 1, 1}
}
-1

모든 오렌지를 썩는 데 필요한 최소 시간을 찾는 알고리즘

모든 썩은 오렌지는 시작점이며 인접한 신선한 오렌지를 1 단위 시간에 썩게합니다. 모든 오렌지를 썩는 데 필요한 총 시간을 찾으려면 다음을 수행 할 수 있습니다. 폭 우선 검색(BFS) 모든 썩은 오렌지를 BFS의 시작점으로 가정하여.

  1. 만들기 변발 즉, 큐는 (row, col) 형식의 데이터를 저장해야합니다. 가변 시간을 0으로 초기화합니다.
  2. 주어진 행렬을 가로 질러 모든 썩은 오렌지의 좌표를 대기열에 추가합니다.
  3. 대기열이 비어 있지 않은 동안 4 단계를 반복합니다.
  4. 큐의 크기로 변수 크기를 초기화하십시오. i가 0과 크기 (포함되지 않음) 인 경우 루프를 실행하고 반복 할 때마다 큐에서 요소를 팝업합니다. 인접한면 (왼쪽, 오른쪽, 위쪽 및 아래쪽)에 신선한 오렌지가 있으면 해당 오렌지의 좌표를 대기열로 밀어 넣고 해당 오렌지를 썩은 것으로 표시합니다. 신선한 오렌지가 있다면 시간을 1 단위로 늘립니다.
  5. 이제 매트릭스에 여전히 신선한 오렌지가 있는지 확인하십시오. 그렇다면 모든 오렌지가 썩을 수 없으므로 -1을 반환하고 그렇지 않으면 시간을 반환하십시오.

설명

예를 고려하십시오.
{
{0, 1, 1}
{2, 1, 2}
{1, 0, 1}
}

모든 오렌지를 썩는 데 필요한 최소 시간

모든 오렌지는 시간 = 2에 썩습니다.

암호

모든 오렌지를 썩는 데 필요한 최소 시간을 찾는 Java 코드

import java.util.LinkedList;
import java.util.Queue;

class MinimumTimeRequiredToRotAllOranges {
    private static int minTimeToRot(int[][] mat) {
        int n = mat.length;
        int m = mat[0].length;

        // create a queue to store coordinates
        Queue<Coordinate> queue = new LinkedList<>();
        // initialize a variable time as 0
        int time = 0;

        // Add all the rotten oranges coordinates to the queue
        // these acts as the starting point of the BFS
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (mat[i][j] == 2) {
                    queue.add(new Coordinate(i, j));
                }
            }
        }

        while (!queue.isEmpty()) {
            // initialise size as size of queue
            int size = queue.size();
            // boolean variable representing whether or not an orange
            // is rotten in this time unit
            boolean isSomeFreshRotten = false;
            for (int i = 0; i < size; i++) {
                // remove an element from the queue
                Coordinate curr = queue.poll();

                // generate the coordinates of adjacent cells
                // if the generated coordinates are valid and there is a fresh orange
                // add the generated coordinates to the queue and mark that orange as rotten

                // left adjacent
                int leftRow = curr.row - 1;
                int leftCol = curr.col;
                if ((leftRow >= 0 && leftRow < n) && (leftCol >= 0 && leftCol < m)) {
                    if (mat[leftRow][leftCol] == 1) {
                        queue.add(new Coordinate(leftRow, leftCol));
                        mat[leftRow][leftCol] = 2;
                        isSomeFreshRotten = true;
                    }
                }

                // right adjacent
                int rightRow = curr.row + 1;
                int rightCol = curr.col;
                if ((rightRow >= 0 && rightRow < n) && (rightCol >= 0 && rightCol < m)) {
                    if (mat[rightRow][rightCol] == 1) {
                        queue.add(new Coordinate(rightRow, rightCol));
                        mat[rightRow][rightCol] = 2;
                        isSomeFreshRotten = true;
                    }
                }

                // up adjacent
                int upRow = curr.row;
                int upCol = curr.col + 1;
                if ((upRow >= 0 && upRow < n) && (upCol >= 0 && upCol < m)) {
                    if (mat[upRow][upCol] == 1) {
                        queue.add(new Coordinate(upRow, upCol));
                        mat[upRow][upCol] = 2;
                        isSomeFreshRotten = true;
                    }
                }

                // down adjacent
                int downRow = curr.row;
                int downCol = curr.col - 1;
                if ((downRow >= 0 && downRow < n) && (downCol >= 0 && downCol < m)) {
                    if (mat[downRow][downCol] == 1) {
                        queue.add(new Coordinate(downRow, downCol));
                        mat[downRow][downCol] = 2;
                        isSomeFreshRotten = true;
                    }
                }
            }

            // if there is some oranges rotten in this time unit,
            // increment time else end the BFS here
            if (isSomeFreshRotten)
                time++;
            else
                break;
        }

        // check if there is some fresh oranges in the matrix, if yes return -1
        // otherwise return time
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (mat[i][j] == 1)
                    return -1;
            }
        }

        return time;
    }

    public static void main(String[] args) {
        // Example 1
        int mat1[][] = new int[][]{
                {0, 1, 1},
                {2, 1, 2},
                {1, 0, 1}
        };
        System.out.println(minTimeToRot(mat1));

        // Example 2
        int mat2[][] = new int[][] {
                {0, 1, 0},
                {2, 0, 2},
                {1, 1, 1},
                {1, 1, 1}
        };
        System.out.println(minTimeToRot(mat2));
    }

    // class representing a coordinate in the matrix
    static class Coordinate {
        int row;
        int col;

        public Coordinate(int row, int col) {
            this.row = row;
            this.col = col;
        }
    }
}
2
-1

모든 오렌지를 썩는 데 필요한 최소 시간을 찾는 C ++ 코드

#include<bits/stdc++.h> 
using namespace std; 

// class representing a coordinate in the matrix
class Coordinate {
    public:
    int row;
    int col;
    
    Coordinate(int r, int c) {
        row = r;
        col = c;
    }
};

int minTimeToRot(vector<vector<int>> &matrix) {
    int n = matrix.size();
    int m = matrix[0].size();
    
    // create a queue to store coordinates
    queue<Coordinate> q;
    // initialize a variable time as 0
    int time = 0;
    
    // Add all the rotten oranges coordinates to the queue
    // these acts as the starting point of the BFS
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (matrix[i][j] == 2) {
                Coordinate coordinate(i, j);
                q.push(coordinate);
            }
        }
    }
    
    while (!q.empty()) {
        // initialise size as size of queue
        int size = q.size();
        bool isSomeFreshRotten = false;
        // boolean variable representing whether or not an orange
        // is rotten in this time unit
        for (int i = 0; i < size; i++) {
            // remove an element from the queue
            Coordinate curr = q.front();
            q.pop();
            
            // generate the coordinates of adjacent cells
            // if the generated coordinates are valid and there is a fresh orange
            // add the generated coordinates to the queue and mark that orange as rotten
            
            // left adjacent
            int leftRow = curr.row - 1;
            int leftCol = curr.col;
            if ((leftRow >= 0 && leftRow < n) && (leftCol >= 0 && leftCol < m)) {
                if (matrix[leftRow][leftCol] == 1) {
                    Coordinate coordinate(leftRow, leftCol);
                    q.push(coordinate);
                    matrix[leftRow][leftCol] = 2;
                    isSomeFreshRotten = true;
                }
            }

            // right adjacent
            int rightRow = curr.row + 1;
            int rightCol = curr.col;
            if ((rightRow >= 0 && rightRow < n) && (rightCol >= 0 && rightCol < m)) {
                if (matrix[rightRow][rightCol] == 1) {
                    Coordinate coordinate(rightRow, rightCol);
                    q.push(coordinate);
                    matrix[rightRow][rightCol] = 2;
                    isSomeFreshRotten = true;
                }
            }

            // up adjacent
            int upRow = curr.row;
            int upCol = curr.col + 1;
            if ((upRow >= 0 && upRow < n) && (upCol >= 0 && upCol < m)) {
                if (matrix[upRow][upCol] == 1) {
                    Coordinate coordinate(upRow, upCol);
                    q.push(coordinate);
                    matrix[upRow][upCol] = 2;
                    isSomeFreshRotten = true;
                }
            }

            // down adjacent
            int downRow = curr.row;
            int downCol = curr.col - 1;
            if ((downRow >= 0 && downRow < n) && (downCol >= 0 && downCol < m)) {
                if (matrix[downRow][downCol] == 1) {
                    Coordinate coordinate(downRow, downCol);
                    q.push(coordinate);
                    matrix[downRow][downCol] = 2;
                    isSomeFreshRotten = true;
                }
            }
        }
        
        // if there is some oranges rotten in this time unit,
        // increment time else end the BFS here
        if (isSomeFreshRotten) {
            time++;
        } else {
            break;
        }
    }
    
    // check if there is some fresh oranges in the matrix, if yes return -1
    // otherwise return time
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (matrix[i][j] == 1)
                return -1;
        }
    }
    
    return time;
}

int main() {
    // Example 1
    vector<vector<int>> mat1 {
        {0, 1, 1},
        {2, 1, 2},
        {1, 0, 1}
    };
    cout<<minTimeToRot(mat1)<<endl;
    
    // Example 2
    vector<vector<int>> mat2 {
        {0, 1, 0},
        {2, 0, 2},
        {1, 1, 1},
        {1, 1, 1}
    };
    cout<<minTimeToRot(mat2)<<endl;
    
    return 0;
}
2
-1

복잡성 분석

시간 복잡성

O (n * m), 입력 행렬의 모든 셀을 순회하는 폭 우선 검색을 사용했기 때문입니다. 따라서 시간 복잡도는 다항식입니다.

공간 복잡성

O (n * m), BFS를 사용하면이 공간이 필요합니다. 요소를 저장하는 큐를 사용하므로 이러한 복잡성이 발생합니다.

여기서 n과 m은 각각 주어진 행렬의 행과 열입니다.

균열 시스템 설계 인터뷰
Translate »