Amazon Interview Question
SDE-2sTeam: Marketplace
Country: United States
Interview Type: In-Person
n = Node('A', Node('B', Node('D'), Node('E')), Node('C', Node('F')))
q = deque()
q.append(n)
num_current_level = 1
num_next_level = 0
while q:
node = q.popleft()
num_current_level -= 1
if not q or not num_current_level:
node.neighbor = Node('None')
else:
node.neighbor = q[0]
print '%s: %s' % (node.value, node.neighbor.value)
if node.left:
q.append(node.left)
num_next_level += 1
if node.right:
q.append(node.right)
num_next_level += 1
if not num_current_level:
num_current_level = num_next_level
num_next_level = 0
BFS using C#:
public void AssignNeighbor(Node root)
{
List<Node> current = new List<Node>();
current.Add(root);
while (current.Count > 0)
{
List<Node> children = new List<Node>();
foreach (var cur in current)
children.AddRange(cur.GetChildren());
if (children.Count > 0)
{
for (int i = 0; i < children.Count - 1; i++)
children[i].Neighbor = children[i + 1];
}
current = children;
}
}
the problem of this solution is that you do too many assumptions.
For example, consider the situation when you are given a third-party lib which contains class Node. And you get to know that method GetChildren() every time returns child nodes in random order. In this case your solution will not work.
Another assumption is that foreach iterator returns elements of collection in desired order. In general this is not true, it depends on the collection's container. Consider the situation when you are to use a container with random elements order. The solution again will not work.
In general the problem is dependency upon the assumptions.
While inserting node maintain horizontal and vertical level of each node as below ::
class node {
private :
int data;
node *left;
node *right;
int level[2];
public :
node(node *rig,node *lef, int d, int vlevel,int hlevel)
{
data=d;
left=lef;
right=rig;
level[0]=vlevel;
level[1]=hlevel;
}
int getData()
{
return data;
}
node *getLeftChild(){
return left;
}
node *getRightChild() {
return right;
}
void setLeftChild(node *n){
left=n;
}
void setRightChild(node *n) {
right=n;
}
void sethLevel(int a)
{
level[1]=a;
}
int gethLevel()
{
return level[1];
}
void setvLevel(int a)
{
level[0]=a;
}
int getvLevel()
{
return level[0];
}
node *getNeighbor()
{
return neighbor;
}
void setNeighbor(node *n)
{
neighbor=n;
}
};
class BST {
private :
node *root;
int _size;
map<int,int> lev;
vector<vector<int> > vec;
int height;
public :
BST() : root(NULL),height(0) {}
BST(int *arr, int siz)
{
_size=siz;
for(int i=0;i<_size;i++)
{
InsertNode(arr[i]);
}
}
void InsertNode(int value)
{
int heit=0;
node *temp=root;
if(temp==NULL)
{
cout << "Adding the root Node" << value << endl;
node *nod=new node(NULL,NULL,value,0,0);
root=nod;
}
while(temp!=NULL)
{
heit++;
if(value>temp->getData())
{
if(temp->getRightChild()==NULL)
{
cout << "Adding the new node" << value << endl;
node *nod=new node(NULL,NULL,value,temp->getvLevel()+1,2*temp->gethLevel()+1);
temp->setRightChild(nod);
temp=NULL;
}
else
{
cout << "Moving Right " << temp->getData() << endl;
temp=temp->getRightChild();
}
}
else
{
if(temp->getLeftChild()==NULL)
{
cout << "Adding the new node" << value << endl;
node *nod=new node(NULL,NULL,value,temp->getvLevel()+1,2*temp->gethLevel());
temp->setLeftChild(nod);
temp=NULL;
}
else
{
cout << "Moving Left " << temp->getData() << endl;
temp=temp->getLeftChild();
}
}
}
if(heit>height)
height=heit;
}
Now maintain a map as below ::
map<pair<int,int>,node *>
Now given a node, you can get vertical level and horizontal level.
from that you get the neighbor by incrementing the horizontal level and fetching the node from the map. All the non values are set to NULL.
public void connectNeighbor(TreeNode root){
if(root == null) return;
TreeNode lastHead = root;//prevous level's head
TreeNode lastCurrent = null;//pointer
TreeNode currentHead = null;//current level's head
TreeNode current = null;//pointer
while (lastHead != null){
lastCurrent = lastHead;
while (lastCurrent !=null){
if(lastCurrent.left != null){
if(currentHead == null)
currentHead = lastCurrent.left;
current = lastCurrent.left;
}else {
current.next = lastCurrent.left;
current = current.next;
}
if(lastCurrent.right != null){
if(currentHead == null){
currentHead = lastCurrent.right;
current = lastCurrent.right;
}else {
current.next = lastCurrent.right;
current = current.next;
}
}
lastCurrent = lastCurrent.next;
}
lastHead = currentHead;
currentHead = null;
}
}
c#.
DFS.
Direction: right to left.
public class Node<T> {
public Node<T> LeftChild;
public Node<T> RightChild;
public T Data;
public Node<T> Neighbor;
public static void SetNeighbors( Node<T> root ) {
_dic = new Dictionary<int, Node<T>>();
_currLevel = -1;
_setNeighbors( root );
}
static private void _setNeighbors( Node<T> node ) {
_currLevel++;
if ( _dic.ContainsKey( _currLevel ) ) {
node.Neighbor = _dic[ _currLevel ];
}
if ( node.RightChild != null ) {
_setNeighbors( node.RightChild );
}
if ( node.LeftChild != null ) {
_setNeighbors( node.LeftChild );
}
_dic[ _currLevel ] = node;
_currLevel--;
}
static private Dictionary<int, Node<T>> _dic;
static private int _currLevel;
}
void connect(TreeLinkNode* root){
queue<TreeLinkNode*> q;
int count = 0;
if(root != NULL) {
q.push(root);
count = 1;
}
while(count != 0){
int newcount = 0;
bool isFirstNode = true;
TreeLinkNode* prev = NULL;
for(int i = 0; i < count; ++i){
TreeLinkNode* curr = q.front();
q.pop();
if(isFirstNode){
isFirstNode = false;
prev = curr;
}
else{
prev->next = curr;
prev = curr;
}
if(curr->left != NULL){
q.push(curr->left);
newcount++;
}
if(curr->right != NULL){
q.push(curr->right);
newcount++;
}
}
count = newcount;
}
}
import java.util.*;
class Node{
int data;
Node left;
Node right;
Node friend;
public Node(int data){
this.data = data;
this.left = null;
this.right = null;
this.friend = null;
}
public String toString(){
if(friend != null)
return " " + data + " : "+friend.data;
else
return " "+data+ " : NULL";
}
}
public class FriendFinder{
public static void printFriends(Node root){
if(root == null)
{
System.out.println("empty");
return;
}
else{
Queue<Node> q1 = new LinkedList<Node>();
Queue<Node> q2 = new LinkedList<Node>();
q1.add(root);
while(!q1.isEmpty() || !q2.isEmpty()){
while(!q1.isEmpty())
{
if(q1.peek().left != null)
q2.add(q1.peek().left);
if(q1.peek().right != null)
q2.add(q1.peek().right);
Node pickedNode = q1.poll();
pickedNode.friend = q1.peek();
System.out.println(pickedNode);
}
while(!q2.isEmpty()){
if(q2.peek().left != null)
q1.add(q2.peek().left);
if(q2.peek().right != null)
q1.add(q2.peek().right);
Node pickedNode = q2.poll();
pickedNode.friend = q2.peek();
System.out.println(pickedNode);
}
}
}
}
public static void main(String []args){
Node root = new Node (1);
Node n2 = new Node (2);
Node n3 = new Node (3);
Node n4 = new Node (4);
Node n5 = new Node (5);
Node n6 = new Node (6);
root.left = n2; root.right = n3;
n2.left = n4;
n3.left = n5;
n3.right = n6;
/*
1
2 3
4 5 6
*/
printFriends(root);
}
}
We need to use BFS and if we use DFS, it would make it
more complicated and inefficient. We just need use a stack or array to store all children of nodes and assign the neighbor while traversing all nodes using BFS.
public class LinkNeighborNode {
public static void main(String[] args) {
Node root, nextLevel;
while(true){
nextLevel = linkLevel(root);
if(nextLevel == null)
break;
}
}
private static Node linkLevel(Node firstParent){
Node node = getFirstNode(firstParent);
Node firstNode = null;
if(node.left != null && node.right != null){
node.left.neighbor = node.right;
firstNode = node.right;
} else {
if(node.left != null) {
firstNode = node.left;
} else {
firstNode = node.right;
}
}
Node nextParentNode = node.neighbor;
Node nodeToStart = firstNode;
while(true){
if(nextParentNode == null) {
break;
}
if(nextParentNode.left != null && nextParentNode.right != null){
nodeToStart.neighbor = nextParentNode.left;
nextParentNode.left = nextParentNode.right;
nodeToStart = nextParentNode.right;
nextParentNode = nextParentNode.neighbor;
} else {
if(nextParentNode.left != null) {
nodeToStart.neighbor = nextParentNode.left;
nodeToStart = nextParentNode.left;
nextParentNode = nextParentNode.neighbor;
} else {
nodeToStart.neighbor = nextParentNode.right;
nodeToStart = nextParentNode.right;
nextParentNode = nextParentNode.neighbor;
}
}
}
return firstNode;
}
private static Node getFirstNode(Node firstParent) {
Node node = firstParent;
while(true){
if(node == null) {
return null;
}
if(node.left == null && node.right == null){
node = node.neighbor;
} else {
return node;
}
}
}
class Node {
int val;
Node left;
Node right;
Node neighbor;
}
}
}
public class LinkNeighborNode {
public static void main(String[] args) {
Node root, nextLevel;
while(true){
nextLevel = linkLevel(root);
if(nextLevel == null)
break;
}
}
private static Node linkLevel(Node firstParent){
Node node = getFirstNode(firstParent);
Node firstNode = null;
if(node.left != null && node.right != null){
node.left.neighbor = node.right;
firstNode = node.right;
} else {
if(node.left != null) {
firstNode = node.left;
} else {
firstNode = node.right;
}
}
Node nextParentNode = node.neighbor;
Node nodeToStart = firstNode;
while(true){
if(nextParentNode == null) {
break;
}
if(nextParentNode.left != null && nextParentNode.right != null){
nodeToStart.neighbor = nextParentNode.left;
nextParentNode.left = nextParentNode.right;
nodeToStart = nextParentNode.right;
nextParentNode = nextParentNode.neighbor;
} else {
if(nextParentNode.left != null) {
nodeToStart.neighbor = nextParentNode.left;
nodeToStart = nextParentNode.left;
nextParentNode = nextParentNode.neighbor;
} else {
nodeToStart.neighbor = nextParentNode.right;
nodeToStart = nextParentNode.right;
nextParentNode = nextParentNode.neighbor;
}
}
}
return firstNode;
}
private static Node getFirstNode(Node firstParent) {
Node node = firstParent;
while(true){
if(node == null) {
return null;
}
if(node.left == null && node.right == null){
node = node.neighbor;
} else {
return node;
}
}
}
class Node {
int val;
Node left;
Node right;
Node neighbor;
}
}
}
A variation of level-order traversal. Because something can only be a neighbor when it's on the same level, it means we should keep the current level and the next level separated. And because a Node only has knowledge of its immediate child, that means we really only need to know about two levels at any time. This algorithm runs in O(n) time, using O(n) space.
void attachNeighbors(Node root) {
Queue<Node> currentLevel = new LinkedList<Node>();
Queue<Node> nextLevel = new LinkedList<Node>();
currentLevel.add(root);
while (!currentLevel.isEmpty()) {
final Node currentNode = currentLevel.remove();
if (currentNode.left != null) {
nextLevel.add(currentNode.left);
}
if (currentNode.right != null) {
nextLevel.add(currentNode.right);
}
if (currentLevel.isEmpty()) {
Queue<Node> temp = currentLevel; //so we don't use more memory than needed
currentLevel = nextLevel;
nextLevel = temp;
} else {
currentNode.neighbor = currentLevel.peek();
}
}
}
This could be done using a level order traversal and collecting elements in same level. collection would be a map keyed on level and the value would be queue of elements. Rest is iterating over the map and assigning neighbors. Collect neighbors in a new map and then finally iterate over it. Below is a working code.
public class AssighnNeighbours {
private static Map<Integer, Queue<Node>> map = new HashMap<>();
private static Map<Integer, Integer> neighbours = new HashMap<>();
public static void main(String[] args) {
Node node = new Node(20);
node.left = new Node(15);
node.right = new Node(30);
node.right.left = new Node(25);
node.right.right = new Node(35);
collectElementsOnSameLevel(node, 0);
Set<Entry<Integer, Queue<Node>>> set = map.entrySet();
for (Entry<Integer, Queue<Node>> entry : set) {
Queue<Node> queue = entry.getValue();
Node prev = queue.remove();
if (queue.isEmpty()) {
neighbours.put(prev.data, null);
}
while (!queue.isEmpty()) {
Node next = queue.remove();
neighbours.put(prev.data, next.data);
prev = next;
}
}
Set<Entry<Integer, Integer>> neighboursSet = neighbours.entrySet();
for (Entry<Integer, Integer> entry : neighboursSet) {
System.out.println("neighbour of : " + entry.getKey() + " is : " + entry.getValue());
}
}
private static void collectElementsOnSameLevel(Node node, int level) {
if (node != null) {
if (map.get(level) != null) {
Queue<Node> queue = map.get(level);
queue.add(node);
} else {
Queue<Node> queue = new LinkedList<Node>();
queue.add(node);
map.put(level, queue);
}
collectElementsOnSameLevel(node.left, level + 1);
collectElementsOnSameLevel(node.right, level + 1);
}
}
}
public void assignNeighborNode(Node root){
Queue<Node> outerQue = new Queue<>();
Queue<Node> innerQue = new Queue<>();
outerQue.enqueue(root);
while(!outerQue.isEmpty()){
while(!outerQue.isEmpty())
innerQue.enqueue(outerQue.dequeue());
Node pre = null;
while(!innerQue.isEmpty()){
Node cur = innerQue.dequeue();
if(pre != null){
pre.neighbor = cur;
}
outerQue.enqueue(cur.left);
outerQue.enqueue(cur.right);
pre = cur;
}
}
}
Searching neighbors by DFS
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.IO;
namespace ConsoleApplication50
{
class Program
{
static void Main(string[] args)
{
Node head = new Node();
// input file contains, for example: 0 1 3 -1 -2 10
string[] input_data = File.ReadAllText(@"g:\input.txt").Split(new char[] {' ','\r','\n','\t' });
// create tree
for (int i = 0; i < input_data.Length; i++)
{
int data = int.Parse(input_data[i]);
if (i == 0) head.data = data;
else GrowTree(head, data);
}
// find neighbors for each node(if it is)
ExploreNeighborhood(head);
}
static void ExploreNeighborhood(Node head)
{
Dictionary<int, Node> d = new Dictionary<int, Node>();
if (head != null)
{
int level = 0;
DFS(head, d ,ref level);
}
}
// process tree by depth-first-search
// from left to right
// in each level remember last node without neighbor.
static Node DFS(Node node, Dictionary<int, Node> d ,ref int level)
{
level++;
if (node.left != null)
{
if (d.ContainsKey(level))
{
d[level].neighbor = node.left;
d[level] = node.left;
}
else
{
d.Add(level, node.left);
}
DFS(node.left, d,ref level);
}
if(node.right !=null )
{
if (d.ContainsKey(level))
{
d[level].neighbor = node.right;
d[level] = node.right;
}
else
{
d.Add(level,node.right);
}
DFS(node.right, d,ref level);
}
level--;
return node;
}
static void GrowTree(Node node, int data)
{
if (node != null)
{
if (node.data > data)
{
if (node.left != null)
{
GrowTree(node.left, data);
}
else
{
node.left = new Node(data);
}
}
else {
if (node.right != null)
{
GrowTree(node.right, data);
}
else {
node.right = new Node(data);
}
}
}
}
}
class Node
{
public int data;
public Node left;
public Node right;
public Node neighbor;
public Node()
{ }
public Node(int in_data)
{
data = in_data;
}
}
}
I think using a BFS and maintaining lastNode of next level can help us set the neighbours. I am using Deque to peek the last node in the queue.
Below is solution in java.
public void setNeighbours() {
if (root == null) {
return;
}
TreeNode2 lastNode = root;
Deque<TreeNode2> queue = new ArrayDeque<>();
queue.add(root);
while (!queue.isEmpty()) {
TreeNode2 node = queue.remove();
if (node.getlChild() != null) {
queue.add(node.getlChild());
}
if (node.rChild != null) {
queue.add(node.getrChild());
}
if (lastNode == node) {
node.setNeighbour(null);
lastNode = queue.peekLast();
} else {
node.setNeighbour(queue.peekFirst());
}
System.out.println(node + " : " + node.getNeighbour());
}
}
#include <iostream>
#include <vector>
struct Node {
Node* leftChild = nullptr;
Node* rightChild = nullptr;
char data;
Node* neighbor = nullptr;
};
std::vector<Node*> nodeQueue;
void populateNeighbor(Node* root) {
nodeQueue.push_back(root);
while (nodeQueue.size() > 0) {
int nodeCountAtDepth = nodeQueue.size();
if (nodeCountAtDepth > 1) {
for (int i = 1; i < nodeCountAtDepth; i++) {
nodeQueue[i - 1]->neighbor = nodeQueue[i];
}
}
for (int i = 0; i < nodeCountAtDepth; i++) {
if (nodeQueue[0]->leftChild) {
nodeQueue.push_back(nodeQueue[0]->leftChild);
}
if (nodeQueue[0]->rightChild) {
nodeQueue.push_back(nodeQueue[0]->rightChild);
}
// a slow operation -- O(n) -- could optimize
nodeQueue.erase(nodeQueue.begin());
}
}
}
{/*
Find the neighbors of a Tree
A
/ \
C D
/\ |\
E F g h
A:null
C:D
*/
node{
node leftChild;
node rightChild;
T data;
node neighbhor;
}
class Solution{
public void getNeighbors(node n){
if(n==null)
return;
node focusNode = n;
n.neighbor=null;
/*BFS*/
node parent;
Queue<node> q = new LinkedList<node>();
List<node> visited = new ArrayList<node>();
q.add(n);
while(!q.isEmpty()){
node focusNode = q.remove();
visted.add(focusNode);
parent = focusNode;
if(focusNode.left!=null){
focosNode = focusNode.left;
focusNode.neighbor = parent.right;
if(!visted.contains(parent.left)){
visted.add(parent.left);
q.add(parent.left);
}
}
if(focusNode.right!=null){
if(!visted.contains(parent.right)){
q.add(parent.right);
visted.add(parent.right);
}
}
else
return;
}
}
}
public class Node<T> {
public T data;
public Node<T> left;
public Node<T> right;
public Node<T> neighbour;
}
public class BinaryTreeTraversal<T> {
private Node<T> root;
private IVisitor<T> visitor;
public BinaryTreeTraversal(Node<T> root) {
this.root = root;
}
public void preOrder(IVisitor<T> v) {
visitor = v;
preOrder(root);
}
private void preOrder(Node<T> node) {
if(node == null) return;
visitor.visit(node);
preOrder(node.left);
preOrder(node.right);
}
}
public class TestBinaryTreeTraversal extends TestCase {
class IVisitorImpl implements IVisitor<String> {
@Override
public void visit(Node<String> node) {
if (node == null)
return;
System.out.print(node.data);
if (node.left != null) {
node.left.neighbour = node.right;
}
}
}
class IVisitorNeighbourImpl implements IVisitor<String> {
@Override
public void visit(Node<String> node) {
if (node == null)
return;
String data = (node.neighbour == null) ? null : node.neighbour.data;
System.out.println(node.data + " --> " + data);
}
}
public void testTraversal() {
Node<String> root = defineDataNode();
BinaryTreeTraversal<String> traversal = new BinaryTreeTraversal<>(root);
traversal.preOrder(new IVisitorImpl());
System.out.println("================================");
traversal.preOrder(new IVisitorNeighbourImpl());
}
private Node defineDataNode() {
Node<String> node = new Node<>();
node.neighbour = null;
node.data = "F";
node.right = new Node<>();
node.left = new Node<>();
node.left.data = "B";
node.right.data = "G";
node.right.right = new Node<>();
node.right.right.right = new Node<>();
node.left.left = new Node<>();
node.left.right = new Node<>();
node.left.right.left = new Node<>();
node.left.right.right = new Node<>();
node.left.left.data = "A";
node.left.right.data = "D";
node.left.right.left.data = "C";
node.left.right.right.data = "E";
node.right.right.data = "I";
node.right.right.left = new Node<>();
node.right.right.left.data = "H";
node.right.right.right.data="J";
return node;
}
}
import datastructures.trees.IVisitor;
import datastructures.trees.Node;
import datastructures.trees.traversal.BinaryTreeTraversal;
import junit.framework.TestCase;
public class TestBinaryTreeTraversal extends TestCase {
class IVisitorImpl implements IVisitor<String> {
@Override
public void visit(Node<String> node) {
if (node == null)
return;
System.out.print(node.data);
if (node.left != null) {
node.left.neighbour = node.right;
}
}
}
class IVisitorNeighbourImpl implements IVisitor<String> {
@Override
public void visit(Node<String> node) {
if (node == null)
return;
String data = (node.neighbour == null) ? null : node.neighbour.data;
System.out.println(node.data + " --> " + data);
}
}
public void testTraversal() {
Node<String> root = defineDataNode();
BinaryTreeTraversal<String> traversal = new BinaryTreeTraversal<>(root);
traversal.preOrder(new IVisitorImpl());
System.out.println("================================");
traversal.preOrder(new IVisitorNeighbourImpl());
}
private Node defineDataNode() {
Node<String> node = new Node<>();
node.neighbour = null;
node.data = "F";
node.right = new Node<>();
node.left = new Node<>();
node.left.data = "B";
node.right.data = "G";
node.right.right = new Node<>();
node.right.right.right = new Node<>();
node.left.left = new Node<>();
node.left.right = new Node<>();
node.left.right.left = new Node<>();
node.left.right.right = new Node<>();
node.left.left.data = "A";
node.left.right.data = "D";
node.left.right.left.data = "C";
node.left.right.right.data = "E";
node.right.right.data = "I";
node.right.right.left = new Node<>();
node.right.right.left.data = "H";
node.right.right.right.data="J";
return node;
}
}
package datastructures.trees.traversal;
import datastructures.trees.IVisitor;
import datastructures.trees.Node;
public class BinaryTreeTraversal<T> {
private Node<T> root;
private IVisitor<T> visitor;
public BinaryTreeTraversal(Node<T> root) {
this.root = root;
}
public void preOrder(IVisitor<T> v) {
visitor = v;
preOrder(root);
}
private void preOrder(Node<T> node) {
if(node == null) return;
visitor.visit(node);
preOrder(node.left);
preOrder(node.right);
}
}
package datastructures.trees;
public class Node<T> {
public T data;
public Node<T> left;
public Node<T> right;
public Node<T> neighbour;
}
package datastructures.trees;
public interface IVisitor<T> {
public void visit(Node<T> node);
}
if any issue with this please let us know
typedef struct _node{
int data;
_node *left;
_node *right;
_node *neighbore;
}node;
int height(node *root){
if (root == NULL) return 0;
return(1 + std::max(height(root->left), height(root->right)));
}
void levelOrder(node* root, int l, node** temp){
if (root == NULL) return;
if (l == 0){
root->neighbore = *temp;
*temp = root;
}
else{
levelOrder(root->right, l - 1, temp);
levelOrder(root->left, l - 1, temp);
}
}
void linkNeighbore(node* root){
int h = height(root);
root->neighbore = NULL;
node* temp = NULL;
for (int i = 1; i < h; i++)
levelOrder(root, i, &temp);
}
private void assignNeighbors(Node n){
ArrayList<Node> current = new ArrayList<BinaryTree.Node>();
if(n!=null) current.add(n);
while(!current.isEmpty()){
ArrayList<Node> parents = current;
current = new ArrayList<BinaryTree.Node>();
for(Node parent: parents){
if(parent.left!=null && parent.right!=null){
parent.left.neighbor = parent.right;
}
if(parent.left!=null)current.add(parent.left);
if(parent.right!=null) current.add(parent.right);
}
}
}
i think we should use breadth first search
- Anonymous December 12, 2015