Monsieur, your problem solving skills are not up to par, or how I failed one interview

I bring to your attention a small story of my failure and of how, at times, there are faceless checks for the ability to "solve problems / problems" during interviews.

Start

About a month ago, a bounty hunter from a large software company contacted me. She explained that the skills and experience indicated in my resume interested the company she represents and briefly described what profile she was looking for. I replied that always dreamed of working for their company In principle, the described post looks tempting. After that, she said that my profile will be reviewed by their team and, if successful, she will invite me to have an interview remotely, via video chat. My profile liked and we agreed on the date of the interview.
')

Interview

It all started pretty well, I was asked a couple of questions about the approaches to software development, software quality assurance. Just a couple of design of distributed systems, and something else on similar topics. I answered all the questions without any particular difficulty, clearly, with feeling, sensibly and in an arrangement. After half an hour of communication, I was offered to test my problems solving skills , I did not mind, because it seemed to me that if they liked my profile, then they would ask me too, something specialized, but it was not there.

Task

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 .