key (/.) is one of the cooler J language features
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 (~. ,: #/.~) list 2 3 4 5 6 7 8 9 1 0 8 11 8 7 5 5 5 2 2 1 sorted /:~&.|:@:(~. ,: #/.~) list 0 1 2 3 4 5 6 7 8 9 1 2 8 11 8 7 5 5 5 2 ________________________________ From: Jon Hough <[email protected]> To: "[email protected]" <[email protected]> Sent: Tuesday, March 31, 2015 12:10 PM Subject: [Jprogramming] Interview question and answer with J 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
