Amazon Interview Question for SDE-2s

• 2

Country: India
Interview Type: Written Test

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

This can be done by BFS algorithm and you only consider nodes that at distance K from the given node. The given node is the parent of the tree we need to parse. A java code for this problem can be like that

``````public ArrayList<Node> printNodes(Node node, int k){
ArrayList<Node> list = new ArrayList<>();
int level = 0;
int nodesToProcess = 1;
int nodesInNextLevel =0;
while(!queue.isEmpty()){
Node n = queue.remove();
nodesToProcess--;
if(n.left!=null){
nodesInNextLevel++;
}
if(n.right!=null){
nodesInNextLevel++;
}

if(nodesToProcess==0){
level++;
nodesToProcess = nodesInNextLevel;
nodesInNextLevel=0;
if(level>k) break;
}
}
return list;
}``````

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

Why not just provide a solution outline and let others to code? Reading code is a challenge of its own.

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

Yes, level order traversal (BFS) will do

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

Parent of the given node has distance 1, which is < K. I think the solution should include nodes other than the nodes below.

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

your solution will return half result, only returning K distance nodes below given node.
Other half (and bigger problem) include K distance nodes above to given node.

See me solution below for reference.

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

I can think of 2 solutions for it

1) Run DFS on the tree to find parent of each node. Now this tree becomes a graph. Run BFS/DFS to find all nodes at distance K

2) Use the concept of rotating trees as in red black trees.
First take the tree with root at the starting node (arbitrary node) and find all nodes at level K. These are all the nodes at distance K in the sub tree.
Then remove all child nodes from the starting node and do multiple rotations so that this node becomes the root. Now find all nodes at level K
The union of both of these is the solution.

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

Solution 1 sounds reasonable. Additional memory is needed.

Have problems with solution 2. What if you have such tree and looking for nodes at distance 5 of F? Looks like nothing will be found while C is the answer. Am I wrong?

``````A
| \
B  C
|
D
|
E
|
F``````

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

Lets rotate the given tree to right so that F is the root. It becomes:
F
\
E
\
D
\
B
\
A
\
C
Now all nodes at level 5 will be the solution which is C

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

I was thinking along similar lines as Arrantinsane. I split the problem into two parts:
+ From the binary tree root, see if the target node can be found at specified distance/depth.
+ From the target node, find all nodes at specified distance/depth.
Here is my pseudo code.

``````void
find_node_at_distance(root, tgt, distance)
{
lroot = root;                       // local copy of root.
ldistance = distance;
while (lroot) {
if (tgt) {
if (lroot->data == tgt->data) {
break;
}
}
if (ldistance < 0) {
break;
}
ldistance--;

if (tgt->data < lroot->data) {
lroot = lroot->left;
} else {
lroot = lroot->right;
}
}

if (ldistance == 0) {
printf("root is at distance of %d from tgt\n", root, distance);
}
}

main()
find_node_at_distance(root, tgt, 2);          // ex distance of 2.
find_node_at_distance(tgt->left, NULL, 2-1);  // NULL means any node at given dist.
find_node_at_distance(tgt->right, NULL, 2-1);``````

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

I guess this idea works ...from root traverse till the target (arbitrary node) next from arbitrary node till the K distance .

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

This problem can be divided into two parts:

``````1) All nodes K distance away from arbitrary node in arbitrary node's subtree.
2) All nodes K distance away from arbitrary node above to this arbitrary node.``````

First part is quite easy.

``````void kdistanceNodes (tree *root, int K)
{
if (root)
{
if (K == 0)
{
print << root->key;
}
kdistanceNodes (root->left, K-1);
kdistanceNodes (root->right, K-1);
}
}``````

when arbitrary node is found
1) process all K distance node in its subtree
for second part,
2) if arbitrary node is not found, at every node, keep distance from leaf node in left subtree and from leaf node in right subtree
3) if arbitrary node is found, at every node, keep distance from arbitrary node from either of subtree and then search for remaining other subtree (K - distance from arbitrary node)

``````pair<bool, int> printKNodes (tree *root, int depth, int node, int K)
{
if (!root) return make_pair(false, 0);
if (K < 0) return make_pair(false, 0);

/*If Node found, then print all nodes at K distance in subtree*/
if (node == root->key)
{
if (K == 0) {print node, return <true, 1>}
kdistanceNodes (root->left, K-1)
kdistanceNodes (root->right, K-1)
return <true, 1>
}
else
{
pair<bool, int> left = printKNodes (root->left, depth+1, node, K)
/*If node is found in left subtree and current node is still <=K nodes away from arbitrary node */
if (left.first == true && left.second <= K)
{
if (K - left.second == 0)
{
print root->key
}
else if ( (K - left.second) > 0)
{
/*remaining distance from arbitrary node to right subtree via this root*/
kdistanceNodes (root->right, (K - left.second - 1) )
}
return <true, left.second+1> //pair
}
pair<bool, int> right = printKNodes (root->right, depth+1, node, K)
/*If node is found in right subtree and current node is still <=K nodes away from arbitrary node */
if (right.first == true && right.second <= K)
{
if (K - right.second == 0)
{
print root->key
}
else if ( (K - right.second) > 0)
{
/*remaining distance from arbitrary node to left subtree via this root*/
kdistanceNodes (root->left, (K - right.second - 1) )
}
return <true, right.second+1> //pair
}
/*If arbitrary node has not been found return total depth from leaf node*/
int biggerSubtree = (left.second > right.second) ? left.second : right.second;
return <false, biggerSubtree+1>
}
}``````

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

As a optimisation, distance from left subtree leaf node can be used in case arbitrary node is found in right subtree.
If remaining distance from arbitrary node is greater than size of left subtree, then left subtree need not to be traversed.

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

``````void printAtLevel(Node *treenode, int level)
{
if(treenode==NULL)
return;
if(level==1)
{
printf(" %d ",treenode->data);
}
else if(level > 0)
{
printAtLevel(treenode->right, level-1);
printAtLevel(treenode->left, level-1);
}
}``````

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

public static int distance;
public static ArrayList<Node> result;

public void findKth(Node root, Node target){
findKth(root, -1, target);
}

private int findKth (Node n, int k, Node target ){
if( n == null ){
return k;
}
if(n == target){
k= distance;
}
if(k == 0){
return k++;
}
if(k == -1){
int temp 1 = findKth( n.left , k, target);
int temp2 = findKth (n.right , k , target);
}else{
int temp 1 = findKth( n.left , --k, target);
int temp2 = findKth (n.right , --k , target);
}
if((temp1-distance)==distance || (temp2-distance) == distance ){
}
return temp1== -1? temp2++ : temp1++;
}

O(n) complexity, any opinion?

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

we have to print all nodes which are child of desired nodes and are child of parent nodes.

``````public int PrintNodesAtKDistance(Node root, int requiredNode, int iDistance)
{
if ((root == null) || (iDistance < 0))
return -1;

int lPath = -1, rPath = -1;

if(root.value == requiredNode)
{
PrintChildNodes(root, iDistance);
return iDistance - 1;
}

lPath = PrintNodesAtKDistance(root.left, requiredNode, iDistance);
rPath = PrintNodesAtKDistance(root.right, requiredNode, iDistance);

if (lPath > 0)
{
PrintChildNodes(root.right, lPath - 1);
return lPath - 1;
}
else if(lPath == 0)
{
Debug.WriteLine(root.value);
}

if(rPath > 0)
{
PrintChildNodes(root.left, rPath - 1);
return rPath - 1;
}
else if (rPath == 0)
{
Debug.WriteLine(root.value);
}

return -1;
}

public void PrintChildNodes(Node aNode, int iDistance)
{
if (aNode == null)
return;

if(iDistance == 0)
{
Debug.WriteLine(aNode.value);
}

PrintChildNodes(aNode.left, iDistance - 1);
PrintChildNodes(aNode.right, iDistance - 1);
}``````

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

(assuming binary search tree)
search for the node, recording parents in path to it
for parent of the node, find all children k-1 from there
for grandparent of the node, find all children k-2 from there
etc.

finally find children of that node that are distance k

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

``````void printKDistant(node *root , int k)
{
if(root == NULL)
return;
if( k == 0 )
{
printf( "%d ", root->data );
return ;
}
else
{
printKDistant( root->left, k-1 ) ;
printKDistant( root->right, k-1 ) ;
}
}``````

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

I think that if we were asked to print all nodes at distance k that is part of subtree of the specific node, then the above solution would be correct. But since we also have to consider the nodes which are at distance k and is not part given node's subtree, we need to modify the solution a bit.
So for its immediate parent, we need to call the same function with k-1 and its parent as k-2 and so on. And since we don't have pointer for parent we need to tweek algo.

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.