[algogeeks] Re: Find longest palindrom in a give n string in O(N)
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 ankur.mast@gmail.com wrote: @abhijeet dryrun on this abbaabba On Mon, Aug 31, 2009 at 5:45 PM, Abhijeet Kumar abhijeet.k.s...@gmail.comwrote: u can push the string onto a stack ... so last element will be on top ... den u can pop out element and compare ... if u have 2 or more set of palindromes .. u can keep a counter and keep a check on dat... --~--~-~--~~~---~--~~ 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 group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Find longest palindrom in a give n string in O(N)
@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 following steps: 1) take the original string say A. 2) make a copy of it say B. 3) find the longest common substring of them. Nitin Mathur --~--~-~--~~~---~--~~ 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 group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
Fwd: [algogeeks] Re: String- Anagrams.
@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: [algogeeks] Re: String- Anagrams. To: algogeeks@googlegroups.com If you have time for pre-processing, you can do this: for each string t in dictionary: s = sort(t) map[s].insert(t) so for printing anagrams of x, we'd just print the contents of map[sort(x)] --~--~-~--~~~---~--~~ 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 group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: N-Ary Tree and Resource management
@ 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 wrote: When we talk of a binary search tree having O(log n) complexity for search, that does assume that the tree is fairly balanced. And of course the that fact we talk of average case. For any tree the worst case would be at least O(n). The whole advantage of using a tree in the 1st place lies in the fact that operations can be done in O(log n) in average case. I don't know of any algo that can do it in O(log n) worst case! :) On Sun, Aug 30, 2009 at 5:05 PM, Dave dave_and_da...@juno.com wrote: When you say that checking if any of the ancestors is O(n log n) are you assuming that the tree is balanced? It wouldn't be O(n log n) if the tree degenerates into a linked list, would it? So what is your justification in assuming balance? Dave On Aug 30, 6:01 pm, Ramaswamy R ramaswam...@gmail.com wrote: To begin with I find the invariant doesn't hold in the system progressively. Forget about islock and assume that we only do lock / unlock. Given that a node cannot be locked if any of its descendants / ancestors is locked. It is never possible for the tree to enter a state where any of the descendant of a locked node is locked. If that invariant holds then all we need to check is if any of the ancestors are locked, which is O(log n). O(1) would either require hash table (and O(n) storage) unless we choose to replicate the lock state in all of the ancestors as well (which is a pretty ugly solution considering what unlock would have to do). If we can supplement the tree node with a lock status and pointer to child (only used while unlocking) which is locked we should be able to do it all in the asked for complexities :). Ugly but possible. Of course there is an O(n) extra storage. On Sat, Aug 29, 2009 at 11:05 AM, nagendra kumar nagendra@gmail.com wrote: Given a n-ary tree of resources arranged hierarchically. A process needs to lock a resource node in order to use it. But, A node cannot be locked if any of its descendant or ancestor is locked. I was supposed to - write the structure of node - write codes for - islock()- returns true if a given node is locked and false if it is not - lock()- locks the given node if possible and updates lock information - unlock()- unlocks the node and updates information. Codes should be : Islock –O(1) Lock()- O(log n) unLock()- O(log n) -- Yesterday is History. Tomorrow is a Mystery. Today is a Gift! That is why it is called the Present :). http://sites.google.com/site/ramaswamyr-Hide quoted text - - Show quoted text - -- Yesterday is History. Tomorrow is a Mystery. Today is a Gift! That is why it is called the Present :). http://sites.google.com/site/ramaswamyr --~--~-~--~~~---~--~~ 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 group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Find longest palindrom in a give n string in O(N)
@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) find the longest common substring of them. Nitin Mathur --~--~-~--~~~---~--~~ 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 group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Median Finding algorithms.
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
selection algorithm - Median of Medians algorithm '*
(http://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selec...)
by finding (n+1)/2 smallest element (for odd n). You can also refer Pg 189,
Introduction of Algorithms , II edition (Cormen) for the algorithm.
Then apply the same algorithm to partition the array by locating the (k+1)th
smallest element. In the corresponding partition function instead of
directly comparing the values at two indexes use a compare function which
compares modulus of difference of the element and the median found ie
int compare (int a, int b, int median){
return ( abs(median - a) - abs(median - b)) ;
}
Overall time complexity : O(n), space complexity : O(1).
On Sun, Aug 30, 2009 at 8:36 PM, Dufus rahul.dev.si...@gmail.com wrote:
Is it acceptable if I
find the median in O(logn) time and then,
Can you elaborate how can we find the median of an unsorted array in O(log
n) time?
find k numbers closest to the median in O(k) space and O(n) time?
_dufus
On Aug 30, 4:38 pm, Nagendra Kumar nagendra@gmail.com wrote:
Given a set S of n distinct numbers and a positive integer k = n.
Determine the k numbers in S that are closest to the median of S.
Find an O(n) algorithm
--
Shishir Mittal
Ph: +91 9936 180 121
--~--~-~--~~~---~--~~
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 group, send email to
algogeeks+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---
[algogeeks] possible in logn
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 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 group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] 1 Trillion integers on hard disk, find the smallest 1 million of them
* 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 subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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 -~--~~~~--~~--~--~---
[algogeeks] adobe interview question
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 ... --~--~-~--~~~---~--~~ 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 group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Median Finding algorithms.
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. To post to this group, send email to algogeeks@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 -~--~~~~--~~--~--~---
[algogeeks] Re: minimum difference.
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, ankur aggarwal ankur.mast@gmail.comwrote: given a array of length n. find 2 number such that their differnce is minimum. -- Yesterday is History. Tomorrow is a Mystery. Today is a Gift! That is why it is called the Present :). http://sites.google.com/site/ramaswamyr --~--~-~--~~~---~--~~ 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 group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: minimum difference.
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, ankur aggarwal ankur.mast@gmail.comwrote: given a array of length n. find 2 number such that their differnce is minimum. -- Regards Bhanu Pratap Singh Software Engineer A R I C E N T Mobile +91 9886738496 Main +91 080 41068106 --~--~-~--~~~---~--~~ 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 group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: minimum difference.
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 minimum. -- Shishir Mittal Ph: +91 9936 180 121 --~--~-~--~~~---~--~~ 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 group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: adobe interview question
@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 squares are not arranged as in a chess board then we can be sure that there are at least two whites and two blacks which are adjacent by the sides. If not they will be adjacent diagonally. So the distance really depends on how it is defined for squares adjacent by a side and by a vertex (diagonally). Only two possibilities! On Tue, Sep 1, 2009 at 8:37 AM, yash yashpal.j...@gmail.com wrote: 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 ... -- Yesterday is History. Tomorrow is a Mystery. Today is a Gift! That is why it is called the Present :). http://sites.google.com/site/ramaswamyr --~--~-~--~~~---~--~~ 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 group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Median Finding algorithms.
@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.e. n= 9 elements and 5
closest medians are required.
First determine the median in O(n) time using Linear general selection
algorithm - Median of Medians
algorithmhttp://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_.22Median_of_Medians_algorithm.22by
looking for 5th largest element in the array.
Median = 11.
int compare (int a, int b, int median){
return ( abs(median - a) - abs(median - b)) ;
}
Rest of the task is similar to first finding the (k)th smallest element in
the array
|2-11|, |5-11|, |7-11|, |10-11|, |11-11|, |14-11|, |19-11|, | 45-11|,
|121-11|
i.e. 9, 6, 4, 1, 0, 3, 8, 34, 110
and then partitioning the array around the pivot and returning the first k
elements as the solution.
Storing the above array in O(n) space and then performing the task would
have ease the task but if space is a constraint (constant space), compare
function described above can be used.
Working for constant space,
Using the compare function, let ** the first recursive call SELECT(arr, 0,
8, 5) *for e.g* does partitioning for index 2.
The partitioned array for pivot arr[2] = 7 is
(10, 11, 14) 7 (2, 5, 19, 45, 121) (order of elements in the bracket may
vary depending upon coding).
equivalent to (1, 0, 3,) 4 ( 9, 6, 8, 34, 110) for O(n) space case.
so 7 is the 4th smallest element.
the above calls SELECT (arr, 4, 8, 5 - 4)
which *ultimately* partitions the array into
(10 , 11, 14, 7,) 5 (2, 19, 45, 121)
equivalent to (1, 0, 3, 4,) 6 ( 9, 8, 34, 110) for O(n) space case.
the first 5 elements is the required answer.
Overall worst case time complexity : O(n), space complexity : O(1).
O(n) space simplifies the coding and understanding of the problem.
On Tue, Sep 1, 2009 at 6:04 PM, ankur aggarwal ankur.mast@gmail.comwrote:
@shishir
i could understand
cann u give an example..
--
Shishir Mittal
Ph: +91 9936 180 121
--~--~-~--~~~---~--~~
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 group, send email to
algogeeks+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---
[algogeeks] Re: N-Ary Tree and Resource management
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 descendant or ancestor is locked .. should not be A node cannot be locked if any of its ancestor is locked. On Sat, Aug 29, 2009 at 11:35 PM, nagendra kumar nagendra@gmail.com wrote: Given a n-ary tree of resources arranged hierarchically. A process needs to lock a resource node in order to use it. But, A node cannot be locked if any of its descendant or ancestor is locked. I was supposed to - write the structure of node - write codes for - islock()- returns true if a given node is locked and false if it is not - lock()- locks the given node if possible and updates lock information - unlock()- unlocks the node and updates information. Codes should be : Islock –O(1) Lock()- O(log n) unLock()- O(log n) --~--~-~--~~~---~--~~ 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 group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: 1 Trillion integers on hard disk, find the smallest 1 million of them
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 Complexity : O(K) On Tue, Sep 1, 2009 at 6:29 PM, ankur aggarwal ankur.mast@gmail.comwrote: * 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. -- Shishir Mittal Ph: +91 9936 180 121 --~--~-~--~~~---~--~~ 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 group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
