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
