(~. ,. #/.~) list Linda
-----Original Message----- From: [email protected] [mailto:[email protected]] On Behalf Of Raul Miller Sent: Tuesday, March 31, 2015 12:47 PM To: Programming forum Subject: Re: [Jprogramming] Interview question and answer with J Instead of duplicates =: (/:~@:~.) ,: (#/.~@:/:~) You could do duplicates =: (~. ,: #/.~)@/:~ Or, you could do duplicates =: |:@/:~@(~. ,. #/.~) Just be warned that you sometimes need to do timings on this kind of thing if you care about performance on large data sets. For example I've seen cases where throwing maybe 10 million boxed strings at #/.~ didn't work very well. That shouldn't matter, of course, for a small list of numbers like you've got here. Thanks, -- Raul On Tue, Mar 31, 2015 at 12:35 PM, Jon Hough <[email protected]> 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 ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
