I don't see why you need O(n^2) time for rearranging.
It can be done in O(n log n) if you maintain the index along with every
element.
Then reordering would mean sort as per the indices.
--
Rohit Saraf
Third Year Undergraduate,
Dept. of Computer Scie
list all groups...with their elements
On Sun, Jan 30, 2011 at 12:32 PM, nishaanth wrote:
> so whats the required outputlist all possiblities or anything else? if
> its just this one output...then it sounds trivial
>
>
> On Sun, Jan 30, 2011 at 11:43 AM, snehal jain wrote:
>
>> @nishanth
so whats the required outputlist all possiblities or anything else? if
its just this one output...then it sounds trivial
On Sun, Jan 30, 2011 at 11:43 AM, snehal jain wrote:
> @nishanth
> divide into groups ( not necessarily 2) in as many group as possible.. such
> that elements in each
@nishanth
oh ya right..
On Sun, Jan 30, 2011 at 11:27 AM, nishaanth wrote:
> @snehalno its incorrect..consider the following example
> -2 3
>
> The answer to this problem is the entire array with sum 1.(not the min of
> positive number)
>
>
>
> On Sun, Jan 30, 2011 at 11:00 AM, snehal jai
@nishanth
divide into groups ( not necessarily 2) in as many group as possible.. such
that elements in each group is consecutive
another example to clearify
A= { 9,7, 13, 11,6,12,8,10,3, 4, 2, 16,14,17,13,15)
ans
<9,7,13,11,6,12,8,10>
<3,4,2>
<16,14,17,13,15>
On Sun, Jan 30, 2011 at 11:32 AM, ni
@snehal..i guess you are missing something in the question...divide it into
2 groups such that (there should be some other condition or criterion).
On Sun, Jan 30, 2011 at 11:29 AM, snehal jain wrote:
> my approach
>
> sort in nlogn and then while traversing the array put the elements in a
>
my approach
sort in nlogn and then while traversing the array put the elements in a
group till they are consecutive . when a[i+1]!=a[i]+1 then put a[i+1] in
different group.. now we need to rearrange elements in the group so that
they are according to the given array.. but that will make it O(n^2)
@snehalno its incorrect..consider the following example
-2 3
The answer to this problem is the entire array with sum 1.(not the min of
positive number)
On Sun, Jan 30, 2011 at 11:00 AM, snehal jain wrote:
> a friend of mine was asked this question in google interview..
>
> according to
@Wei.Qi Can you clarify when your algorithm terminates and also what is
the running time of the algorithm ?
On Sun, Jan 30, 2011 at 9:46 AM, yq Zhang wrote:
> can you prove it?
>
> On Jan 29, 2011 6:38 PM, "Wei.QI" wrote:
> >
> > Starting with any pump A, try to finish the circle, if at pum
a friend of mine was asked this question in google interview..
according to me the min element in the array is the answer provided that its
not zero.. as 1 element can also be a subarray. but that would solve the
problem in O(n) only.. ( this is what i understood) am i missing anything..?
please h
can you prove it?
On Jan 29, 2011 6:38 PM, "Wei.QI" wrote:
>
> Starting with any pump A, try to finish the circle, if at pump B that can
not reach pump B+1, it means all pumps from A to B can not finish the circle
(it will go broke at pump B), then just start with B+1. After go through all
the pum
Starting with any pump A, try to finish the circle, if at pump B that can
not reach pump B+1, it means all pumps from A to B can not finish the circle
(it will go broke at pump B), then just start with B+1. After go through all
the pumps start from some pump, we got an answer. if we go back to pump
what do you mean by spiral order ?
On Sat, Jan 29, 2011 at 8:25 PM, bittu wrote:
> Convert BT in to DLL such that DLL represents the Sprial order
> traversal of BT.
>
> "Inplace"
>
> its Written Test Question & They wants Exact Working Code...Not
> Approach..Be Clear..Try to provide best solutio
On Jan 21, 1:05 am, snehal jain wrote:
> In this variation of the Maximum-Sum Subarray Problem, you are given a
> one-dimensional array A[1 : n] of positive or negative numbers, and
> you are asked to find a subarray A[i : j] such that the sum of its
> elements is (1) strictly greater than zero, a
@ Sankalp : plz explain this line of yours : No. of As=A*(total number
of keystrokes) , gives us a bound . We
should have a lower bound as this , we can always get this much As
On Jan 29, 5:32 pm, sankalp srivastava
wrote:
> We can do it Using a binary search approach (The cost function is
> mon
CALL FOR PAPERS
and
Call For Workshop/Session Proposals
SERP'11
The 2011 International Conference on Software
Engineering Research and Practice
Date and Location: Ju
anyone here?
On Fri, Jan 21, 2011 at 2:35 PM, snehal jain wrote:
> In this variation of the Maximum-Sum Subarray Problem, you are given a
> one-dimensional array A[1 : n] of positive or negative numbers, and
> you are asked to find a subarray A[i : j] such that the sum of its
> elements is (1) s
@bittu
offtopic: could you please tell us why do you use uppercase letters in > 50%
of the words?!
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this grou
Convert BT in to DLL such that DLL represents the Sprial order
traversal of BT.
"Inplace"
its Written Test Question & They wants Exact Working Code...Not
Approach..Be Clear..Try to provide best solutions
Thanks & Regards
Shashank " "The best way to escape from a problem is to solve it."
--
Yo
the paper:
http://www.cosc.canterbury.ac.nz/research/reports/MastTheses/2007/mast_0705.pdf
On Jan 29, 3:31 pm, AKO wrote:
> I am a rookie working with algorithms and especially implementing
> them.
>
> Im trying to implement the brute force method using the prefix sum of
> the NxN-array
> I got t
I am a rookie working with algorithms and especially implementing
them.
Im trying to implement the brute force method using the prefix sum of
the NxN-array
I got this piece of code, in which i want to return the sum of maximum
subarray.
prefix sum means that the array {{2, -1},{4, 19}} becomes {{
I'm sure you have misstated the problem statement
just find out the total path length and return the first petrol pump
which gives you the required milage
go greedy
On Jan 28, 5:09 pm, bittu wrote:
> There are N petrol pumps along a circular path. Every petrol pump
> gives some amount of fixed p
We can do it Using a binary search approach (The cost function is
monotonic over here , so we can use binary search)
No. of As=A*(total number of keystrokes) , gives us a bound . We
should have a lower bound as this , we can always get this much As
Take the initial value as high and low as possi
Yuo might wanna check out The latest codeforces beta round problem
C .
On Jan 28, 8:34 pm, nishaanth wrote:
> @All... According to the constraints(SPOJ problem) wont this dp solution
> time out ?
>
> On Tue, Jan 25, 2011 at 12:23 AM, sankalp srivastava <
>
>
>
>
>
> richi.sankalp1...@gmail.com> w
Okay I got it myself
@OP
This can be done in O(n*k*logn)
where k is of order 10^3 at the very max , when u need a prime like 1
trillion
On Jan 28, 6:44 pm, sankalp srivastava
wrote:
> Correct me if I'm wrong , but according to you , will this be the
> approach ?
>
> boolean array[10];
> int
No , actually it's not ... it's O(n^2) , I misunderstood the
"subsequence" thing , it could be discontinuous .. we , then need to
find the maximum of dp[l] ...
the second term makes sure that the sign of the two quantities is
alternating i.e. positive or negative !
On Jan 29, 11:06 am, nishaanth
Yes,it works for binary search tree only
On Sat, Jan 29, 2011 at 2:22 PM, nphard nphard wrote:
> Looks good. I concede that it works for a Binary "Search" Tree.
>
> On Sat, Jan 29, 2011 at 1:35 AM, Ritu Garg wrote:
>
>> @nphard,see the following approach carefully to know *if right pointer is
>>
Looks good. I concede that it works for a Binary "Search" Tree.
On Sat, Jan 29, 2011 at 1:35 AM, Ritu Garg wrote:
> @nphard,see the following approach carefully to know *if right pointer is
> pointing to right child or in order successor*
> *
> *Q = node->right
> IF (Q is not NULL)
> {
>
28 matches
Mail list logo
