Given three lists: A, B and C of length n each. Write a function which returns true if any 3 three numbers (1 from each list), sum up to zero. Else return false, if there is no such combination.
Time Complexity O(n^3) for your solution. Here is another thought
Make a Hash Map for sum of all the elements of first two Linked Lists. Now traverse the third list, for each element M (of third list), look for -M in Hash Map, if found return true.
while(p!=null){ while(q!=null){ int d=p->value+q->value;
By doing this you are computing sum of all pairs of two linked list.this is done in o(n^2). You add these elements in a hash map which takes o(1) time. Now traverse through the third linked list and for every element search for collision which again will take constant time. so whole algo will take o(n^2) time.
for hashing you can look at wikipedia. let's take a brief intro how insertion and lookup takes o(1) time.
Basically, a hash table is an array containing all of the keys to search on. The position of each key in the array is determined by the hash function, which can be any function which always maps the same input to the same output. We shall assume that the hash function is O(1).
So when we insert something into the hash table, we use the hash function (let's call it h) to find the location where to put it, and put it there. Now we insert another thing, hashing and storing. And another. Each time we insert data, it takes O(1) time to insert it (since the hash function is O(1).
Looking up data is the same. If we want to find a value, x, we have only to find out h(x), which tells us where x is located in the hash table. So we can look up any hash value in O(1) as well.
Implement a function getbits, that returns the(right adjusted) n bits that begin at position p of an integer. Assume bit position 0 is at the right end and that n and p are sensible positive values.
You are given n real numbers in an array. A number in the array is called a decimal dominant if it occurs more than n/10 times in the array. Give an O(n) time algorithm to determine if the given array has a decimal dominant.
const char * (node*p,node *q,node *r){
ReplyDeletewhile(p!=null){
while(q!=null){
int d=p->value+q->value;
while(r!=null){
if(-d==r->value)
return "true";
else
r=r->next;
}
q=q->next;
}
p=p->next;
}
return "false";
}
Time Complexity O(n^3) for your solution.
ReplyDeleteHere is another thought
Make a Hash Map for sum of all the elements of first two Linked Lists. Now traverse the third list, for each element M (of third list), look for -M in Hash Map, if found return true.
i hv very less idea about the hash map. can you please elaborate the method?
ReplyDeletewhile(p!=null){
ReplyDeletewhile(q!=null){
int d=p->value+q->value;
By doing this you are computing sum of all pairs of two linked list.this is done in o(n^2).
You add these elements in a hash map which takes o(1) time.
Now traverse through the third linked list and for every element search for collision which again will take constant time.
so whole algo will take o(n^2) time.
for hashing you can look at wikipedia.
ReplyDeletelet's take a brief intro how insertion and lookup takes o(1) time.
Basically, a hash table is an array containing all of the keys to search on. The position of each key in the array is determined by the hash function, which can be any function which always maps the same input to the same output. We shall assume that the hash function is O(1).
So when we insert something into the hash table, we use the hash function (let's call it h) to find the location where to put it, and put it there. Now we insert another thing, hashing and storing. And another. Each time we insert data, it takes O(1) time to insert it (since the hash function is O(1).
Looking up data is the same. If we want to find a value, x, we have only to find out h(x), which tells us where x is located in the hash table. So we can look up any hash value in O(1) as well.
Thanks for all your efforts...really helpful.
ReplyDeletethnx buddy..:)
ReplyDelete