구글 면접 문제

코드 회고로 돌아온 것을 환영합니다.만약에 저희에 방금 가입하셨다면, Coderbyte's 매주 인코딩 도전에 대한 더 많은 정보를 알고 저희의 첫 번째 도전을 해결해 주십시오.
나는 모든 사람들이 즐거운 일주일을 보냈으면 좋겠다.바로 해결 방안에 들어가 봅시다. 그중에 페이스북 인터뷰 문제가 있습니다.

지난주 도전

treeConstructor의 도전에 대해 우리는 함수를 작성해야 한다. 이 함수는 문자열을 포함하는 수조를 수신하고 각 문자열은 다음과 같은 형식의 정수 쌍을 가진다. (i1,i2), 그 중에서 i1는 트리의 하위 노드를 나타내고, 두 번째 정수i2는 i1의 부 노드를 나타낸다.우리의 목표는 되돌아오는 것이다true. 만약 값이 두 갈래 나무를 형성할 수 있다면 되돌아오는 것이다false.50여만 명의 다른 사용자와 솔루션을 비교하려면 Coderbytehere의 도전 페이지를 방문하십시오.

지난주 솔루션

인코딩하기 전에 두 갈래 나무가 무엇인지 빠르게 되돌아봅시다.만약 당신이 더욱 투철한 복습을 필요로 한다면, 우리의 나무 시리즈 영상을 보십시오.두 갈래 나무가 무엇인지 이해하기 위해서 우리는 먼저 나무가 무엇인지를 정의해야 한다.트리는 다음과 같은 노드의 집합입니다.
조건 1에는 루트 노드 (또는 부모 노드) 가 있습니다.
조건 2 두 노드 사이에는 경로가 하나뿐입니다(하위 노드마다 부모 노드가 하나씩).
두 갈래 나무는 특수한 유형의 나무로 그 중에서 다음과 같다.
조건 3 트리의 각 노드에는 최대 두 개의 하위 노드가 있습니다.이것은 하나의 노드가 하나의 하위 노드가 없을 수도 있고, 하나의 하위 노드나 두 개의 하위 노드가 있을 수도 있다는 것을 의미한다.

우리 유튜브 나무에서 캡처.
이제 우리는 두 갈래 나무가 무엇인지 알게 되었다. 우리는 이 문제를 해결하기 위해 위조 인코딩을 할 수 있는 방법을 찾아야 한다.

상기 조건을 확인하기 위해 하위 대상을 부모 대상과 분리하는 방법이 필요하기 때문에 해시표를 작성하여 부모 대상: 하위 대상과 하위 대상: 부모 대상 관계를 저장할 수 있습니다.

학부모에 대해 우리는 다음과 같이 구성할 것이다parents = { p1: [c1, ch2], p2: [c3]},

아이에게 우리는 children = { c1: p1, c2: p2 }

그리고 문자열 그룹을 훑어보고 각 문자열을 조합해야 합니다.

문자열"(child, parent)"을 해석하여 의미 변수를 사용하여 child 및 parent 을 쉽게 처리할 수 있도록 합니다.

현재 상위 항목이 상위 해시에 있는지 확인합니다.만약 그렇다면 하위 레벨을 그룹에 추가합니다.없으면 하위 그룹을 포함하는 새 그룹을 만듭니다.현재 상위 그룹의 하위 레벨 길이가 2보다 크면 조건 3을 위반하고false로 돌아가야 합니다.

현재 하위 항목이 하위 해시에 존재하면false로 돌아갑니다. 저희가 조건 2를 위반했기 때문입니다. (자 항목은 여러 개의 상위 항목이 있습니다.)그렇지 않으면 하위 및 해당 상위 레벨을 하위 해시에 추가합니다.

루트 노드가 하나밖에 없음을 확보함으로써 검사 조건 1이 성립된다.

function treeConstructor(strArr) {
    let parents = {};
    let children = {};

    for (let i = 0; i < strArr.length; i++) {
        // i.e. ("1,2") => ["1", "2"]
        let pair = strArr[i].replace(/[()]/g, "").split(",");
        let child = pair[0];
        let parent = pair[1];

        //  check parents have at most 2 children 
        if (parents[parent]) {
            parents[parent].push(child);
        } else {
            parents[parent] = [child];
        }

        if (parents[parent].length > 2) {
            return false;
        }

        // check child has one parent 
        if (children[child]) {
            return false;
        } else {
            children[child] = parent;
        }
    }
    // check there is only one root node 
        let root_count = 0;
        let parent_values = Object.keys(parents)
        for(let i = 0; i < parent_values.length; i++){
            if(!children[parent_values[i]]){
                root_count += 1;
            }
            if(root_count > 1){
                return false;
            }
        }
    return true;
}

// Given test cases 
console.log(treeConstructor(["(1,2)", "(2,4)", "(5,7)", "(7,2)", "(9,5)"])) // return true 

console.log(treeConstructor(["(1,2)", "(1,3)"])) // return false since we have a child with more than 1 parent

// Additional test cases 
console.log(treeConstructor(["(1,2)", "(3,2)", "(4,2)"])) // return false since we have a parent with more than 2 children 
console.log(treeConstructor(["(3,2)", "(4,5)" ])) // return false where we have disconnected nodes (more than 1 parent)

이것은 내가 트리 구조 함수를 구해내는 방법이다.만약에 내가 현장 인터뷰에서 이 문제를 해결한다면 내가 좋아하는 방법은 내가 먼저 효과적인 두 갈래 나무를 구축하는 데 필요한 조건부터 시작한 다음에 이런 장면에 대해 한 번에 한 문제를 해결하고 모든 문제를 한 번에 해결하지 않는 것이다.이것은 이 문제를 나에게 있어서 더욱 쉽게 해결하게 한다.그럼에도 불구하고 우리는 이 해결 방안을 최적화할 방법이 있다.당신은 우리가 무엇을 개선할 수 있다고 생각합니까?

이번 주 도전

구글 인터뷰에서 우리는 행렬을 사용하라는 도전에 부딪혔다. (내가 처음으로 알고리즘 문제를 해결하기 시작했을 때 나는 이 점을 매우 두려워했다.)
이번 주 도전에서 우리는 함수bitmapHoles를 작성해야 한다. 함수는 받아들인다strArr. 이것은 문자열 수조로 0과 1의 2D 행렬을 형성한다. 이 함수는 행렬에 구멍이나 0의 연속 구역이 얼마나 있는지 확인해야 한다.연속 영역은 네 방향 중 하나 이상의 방향에서 0, 아래, 왼쪽 또는 오른쪽으로 구성된 연결 그룹을 실행합니다.
예제 1
strarr가 ["10111", "10101", "11101", "11111"]인 경우 이 행렬은 다음과 같습니다.

1 0 1 1 1
1 0 1 0 1
1 1 1 0 1
1 1 1 1 1

위의 입력에 대해 함수는 두 개의 독립된 연속 0 영역이 있기 때문에 매트릭스에 구멍을 생성합니다.
기타 예

은strArr = ["01111", "01101", "00011", "11110"]에 대해 2로 돌아갑니다.

은strArr = ["1011", "0010"]에 대해 2로 돌아갑니다.

은strArr = ["110", "000", "111"]에 대해 2로 돌아갑니다.

입력 strArr 이 비어 있지 않다고 가정할 수 있습니다.

당신은 이 도전을 어떻게 해결할 것입니까?

나는 네가 이 문제를 어떻게 해결하는지 매우 보고 싶다.만약 미래의 도전에 대해 조언이 있다면, 코드 심사 기간에 소개해 주십시오. 언제든지 논평을 발표해 주십시오.면접 준비 기교와 학습 도구에 대해 더 알고 싶으면 Coderbyte 을 클릭하세요.다음 주에 봐요!
사진은 Johannes Plenio 에서 Unsplash