If you're going to sort the list you can then split on the boundaries
between groups of equal terms (that is, split where adjacent items are
unequal):
(({.,#);.1~ 1,2~:/\]) /:~ list
0 1
1 2
2 8
3 11
4 8
5 7
6 5
7 5
8 5
9 2
This seems to be about half as fast as the solution with (~.,.#/.~), but
is slightly quicker for an already-sorted list. The functions ~. and /.
are implemented using hashing (or, for appropriate integer lists,
small-range special code) and take linear time. Sorting uses a radix-ish
sort (or small-range special code) and also takes linear time.
Marshall
On Tue, Mar 31, 2015 at 05:35:10PM +0100, Jon Hough wrote:
> Raul, Pascal,
> Thanks. I had a feeling there was going to be a "Oh yeah, J uses its own
> thing" type answer. Playing around with your verbs and writing my own, I have
> my own humble attempt:
>
> duplicates =: (/:~@:~.) ,: (#/.~@:/:~)
>
>
> Seems to work, although doing sort /:~ twice doesn't feel good.
>
>
> Nuvoc indicates that the /. is optimized but I still wonder what sort of time
> complexity we're looking at.
>
>
> I suppose I should do some quick tests to measure the time taken on various
> lists.
>
>
>
>
> For completeness I also have my original verb as a tacit verb: duplicates =:
> +/ @: ((/:~@~.) (="_ 0) ])
>
>
>
> Thanks,Jon
> > From: [email protected]
> > Date: Tue, 31 Mar 2015 12:17:49 -0400
> > To: [email protected]
> > Subject: Re: [Jprogramming] Interview question and answer with J
> >
> > I usually use something like this:
> >
> > (~. ,. #/.~) list
> > 2 8
> > 3 11
> > 4 8
> > 5 7
> > 6 5
> > 7 5
> > 8 5
> > 9 2
> > 1 2
> > 0 1
> >
> > You can sort that if you prefer:
> >
> > /:~ (~. ,. #/.~) list
> > 0 1
> > 1 2
> > 2 8
> > 3 11
> > 4 8
> > 5 7
> > 6 5
> > 7 5
> > 8 5
> > 9 2
> >
> > That said, when working with really large data sets, sometimes it
> > makes more sense to sort the values and then look for where they
> > change.
> >
> > L=: /:~ list
> > b=: 1,2 ~:/\ L
> > ...
> >
> > Thanks,
> >
> > --
> > Raul
> >
> > On Tue, Mar 31, 2015 at 12:10 PM, Jon Hough <[email protected]> wrote:
> > > A fairly common technical question for programming interviews is to write
> > > (on a whiteboard)a method to find how many duplicates of each number
> > > exist in a list of numbers.
> > > e.g. if list = 1 3 2 1 5 2
> > > then the answer would be 2 1's, 2 2's, one 3 and one 5.
> > > The trick is to do it in a time efficient way. In a standard programming
> > > language (Java, C++ etc),the naive approach is to do two passes and count
> > > how many of each number are duplicated. This approach takes n(n-1)/2
> > > comparisons, so could be regarded as O(n^2).The better approach would be
> > > to create a dictionary / hashtable for each number and add items to the
> > > correctslot (i.e. key in the dictionary).
> > >
> > > But for J, it seems there is not a readily available fast approach to
> > > this.e.g.
> > >
> > > list =: 2 3 4 3 2 3 4 5 6 5 4 7 8 9 7 6 4 6 2 1 2 3 4 3 2 3 4 5 7 5 2 3 5
> > > 8 9 0 4 3 2 3 1 2 6 5 7 8 7 8 3 4 5 3 6 8
> > >
> > >
> > > I want to count how many duplicates appear:
> > >
> > >
> > >
> > >
> > > +/ ((i.10)&="_ 0)list
> > >
> > >
> > > (result: 1 2 8 11 8 7 5 5 5 2)
> > >
> > >
> > >
> > >
> > >
> > > I think this is O(n^2), since it first constructs nxn table before
> > > folding +/.
> > >
> > >
> > > My result is correct but my method is slooow.
> > > Is there a better (faster, lower complexity) way to solve this?
> > >
> > >
> > > Regards,
> > > Jon
> > >
> > >
> > >
> > >
> > >
> > > ----------------------------------------------------------------------
> > > For information about J forums see http://www.jsoftware.com/forums.htm
> > ----------------------------------------------------------------------
> > For information about J forums see http://www.jsoftware.com/forums.htm
>
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
