This is one of the most difficult dynamic programming problem I have
faced so far.
A good discussion on this problem and different solutions can be found
at
http://www.akalin.cx/2007/11/28/finding-the-longest-palindromic-substring-in-linear-time/
_dufus
On Aug 31, 6:01 pm, ankur aggarwal
@Nitin, your algorithm, as you know takes O(n) extra space.
Arguably the next step of the interviewer would be to ask for O(1)
space algorithm :D
_dufus
On Aug 31, 5:37 pm, nitin mathur nitinkumar.mat...@gmail.com wrote:
We can use the concept of longest common substring. For that use
@Anil: I will request you to completly explain the things. Not just
write a bit of code. So what is map and how are
you implementing the insert operation.
-- Forwarded message --
From: Anil C R cr.a...@gmail.com
Date: Mon, Aug 31, 2009 at 7:59 PM
Subject:
@ all. how come it is O(log n). It should be order (height) whcih is
not the O(log n) unless and until tree is not balanced.
On Mon, Aug 31, 2009 at 11:39 AM, Dufusrahul.dev.si...@gmail.com wrote:
Rama, I cannot agree with you more here.
On Aug 31, 5:34 am, Ramaswamy R ramaswam...@gmail.com
@nitin
wat is the complexity ??
can it be done linear ??
On Mon, Aug 31, 2009 at 6:07 PM, nitin mathur
nitinkumar.mat...@gmail.comwrote:
We can use the concept of longest common substring. For that use following
steps:
1) take the original string say A.
2) make a copy of it say B.
3)
Yup, my bad.
Its not O(logn) but O(n) algorithm to find median.
Shishir, are you sure that your algorithm will emit K elements CLOSEST
to median?
_dufus
On Aug 31, 12:56 pm, Shishir Mittal 1987.shis...@gmail.com wrote:
First find the median of the array in O(n) time using *'Linear general
there is an array with m elements...
it is known that first n elements are sorted... but dont know what is
'n' nm
given an element x find whether x is there in sorted elements.
Can this be done in O(log n)??
--~--~-~--~~~---~--~~
You received this message
* Q.3: Given a set of 1 Trillion integers on hard disk, find the smallest 1
million of them. You can fit at most 1 million integers in memory at a time.
State the fastest solution you can think of.
--~--~-~--~~~---~--~~
You received this message because you are
Given a chessboard in which u dont know how the black and white boxes
are arranged but this is sure that there will 32 black squares and 32
white squares.You have to find the least possible disatnce between any
two sqaures of same colour ...
--~--~-~--~~~---~--~~
On Tue, Sep 1, 2009 at 6:04 PM, ankur aggarwal ankur.mast@gmail.comwrote:
@shishir
i could *not *understand
cann u give an example..
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
Brute force, pick all combinations and keep track of minimum difference.
Complexity: O(n^2) - (n-1)+(n-2)+(n-3) ... 1
A little better, use any of the O(nlog n) sorting algorithm. In O(n) compare
adjacent pairs and find the minimum difference. Complexity O(nlog n).
On Tue, Sep 1, 2009 at 6:05 AM,
one simple brute force method I see is that sort the array with the best
possible time complexity and then take the difference between the two middle
most if n is even or compare the difference between the adjacent and middle
element and take the lower is n is odd.
On Tue, Sep 1, 2009 at 6:35 PM,
Sort the array and find the minimum of difference of adjacent values of the
sorted array.
Time Complexity : O(nlogn), Space Complexity : O(1)
On Tue, Sep 1, 2009 at 6:35 PM, ankur aggarwal ankur.mast@gmail.comwrote:
given a array of length n. find 2 number such that their differnce is
@all: Yah it's 100% true that for 32 white and 32 black we have min
distance at 0.
But question will become difficult when the number of white
and blacks are less than 32.
-Nagendra
On Tue, Sep 1, 2009 at 9:30 PM, Ramaswamy Rramaswam...@gmail.com wrote:
If the white and the black
@Nagendra : As earlier told Refer Pg 189, Cormen, an algorithm is given to
find the Kth largest element in O(n) *worst* time complexity.
@Dufus: yeah, am pretty sure that the algorithm I have described results in
K closest elements to median.
For e.g. Let the array be 2 5 7 10 11 14 19 45 121
I thnik the statement is : a node cannot be locked of any of its
ancestors and descendents are locked.
On Tue, Sep 1, 2009 at 8:21 PM, ankur aggarwalankur.mast@gmail.com wrote:
@narendra..
i think ques need to recheck becoz the statement u r giving A node cannot
be locked if any of its
Build MAX-HEAP for first 1 million integers.
For next elements in the array,
if ele root node value, replace ele with root node value and apply
MAX-HEAPIFY
Time Complexity : NlogK , where N is total no of elements and K is the size
of heap. Here N is 1 trillion and K is 1 million
Space
17 matches
Mail list logo
