Amazon Interview Question
Software Engineer / DevelopersCountry: CANADA
Interview Type: In-Person
Its a modification of Level Order traversal / BFS of binary tree.
For each level, find the count of -ve numbers. Compare it with a max_count, which indicates what level has the max -ve numbers and swap if needed.
As for the BFS search with level number, it can be done in many ways:
1. Using a dummy node
2. Keeping a count of nodes in current level and next leve
3. Using separate queues for current and next level.
we can keep a counter to track the nodes in the same level.
public class TreeNode
{
int key;
int value;
TreeNode left;
TreeNode right;
}
public static int mostNegativeLevel(TreeNode root)
{
if(root == null)
return -1;
Queue q = new Queue<TreeNode>();
int count = 0;
int level = 0;
int maxNegativeLevel = 0;
int negativeCount = 0;
int maxNegativeCount = 0;
q.enqueue(root);
count++;
while(!q.empty())
{
TreeNode node = stack.dequeue();
negativeCount+= (node.number < 0)? 1:0;
count --;
if(node.left != null)
q.push(node.left);
if(node.right !- null)
q.push(node.right);
if(count == 0)
{
if(negativeCount > maxNegativeCount)
{
maxNegativeCount = negativeCount;
maxNegativeLevel = level;
}
count = q.size();
level++;
negativeCount = 0;
}
}
return maxnegativeLevel;
}
Here is working version in python
//tree node structure
class Node:
left = None
right = None
value = -1
def __init__(self, value =-1):
self.value = value
def find_negatives(tree):
count = []
count_negatives(tree, count, 0)
max = 0;
depth = 0;
for i in range(0, len(count)):
print "depth " + str(i) + " count: " + str(count[i])
if (count[i] > max):
max = count[i]
depth = i
print "result depth : " + str(depth) + " count : " + str(max)
return max
def count_negatives(tree, count, depth):
if tree is None:
return
if tree.value < 0:
print "found : " + str(tree.value) + " depth : " + str(depth)
if (len(count) -1 < depth):
count.append(1)
else:
count[depth] = count[depth] +1
count_negatives(tree.left, count, depth+1)
count_negatives(tree.right, count, depth+1)
return
This is another one using BFS.
def bfs_count(root):
result = {}
current_depth =0
current_node_count = 0
current_negative_count = 0
next_node_count = 0
queue = deque()
queue.append(root)
current_node_count =1
max_count = 0
max_depth = 0
while (len(queue)):
node = queue.popleft()
current_node_count-=1
if (node.value < 0):
current_negative_count+=1
if (node.left != None):
queue.append(node.left)
next_node_count += 1
if (node.right != None):
queue.append(node.right)
next_node_count +=1
if (current_node_count == 0):
if (current_negative_count > max_count):
max_count = current_negative_count;
max_depth = current_depth
current_depth+=1
current_node_count = next_node_count
next_node_count = 0
current_negative_count = 0;
result[max_depth] = max_count
return result
This is my proposal in C++. I assumed we have a BST:
#include <iostream>
using namespace std;
struct node
{
int data;
node* p_left;
node* p_right;
};
node* addNode(node* root, int value)
{
if(root == NULL)
{
node* n = new node;
n->data = value;
n->p_left = NULL;
n->p_right = NULL;
return n;
}
if(value <= root->data)
root->p_left = addNode(root->p_left, value);
else
root->p_right = addNode(root->p_right, value);
return root;
}
int getDepth(node* root)
{
if(root == NULL)
return 0;
return 1 + max(getDepth(root->p_left), getDepth(root->p_right));
}
void maxNegativeInLevel(node* root, int * arr, int level)
{
if(root == NULL)
return;
if(root->data < 0)
arr[level]++;
maxNegativeInLevel(root->p_left, arr, level + 1);
maxNegativeInLevel(root->p_right, arr, level + 1);
}
int main()
{
node* tree = NULL;
tree = addNode(tree, -8);
tree = addNode(tree, -15);
tree = addNode(tree, -3);
tree = addNode(tree, -21);
tree = addNode(tree, -14);
tree = addNode(tree, -3);
tree = addNode(tree, 4);
tree = addNode(tree, -6);
int depth = getDepth(tree);
int * quantities = new int[depth];
maxNegativeInLevel(tree, quantities, 0);
int max_level = 0;
for(int i = 0; i < depth; i++)
if(quantities[i] > quantities[max_level])
max_level = i;
cout << "Level " << max_level << " with " << quantities[max_level] << " node(s)" << endl;
}
we can keep a counter to track the nodes in the same level.
- zahidbuet106 May 19, 2014