## Amazon Interview Question for Software Engineer / Developers

• 0

Country: India
Interview Type: Written Test

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

We shall have to do breadth first scan
For a normal binary tree (not BST), I think we shall to sort node by node value, explicitly by collecting them. Is there anyway to do it directly from in the tree?

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

BFS to know the depth of all nodes in the tree and then consider those which comprise u + d = K. u = upward distance, d = downward distance from the start node. Ex:- K= 4, and start node is at depth 3.
The u and d can take values (0,4)(1,3)(2,2)(3,1)(4,0). Meaning consider the upward distance of 0 and downward distance of 4 from from start node => 3 + 4 = 7. Consider nodes beneith start node which are at level 3. Similarly for other combinations.

As and when fetching the nodes do an insertion sort.

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

CORRECTION at the end of 1st para: Consider nodes beneith start node which are at level 7. Similarly for other combinations.

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

The up or down distance has to be measured from the start node. It is not that we have to find nodes which are K distance apart. Like if the depth of start node is 3 and the distance given is 1, then we will print all nodes at level 2 and 4.

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

``````void PrintKDepth(node *root, int depth)
{
if (root == null) return;

if (depth == 0 )
{
Print the root;
}
PrintKDepth(root->left,depth-1);
PrintKDepth(root->right,depth-1);
}
int PrintAllKthDistance(node *root, node *start, int depth K)
{
if(root == null) return -1;
if(root == start)
{
PrintKDepth(root->left, k);
PrintKDepth(root->right, k);
return k-1;
}
int leftDepth = PrintAllKthDistance(root->left,start,found,K);
if(leftDepth == 0)
{
print the node;
}
else if (leftDepth > 0)
{
PrintKDepth(root->right, leftDepth);
return leftDepth-1;
}
int rightDepth = PrintAllKthDistance(root->right, start, found, k);
if(rightDepth == k)
{
print the node
}
else if (rightDepth > 0)
{
PrintKDepth(root->left, rightDetph);
return rightDepth-1;
}
return -1;
}``````

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

sorry ..Actually In found is not there ..so you remove found argument ..

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

How do u deal with the Nodes that are K-distance up from the start node ?

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

This code handles the up distance from start ..

on recursion - when we return to up from start node, and if its value is greater than 0, then we are querying left/right subtree depending on the start node. This way we query up node and also other side of subtree..
Please give an example..the case ..where you are not able to print out all the nodes from the start node...

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

Do we need to print only the nodes which are connected to start node and are at K distance from start node OR We should print all the nodes from the Kth distance level?

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

As par my understanding, We have to print K distance from the start node assuming as graph.

so if we have to only print the Kth distance of path node, then you simply put a very easily contraint...that would also be solvable by this methog

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

As par my understanding, We have to print K distance from the start node assuming as graph.

so if we have to only print the Kth distance of path node, then you simply put a very easily contraint...that would also be solvable by this methog

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

is distance is like just height or depth or else it can be any distance (like hop)
suppose k=2... so for this do we need to find the immediate sibling?

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

Is there any constraint on the space usage? if not, lets say that we're allowed to use extra space of O(n). We can create an array, do a BFS on the binary tree and store the nodes encountered in our array. One we're done with the BFS, we can find the nodes with satisfy the distance property. For example, lets say our tree was:

4
/ \
2 6
/ \ / \
1 3 5 7

Now if we did a BFS, we would get the array as: 4,2,6,1,3,5,7. Lets say the start node is root node (i.e. 4), the node to be searched is 3 and K = 2.

Now we know that we can find the children of a node at 2n+1, 2n+2 position (en.wikipedia.org/wiki/Binary_tree#Arrays)

Given this array, we can look for the index of node 3 (which happens to be 4 in our example). Now, we are looking for all nodes which are at a distance of k = 2 from node 3. We know that the parent of 3 (if it exists) must be at a distance = 1 from 3. This parent can be found at (index of node3 -1)/2. This node is at index = 1. Now node 3 can ask its parent to return all nodes which are at a distance (k-1) [such that k-1 ==0].Node 2 sees that there are only 2 nodes which satisfy this property: Node 4 and Node 1 (ignoring Node 3 itself). so these 2 nodes are printed. Node 3 also asks its children to return all nodes which are at a distance of k.

Hence, recursively it looks possible to discover all the nodes (including siblings) which are at a distance of k from node 3.

This is just an initial idea. And requires O(n) extra space. Runs in O(n) time.

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

Start from root node. Identify if start node is to left of root node or right of root node.

Start bfs:
label each node with the 'level' value
also label each node with flag '1', if nodes are on other side of 'start' node
if nodes have startnode as ancestor , label them as '2'
else label them with '0'.

Now, while printing, do in-order traversal, and only print nodes that meet the following condition:

if ( node.side = '1' and startnode.level + node.level == k ) print node
if ( node.side = '2' and node.level - startnode.leve == k ) print node
if ( node.slide = '0' )
common ancestor between startnode and node is at l = abs(startnode.level - node.level)
now if l + node.level == k , then print.

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

Use recursion to first find downwards distance

Signature is:

``````kDistDown(node *root, node *start, int k)   {
<check for halting condition: k=0 and start !=null >
kDistDown(node *root, node  *start->left, k-1)
kDistDown(node *root, node *start->right, k-1)
}``````

Now to check the upwards condition.
This is kind of a hack really. By no means elegant.
Write a recursive function to exhaustively search a tree for a given node returning the distance from the ROOT as the output.
Call the function TWICE passing root->left and root->right as args.
Now you'll know which subtree our start node is on. Left or right.
Also you'll know the distance from root to the start node.
Let this be 'n'.

Exhaustively search for all nodes at a distance k-n in the OPPOSITE subtree.

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

The Algorithm would be something like this(would post the code later)
1.Do a DFS traversal for the tree(Inorder)
2.In the Process node part call a sub routine find_distance between_two_nodes
3.Check if the return val of 2 is equal to k, if yes print it or store it in an array(for sorting)

find_distance between_two_nodes works as follows
1. Find LCA of the 2 nodes under discussion
2.from the LCA call get_node_distance_from_lca subroutine for both the nodes and add the result and return

get_node_distance_from_lca works as follows
find the difference between the level of lca and the node(using BFS)

Space Complexity : S(n)--queue
Time Complexity : O(n)

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

I think your solution in O(n^2). Since, you do the processing for each pair of nodes. And, then between each pair of nodes you do an bfs. which in O(n)

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

No,I am calculating distance of the given node with all other nodes(for LCA) and the other for length of path, the maximum nodes that would be traversed is again n, so the total complexity is O(n) + O(n) =~ O(n).

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

sorry,you are right,it will trend towards O(n2) and one optimization could be done, i.e. when doing a level order traversal store the nodes in a map(hash on node value as key) and store its level as the value.Now during the calculation of the path length from lca to each node, the lookup should only be O(1).

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

I think you can do it without recursion (assuming bst, otherwise sorted order does not make sense):

Find your node using binary search and note the path like LLR

start a stack based in order traversal and check whether the distance is less than or equal to K

The distance calculation: find the longest prefix of the two paths then add the tail length of both paths. So, distance between LLR and LR is 3 (L is common, dist: len(LR) + len(R) = 2+1)

Don't enter a subtree/ignore pop from the stack if already too far from the original node (limiting the number of visited nodes to K)

To speed up the distance calc a little bit, you can supply the parent result and add the child difference only.

Time complexity: O(logn) + O(k)

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

Would anyone make clear to me what it means by distance?

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

5
/ \
2 8
/ \ / \
-4 4 6 9

input :
Root node: 5
search node: 8
Distance (K): 1

output : 5, 6, 9

if k is 3 then output should be -4 and 4 respectively, the problem i feel is how to navigate upwards considering that we do not have reference to parent node.

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

@Cooldaa: Distance is the length of the path from one node to another node
OR The number of edges/links between two nodes. An Edge is counted as 1 in a Tree by default.
For example in the above given tree, the distance between 5 & 8 is 1, between 5 & 9 is 2 and so on...

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

2 Passes

1st Pass

1. Find the level at which startNode occurs using recursion to traverse the tree

2nd Pass

1. Print all nodes at level- distance and level+distance using recursion to traverse nodes

Code follows in Java

``````private static int findLevel(TreeEntry root,TreeEntry startNode,int level) {
int level1,level2;
if (root == null)
return -1;

else {
if (root == startNode)
return level;
level1 = findLevel(root.left,startNode,level+1);
level2 = findLevel(root.right,startNode,level+1);
}
if (level1 != -1)
return level1;
if (level2 != -1)
return level2;

return -1;
}

private static void printNodes(TreeEntry root,int interestedLevel1,int currLevel,int interestedLevel2) {
if (root == null)
return;
else {
if ( (currLevel == interestedLevel1) || (currLevel == interestedLevel2) ){
System.out.println(root.data);
}

printNodes(root.left,interestedLevel1,currLevel+1,interestedLevel2);
printNodes(root.right,interestedLevel1,currLevel+1,interestedLevel2);

}
}``````

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

// Takes searchNode (startNode) as int and prints all the nodes // at distance k from it. But the printed nodes are not in sorted //order
void printKDistanceNodes( BinaryNode *root , int searchNode ,int level , int x , int *y , int *found )
{
if( root == NULL ) return ;

if( root->data == searchNode )
*found = 1;

if( *found == 1 )
{
printKDistanceNodes ( root->left , searchNode , level, x+1, y , found);
printKDistanceNodes ( root->right , searchNode , level, x+1, y , found);
}
else
{
printKDistanceNodes ( root->left , searchNode , level, x, y , found);
if(*found)
printKDistanceNodes ( root->right , searchNode , level, x+1, y , found);
else
printKDistanceNodes ( root->right , searchNode , level, x, y , found);
if(found)
printKDistanceNodes ( root->left , searchNode , level, x + 1, y , found);
}

if( x + *y == level )
{
cout<< root->data << "\n";

}

if(*found && x == 0 )
(*y)++;

return;
}

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

``````void printk(Node root, int k)
{

if(root!=NULL )
{
if(k==0) cout<<"@"<<root->data<<"@"<<endl;
else{printk(root->left, k-1);
printk(root->right, k-1);}

}``````

}

^ above to print downword .. upward can be similarly printed by calculating the depth of the given node.. then calculating relative distance of the level to be printed from node.. then by calling the above function again

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

I hope following looks cleaner.

``````public void printKDistanceNodes(TNode head, TNode node, int k){
if(null == head || null == node || k < 0){
return;
}

} else {
}
}

/* This function initializes the distances of the nodes from root
* to the given node in using post order traversal

Tree after the execution of initializeAndUpdateDitanceFromRootToNode(head, nodeof(4))
1
2        3
4       6

Transforms to

1,-2
2,-1        3
4,0           6

In the above minus negative sign denotes whether node in in left side or right side.
Negative value means node is in the left side.

Tree after the execution of initializeAndUpdateDitanceFromRootToNode(head, nodeof(6))
1
2        3
4       6

Transforms to

1,2
2        3,-1
4      6,0

*/

public ReturnStrcture initializeAndUpdateDitanceFromRootToNode(TNode head, TNode node){
ReturnStrcture c = new ReturnStrcture();
ReturnStrcture l = new ReturnStrcture();
ReturnStrcture r = new ReturnStrcture();
int distance = 0;

c.setDistance(0);
c.setIsFoundNode(true);
return c;
}

l = initializeAndUpdateDitanceFromRootToNode(head.getLeft(), node);
r = initializeAndUpdateDitanceFromRootToNode(head.getRight(), node);

if(l.getIsFoundNode()){
c.setDistance(l.getDistance() + 1);
c.setIsFoundNode(true);

distance = -(l.getDistance() + 1);
} else if (r.getIsFoundNode()) {
c.setDistance(r.getDistance() + 1);
c.setIsFoundNode(true);

distance = r.getDistance() + 1;
} else {
c.setIsFoundNode(false);
}

return c;
}

/*
* This function uses another function printNodesInDistanceKFromRoot and print all the nodes
* that are in distnce k from given node.
*/
public void printNodesInDistanceKFromAGivenNode(TNode head, TNode node, int k){
return;
}
// Given node is in the left subtree

System.out.println("Node value - "+head.getVal());
} else if (Math.abs(head.getDistance()) < k){
}
} else if (head.getDistance() > 0){
// Given node is in the right subtree

System.out.println("Node value - "+head.getVal());
} else if (head.getDistance() < k){
}
}
}

/*
* Print all the values nodes with distnce k from the head.
*/
private void printNodesInDistanceKFromRoot(TNode head, int k) {
if(k == 0){
System.out.println("Node value - "+head.getVal());
return;
} else {
}
}
}

public class TNode {
Integer val;
TNode left;
TNode right;
Integer distance;

public Integer getVal() {
return val;
}
public void setVal(Integer val) {
this.val = val;
}
public TNode getLeft() {
return left;
}
public void setLeft(TNode left) {
this.left = left;
}
public TNode getRight() {
return right;
}
public void setRight(TNode right) {
this.right = right;
}
public Integer getDistance() {
return distance;
}
public void setDistance(Integer distance) {
this.distance = distance;
}
}

public class ReturnStrcture {
private int distance;
private boolean isFoundNode; // 1 for left, 2 for right

public int getDistance() {
return distance;
}

public void setDistance(int distance) {
this.distance = distance;
}

public boolean getIsFoundNode() {
return isFoundNode;
}

public void setIsFoundNode(boolean isFoundNode) {
this.isFoundNode = isFoundNode;
}
}``````

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

1. Initialize stack.
2. Start with the root and do a DFS.
3. Once node found,
3.1 Upward, pop the stack K times.
3.2 Downward,
3.2.1 Do DFS on node->lchild and on node->rchild K times

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

node *arr[20];
void distup(node *root,node *start,int k)
{
while(root!=start)
{
arr[i++]=root;
if(start->data > root->data)
root=root->rightchild;
else
root=root->leftchild;
}
if(root==start)
printf("%d",arr[i-k]->data);
}// will print K distance UP

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

steps:
1. get the distance of the start node in the tree.
2. make a function printk(node , distance) which prints all the nodes at a level of k from the given node passed as a paramenter.
3. Run the printk(start node , k) with start node and k , it prints the nodes at level k down from the start node.
4. let k=4 for eg. and the level of start is 6 , so 6-4 = 2 is the level upto which we need to print the nodes. these will be the node k distance from the start node
5. done

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

fun(node* root,node*start,int k)
{
static int flag=0,level= 0;
if(n!=NULL)
{
if(root==start) // start node found now proceed
{ flag=1;
}
if( flag==1)
{
level++;
if(level==k)
cout<<root.data;
return;
}
fun(n->left);
if(level==k&&n!=start)
{ return;
}
else if(n==start)
{
level=0;
}
fun(n->rite)
if(n==start)
{ k=1;
}
}
}

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

Going down was easy but once i hit the K nodes from bottom, i start returning the value 2*k-1 up along the path.This way , when we again hit the target node while backtracking, we are at (2k-1)/2 and as we move up, we will again be at 0 (or -k) value

``````private static int fn(Node root, Node x, int level, int curr) {
if (root == null) return -1;

if (curr == level) {
System.out.println(root.data);
return (2 * (level)) - 1;
}

if (root == x || curr > 0) {
curr++;
}

int l = fn(root.left, x, level, curr);
int r = fn(root.right, x, level, curr);
if ((max(l, r) != -1)&&( max(l,r)==0)) {
System.out.println(root.data);
return -1;

}   else{
return max(l,r)-1;
}``````

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

Here is O(n) solution, but program modifies the tree node, it stores the distance from root to current node.

``````public void printKDistanceNodes(TNode head, TNode node, int k){
if(null == head || null == node || k < 0){
return;
}

} else {
}
}

/* This function initializes the distances of the nodes from root
* to the given node in using post order traversal

Tree after the execution of initializeAndUpdateDitanceFromRootToNode(head, nodeof(4))
1
2		3
4       6

Transforms to

1,-2
2,-1		3
4,0     	  6

In the above minus negative sign denotes whether node in in left side or right side.
Negative value means node is in the left side.

Tree after the execution of initializeAndUpdateDitanceFromRootToNode(head, nodeof(6))
1
2		3
4       6

Transforms to

1,2
2		3,-1
4      6,0

*/

public ReturnStrcture initializeAndUpdateDitanceFromRootToNode(TNode head, TNode node){
ReturnStrcture c = new ReturnStrcture();
ReturnStrcture l = new ReturnStrcture();
ReturnStrcture r = new ReturnStrcture();
int distance = 0;

c.setDistance(0);
c.setIsFoundNode(true);
return c;
}

l = initializeAndUpdateDitanceFromRootToNode(head.getLeft(), node);
r = initializeAndUpdateDitanceFromRootToNode(head.getRight(), node);

if(l.getIsFoundNode()){
c.setDistance(l.getDistance() + 1);
c.setIsFoundNode(true);

distance = -(l.getDistance() + 1);
} else if (r.getIsFoundNode()) {
c.setDistance(r.getDistance() + 1);
c.setIsFoundNode(true);

distance = r.getDistance() + 1;
} else {
c.setIsFoundNode(false);
}

return c;
}

/*
* This function uses another function printNodesInDistanceKFromRoot and print all the nodes
* that are in distnce k from given node.
*/
public void printNodesInDistanceKFromAGivenNode(TNode head, TNode node, int k){
return;
}
// Given node is in the left subtree

System.out.println("Node value - "+head.getVal());
} else if (Math.abs(head.getDistance()) < k){
}
} else if (head.getDistance() > 0){
// Given node is in the right subtree

System.out.println("Node value - "+head.getVal());
} else if (head.getDistance() < k){
}
}
}

/*
* Print all the values nodes with distnce k from the head.
*/
private void printNodesInDistanceKFromRoot(TNode head, int k) {
if(k == 0){
System.out.println("Node value - "+head.getVal());
return;
} else {
}
}
}

public class TNode {
Integer val;
TNode left;
TNode right;
Integer distance;

public Integer getVal() {
return val;
}
public void setVal(Integer val) {
this.val = val;
}
public TNode getLeft() {
return left;
}
public void setLeft(TNode left) {
this.left = left;
}
public TNode getRight() {
return right;
}
public void setRight(TNode right) {
this.right = right;
}
public Integer getDistance() {
return distance;
}
public void setDistance(Integer distance) {
this.distance = distance;
}
}

public class ReturnStrcture {
private int distance;
private boolean isFoundNode; // 1 for left, 2 for right

public int getDistance() {
return distance;
}

public void setDistance(int distance) {
this.distance = distance;
}

public boolean getIsFoundNode() {
return isFoundNode;
}

public void setIsFoundNode(boolean isFoundNode) {
this.isFoundNode = isFoundNode;
}
}``````

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.