## Service Now Interview Question

Country: United States
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
0
of 0 vote

can you please explain the distance ? thank you

Comment hidden because of low score. Click to expand.
0

This algorithm is same as the one for "Printing all nodes at distance k from a given node".

Distance is the height. If distance is 2, we need all the nodes that are two edges away from that node.

I am not able to solve this using javascript

Comment hidden because of low score. Click to expand.
0
of 0 vote

Something in these lines. But it gives me an incorrect output

``````var allNodes =[];
function NodeClass(value){

this.value = value;

}

var  root = new NodeClass(20);
root.left = new NodeClass(8);
root.right = new NodeClass(22);
root.left.left = new NodeClass(4);
root.left.right = new NodeClass(12);
root.left.right.left = new NodeClass(10);
root.left.right.right = new NodeClass(14);
var target = root.left.right;

function printkdistanceNodeDown(root,  k) {
// Base Case
if (root == null || k < 0)  return;

// If we reach a k distant node, print it
if (k==0)
{
//  console.log(root.value);
allNodes.push(root.value)
return;
}

// Recur for left and right subtrees
printkdistanceNodeDown(root.left, k-1);
printkdistanceNodeDown(root.right, k-1);
}

function printkdistanceNode(root, target ,  k) {
// Base Case 1: If tree is empty, return -1
if (root == null) return -1;

if (root == target)
{
printkdistanceNodeDown(root, k);
return 0;
}

// Recur for left subtree
var dl = printkdistanceNode(root.left, target, k);

// Check if target node was found in left subtree
if (dl != -1)
{

if (dl + 1 == k){
console.log(root.value);
allNodes.push(root.value);
}

else
printkdistanceNodeDown(root.right, k-dl-2);

return 1 + dl;
}

var dr = printkdistanceNode(root.right, target, k);
if (dr != -1)
{
if (dr + 1 == k){
console.log(root.value);
allNodes.push(root.value);

}

else
printkdistanceNodeDown(root.left, k-dr-2);
return 1 + dr;
}

return -1;
}

console.log(printkdistanceNode(root, target, 2));``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

The expected answer is 4, 20. I get 2,20 :(

Comment hidden because of low score. Click to expand.
0
of 0 vote

sorry, it is not java script (it is c#), but the idea is in code, you can translate it into java script.
In function I don't use parameter "rootNode". It is because my class "BSTNode" contains reference to parent node.
If it is not allowed, then to obtain parent node just create method with input parameters "rootNode" and "currentNode", and then it will be necessary to change only 1 line in below code as follows:
foreach ( var item in new[] { node.GetRightChild(), node.GetLeftChild(), GetParent( rootNode, node ) } ) {

``````using System.Collections.Generic;

namespace BST {

public static class NodesFinder<T> {

public static BSTNode<T>[] FindNodes( BSTNode<T> rootNode, BSTNode<T> initNode, int distance ) {

var listOfStartNodes = new List<BSTNode<T>> { initNode };
var excList = new List<BSTNode<T>>();

for ( int i = 0; i < distance; i++ ) {
var inclList = new List<BSTNode<T>>();

foreach ( var node in listOfStartNodes ) {
var nearestNodes = new List<BSTNode<T>>();

foreach ( var item in new[] { node.GetRightChild(), node.GetLeftChild(), node.GetParent() } ) {
if ( item == null || excList.Contains( item ) ) { continue; }
}
}
listOfStartNodes = inclList;
}
return listOfStartNodes.ToArray();
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

By the definition "Printing all nodes at distance k from a given node" is the general for any graph, we can use a modified version of BFS where we keep track of the level as we goes. For particular, we insert -1 (or null as a indicator) when a complete level is push onto the queue. In the case of BST we only have a maximum of two node for the first level and maximum of 4 nodes for the second level (assumption that we start from root). Otherwise if we start from any node, we just need to remember to add parent, left and right as we expand the search tree, when we reach the desire level we can stop.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Just do a BFS with tracking depth as we goes along. Store the node to return if the depth is at desired k-th level. As soon as we start processing k+1-th, we can just stop as we has seen all the k-th level node. We can modified the queue to hold the Node and the depth and pushing start node as

``(node, 0)``

. When ever you pop and node and pushing it child we push

``(node, parent.depth + 1)``

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.