[algogeeks] Re: Dynamic Programming

Thanks everyone for suggestions and follow my Dynamic Programming - Series for more questions on DP . -- 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 gr

Re: [algogeeks] quick sort

This is correct. It ensures there can be no degenerate partitions and improves the worse case run time to be asymptotically equal to the average case. In practice you would want to use a simple pivot selection algorithm and only resort to SELECT when the simple algorithm fails to produce a p

Re: [algogeeks] Re: Find a specific number in a special matrix.

Thanks for sharing! It's good to know the data structure. On Wed, Jan 5, 2011 at 9:10 AM, juver++ wrote: > Other useful information about this structure is > here. > > > -- > You received this message because you are subscribed t

[algogeeks] Re: Dynamic Programming - Series

Complexity of above solution is O(n) On Jan 5, 10:50 pm, suhash wrote: > In any column, we can place atmost 2 pebbles. > > (a) Considering an isolated column, we can place 1 or 2 pebbles. > Solutions: {1},{2},{3},{4},{1,3},{1,4},{2,4} > (b) Have an array dp[n][5][5]. Let dp[i][j][k] store the max

[algogeeks] Re: Dynamic Programming - Series

In any column, we can place atmost 2 pebbles. (a) Considering an isolated column, we can place 1 or 2 pebbles. Solutions: {1},{2},{3},{4},{1,3},{1,4},{2,4} (b) Have an array dp[n][5][5]. Let dp[i][j][k] store the maximum sum that can be achieved starting from column 'i' to column 'n-1' (columns ar

Re: [algogeeks] Re: Dynamic Programming

yes u correct on this d = val[id] is correct initialization. On Wed, Jan 5, 2011 at 11:02 PM, juver++ wrote: > However, initial value of d should be profit of position id. > There is a case when there is an optimal way not to take any > restaurants to the right of id position, only current is en

Re: [algogeeks] Re: Dynamic Programming

However, initial value of d should be profit of position id. There is a case when there is an optimal way not to take any restaurants to the right of id position, only current is enough. Consider, the following case: m = {1, 2} p = {1, 4}; k = 10; right answer is 4, not 1 :). Also optimal solution

Re: [algogeeks] Re: Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations.

That's a big save of space! On Jan 5, 2011 9:03 AM, "juver++" wrote: > Good point. Right. > But we can avoid first stack of such structure, having separate variable > (Minimum) for this. > > -- > You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. > T

Re: [algogeeks] Re: Dynamic Programming

In main just pass answerIs = max(val[0], solve(0)); On Wed, Jan 5, 2011 at 10:49 PM, juver++ wrote: > Sorry, disregard my first proposition about index i. > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send

Re: [algogeeks] Re: Dynamic Programming

Sorry, disregard my first proposition about index i. -- 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...@googleg

Re: [algogeeks] Re: Dynamic Programming

Minor fixes: i loop should be from 0 to id - 1, if you are moving from left to right. initial value of d should be the val[id] not 0. -- 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.

Re: [algogeeks] Re: Dynamic Programming

ok :):) On Wed, Jan 5, 2011 at 10:43 PM, juver++ wrote: > I was replying to the @Decipher post. Not yours. :) > Your algorithm seems to be ok. > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algo

Re: [algogeeks] Re: Dynamic Programming

I was replying to the @Decipher post. Not yours. :) Your algorithm seems to be ok. -- 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] Re: Find a specific number in a special matrix.

Other useful information about this structure is here . -- 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 uns

Re: [algogeeks] Re: Dynamic Programming

I am telling the DP O(n^2) solution, whts wrong in it?? On Wed, Jan 5, 2011 at 10:36 PM, juver++ wrote: > Unfortunately, you are wrong. > We need one loop for i and that is all. All other things for searching max > p[j] is solved by segment tree in O(log n). > > -- > You received this message be

[algogeeks] Re: Dynamic Programming

Unfortunately, you are wrong. We need one loop for i and that is all. All other things for searching max p[j] is solved by segment tree 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 algoge.

Re: [algogeeks] Re: Dynamic Programming

int solve(int id) { if(id==n) return 0; int &d = dp[id]; if(~d) return d; d = 0; for(int i=id+1;i=k) { d >?= val[id] + solve(i); } } return d; } Its O(n^2), and Juver++, is very correct. On Wed, Jan 5, 2011 at 10:22

Re: [algogeeks] Find a specific number in a special matrix.

Either x is greater or less than the middle vale you have to search 3 quardant. Because the value could be in bottom left or top tight. On Jan 5, 2011 7:14 AM, "ADITYA KUMAR" wrote: > @ankit thanks for correcting > @naveen yeah that will make it more precise > > On Wed, Jan 5, 2011 at 7:51 PM, An

Re: [algogeeks] Re: Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations.

Good point. Right. But we can avoid first stack of such structure, having separate variable (Minimum) for this. -- 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 f

[algogeeks] Dynamic Programming - Series

We are given a checkerboard which has 4 rows and n columns, and has an integer written in each square. We are also given a set of 2n pebbles, and we want to place some or all of these on the checkerboard (each pebble can be placed on exactly one square) so as to maximize the sum of the integers in

[algogeeks] Re: Dynamic Programming

I think your solution will take O(n3) time , as it will require three loops . 1st for index i , 2nd for first max and 3rd for second max . Instead we should take : dp[i] = max(dp[j]) + p[i] , where j k . Pls correct me if something is wrong . -- You received this message because you are subscribe

Re: [algogeeks] Re: Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations.

I think both of them should provide min function? When you call getmin you should use min value of the two min from both stack? On Jan 5, 2011 8:10 AM, "juver++" wrote: > > only 2 stacks, one of them (or both...) should provide functionality for retrieving minimum. > > -- > You received this messa

Re: [algogeeks] Re: Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations.

only 2 stacks, one of them (or both...) should provide functionality for retrieving minimum. -- 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, sen

[algogeeks] error in code

Hi , i m getting error can u find the error in code for following problem?? We will use the following (standard) definitions from graph theory. Let V be a nonempty and finite set, its elements being called vertices (or nodes). Let E be a subset of the Cartesian product V×V, its elements being c

Re: [algogeeks] Google Interview Question

may be use of double free ..? -- 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 opt

Re: [algogeeks] Google Interview Question

There might be some error in calculating the value of some variable(s) which might be used to retrieve elements in some arrays/maintaining stack/linked list or any other data structure that uses the value of that variable to retrieve information from memory. Carefully checking the values of variab

Re: [algogeeks] Re: Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations.

then we are using 3 stack?? 1 for pop_rear 1 for operation of pop_front and 1 for get_min??? -- 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

[algogeeks] Garbage collection without pauses or circular list structure memory leak.

http://wp.me/1fZn6 for the algorithm description. Cheers Jacko -- 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

Re: [algogeeks] Find a specific number in a special matrix.

@ankit thanks for correcting @naveen yeah that will make it more precise On Wed, Jan 5, 2011 at 7:51 PM, Ankit Babbar wrote: > @ Aditya: Mac's Solution works correctlyfor your example: > > Start from 24(top right)..24>5: go left;9>5: go left; 1<3: go > down; 2<3:go down: 3 found..:

Re: [algogeeks] Find a specific number in a special matrix.

@ Aditya: Mac's Solution works correctlyfor your example: Start from 24(top right)..24>5: go left;9>5: go left; 1<3: go down; 2<3:go down: 3 found..:) On Wed, Jan 5, 2011 at 7:37 PM, Naveen Kumar wrote: > I think if x < a[n/2][n/2] than we need to search in 1st quadrant otherwis

Re: [algogeeks] Find a specific number in a special matrix.

I think if x < a[n/2][n/2] than we need to search in 1st quadrant otherwise in others. On Wed, Jan 5, 2011 at 7:20 PM, sourabh jakhar wrote: > aditya solution is correct > it is a standard question of young tabuleau > it is complexity is log(n) > > > On Wed, Jan 5, 2011 at 6:52 PM, ADITYA KUMAR

Re: [algogeeks] Find a specific number in a special matrix.

aditya solution is correct it is a standard question of young tabuleau it is complexity is log(n) On Wed, Jan 5, 2011 at 6:52 PM, ADITYA KUMAR wrote: > @MAC > ur solution is wrong > > 1 9 24 > 2 12 33 > 3 16 49 > > search for 3 > > > O(logn) solution > let the matrix be A[][] and number to be se

Re: [algogeeks] Find a specific number in a special matrix.

@MAC ur solution is wrong 1 9 24 2 12 33 3 16 49 search for 3 O(logn) solution let the matrix be A[][] and number to be searched is x divide the array from middle in 4 parts lets say it four quadrants now check if x>A[n/2][n/2] search in bottom right quadrant if x wrote: > Suppose you have a m

[algogeeks] Re: quick sort

Your version is false. Randomized quick sort provides expected time O(nlogn). But in worst case it can be near quadratic time. However, in practice is can be solved using random shuffling. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To

Re: [algogeeks] Re: quick sort

selecting pivot as a near median using order stastics method(O(n)) we can run it in worst case O(nlogn) -- 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 thi

[algogeeks] Re: quick sort

using randomized version of quick sort time complexity even in the worst case is o(nlogn) Regards priyaranjan code-forum.blogspot.com On Jan 5, 12:55 pm, lee wrote: > how can we make quick sort to run in O(logn) time in worst case?? -- You received this message because you are subscribed to th

[algogeeks] Google Interview Question

You have a stream of infinite queries (ie: real time Google search queries that people are entering). Describe how you would go about finding a good estimate of 1000 samples from this never ending set of data and then write code for it. -- You received this message because you are subscribed to the

Re: [algogeeks] Google Interview Question

Corrupted stack - buffer overflow. -- 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 mor

Re: [algogeeks] Google Interview Question

dangling pointers ?? maybe.. also corrupted heap On Wed, Jan 5, 2011 at 4:46 PM, bittu wrote: > You are given a the source to a application which is crashing when > run. After running it 10 times in a debugger, you find it never > crashes in the same place. The application is single threaded,

Re: [algogeeks] Google Interview Question

since it crashes at different places each time when it runs so there must be some problem which is not related to syntax there shud be some logical errors in code On Wed, Jan 5, 2011 at 4:46 PM, bittu wrote: > You are given a the source to a application which is crashing when > run. After runnin

[algogeeks] Google Interview Question

You are given a the source to a application which is crashing when run. After running it 10 times in a debugger, you find it never crashes in the same place. The application is single threaded, and uses only the C standard library. What programming errors could be causing this crash? How would you

Re: [algogeeks] Dynamic Programming

dp[i] - profit from the opening restaurants up to the i-th position. dp[i] = max(dp[i - 1], p[i] + max[dp[j], j <= A and distance between i and j at least k]). Segment trees are helpful to find maximum profir for the positions to th elft of the current. So we use tree of maximums. To satisfy th

Re: [algogeeks] Dynamic Programming

Can you elaborate how to put segment tree into picture On Wed, Jan 5, 2011 at 2:57 PM, juver++ wrote: > Right. It can be solved simply in O(n^2). To optimize use segment trees. > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post

Re: [algogeeks] Dynamic Programming

Right. It can be solved simply in O(n^2). To optimize use segment trees. -- 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

[algogeeks] Re: quick sort

There is a killer-case for the quicksort algorithm on which it runs in a quadratic time. However, before running sorting algorithm we can randomly shuffle the array, so time will be reduced to the expected. -- You received this message because you are subscribed to the Google Groups "Algorith

Re: [algogeeks] Re: XOR Rounds

Space complexity is O(N^2), but time complexity will be O(N^3 log K) - this is too slow. -- 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 em

Re: [algogeeks] Dynamic Programming

1-D simple dp with state current index you are at On Wed, Jan 5, 2011 at 7:41 AM, Akash Agrawal wrote: > didn't get the question correct... > Can u cite an example... > > Regards, > Akash Agrawal > http://tech-queries.blogspot.com/ > > > > On Wed, Jan 5, 2011 at 12:36 AM, Decipher wrote: > >> Yu

Re: [algogeeks] quick sort

If we modify the PARTITION to use SELECT algorithm given in clrs to find median and partition the array about it, then i think it will be O(nlogn) worst case, because the array will be perfectly divided into 2 equal size arrays each time. But is the practical implementation of SELECT that fast? --

Re: [algogeeks] quick sort

You can't make it deterministically run in O(nlogn). On Wed, Jan 5, 2011 at 1:25 PM, lee wrote: > how can we make quick sort to run in O(logn) time in worst case?? > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this grou