monj021
BAN USERheap would be the most suitable implementation for this problem,
but using a BST,i think traversing in reverse inorder might solve the problem
the steps would be
1.construct the BST as when the values arrive with arrival time as the key value along with necessary balancing at each step(otherwise no point in using bst and it will end up to be a linked list).
2.do reverse inorder traversal(this will print the values in decreasing order equivalent to a stack pop operation)
order would be O(nlogn)
please correct me if i am wrong!!
how about doing an inorder traversal of the nodes,inorder traversal will give the birthdates in sorted order.this problem can be divided into three subproblems
1.construct hash table for birthdays and corresponding customer names
2.construct a binary search tree with the birthdays(O(nlogn))
3.Traverse and print O()
{void find_cust(ptr)
{
find_cust(ptr->left);
print(HashTable[F(ptr->birthdate)]); //F=hash function
find_cust(ptr->right);
}}
overall complexity would be O(nlogn)
sorry this is the correct code.....
- monj021 November 03, 2009void reverse(int m)
{
int n=0;
for(i=0;i<32;i++)
{
n<<=1;
n=n|(m&1);
m>>=1;
}
}