Re: [algogeeks] Questions on Hashing ...Share ur ideas...
Solution for Problem 4:
#includeiostream
#define size 10 //size = sizeof(arr);
#define max 8 //max = maxof(arr[])+1;
using namespace std;
int main()
{
int arr[] = {2,4,6,4,6,3,5,1,5,7}, hasharr[max] = {0}, i, sum=8;
for(i=0; isize; i++)
hasharr[arr[i]] = 1;
for(i=0; imax; i++)
{
if((hasharr[i] != 0) (hasharr[sum-i] != 0))
{
couti+(sum-i)=sumendl;
hasharr[i] = hasharr[sum-i] = 0;
}
}
}
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Questions on Hashing ...Share ur ideas...
Problem 1: Remove duplicate elements from an unsorted array of size N
Problem 2: Find intersection of K unsorted array of N elements each.
Intersection consists of elements that appear in all the K arrays.
Problem 3: How to make a linked list support operations in O(1) time. The
operations on linked list can be insertion after any arbitrary valued node,
deletion of any arbitrary valued node
Problem 4: Find all unique pairs of element in an array that sum to S. For
ex. If array = {2,4,6,4,6} and S = 8 then answer is {2,6, 4,4}
Problem 5: Consider an array containing unique elements. Find a triplet of
elements in the array that sum to S (extension of problem 4). Can hashtables
improve the running time of your algorithm.
Problem 6: Consider two strings of size M, N. Perform string matching in
size O(M+N).
Problem 7: Find top K most frequent elements in an array of size N.
Problem 8: Given a file with N integers. Find top K most frequent integers.
Assume N to be very large such that all the N numbers cannot fit into
memory. Design for the worst case.
--
Regards
Kumar Raja
M.Tech(SIT)
IIT Kharagpur,
10it60...@iitkgp.ac.in
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Questions on Hashing ...Share ur ideas...
problem 4.. good question...
With regards,
Praveen Raj
DCE-IT 3rd yr
735993
praveen0...@gmail.com
On Tue, Oct 25, 2011 at 5:57 PM, kumar raja rajkumar.cs...@gmail.comwrote:
Problem 1: Remove duplicate elements from an unsorted array of size N
Problem 2: Find intersection of K unsorted array of N elements each.
Intersection consists of elements that appear in all the K arrays.
Problem 3: How to make a linked list support operations in O(1) time. The
operations on linked list can be insertion after any arbitrary valued node,
deletion of any arbitrary valued node
Problem 4: Find all unique pairs of element in an array that sum to S. For
ex. If array = {2,4,6,4,6} and S = 8 then answer is {2,6, 4,4}
Problem 5: Consider an array containing unique elements. Find a triplet of
elements in the array that sum to S (extension of problem 4). Can hashtables
improve the running time of your algorithm.
Problem 6: Consider two strings of size M, N. Perform string matching in
size O(M+N).
Problem 7: Find top K most frequent elements in an array of size N.
Problem 8: Given a file with N integers. Find top K most frequent
integers. Assume N to be very large such that all the N numbers cannot fit
into memory. Design for the worst case.
--
Regards
Kumar Raja
M.Tech(SIT)
IIT Kharagpur,
10it60...@iitkgp.ac.in
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Questions on Hashing ...Share ur ideas...
First of Happy Diwali 2 all.
For question number 4, this can be done by using a chained hashing
technique along with a valid/invalid bit which wil say it has been
processed or not..
After insertion has been done in the hash table. For finding the unique pairs ..
Iterate over the elements in the original array .
Now set the valid/invalid bit of the present element(p) and now search
for the element (N-p) in the hash table :-
case 1: if N-p element is present then set the valid/invalid bit .
case 2:if not present then repeat the above step for the elements with
valid bit .
This will serve the purpose..
On 10/25/11, praveen raj praveen0...@gmail.com wrote:
problem 4.. good question...
With regards,
Praveen Raj
DCE-IT 3rd yr
735993
praveen0...@gmail.com
On Tue, Oct 25, 2011 at 5:57 PM, kumar raja rajkumar.cs...@gmail.comwrote:
Problem 1: Remove duplicate elements from an unsorted array of size N
Problem 2: Find intersection of K unsorted array of N elements each.
Intersection consists of elements that appear in all the K arrays.
Problem 3: How to make a linked list support operations in O(1) time. The
operations on linked list can be insertion after any arbitrary valued
node,
deletion of any arbitrary valued node
Problem 4: Find all unique pairs of element in an array that sum to S. For
ex. If array = {2,4,6,4,6} and S = 8 then answer is {2,6, 4,4}
Problem 5: Consider an array containing unique elements. Find a triplet of
elements in the array that sum to S (extension of problem 4). Can
hashtables
improve the running time of your algorithm.
Problem 6: Consider two strings of size M, N. Perform string matching in
size O(M+N).
Problem 7: Find top K most frequent elements in an array of size N.
Problem 8: Given a file with N integers. Find top K most frequent
integers. Assume N to be very large such that all the N numbers cannot fit
into memory. Design for the worst case.
--
Regards
Kumar Raja
M.Tech(SIT)
IIT Kharagpur,
10it60...@iitkgp.ac.in
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Somnath Singh
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Questions on Hashing ...Share ur ideas...
On 10/26/11, SAMM somnath.nit...@gmail.com wrote:
First of Happy Diwali 2 all.
For question number 4, this can be done by using a chained hashing
technique along with a valid/invalid bit which wil say it has been
processed or not..
After insertion has been done in the hash table. For finding the unique
pairs ..
Iterate over the elements in the original array .
Now set the valid/invalid bit of the present element(p) and now search
for the element (N-p) in the hash table :-
case 1: if N-p element is present then set the valid/invalid bit .
case 2:if not present then repeat the above step for the elements with
valid bit .
This will serve the purpose..
On 10/25/11, praveen raj praveen0...@gmail.com wrote:
problem 4.. good question...
With regards,
Praveen Raj
DCE-IT 3rd yr
735993
praveen0...@gmail.com
On Tue, Oct 25, 2011 at 5:57 PM, kumar raja
rajkumar.cs...@gmail.comwrote:
Problem 1: Remove duplicate elements from an unsorted array of size N
Problem 2: Find intersection of K unsorted array of N elements each.
Intersection consists of elements that appear in all the K arrays.
Problem 3: How to make a linked list support operations in O(1) time.
The
operations on linked list can be insertion after any arbitrary valued
node,
deletion of any arbitrary valued node
Problem 4: Find all unique pairs of element in an array that sum to S.
For
ex. If array = {2,4,6,4,6} and S = 8 then answer is {2,6, 4,4}
Problem 5: Consider an array containing unique elements. Find a triplet
of
elements in the array that sum to S (extension of problem 4). Can
hashtables
improve the running time of your algorithm.
Problem 6: Consider two strings of size M, N. Perform string matching in
size O(M+N).
Problem 7: Find top K most frequent elements in an array of size N.
Problem 8: Given a file with N integers. Find top K most frequent
integers. Assume N to be very large such that all the N numbers cannot
fit
into memory. Design for the worst case.
--
Regards
Kumar Raja
M.Tech(SIT)
IIT Kharagpur,
10it60...@iitkgp.ac.in
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Somnath Singh
--
Somnath Singh
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
