Amazon Interview Question
Team: amazon local
Country: United States
Interview Type: Phone Interview
public void printExtraDups(MyNode root){
//int prev = 0;
if(root != null)
{
if (root.left != null )
printExtraDups(root.left);
if( prevData == root.data) prevCount++;
else {
if(prevCount > 0)
System.out.println("Prev: "+prevData+" count: "+(prevCount -1));
prevCount = 0;
}
prevData = root.data;
if(root.right !=null )
printExtraDups(root.right);
}
}
Yeah this seems right assuming prevData and prevCount are declared as static variables and also u should print prevCount rather than prevCount-1
Yes the inorder traversal would work. And instead of static, prevData abd prevCount can be parameter to the function.
If you pass it as a parameter u would have to use pointers. I don't think its possible otherwise.
I do not quite understand the question. If the tree is a BST, there should not be any duplicates.
The definition of BST on wikipedia is as following:
The left subtree of a node contains only nodes with keys less than the node's key.
The right subtree of a node contains only nodes with keys greater than the node's key.
Both the left and right subtrees must also be binary search trees.
There must be no duplicate nodes.
Use a regular BST search but send parent value to children and keep a class level HashMap of current dups
{
HashMap<BSTNode, Integer> dupMap = HashMap<BSTNode, Integer>();
//head will trying to compare with null
void findDups(BSTNode parent, BSTNode current)
{
if(current.data == parent.data)
{
//see if already in map, if not put it in with value 1, else pull out value, increment, insert again
}
parent = current
for(BSTNode child : current.getChildren)
{
findDup(child, parent)
}
}
}
Not the best pseudo code but you get the point
import java.util.ArrayList;
public class amazon
{
private static node root=new node();
void input(int value)
{
node temp=new node();
temp.value=value;
if(root==null)
{
root=temp;
}
else
{
setvalues(root, temp);
}
}
void setvalues(node root, node temp)
{
if(root.value>temp.value)
{
if(root.left==null)
{
root.left=temp;
}
else
setvalues(root.left, temp);
}
if(root.value<=temp.value)
{
if(root.right==null)
{
root.right=temp;
}
else
setvalues(root.right, temp);
}
}
static void printDuplicates(ArrayList<Integer> tem1)
{
int pointer1=tem1.get(0), pointer2=0;
for(int x=1;x<tem1.size();x++)
{
if(pointer1==tem1.get(x))
{
pointer2++;
}
else
{
System.out.println(pointer1+"hekllo"+pointer2);
pointer1=tem1.get(x);
pointer2=0;
}
}
}
public static ArrayList<Integer> display(node temp,ArrayList<Integer> tem1)
{
if(temp!=null)
{
display(temp.left, tem1);
tem1.add(temp.value);
System.out.println(temp.value);
display(temp.right, tem1);
}
return tem1;
}
}
class node
{
int value;
node left;
node right;
node()
{
this.value=0;
this.left=null;
this.right=null;
}
}
Do inorder traversal and put each element in an array. Now traverse the array and have 2 vars.
count and lookingFor. Initialize count=1 and lookingFor=a[0] if a is the obtained array.
Now,
int i=1;
while(i<length)//length is array length
{
if(a[i]==a[i-1])
count++;
else
{
cout<<lookingFor<<"is duplicated"<<count<<"times\n";
lookingFor = a[i+1];
count=1;
i++;
}
}
import java.util.*;
class Node{
int value;
Node left=null;
Node right=null;
public Node(int value){
this.value=value;
}
public int get(){
return this.value;
}
public void set(int value){
this.value=value;
}
}
class hashmapResult{
HashMap hm = new HashMap();
}
public class BST {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
System.out.println("Starting...");
System.out.println();
int bstHeight=5;
double totalnumofNode=Math.pow(2, bstHeight)-1;
LinkedList<Node> bst= new LinkedList<Node>();
constructBst(bst,bstHeight,totalnumofNode);
for(int i=0;i<totalnumofNode;i++)
{
if(bst.get(i).left==null||bst.get(i).right==null){
System.out.println("Node " +i +": "+bst.get(i).value+" Left: NULL Right: NULL");
}
else{
System.out.println("Node " +i +": "+bst.get(i).value+" Left: "+bst.get(i).left.value+" Right: "+bst.get(i).right.value);
}
}
printDups(bst);
}
private static void printDups(LinkedList<Node> bst){
hashmapResult hmR= new hashmapResult();
fillHashmap(bst.getFirst(),hmR);
Set entries = hmR.hm.entrySet();
Iterator it = entries.iterator();
while(it.hasNext()) {
Map.Entry me = (Map.Entry)it.next();
System.out.print(me.getKey() + ": ");
System.out.println(me.getValue());
}
System.out.println();
}
private static void fillHashmap(Node root,hashmapResult hmR){
if(root!=null&&root.value!=0){
if(root.left!=null&&root.left.value!=0)
{
fillHashmap(root.left, hmR);
}
Set keys = hmR.hm.keySet();
if(!keys.contains(root.value))
{
hmR.hm.put(root.value,0);
}
else
{
int count=(int)hmR.hm.get(root.value)+1;
hmR.hm.put(root.value,count);
}
if(root.right!=null&&root.right.value!=0)
{
fillHashmap(root.right, hmR);
}
}
}
private static void constructBst(LinkedList<Node> bst, int bstHeight,double totalnumofNode) {
// TODO Auto-generated method stub
Random randomGenerator = new Random();
for(int i=0;i<totalnumofNode;i++){
Node node=new Node(0);
bst.add(node);
}
for(int i=0;i<Math.pow(2, bstHeight-1)-1;i++){
bst.get(i).left=bst.get(i*2+1);
bst.get(i).right=bst.get(i*2+2);
}
for(int i=0;i<10;i++){
int randomInt = randomGenerator.nextInt(5)+1;
insertNode(bst.get(0),randomInt);
}
}
private static void insertNode(Node root,int value){
if(root.value==0)
{
root.value=value;
}
else{
if(root.value>value)
insertNode(root.left,value);
if(root.value<=value)
insertNode(root.right,value);
}
}
}
The given tree in input 2 is NOT a BST. A BST must maintain an invariant that given any node, all nodes in the sub-tree rooted at the given node must follow some kind of order, say all nodes in the left side of the root of the sub-tree must be less than the root (given node) and similarly all nodes from right side of the sub-tree must be greater than the root (given node). For a BT to become a BST this invariant must be true for all sub-trees rooted at all of its nodes. The tree in example 2 doesn’t follow this invariant as it has root 3 which has node 5 on its left. I think ‘pradegup’ has already noticed this anomaly – kudos to him.
However the question can still be valid for either a BT or a BST. In both cases a traversal of tree along with comparing duplicate check and maintaining their count can be done in theta(n) time. In case of BT I think additional memory in the form of hash-table like data structure would be required in maintaining the duplicate key’s count. However for BST we don’t need any additional memory if we maintain a collection of values for duplicate keys ensuring even a duplicate key occurs only once in the tree (but they may have more than one value per duplicate key). Anyway the idea is that with actual implementation of a BST with duplicates the need for additional memory (Hash-table) may go away whereas for BT additional memory is essential.
I believe that’s the indentation problem, input#2 is correct.
At level 4, 3 and 4 are left and right children of 4 respectively. 5 is right child of 4 and another 5 is right child of 5.
This makes it correct BST.
@maveric:
Applying your idea the tree has root 3 which has another 3 as right child which in turn has 4 as right child. This 4 has another 3 as left child. To me this last 3 should not be the left child of 4 rather it should have been the parent of 4. Is there any explanation behind this!! I don't think I'm missing some specific order which might cause such form. Without any proper explanation this would still be a faulty BST.
@buckCherry:
It depends on your insertion algorithm.
Assuming root =3 , its right child=4.
3
\
4
Now if you want to insert 3 to this , where your insertion algorithm would insert it ?
1. One solution would be to insert it as a left child of 4
2. Other solution would be to insert it as right child of 3 and then make 4 as a child of 3 ( i.e. 2nd 3 ).
Irrespective of above two solutions, your tree is a valid BST. It satisfies you invariant i.e. all the nodes in the left side of the root should be less than root and all the nodes in the right side of the root should be greater than or equal to root.
I don’t see the reason you are seeing this as an invalid BST . Are you seeing any property of BST not getting satisfied ?
@maveric:
Yes you're right, the given tree can be considered as a BST.
Note that wikipedia defines a BST only with no duplicate keys even though I don't agree with it. In fact all the authors including "Cormen et al" speak of BST in terms of the invariant I've mentioned.
Thus based on wiki this is not a BST, but based on my invariant and most of the authors this is a valid BST.
Thanks for sticking to your idea and pointing me to my earlier mistake.
int prev = -1;
int count = 0;
print_dup (node *root)
{
if (root != NULL)
{
print_dup(root->left);
if (root->val == prev)
count++;
else
{
if (count > 0)
{
printf (" num:%d, count:%d", prev, count);
count = 0;
}
}
print_dup(root->right);
}
}
Sorry - missed a line
if (count > 0)
{
printf (" num:%d, count:%d", prev, count);
count = 0;
>> prev = root->val;
}
void print_extra_duplicates(node *root)
{
int count = 0;
node *tmp;
if(root == NULL) return;
print_extra_duplicates(root->left);
tmp = root->right;
while(tmp != NULL && root->data == tmp->data)
{
count++;
tmp = tmp->right;
}
if(count)
{
printf("\n Data:%d Extra Duplicate:%d\n", root->data, count);
root = tmp;
if(root == NULL) return ;
}
print_extra_duplicates(root->right);
}
void print_extra_duplicates(node *root)
{
int count = 0;
node *tmp;
if(root == NULL) return;
print_extra_duplicates(root->left);
tmp = root->right;
while(tmp != NULL && root->data == tmp->data)
{
count++;
tmp = tmp->right;
}
if(count)
{
printf("\n Data:%d Extra Duplicate:%d\n", root->data, count);
root = tmp;
if(root == NULL) return ;
}
print_extra_duplicates(root->right);
}
#include<stdio.h>
#include<stdlib.h>
typedef struct node
{
node *left;
int data;
node *right;
};
int inorder_array[20];
int index;
node *insert(node *root, int data);
void print_extra_duplicates(node *root);
void inorder_traverse(node *);
int main()
{
printf("\n Welcome Pankaj....\n");
node *root = NULL;
int n1 =0, sum = 0;
int n,i;
int input[20];
printf("\n Enter size of array=");
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&input[i]);
for(i=0;i<n;i++)
{
root = insert(root, input[i]);
}
inorder_traverse(root);
print_extra_duplicates(root);
return 0;
}
void inorder_traverse(node *root)
{
if(root == NULL) return;
inorder_traverse(root->left);
inorder_array[index++] = root->data;
inorder_traverse(root->right);
}
void print_extra_duplicates(node *root)
{
int count = 0, i;
node *tmp;
for(i = 0; i<index-1; i++)
{
while(inorder_array[i] == inorder_array[i+1])
{
i++;
count++;
}
if(count)
{
printf("\n Data:%d Extra Duplicate:%d\n", inorder_array[i], count);
}
count =0;
}
}
node *insert(node *root, int data)
{
if(root == NULL)
{
root = (node *)malloc(sizeof(node));
root->data = data;
root->left = NULL;
root->right = NULL;
return root;
}
if(root->data > data) root->left = insert(root->left, data);
else root->right = insert(root->right, data);
return root;
}
Keeping totalCount as global variable
private static Node fn2(Node root, Node prev) {
if (root == null) return prev;
prev = fn2(root.left, prev);
if (prev!=null&&prev.data == root.data) {
totalCount++;
} else if(totalCount >0)
{
System.out.println("Node " + prev.data + " totalCount" + totalCount);
totalCount = 0;
}
fn2(root.right, root);
return root;
}
Simply use iterative in-order traversal :
void extra_duplicates(Node root){
Stack<Node> S = new Stack<Node>();
Node current = root;
int prev = -1;
int dups = 0;
do{
while (current.leftChild != null){
S.push(current);
current = current.leftChild;
}
current = S.pop();
if (current.val == prev){
dups++;
}else if {
if (dups >0)
System.out.prinln(curren.val + " : " + dups);
dups++;
prev = current.val;
}
if (current.rightChild != null)
current = current.rightChild;
}while (!S.isEmpty());
return;
}
Easy since the input tree is BST. if we do inorder traversal we will get data in sorted order.
- Amitesh Madhur November 01, 20121. Do inorder traversal
2. Have 2 class member variable prevValue and valueCount
3. while traversing check if node.data == prevValue the increase the count
4. else print the value and count - 1
All set
///
public void printExtraDups(Node root){
//int prev = 0;
if(root != null)
{
if (root.left != null )
printExtraDups(root.left);
if( prevData == root.data) count++;
else System.out.println("Prev: "+prevData+" count: "+(count -1));
prevData = root.data;
if(root.right !=null )
printExtraDups(root.right);
}
}
\\\