@Rashmi: I did not get your approach. I do not get emails from the group just in case you have posted a solution :( What do you mean by keeping a count? Also, are you using a hashmap? If yes, whats ur K,V? #Pralay
On Tue, Feb 12, 2013 at 10:00 AM, rashmi i <[email protected]> wrote: > Hey Pralay, > Sorry, if I have missed any point.Why would we need to map the > frequencies when the second problem can be solved by simply keeping a count > and comparing the index values that have been already mapped. > > > On Fri, Feb 8, 2013 at 11:19 AM, sourabh jain <[email protected]> wrote: > >> One solution for the 2nd question can be LinkedHashMap (linked list + >> hashmap) . >> Store the integer in linked list in the order of occurrence in stream and >> make an entry in hashmap on first occurence. Delete the integer entry from >> linked list on 2nd occurence and replace the reference with some special >> value so for 3rd time no need to touch the linked list. while printing the >> result print first k integers from linked list. >> >> >> On Fri, Feb 8, 2013 at 9:46 AM, 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. >>> >>> >>> >> >> >> >> -- >> 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. >> >> >> > > > > -- > R@$!-! > "DoN'T LimIt Ur cHaLlEngeS, ChAlLenGe uR LImItS." > > -- > 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.
