tag:blogger.com,1999:blog-6373963829340632529.post5474412766782477980..comments2024-01-30T05:40:30.415-03:00Comments on Algorithmically challenged: A Cute AlgorithmDanielhttp://www.blogger.com/profile/07505997833685327219noreply@blogger.comBlogger6125tag:blogger.com,1999:blog-6373963829340632529.post-38791262680957897022011-05-20T16:04:52.487-03:002011-05-20T16:04:52.487-03:00Interesting.
RE: http://analgorithmaday.blogspot....Interesting.<br /><br />RE: http://analgorithmaday.blogspot.com/2011/05/count-duplicates-in-integer-arraygoogle.html<br /><br />A couple of points:<br />1. The algorithm on that page doesn't work. It counts incorrectly:<br /><br />"if you have, A[] = {1,1,1,2,2,2,3,3,4}<br />you should print, 1=>3, 2=>3, 3=>2, 4=>1"<br /><br />The program produces:<br />1=>3, 2=>1, 3=>1, 4=>1<br /><br />The author even states:<br />"I came up with a approach but cannot make that into a working code"<br /><br />Now, the O(n) is on the number of comparisons, not the number of recursions of the function. Given that, I augmented the code to count the number of comparisons actually executed:<br /><br />Input: 1,1,1,2,2,2,3,3,4<br />Comparisons: 9<br /><br />Input: 1,2,2,3,3,3,4,4,4,5,5,5,5,6,6,6,6,7,7,8,9<br />Comparisons: 34<br /><br />Input: 1,1,2,2,2,3,4,4,4,5,5,6,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,8,9<br />Comparisons: 61<br /><br />So the performance is worse than the naive approach of just walking the list. This is because the algorithm is based on guessing and the costs for bad guessing are very high.<br /><br />There may be an algorithm that can do this in better than O(n), but I haven't seen it.<br /><br />Frankly, I think that the answer the interviewer is looking for is a parallel one where this problem can be solved in O(n)/m time where m is the number of parallel partitions.<br /><br />RE: definition of k-smallest<br /><br />That's fine. That particular definition is not one I've encountered, on the other hand the one I proposed is one I encounter quite frequently. Different strokes for different folks I guess.Jim Powershttps://www.blogger.com/profile/08023415289970828051noreply@blogger.comtag:blogger.com,1999:blog-6373963829340632529.post-18654441800257226302011-05-15T21:28:02.038-03:002011-05-15T21:28:02.038-03:00@corruptmemory
There are two issues here: whether...@corruptmemory<br /><br />There are two issues here: whether my interpretation of k-smallest number is correct or not, and how to adapt the algorithm to make it work according to your interpretation.<br /><br />The k-smallest number is formally known as the k-th order statistic. It is usually defined over distinct numbers, but, for a list of n numbers, the minimum is the 1st order statistic, the maximum the n-th order statistic, and, if n = m * 2, the median is the (m+1) order statistic. Given that, I feel my definition is correct -- or, at least, more common.<br /><br />Regardless, there's the question of how to adapt the algorithm to meet your own definition. First, I can guarantee that you won't get better than O(min(k, log N+M)), since you'll need to "confirm" at least k numbers to be distinct.<br /><br />However, you _can_ get that performance, since one can count the number of distinct elements in a list in O(distinct numbers). In fact, the very same blog that inspired post has that algorithm as well: http://analgorithmaday.blogspot.com/2011/05/count-duplicates-in-integer-arraygoogle.html.<br /><br />So, one possible solution is the following. First, adapt that algorithm to just store the numbers it finds in an array. It only need to get the first k numbers -- once it does that, it can finish.<br /><br />Now apply this algorithm to each of the two sorted arrays. Finally, run my algorithm over the output of the previous step, which is guaranteed to only contain distinct numbers.<br /><br />Seems to me that the performance should be O(k), or, perhaps, O(k log k).Danielhttps://www.blogger.com/profile/07505997833685327219noreply@blogger.comtag:blogger.com,1999:blog-6373963829340632529.post-86032205592400956382011-05-15T20:12:57.024-03:002011-05-15T20:12:57.024-03:00Correction: m.length tests, sorry.Correction: m.length tests, sorry.Jim Powershttps://www.blogger.com/profile/08023415289970828051noreply@blogger.comtag:blogger.com,1999:blog-6373963829340632529.post-22511181286882460522011-05-15T20:01:42.834-03:002011-05-15T20:01:42.834-03:00Well, the point I was getting at is that the solut...Well, the point I was getting at is that the solution provided only works if the two sublists to be merged to not contain duplicate elements before the k-th element (of course you may not know this fact before looking for the k-th element). So a general, and I would argue correct, solution needs to be able to handle duplicate elements correctly. I do not see a solution that is O(k) for the general case, take, for example:<br /><br />val k = 3<br />val m = Array(1,1,1,1,1,1,1,1,1,2,3)<br />val n = Array(1,1,1,1,1,1,1,1,1)<br /><br />This particular problem will require m.length+n.length tests as best as I can tell.Jim Powershttps://www.blogger.com/profile/08023415289970828051noreply@blogger.comtag:blogger.com,1999:blog-6373963829340632529.post-24514626685890869792011-05-15T03:53:07.181-03:002011-05-15T03:53:07.181-03:00@corruptmemory, if you allow duplicate elements t...@corruptmemory, if you allow duplicate elements the elementary action "get the k^{th} element of the sorted array" requires at least O(min(k,n-k)). Since imagine you checked through all elements 1..k, and imagine they're all distinct. In that case, ar[k] is the k^{th} element if ar[0]≠ar[1] and ar[k+1] is the k^{th} element if ar[0]=ar[1].<br /><br />You can keep the same algorithm and use described O(k) method of finding the k^th element instead of just applying ar(k), though.Elazar Leibovichhttps://www.blogger.com/profile/00122966197979737199noreply@blogger.comtag:blogger.com,1999:blog-6373963829340632529.post-76303592279930727202011-05-15T02:08:32.271-03:002011-05-15T02:08:32.271-03:00Perhaps this is stated in the original problem, bu...Perhaps this is stated in the original problem, but your solution is assuming that the 'k'-th smallest is based on "position" within in the array instead of the 'k'-th smallest number overall.<br /><br />Limiting the example to 1 array, there are two interpretations of 'k' smallest:<br /><br />k=3<br />Array(1,1,1,2,2,4,4,5,5,7,7,8)<br /><br />Given your solution you would choose 1 as the k-smallest integer whereas I would argue that the k-smallest is 4.Jim Powershttps://www.blogger.com/profile/08023415289970828051noreply@blogger.com