[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 aggarwal 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 ancesto

[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

[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 Comple

[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 R wrote: > If the white and the black squares are not arrange

[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 wrote: > given a array of length n. find 2 number such that their differnce is > minimum. > > > > > >

[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,

[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, a

[algogeeks] Re: adobe interview question

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

[algogeeks] Re: Median Finding algorithms.

On Tue, Sep 1, 2009 at 6:04 PM, ankur aggarwal wrote: > @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

[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 ... --~--~-~--~~~---~--~~ Y

[algogeeks] Re: possible in logn

it is a jus a try i=1,j=2; while (a[i][z+1] now apply the abive procedure between i and j (its like binary search) eg we have m=50 and let n=24 (we dont know this value) then for i=16 and j=32 this condition will break .. now apply this logic in between 16 and 32. if u find z(or say n) then w

[algogeeks] Re: N-Ary Tree and Resource management

@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 wrote: >

[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 subs

[algogeeks] Re: Find longest palindrom in a give n string in O(N)

@dufus but nitis algo is not correct also check the definition of LCS and wat is the probelm given.. comment.. On Tue, Sep 1, 2009 at 1:39 PM, Dufus wrote: > > @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) > sp

[algogeeks] minimum difference.

given a array of length n. find 2 number such that their differnce is minimum. --~--~-~--~~~---~--~~ 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

[algogeeks] Re: Median Finding algorithms.

@shishir i could 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 g

[algogeeks] Re: Find longest palindrom in a give n string in O(N)

@nitin apply LCS on "abcda" and reply wat r u trying 2 do --~--~-~--~~~---~--~~ 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

[algogeeks] Re: Find longest palindrom in a give n string in O(N)

On Tue, Sep 1, 2009 at 2:24 PM, Nayn wrote: > * > "Working with stack doesn't work. Push down Automata is usefull in > checking if a given string in palindrom or not... But useless for > finding longest palindrom."* correct dufus > > --~--~-~--~~~---~--~~ You r

[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' n

[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

[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 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 su

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 Date: Mon, Aug 31, 2009 at 7:59 PM Subject: [algogeeks] Re: String- Anag

[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, Dufus wrote: > > Rama, I cannot agree with you more here. > > On Aug 31, 5:34 am, Ramaswamy R wrote: >> When we talk of a binary search

[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 wrote: > We can use the concept of longest common substring. For that use following > steps: > 1) take the

[algogeeks] Re: Median Finding algorithms.

@Prashant: Reading a book and getting the things discussed is sth different. In cormen some algorithms are randomised which in worst case may go upto O(n^2) for kth smallest or kth largest element find. So i was aking for a new answer. On Mon, Aug 31, 2009 at 9:04 AM, Prashant w

[algogeeks] Re: Find longest palindrom in a give n string in O(N)

Working with stack doesn't work. Push down Automata is usefull in checking if a given string in palindrom or not... But useless for finding longest palindrom. try on 'aabaabaabbaabbabba' => baabbaab || On Aug 31, 6:01 pm, ankur aggarwal wrote: > @abhijeet > dryru

[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 wrot