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.
