페이스북 인터뷰 질문

안녕하세요! 즐거운 한 주를 보내셨기를 바라며 Microsoft에서 사용하는 코딩 인터뷰 질문을 소개한 지난 주 를 확인하실 수 있는 기회가 있으셨기를 바랍니다.

지난 주 솔루션

이 챌린지에서 우리는 foodDistribution에 arr 샌드위치를 ​​포함하고 다양한 배고픔 수준arr을 포함하는 N 숫자를 취하는 함수h1, h2, h3 ...를 작성하라는 요청을 받았습니다. 우리의 목표는 사용 가능한 샌드위치를 ​​사용하여 배열에 있는 각 쌍의 사람들 사이의 배고픔 차이를 최소화하는 것입니다.

이 문제를 해결하려고 할 때 저에게 도움이 된 것은 코딩 전에 공격 계획을 단계별로 예를 들어 슈도코딩하는 것이었습니다. arr = [5, 3, 1, 2, 1] 가 있는 시나리오에 대한 접근 방식을 살펴보겠습니다.

접근 방식의 유사 코드:

지정된 배열에서 샌드위치 수N와 배고픔 수준(배열의 나머지 모든 요소)을 추출합니다. N = 5, hungers = [3,1,2,1]

각 숫자 쌍을 검사하고 각 값 쌍의 차이를 확인합니다. 이러한 차이differences를 계산할 수 있도록 이들sum을 배열에 저장합니다. 우리는 차이를 최소화하기를 원하기 때문에 차이의 합에 주의를 기울입니다(굶주림 수준에 따라 균등한 분배를 촉진하기 위해). 아래 코드에서 도우미 메서드sum(array) 및 differences(array)를 사용하여 이러한 값을 계산했습니다. diffs = [2, 1, 1], sum = 4

각 샌드위치를 ​​배분할 때 해당 샌드위치를 ​​배급할 최적의 배고픔 수준이 무엇인지 조사하십시오. 샌드위치가 떨어지거나 배고픔 수준 차이의 합이 0인 시나리오에 도달할 때까지 이 과정을 반복합니다. "최적"은 한 번에 하나의 샌드위치 분포와 배고픔 수준의 조합이 가장 낮은 차이 합계를 생성하는 것을 기준으로 계산됩니다.

마지막 단계에서는 모든 샌드위치를 ​​분배하거나 차이의 합계가 0이 되어 평등에 도달한 후 배고픔 수준 쌍 간의 차이의 합계를 반환해야 합니다.

예제 살펴보기:

        N = 5, hungers = [3,1,2,1], diffs = [ 2, 1, 1], sumDiff = 4;

        // Distribute one sandwich 
        N = 4;
        // Possible combos
        [2,1,2,1], diffs = [1,1,1], sumDiff = 3; 
        [3,0,2,1], diffs = [3,2,1], sumDiff = 6;
        [3,1,1,1], diffs = [2,0,0], sumDiff = 2; // Optimal 
        [3,1,2,0], diffs = [2,1,2], sumDiff = 5;

        // since sumDiff = 2 > 0 && N = 4 > 0, continue to distribute sandwiches 

        N = 3;
        // Possible combos
        [2,1,1,1], diffs = [1,0,0], sumDiff = 1; // Optimal
        [3,0,1,1], diffs = [3,0,0], sumDiff = 3;
        [3,1,0,1], diffs = [2,1,1], sumDiff = 4; 
        [3,1,1,0], diffs = [2,0,1], sumDiff = 3;  

        // since sumDiff = 1 > 0 && N = 3 > 0, continue to distribute sandwiches 

        N = 2;
        // Possible combos
        [1,1,1,1], diffs = [0,0,0], sumDiff = 0;// Optimal
        [2,0,1,1], diffs = [2,1,0], sumDiff = 3;
        [2,1,0,1]], diffs = [1,1,1], sumDiff = 3; 
        [2,1,1,0], diffs = [1,0,1], sumDiff = 2;  

        // Since sumDiff = 0, we can stop distributing sandwiches because we've reached equality across the pairs of hunger levels. By distributing 3 sandwiches we went from hunger levels of `[3,1,2,1]` to `[(3-2),1,(2-1),1] = [1,1,1,1]`.

// Return 0  

자바스크립트 솔루션

    function foodDistribution(arr) {
        let N = arr.shift();
        let hungers = arr;
        let diffs = differences(hungers);
        if (N >= diffs){ return 0 }
        while (N > 0 && sum(diffs) > 0) {
                let combos = [];
                for (let i = 0; i < hungers.length; i++) {
                let combo = hungers.slice();
                combo[i]--;
                combos.push(combo);
            }

            hungers = combos.reduce(minDiff);
            N--;

            diffs = differences(hungers);
    }

    return sum(diffs);
    }

    // HELPER METHODS  
    // Returns an array of differences across each pair 
    function differences(array) {
    let diffs = [];

    for (let i = 0; i < array.length - 1; i++) {
        diffs.push(Math.abs(array[i] - array[i + 1]));
    }
    return diffs;
    }

    // Returns the sum of all values in an array (i.e. sum of all diffs)
    function sum(array) {
    return array.reduce((p, c) => p + c, 0);
    }

    // Compares two array and returns the array with the smallest sum of differences
    function minDiff(arr1, arr2) {
        if(sum(differences(arr1)) <= sum(differences(arr2))){
            return arr1;
        } else {
            return arr2;
        }
    }

    // GIVEN TEST CASES
    console.log(foodDistribution([5, 3, 1, 2, 1])); // return 0 b/c you distribute 5 sandwiches as 2, 0, 1, 0, making hunger levels [1, 1, 1, 1]

    console.log(foodDistribution([5, 2, 3, 4, 5])); // return 1 b/c you distribute 5 sandwiches as 2, 2, 1, 0 making hunger levels [4,5,5,5]  

    console.log(foodDistribution([3, 2, 1, 0, 4, 1, 0])); // return 4

    // ADDITIONAL TEST CASES
    console.log(foodDistribution([1, 5, 4, 1])); // return 3 
    console.log(foodDistribution([20, 5, 4, 1])); // return 0
    console.log(foodDistribution([5, 4, 2, 5, 1, 1])); // return 1 
    console.log(foodDistribution([12, 5, 5, 5, 5, 5])); // return 0

이것이 제가 이 문제를 해결하기 위해 취한 접근 방식을 마무리합니다. 당신의 생각은 무엇입니까? 이것은 시간 및 공간 복잡성 측면에서 어떻게 수행됩니까? 이 솔루션을 개선할 방법이 있습니까? 아래 의견에서 귀하의 생각을 듣고 싶습니다.

이번 주 챌린지

우리는 Facebook 인터뷰에서 요청된 문제에 초점을 맞추고 있으며 이진 트리에 대한 우리의 이해를 테스트하고 있습니다.

이번 주에 우리는 treeConstructor 형식의 정수 쌍을 포함하는 문자열 배열인 strArr를 받는 함수 (i1,i2)를 작성하라는 요청을 받았습니다. 여기서 i1는 트리의 자식 노드를 나타냅니다. 두 번째 정수i2는 i1의 부모임을 나타냅니다.

예를 들어 strArr가 ["(1,2)", "(2,4)", "(7,2)"]인 경우 다음 트리를 형성합니다.



이것은 이진 트리이므로 유효한 이진 트리를 형성할 수 있으므로 함수가 반환되어야 합니다true. 정수 쌍으로 적절한 이진 트리를 형성할 수 없는 경우 false를 반환합니다.

우리는 트리 내의 모든 정수가 고유하다고 가정할 수 있습니다. 즉, 주어진 정수 값을 가진 트리의 노드는 하나만 있을 수 있습니다.

추가 예시:

입력: ["(1,2)", "(2,4)", "(5,7)", "(7,2)", "(9,5)"] , 출력: true

입력: ["(1,2)", "(1,3)"] , 출력: false

이 문제를 해결하기 위한 귀하의 접근 방식은 무엇입니까?

아래에서 이 챌린지에 대한 생각을 공유해 주세요. 우리는 당신이 어떤 해결책을 제시하는지 알고 싶습니다. 그 동안 500,000명 이상의 개발자가 인터뷰를 준비하는 데 도움을 준 인터뷰 준비 플랫폼인 Coderbyte에서 무료 계정에 가입하면 액세스할 수 있는 무료 10일 이메일 인터뷰 준비 과정을 확인하십시오.

다음주에 보자!

사진 제공: Emile Perron on Unsplash