@srikar : approach2 is wrong. ex: [1, 5, 7, 66, 7, 1, 77] first window [1,5,7] all are unique.....oops!!!!
On Wed, Feb 6, 2013 at 11:31 PM, Srikar <srikar2...@gmail.com> wrote: > *APPROACH 1:* > use a hashtable for both the questions ? > > Insert the integers as they are given in the array into a hashtable. The > structure I am thinking is key (the integer) -> [index]. Once all elements > are inserted. Run through the hashtable and select the one which has > len(value) == 1 and is least, since we want the first unique integer. > > for the second Q, its a more general Q of the first one. In first k=1. > > space: 2O(n) > time: 2O(n) > > *APPROACH2: * > When we say unique, we will have a pattern. Eg: [5, 5, 66, 66, 7, 1, 1, > 77]. In this lets have moving window of 3. first consider (5,5,66). we can > easily estab. that there is duplicate here. So move the window by 1 element > so we get (5,66,66). Same here. move to next (66,66,7). Again dups here. > next (66,7,1). No dups here! take the middle element as this has to be the > first unique in the set. The left element belongs to the dup so could 1. > Hence 7 is the first unique element. > > space: O(1) > time: O(n) > > For seond Q I still think hashtable is best. As the numbers are streamed, > keep inserting. > > > Srikar > > > > On Wed, Feb 6, 2013 at 10:00 AM, navneet singh gaur < > navneet.singhg...@gmail.com> 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 <k.anki...@gmail.com> 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 >> > <navneet.singhg...@gmail.com> 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 algogeeks+unsubscr...@googlegroups.com. >> >> 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 algogeeks+unsubscr...@googlegroups.com. >> > 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 algogeeks+unsubscr...@googlegroups.com. >> 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 algogeeks+unsubscr...@googlegroups.com. > 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
