Guys, Why can't we simply use a hashset for both the questions. hash the arr[i] and the frequencies in the hash map in the first pass. Then iterate over the array to find the first arr[i] whose freq is 1 in the hash map. For second part, keep a count and find the kth element in the array whose freq in the hashmap is 1. *Pralay MS-Comp Sci* *Univ of California*
On Thu, Feb 7, 2013 at 8:16 PM, bharat b <[email protected]>wrote: > @sourabh : how do u find whether the element in stream gets repeated in > heap.--> O(n) time...totally its O(nk) algo .. > > If we maintain max-heap with BST property on index, then it would be > O(nlogk). > > > On Wed, Feb 6, 2013 at 12:25 PM, sourabh jain <[email protected]> wrote: > >> for 2nd question you can make a heap with their index as a factor to >> heapify them. whenever a integer in stream gets repeated you just nead to >> remove it from heap and heapify it. >> >> >> On Wed, Feb 6, 2013 at 10:00 AM, navneet singh gaur < >> [email protected]> wrote: >> >>> nice algo ankit, so it will be nlogn using O (n) space only. What abt >>> 2nd Q., which have a big online stream. >>> >>> On Mon, Feb 4, 2013 at 9:30 PM, kumar ankit <[email protected]> wrote: >>> > For 1: >>> > i think you can use sorting, sort the array and keep the indices of the >>> > numbers in the sorted list. >>> > Now traverse the sorted list and in the sorted list you need to find >>> the >>> > unique number with the >>> > minimum index which is easy to find. >>> > >>> > Eg: Array: 5 3 1 2 4 1 4 >>> > Indices: 0 1 2 3 4 5 6 >>> > >>> > >>> > After sorting : Array: 1 1 2 3 4 4 5 >>> > Indices: 2 5 3 1 4 6 1 >>> > >>> > Now you can see the unique number with lowest index is 3(index=1). So >>> , you >>> > have your answer. >>> > >>> > >>> > On Mon, Feb 4, 2013 at 3:45 PM, navneet singh gaur >>> > <[email protected]> wrote: >>> >> >>> >> 1. Given a array,find a first unique integer. >>> >> 2. Integers are coming as online stream,have to find a kth unique >>> integer >>> >> till now. >>> >> >>> >> For 1. >>> >> >>> >> Even we cannot use sorting for solving this as if we sort it than our >>> >> first number which is non-repetitive changes. >>> >> >>> >> The best I am able to do is nlogn using a space of O( n ). >>> >> >>> >> For 2. No idea >>> >> >>> >> -- >>> >> You received this message because you are subscribed to the Google >>> Groups >>> >> "Algorithm Geeks" group. >>> >> To unsubscribe from this group and stop receiving emails from it, >>> send an >>> >> email to [email protected]. >>> >> For more options, visit https://groups.google.com/groups/opt_out. >>> >> >>> >> >>> > >>> > >>> > >>> > >>> > -- >>> > Kumar Ankit >>> > Senior Undergraduate >>> > Department of Computer Engineering >>> > Institute of Technology >>> > Banaras Hindu University >>> > Varanasi >>> > Ph: +91 9473629892 >>> > >>> > -- >>> > You received this message because you are subscribed to the Google >>> Groups >>> > "Algorithm Geeks" group. >>> > To unsubscribe from this group and stop receiving emails from it, send >>> an >>> > email to [email protected]. >>> > For more options, visit https://groups.google.com/groups/opt_out. >>> > >>> > >>> >>> >>> >>> -- >>> navneet singh gaur >>> >>> -- >>> You received this message because you are subscribed to the Google >>> Groups "Algorithm Geeks" group. >>> To unsubscribe from this group and stop receiving emails from it, send >>> an email to [email protected]. >>> For more options, visit https://groups.google.com/groups/opt_out. >>> >>> >>> >> >> >> -- >> Regards, >> Sourabh Kumar Jain >> +91-8971547841 >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To unsubscribe from this group and stop receiving emails from it, send an >> email to [email protected]. >> For more options, visit https://groups.google.com/groups/opt_out. >> >> >> > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to [email protected]. > For more options, visit https://groups.google.com/groups/opt_out. > > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. For more options, visit https://groups.google.com/groups/opt_out.
