Amazon Interview Question SDE1s
Country: India
Interview Type: In-Person
do BSF, for each level create a linked list and put it in a stack,
then for each element on the stack print out the list, when printing check if next. next == null, if so, terminate the print loop
time complexity = time to build the stack of linked lists + time to pop lists and print them out
time complexity = traverse time + time to pop lists and print them out
traverse time = O(N)
time to pop lists and print them out = O(N)
time complexity = 2 * O(N) = O(N)
space complexity = O(N)
Using a Stack is not necessary here. Use this (List<List<Node>>) will also work.
The List<Node> are nodes at the same level. Build List<List<Node>> while doing BFS. Print the nodes using 2 nested for loops. The outside loop walk the ArrayList from Count-1 to 0 and inside loop from 0 to count-2.
If N is huge and the depth of the tree is K, such that K nodes can fit in memory but N nodes can not than the above solution will not work.
Also note, that time complexity O(N) with space complexity O(N) gives you a total complexity of O(N^2).
traversing the tree K times, each time printing a single depth, is much simpler.
this is easy to do with a time complexity of O(K*N) and a space complexity of O(K) holding only 1 brunch at a time (printing when finding the next node).
this gives a total complexity of O(K^2*N)
"If N is huge and the depth of the tree is K, such that K nodes can fit in memory but N nodes can not than the above solution will not work."
agree
"Also note, that time complexity O(N) with space complexity O(N) gives you a total complexity of O(N^2). "
I disagree, perhaps I'm missunderstanding but you can't multiply time complexity by space complexity, it's different things
"traversing the tree K times, each time printing a single depth, is much simpler. "
if we traverse printing a single depth using BSF, we get up-bottom level order, so this doesn't solve the issue, I'm curious to know if there is something that does "backwards BSF" without a helper structure such as the stack,
also note that BSF does O(N) and K = F(N) = Log N, where the base is the number of childs per node
so what you propose is O(K^2*N) = (Log N * Log N * N) therefore O(N) < O(K^2*N)
therefore O(K^2*N) is much worse than O(N)
This solution is only applicable when N is so big that it cannot be fit into memory. For a smaller N BFS is the way to go. But can't compare the complexity of both the solution as they work in different scenarios.
Also I don't understand how do we combine space and time complexity into one single complexity. I haven't read any such thing till now. Share any links if you find.
import java.util.*;
public class Solution {
class Node {
private Node parent;
private List<Node> childs;
private Character data;
public Character getData() {
return data;
}
public Node getParent() {
return parent;
}
public void setData(Character d) {
this.data = d;
}
public void setParent(Node parent) {
this.parent = parent;
}
public List<Node> getChilds() {
return childs;
}
public void addChild(Node child) {
if(childs == null) {
childs = new ArrayList<Node>();
}
childs.add(child);
}
}
class LevelMapHandler {
Map<Integer, List<Node>> levelMap;
public void addNodeToLevel(int level, Node node) {
if (levelMap == null) {
levelMap = new HashMap<Integer, List<Node>>();
}
List<Node> nodesAtLevel = levelMap.get(level);
if (nodesAtLevel == null) {
nodesAtLevel = new ArrayList<Node>();
}
if (nodesAtLevel.contains(node)) {
System.out.println("error : node " + node.getData() + " already in List of level " + level);
}
nodesAtLevel.add(node);
levelMap.put(level, nodesAtLevel );
}
public Map<Integer, List<Node>> getLevelMap(){
return levelMap;
}
}
/*
1
2 3 4
a b c d e
*/
public Node buildTestTree() {
Node root = new Node();
root.setParent(null);
root.setData('1');
Node n2 = new Node();
n2.setParent(root);
n2.setData('2');
Node n3 = new Node();
n3.setParent(root);
n3.setData('3');
Node n4 = new Node();
n4.setParent(root);
n4.setData('4');
root.addChild(n2);
root.addChild(n3);
root.addChild(n4);
Node na = new Node();
na.setParent(n2);
na.setData('a');
Node nb = new Node();
nb.setParent(n2);
nb.setData('b');
n2.addChild(na);
n2.addChild(nb);
Node nc = new Node();
nc.setParent(n3);
nc.setData('c');
n3.addChild(nc);
Node nd = new Node();
nd.setParent(n4);
nd.setData('d');
Node ne = new Node();
ne.setParent(ne);
ne.setData('e');
n4.addChild(nd);
n4.addChild(ne);
return root;
}
public void loadLevelMap(Node root, int level, LevelMapHandler levelMapHandler) {
if (root == null) return;
// print root ?
if (root.getData() != null) {
levelMapHandler.addNodeToLevel(level, root);
}
if (root.getChilds() != null && !root.getChilds().isEmpty()) {
for (Node child : root.getChilds()) {
loadLevelMap(child, level + 1, levelMapHandler);
}
}
}
public void printAllExceptRightMost(Map<Integer, List<Node>> mapLevel) {
for (Map.Entry<Integer, List<Node>> entry : mapLevel.entrySet())
{
List<Node> nodeList = entry.getValue();
Integer level = entry.getKey();
int n = nodeList.size();
for (int i = 0; i < n-1; i++) {
Node node = nodeList.get(i);
System.out.println(level + " - " + node.getData());
}
}
}
public void execute() {
Node root = buildTestTree();
LevelMapHandler levelMapHandler = new LevelMapHandler();
loadLevelMap(root, 0, levelMapHandler);
printAllExceptRightMost(levelMapHandler.getLevelMap());
}
public static void main(String[] args) {
Solution sol = new Solution();
sol.execute();
}
}
import java.util.*;
public class Solution {
class Node {
private Node parent;
private List<Node> childs;
private Character data;
public Character getData() {
return data;
}
public Node getParent() {
return parent;
}
public void setData(Character d) {
this.data = d;
}
public void setParent(Node parent) {
this.parent = parent;
}
public List<Node> getChilds() {
return childs;
}
public void addChild(Node child) {
if(childs == null) {
childs = new ArrayList<Node>();
}
childs.add(child);
}
}
class LevelMapHandler {
Map<Integer, List<Node>> levelMap;
public void addNodeToLevel(int level, Node node) {
if (levelMap == null) {
levelMap = new HashMap<Integer, List<Node>>();
}
List<Node> nodesAtLevel = levelMap.get(level);
if (nodesAtLevel == null) {
nodesAtLevel = new ArrayList<Node>();
}
if (nodesAtLevel.contains(node)) {
System.out.println("error : node " + node.getData() + " already in List of level " + level);
}
nodesAtLevel.add(node);
levelMap.put(level, nodesAtLevel );
}
public Map<Integer, List<Node>> getLevelMap(){
return levelMap;
}
}
/*
1
2 3 4
a b c d e
*/
public Node buildTestTree() {
Node root = new Node();
root.setParent(null);
root.setData('1');
Node n2 = new Node();
n2.setParent(root);
n2.setData('2');
Node n3 = new Node();
n3.setParent(root);
n3.setData('3');
Node n4 = new Node();
n4.setParent(root);
n4.setData('4');
root.addChild(n2);
root.addChild(n3);
root.addChild(n4);
Node na = new Node();
na.setParent(n2);
na.setData('a');
Node nb = new Node();
nb.setParent(n2);
nb.setData('b');
n2.addChild(na);
n2.addChild(nb);
Node nc = new Node();
nc.setParent(n3);
nc.setData('c');
n3.addChild(nc);
Node nd = new Node();
nd.setParent(n4);
nd.setData('d');
Node ne = new Node();
ne.setParent(ne);
ne.setData('e');
n4.addChild(nd);
n4.addChild(ne);
return root;
}
public void loadLevelMap(Node root, int level, LevelMapHandler levelMapHandler) {
if (root == null) return;
// print root ?
if (root.getData() != null) {
levelMapHandler.addNodeToLevel(level, root);
}
if (root.getChilds() != null && !root.getChilds().isEmpty()) {
for (Node child : root.getChilds()) {
loadLevelMap(child, level + 1, levelMapHandler);
}
}
}
public void printAllExceptRightMost(Map<Integer, List<Node>> mapLevel) {
for (Map.Entry<Integer, List<Node>> entry : mapLevel.entrySet())
{
List<Node> nodeList = entry.getValue();
Integer level = entry.getKey();
int n = nodeList.size();
for (int i = 0; i < n-1; i++) {
Node node = nodeList.get(i);
System.out.println(level + " - " + node.getData());
}
}
}
public void execute() {
Node root = buildTestTree();
LevelMapHandler levelMapHandler = new LevelMapHandler();
loadLevelMap(root, 0, levelMapHandler);
printAllExceptRightMost(levelMapHandler.getLevelMap());
}
public static void main(String[] args) {
Solution sol = new Solution();
sol.execute();
}
}
Simply.pass a flag to the recursive function mentioning whether or not it is the rightmost node. By definition, root is also the rightmost(as well as the leftmost node) and hence, technically it should not get printed. If the interviewer wants so, we can make an exception to this, by exploiting the fact that root node can always be known..
f (node, isRightMost) { for (i = 1 to node.Children.size() - 1) { f(node.Children[i], false) } f(node.Children.lastChild, isRightMost) if (!isRightMost) { print node.value } }Invoke using: f(root, true)
- Murali Mohan February 11, 2014