Yahoo Interview Question
Software Engineer / Developersbecause suppose there are many occurrence of an number in BST whenever you find first occurance you just terminate search operation right? so we cant find all occurance of number
dude, we are not storing elements for each occurrence.. instead we store count so an element at any time is stored only once.. so yes bst is good too.. but searching in bst = O(log n) but for hash its O(1)..
we can create a structure like this
struct node{
int n;
int count;
struct node *left;
struct node *right;
};
then we will create a bst
whenever the element will be encountered for the first time then it will be added to the best else the count will be incremented for that particular element
/// Using BST Method
struct Node
{
int val;
int cnt;
Node * left;
Node * right;
Node(int v = 0, int n = 1) : val(v), cnt(n), left(NULL), right(NULL)
{
}
};
Node * insert_bst(Node * root, int v)
{
if(NULL == root) {
Node * r = new Node(v);
return r;
}
Node * cur = root;
while(cur) {
if(cur->val == v) {
cur->cnt ++;
break;
}
else if(cur->val < v) {
if(NULL == cur->right) {
cur->right = new Node(v);
break;
}
cur = cur->right;
}
else {
if(NULL == cur->left) {
cur->left = new Node(v);
break;
}
cur = cur->left;
}
}
return root;
}
hash
- Anonymous September 13, 2010