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
