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 <[email protected]> wrote: > problem 4.. good question... > > With regards, > > Praveen Raj > DCE-IT 3rd yr > 9999735993 > [email protected] > > > > On Tue, Oct 25, 2011 at 5:57 PM, kumar raja <[email protected]>wrote: > >> 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, >> [email protected] >> >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to [email protected]. >> To unsubscribe from this group, send email to >> [email protected]. >> 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 [email protected]. > To unsubscribe from this group, send email to > [email protected]. > 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 [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
