No it will be O(n).
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14
--
You received this message because you are subscribed to the Google Groups
Algorithm
Tokenization is done in linear time. Just save the words in an list (And
what makes you think of non-linearity in tokenization!)
And then iteration over the tokens is trivially linear.
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer
Actually he means the case when you implement quicksort using stacks.
--
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14
--
You received this message because you
.
Dynamic programming is a more general approach which is generally used when
there is optimal substructure and has mostly found use in doing exponential
looking problems in polynomial time.
i hope u understood
--
Rohit Saraf
Second Year Undergraduate
If you make it unsigned short int.. then it goes to 65535 on g++/gcc
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14
--
You received this message because you
Ok. so you have a list.
Iterating over it is linear isn't it?
Ahh... you will need a doubly linked list or an arraylist.does it solve ur
prob?
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http
oh... why did u put %u.
i did not even notice that :P
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14
--
You received this message because you
What makes you think it is O(n^3).
I did not read the code one but divya's solution seems to be O(n^2)
for worst case.
--
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in
Just read your code. It wont even work.
Do you assume only one even length palindrome!?
--
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14
--
You received
Can u elaborate on the 2nd step.
btw, did u understand my soln?
--
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14
--
You received this message because you
This is almost the most basic dp. Read some of the examples from eva
tardos. That would help.
--
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14
--
You received
@jitendra: How can you say that no polynomial algo can be found. I think you
are wrong.
A simple memoized formulation will make this polynomial because of the
optimal substructure..
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science
Oh i am talking only about printing the total number of solutions...
If you backtrack... Obviously it would not be polynomial
--
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http
if you short the larger one first, then the smaller one will be in the
stack for a long time. Which is wasting stack space.
Now stop shorting and start sorting ! :)
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
Make a hashmap... Any problem doing that?
--
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14
--
You received this message because you are subscribed
What precisely did you not understand??
--
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14
--
You received this message because you are subscribed to the Google
Have you posted the same question twice or i am feeling sleepy?
--
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14
--
You received this message because you
Exactly that's what you need to do.
--
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14
--
You received this message because you are subscribed to the Google
@divya: but still haven't you seen Jagadish's example? It is a
counterexample to your greedy approach.
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14
--
You
Still the solution will be similar and actually a bit simpler.
--
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14
--
You received this message because you
A*(B+C*D)
--
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group
So there is a prob algoose A*(B*C) and a*(b*c+d)
i hope you understood
--
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14
--
You received this message
why don't you make use of the optimal substructure.
You can easily use the recurrence relation as DP
@all : people don't just paste your code. Words are better than code
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this
!
--
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com
at
http://groups.google.com/group/algogeeks?hl=en.
--
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14
--
You received this message because you are subscribed
+200)-500)abs((2000)-(500+200))
so we ll put 200 in array B. now since B has n/2 elements rest of the
element goes to array which is 1.
so the ans is
A={2000,1}
b={500,200}
On 15 May 2010 19:10, Rohit Saraf rohit.kumar.sa...@gmail.com wrote:
so what will ur algo give for array
}
the difference is 40
the correct ans:
A = { 110, 100 , 10 }
B = { 90 , 70 , 60 }
the difference is 0
i don't believe a greedy algorithm would work for this problem!
On Mon, May 17, 2010 at 5:06 PM, Rohit Saraf
rohit.kumar.sa...@gmail.comwrote:
@divya : descending order sorting works
@Navin: and that works ! :)
@all : i am sure no heuristic/greedy strategy can be applied.
@divya : did you check your array partitioning algorithm with my example !
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
suggesting will be polynomial.
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14
--
You received this message because you are subscribed to the Google Groups
Algorithm
@anurag : won't work
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks
Read it up : http://www.eecs.umich.edu/~qstout/pap/CACM86.pdf
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14
--
You received this message because you
@Nikhil : For that size of subtrees at all nodes needs to be maintained. And
in that case this is a trivial problem.
@Sathaiah : See my solution :)
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http
/2 where n is
the no. of elements in the given aaray. then store rest element in the
other array.
5. repeat step 5 until both array A n B get n/2 elements..
hope my approach is clear and correct.
comments are welcomed.
On 15 May 2010 08:47, Rohit Saraf rohit.kumar.sa...@gmail.com wrote
.
--
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send
.
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send
A simple DP should work. Should it not?
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14
On Fri, May 14, 2010 at 4:15 PM, Sathaiah Dontula don.sat
I think... it will work :)
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14
On Fri, May 14, 2010 at 2:20 PM, divya sweetdivya@gmail.com wrote:
Given a graph's
hmmm i already realised that and even mailed that before :)
and if we want to use constant space do not make an array. the bst
itself is good enough to do what we are doing.
On 5/14/10, anna thomas annathoma...@gmail.com wrote:
@rohit: Divya's soltn works in this way, if the sum of 2 nos
to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
--
Rohit Saraf
Second
exactly ..
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14
On Fri, May 14, 2010 at 10:07 AM, vignesh radhakrishnan
rvignesh1...@gmail.com wrote
This was also asked in my Yahoo! Interview this year. :)
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14
On Fri, May 14, 2010 at 10:10 AM, Rohit Saraf
i guess the rotation solution i gave will take O(n) with the list as
well
(btw.. u can convert a list to array :P)
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in
are forget abt representation. It can be stored as string anyways.
Tail recursion is awesome at times !
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14
On Mon
1) Make the middle element the root.
Recursively make the left and right subtrees from the left and right
halves of the link list.
2) Implement balanced insertion in trees (via rotations on every step...).
Now insert each element
--
Rohit Saraf
google it... u will gt it
i am on mobile... cannot explain now..
On 5/2/10, divya jain sweetdivya@gmail.com wrote:
wat is tail recursion plz explan in detail
On 2 May 2010 08:15, Rohit Saraf rohit.kumar.sa...@gmail.com wrote:
@divya use tail recursion and rest should be fine
It cannot just be partitioned in such a manner that the middle element
is *always
*the mode !
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14
On Thu, Apr 15, 2010
say u choose the last value as pivot
1 1 1 1 1 1 1 (499 times) 2 2 2 2 1 1 3 3 3 3 (499 times) 4
4 is your pivot
try out
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http
, vivek bijlwan viv...@gmail.com wrote:
@rohit : thats more than 1000 elements in the array
On Thu, Apr 15, 2010 at 7:48 PM, Rohit Saraf
rohit.kumar.sa...@gmail.comwrote:
say u choose the last value as pivot
1 1 1 1 1 1 1 (499 times) 2 2 2 2 1 1 3 3 3 3 (499 times) 4
4 is your
the array exactly once = O(n)
= O(n) solution.
And it cannot be made better !
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14
On Wed, Apr 14, 2010 at 4:14 PM, Gauri
(n)
solution has been identified, using the median of medians algorithm. A
heap would be O(n ln k).
Dave
On Apr 14, 4:25 am, Ashish Mishra amishra@gmail.com wrote:
can't we build a min-heap (kinda opposite of max-heap) ??
On Wed, Apr 14, 2010 at 8:42 AM, Rohit Saraf
rohit.kumar.sa
for an algorithm to find the mode in O(n) worst
case time complexity.
On Wed, Apr 14, 2010 at 6:33 PM, Rohit Saraf
rohit.kumar.sa...@gmail.comwrote:
O(n log n) will be trivial.
O(n) is required at any cost. (Consider the case with 501 1s and 499
0's)
Ok, so u can make a hashmap with your integer
@rizwan : Think!!. *my algorithm is worst case O(n)*..
no doubt !
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14
On Wed, Apr 14, 2010 at 10:01 PM, sharad
...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Sent from my mobile device
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http
united.
find the one with count500
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14
On Thu, Apr 15, 2010 at 9:16 AM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote:
I
are yaar... i meant BST... i thought that was obvious !
sry if i confused you
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14
On Mon, Apr 12, 2010 at 12:38
I have already given an O(n) solution. See above !
The BST solution is O(nlogn) but is practically more nice. :)
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14
Find the kth element using order statistics - O(n)As far as i know , u
will have to use median of medians selection algorithm for this...
Rest is fine..
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT
Time complexity is O(n log n). But the last solution I gave has O(n).
What did u not understand abt thesolution
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14
once u get kth element , u can find first k by a linear travel through the array
On 4/11/10, Priyanka Chatterjee dona.1...@gmail.com wrote:
On 11 April 2010 11:06, Rohit Saraf rohit.kumar.sa...@gmail.com wrote:
I realised now that it can be done easily as :
we can find the kth largest
but still the binary tree solution is of more practical use.i will
explain the solution once i reach my comp
On 4/11/10, Nikhil Agarwal nikhil.bhoja...@gmail.com wrote:
On Sun, Apr 11, 2010 at 9:56 PM, Rohit Saraf rohit.kumar.sa...@gmail.com
wrote:
Time complexity is O(n log n
What do u mean by y u need backtracking
DP needs backtracking to reconstruct the solution.
-Rohit
On Sat, Apr 10, 2010 at 3:27 PM, Ashish Mishra amishra@gmail.comwrote:
y u need backtracking
i think it can be done with DP
On Sat, Apr 10, 2010 at 9:12 AM, «« ÄÑÜJ »» anujlove
why don't you remove all even numbers from consideration and add 2
explicitly. I think that would help.
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14
On Sun
Construct a binary tree from the data (maintain the size of subtree under
each node).
Do rotations till the left subtree does not have size k. Rotation is a
constant time operation.
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science
hmm... that can always be done !
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14
On Wed, Mar 24, 2010 at 6:24 PM, Dave dave_and_da...@juno.com wrote:
Please
?
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14
On Sun, Apr 11, 2010 at 10:46 AM, Rohit Saraf
rohit.kumar.sa...@gmail.comwrote:
Construct a binary tree from the data (maintain the size of subtree under
each
of red.
Now modify the weights of green as = original weight - max weight of the red
that can be replaced on adding this in the cycle formed.
Include the min wt green edge.
Proof trivial
-Rohit
On Sat, Apr 3, 2010 at 11:38 PM, shruti s shrutia...@gmail.com wrote:
Hi,
Please help me
it would be better that O(n). !!
-Rohit
On Wed, Mar 31, 2010 at 4:59 AM, Priyanka Chatterjee dona.1...@gmail.comwrote:
Design an efficient algorithm to report all the points within x1 and x2
from a list of N integers.
What data structure will you use to implement this algorithm?
Find
sorry, i forgot to see *singly* linked list.
what about doing a topological sort and returning the middle element.
-Rohit
On Sun, Mar 28, 2010 at 11:54 AM, Rohit Saraf
rohit.kumar.sa...@gmail.comwrote:
@sanjana: but what in case of 1-2-3-1-4-5-6
-Rohit
On Sat, Mar 27, 2010 at 11:19
sry... i got confused
-Rohit
On Sun, Mar 28, 2010 at 3:14 PM, saurabh gupta sgup...@gmail.com wrote:
@Rohit we have a cycle here
On Sun, Mar 28, 2010 at 2:42 PM, Rohit Saraf
rohit.kumar.sa...@gmail.comwrote:
that is topologcall sort
On 3/28/10, saurabh gupta sgup...@gmail.com wrote
anyways.. the solution becomes still more trivial...
as there can be only one cycle remove it easily and that helps to find
the centre.
-Rohit
On Sun, Mar 28, 2010 at 4:12 PM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote:
sry... i got confused
-Rohit
On Sun, Mar 28, 2010 at 3:14 PM
Even when you are writing a recursive function.. you are not using one
stack.
One stack is yours. Other used for recursion.
Making queue from a single stack = Making turing machine from CFG.
-Rohit
On Wed, Mar 24, 2010 at 9:18 AM, chitta koushik
koushik.infin...@gmail.comwrote:
Can we
try using dynamic programming approach
k length path from v = k-1 length subproblem from all of v's neighbours.
(and yes you will have to keep some pointers to ensure that it remains a
path (if u want simple path).
-Rohit
On Sun, Dec 27, 2009 at 8:35 AM, me13013 me13...@gmail.com wrote
once u do that.. the solution is trivial :P
-Rohit
On Mon, Mar 8, 2010 at 5:54 PM, Nikhil Agarwal nikhil.bhoja...@gmail.comwrote:
On Mon, Mar 8, 2010 at 5:04 PM, Rohit Saraf
rohit.kumar.sa...@gmail.comwrote:
can we assume that we have the sizes of subtree rooted at all nodes in our
With only these 2 constraints you can just insert the root of smaller tree
into bigger one and using rotations bring it to leaf.
Now attach the left and right subtrees to the inserted node.
Expected O(log n) Worst O(n)
Space O(1)
-Rohit
On Mon, Mar 8, 2010 at 5:14 AM, lalit gera lalitger
The answer is simply : (N-1) Choose (k-1)
-Rohit
On Sun, Mar 7, 2010 at 2:11 PM, naga vinod kumar
vinodkumark...@gmail.comwrote:
How to solve this problem
http://www.codechef.com/problems/MARBLES/
K.Naga Vinod Kumar
--
You received this message because you are subscribed
= 1; i = k; i++)
accum = accum * (n-k+i) / i;
return accum + 0.5; // avoid rounding error
}
call choose(n-1,k-1);
-Rohit
On Sun, Mar 7, 2010 at 2:49 PM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote:
The answer is simply : (N-1) Choose (k-1)
-Rohit
On Sun, Mar 7, 2010 at 2
It's difficult and boring(:P) to go through the code...
better give ur logic..
-Rohit
On Sun, Mar 7, 2010 at 3:04 PM, B |_ /\ C |--D ! /\ /\/\ O /\| D
patidarc...@gmail.com wrote:
/ this is the problem of finding first K and last k of N^N but i am
failling somewhere what's wrong thing
even my code would work if u make everything long long... i guess..
-Rohit
On Sun, Mar 7, 2010 at 3:15 PM, B |_ /\ C |--D ! /\ /\/\ O /\| D
patidarc...@gmail.com wrote:
long long r=N-KK?(N-K):K;//chose small to miimize the loop
int n=N-(N-r)+1;
r=1;
long long res=1;
for(long long i=n;i
@sharad : yes... prime number generation for RSA :P
-Rohit
On Sun, Mar 7, 2010 at 3:19 PM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote:
even my code would work if u make everything long long... i guess..
-Rohit
On Sun, Mar 7, 2010 at 3:15 PM, B |_ /\ C |--D ! /\ /\/\ O /\| D
patidarc
a; cina;
20. for(int i=0;ia;i++){
21. long int n,k;
22. cinn; cink;
23. coutchoose((float)n-1,(float)k-1)endl;
24. }
25. return 0;
26. }
-Rohit
On Sun, Mar 7, 2010 at 3:22 PM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote:
@sharad : yes... prime
There are n men. And you have been given say m information's like :
m_i was born after m_j died
m_i talked to m_j sometime
You need to find the consistency of the sets of information in O(n+m).
-Rohit
--
You received this message because you are subscribed to the Google Groups
hmmm i fgured it out
-Rohit
On Thu, Feb 11, 2010 at 12:03 PM, Miroslav Balaz gpsla...@googlemail.comwrote:
EASY!
2010/2/10 Rohit Saraf rohit.kumar.sa...@gmail.com
There are n men. And you have been given say m information's like :
m_i was born after m_j died
m_i talked to m_j
everywhere above.
I guess you will be able to do the reasoning part now
Rohit Saraf
Sophomore
IIT Bombay
---
http://www.cse.iitb.ac.in/~rohitfeb14
On Tue, Feb 9, 2010 at 8:03 PM, suganya c sugu18901...@gmail.com wrote:
can u help with the solution for this problem.??
You’re doing some stress
rewarding in what sense?
-Rohit
On Tue, Feb 2, 2010 at 8:28 PM, vivek bijlwan viv...@gmail.com wrote:
you want it rewarding , go to codechef.com
On Tue, Feb 2, 2010 at 6:30 PM, Anurag Bhatia abhati...@gmail.com wrote:
www.projecteuler.net has some interesting problems.
On Tue, Feb 2
uva online judge
-Rohit
On Wed, Feb 3, 2010 at 8:45 AM, Dheeraj Jain dheerajj...@gmail.com wrote:
Please go through the site http://geeksforgeeks.org/
I recently found the site. This is a great site as this provides well
organized and well coded solutions for generally asked interview
:= uv.destination
*if* u.distance + uv.weight v.distance:
*error* Graph contains a negative-weight cycle
Rohit Saraf
Sophomore
Computer Science and Engineering
IIT Bombay
On Mon, Dec 14, 2009 at 11:40 AM, vicky mehta...@gmail.com wrote:
What is the difference between Dijkstra's
to allow negative weights
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options,
i guess using a fibonacci heap would be a much better idea..
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
if you don't know abt fibonacci heaps then check out
http://en.wikipedia.org/wiki/Fibonacci_heap
Rohit Saraf
Sophomore
Computer Science and Engineering
IIT Bombay
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send
similar.
Rohit Saraf
Sophomore
Computer Science and Engineering
IIT Bombay
On Wed, Dec 9, 2009 at 4:49 PM, Mayur mayurhem...@gmail.com wrote:
We have a server hit by millions of users. Sever log files contains
the user ids of all of them. How do we find the frequency of login of
each user
@manisha: yes you are right. if search is the primary operation done by the
server, then B+ is obviously better..
Rohit Saraf
Sophomore
Computer Science and Engineering
IIT Bombay
On Wed, Dec 9, 2009 at 7:48 PM, Aditya Shankar iitm.adityashan...@gmail.com
wrote:
Hi,
On Wed, Dec 9, 2009
do it iteratively either by:
1) If size of left tree is less than k, rotate the tree left. and so on till
.single while loop required for this.
or
2) Start from head, if k is more than size of left-tree, go to left and
continue searching.. other wise go right and search for k-size(left)-1 in
search for
Tiger tree hash !!
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more
u can maintain the size..
and if you don't want that , at least memoize it.. it won't be O(n^2) then.
Rohit Saraf
Sophomore
Computer Science and Engineering
IIT Bombay
On Wed, Dec 9, 2009 at 9:12 PM, chitta koushik
koushik.infin...@gmail.comwrote:
Though i couldn't get both ur approaches
You can maintain the size. or it can be computed in at worst linear time.
In first method, the only difference is that it will make the kth smallest
element the root of the tree. When in 2nd method it goes to left, in first
method it will also go to left but rotate the tree right.
Rohit Saraf
check this out.. an efficient algorithm to balance a binary tree in linear
time and space.
The other famous algorithm(easier one) by sedgewick does not give O(n) but
average case linear time.
http://www.eecs.umich.edu/~qstout/pap/CACM86.pdf
Rohit Saraf
Sophomore
Computer Science and Engineering
@prakhar: If k=size, you would iterate over whole of the tree, which you can
see is not required.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group,
i have got the O(n^2) solution.
I will post it by night whenever i get to my comp.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
Arun's idea was what i tried for the nxm version of this problem.
And the log(n) wala is not correct for sure.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe
201 - 300 of 317 matches
Mail list logo