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 <wsour...@gmail.com> 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 <bagana.bharatku...@gmail.com>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 <wsour...@gmail.com> 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 <
>>> 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.
>>>>
>>>>
>>>>
>>>
>>>
>>> --
>>> 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 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.
>>
>>
>>
>
>
>
> --
> 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 algogeeks+unsubscr...@googlegroups.com.
> 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 algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
