Amazon Interview Question
SDE-2sCountry: United States
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);
}
Queue<Node> q = new LinkedList<>();
q.add(head);
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;
}
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);
}
Queue<Node> queue = new LinkedList<>();
queue.offer(head);
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)
queue.add(temp.left);
if(temp.right !=null)
queue.add(temp.right);
size--;
}
level++;
}
return result;
}
Level order bfs
- Ashu July 22, 2020