ムッシュー、あなたの問題解決能力は標準に達していません。

私の失敗についての小さな話と、インタビュー中に「問題を解決する」能力について、場合によっては顔の見えないテストがあります。

開始する

約1か月前、大手ソフトウェア会社の賞金稼ぎから連絡がありました。 彼女は、私の履歴書に示されているスキルと経験が、彼女が代表する会社に興味があることを説明し、探しているプロファイルを簡単に説明しました。 私はそれを答えた 常に彼らの会社で働くことを夢見ていた 原則として、説明されている投稿は魅力的に見えます。 その後、彼女は私のプロフィールがチームによってレビューされ、成功した場合、ビデオチャットを介してリモートでインタビューを受けるように彼女に言った。 私は自分のプロフィールが好きで、インタビューの日付に同意しました。

就職面接

すべてが順調に始まり、ソフトウェア開発、ソフトウェア品質保証へのアプローチについていくつか質問がありました。 また、分散システムの設計のいくつか、および同様のトピックに関する何か。 私はすべての質問に、明確に、明確に、きちんと整理された状態で、多くの困難なく答えました。 30分間のコミュニケーションの後、 問題解決スキルをテストするように申し出られましたが、気になりませんでした。彼らは私のプロフィールが気に入ったら、特別なことも聞いてくれるように思えたのですが、それがなかったからです。

挑戦する

javascript . ,

          1
         / \
        2   3
      /     / \
     4     6   7

, , :

          1-> Nil
         / \
        2-> 3-> Nil
       /   / \
     4 -> 6-> 7-> Nil

:

function Node(data) {
    this.data = data;
    this.left = this.right = null;
    this.neighbour = null;
}

, , , , . , , , . C#, javascript.

, , , . 5 . 5 . , , - . , ~30 , , . .

5 , , IDE, .

1,

20 , , , , , . . , , . , , . , , . , :

BinaryTree.prototype.findLinkedNeighbours = function (entry) {
    var links = [];
    var node = entry || this.root;
    var i, j, size;
    this.navigate(node, 0, links);
    size = links.length;
    for (i = 1; i < size; i++) {
        var link = links[i];
        var linkLength = link.length;
        if (linkLength < 2) {
            continue;
        }
        for (j = 1; j < linkLength; j++) {
            link[j-1].neighbour = link[j];
        }
    }
};

BinaryTree.prototype.navigate = function (node, level, links) {
    if (node === null) {
        return;
    }
    if(!links[level]) {
        links[level] = [];
    }
    links[level].push(node);
    this.navigate(node.left, level + 1, links);
    this.navigate(node.right, level + 1, links);
};

. :
Time complexity: O(n), Space complexity: O(n)

2, .

, , . . , , , . , , . :


:

  i,       : 2i+1,
       : 2i+2.
     : (i-1)/2

. . , , . :

BinaryTree.prototype.linkNeighbours = function(array) {
    var pace = 0;
    var level = 0;
    var limit = 0;
    var size = array.length;
    var previous = null;
    while (pace < size) {
        limit = (Math.pow(2, level) + pace);
        for (;pace < limit; pace++) {
            if (array[pace]) {
                if (previous !== null) {
                    previous.neighbour = array[pace];
                }
                previous = array[pace];
            }
        }
        previous = null;
        level++;
    }
};

BinaryTree.prototype.printNeighbours = function(array) {
    var length = array.length,
        level = 0,
        left = 0,
        right = 0;
    while(right < length) {
        left = right;
        right = Math.pow(2, level) + right;
        console.log(array.slice(left, right)
            .filter(function(x) { return x != null;})
            .map(function(x) {return x.data;})
        );
        level ++;
    }
};

:
Time complexity: O(2^h), Space complexity: O(1)
O(1) , , , , .

3, , .

, , , , . , , . — , . , . , :

LinkedTree.prototype.traverseAndCountingLevel = function() {
    var queue = new Queue();
    var node = this.root;
    var result = [];
    var level = 0, pace = 1, capacity = 1, leafsFactor = 0;

    queue.add(node);

    while(queue.size() > 0) {
        node = queue.poll();
        if(pace === capacity) {
            result.push([]);
            level++;
            leafsFactor *= 2;
            capacity = (Math.pow(2, level) - leafsFactor);
            pace = 0;
        }
        result[result.length-1].push(node.data);

        if (node.left !== null) {
            queue.add(node.left);
        } else {
            leafsFactor += 1;
        }
        if (node.right !== null) {
            queue.add(node.right);
        } else {
            leafsFactor += 1;
        }
        pace += 2;
    }
    return result;
};

:
Time complexity: O(n), Space complexity: O(n)
result, . O(log n) O(n).

, , , . , , , IDE , . . , , - . , , IDE .

, , ? , , — problem solving skills.

, SkidanovAlex .