## Amazon Interview Question for SDE-2s

• 0

Country: United States

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

Level order bfs

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

use bfs/level order traversal while keeping track of a distance from a root. If the first occurence of each number of the given array is found, update the result array with the current distance.
time O(n) where n is the total number of nodes in a tree
space O(Math.max(k, n)) where k is the total number of elements in an array.

``````public static int[] getDistanceFromRoot(Node head, int[] arr) {
int[] result = new int[arr.length];
for (int i = 0; i < result.length; ++i) {
result[i] = -1;
}

HashMap<Integer, Integer> hm = new HashMap<>();
for (int j = 0; j < arr.length; ++j) {
hm.put(arr[j], j);
}

int level = 0;

while (!q.isEmpty()) {
int size = q.size();
while (size > 0) {
Node temp = q.remove();
if (hm.containsKey(temp.val) && result[hm.getValue(temp.val)] == -1) {
result[hm.get(temp.val)] = level;
}

--size;
}
++level;
}

return result;
}``````

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

``````public int[] getDistanceFromRoot(Node head,int[] arr){
int[] result = new int[arr.length];
Arrays.fill(result,-1);
Map<Integer,Integer> map = new HashMap<>();
for(int j =0; j<arr.length;j++){
map.putIfAbsent(arr[j],j);
}
int level =0;
while (!queue.isEmpty()){
int size = queue.size();
while (size > 0){
Node temp = queue.poll();
if(map.containsKey(temp.val) && result[map.get(temp.val)]==-1){
result[map.get(temp.val)]= level;
}
if(temp.left !=null)
if(temp.right !=null)
size--;
}
level++;
}
return result;
}``````

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.