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;
}
Level order bfs
- Ashu July 22, 2020