2
\$\begingroup\$

I put a solution to this coding problem together. The problem is this:

Create a function that takes an array, finds the most often repeated element(s) within it and returns it/them in an array. The function should work for both integers and strings mixed together within the input list (e.g. [1, 1, "a"]).

If there is a tie for highest occurrence, return both.

Separate integers and strings in the result.

If returning multiple elements, sort result alphabetically with numbers coming before strings.

This is the solution I came up with:

def highest_occurrence(arr)

  # Separate the unique values into individual sub-arrays
  x = rand(2**32).to_s(16)
  result = arr.sort do |a, b| 
    a = a.to_s + x if a.is_a?(Numeric)
    b = b.to_s + x if b.is_a?(Numeric)
    a <=> b
  end.chunk_while {|a, b| a == b }.to_a

  # Get an array of all of the individual values with the max size,
  # Sort them by integers first, strings second
  result = result.select do |a2| 
    a2.size == result.max_by(&:size).size 
  end.map(&:uniq).flatten.sort_by { |v| v.class.to_s }

end

It passes these tests:

p highest_occurrence(["a","a","b","b"]) == ["a","b"]
p highest_occurrence([1,"a","b","b"]) == ["b"]
p highest_occurrence([1,2,2,3,3,3,4,4,4,4]) == [4]
p highest_occurrence(["ab","ab","b"]) == ["ab"]
p highest_occurrence(["ab","ab","b","bb","b"]) == ["ab","b"]
p highest_occurrence([3,3,3,4,4,4,4,2,3,6,7,6,7,6,7,6,"a","a","a","a"]) == [3,4,6,"a"]
p highest_occurrence([2,2,"2","2",4,4]) == [2,4,"2"]

I'd like to know whether there are better ways to solve some of the specific problems in this exercise. In particular, the requirement to sort strings and integers together without being able to convert the integers to strings in the sort block was an interesting one. I managed this by appending a random hex value (the same value) to each integer during the sort process. This seems a bit hackish, and I have the feeling it could be improved upon.

I would also appreciate any other suggestions for how to do a cleaner job.

\$\endgroup\$
3
\$\begingroup\$

Your test cases should include lexical sort of integers; that is, [9,11] must return [11,9]. (Your implementation does pass this test since you're converting everything to a string).

As you suspected, mangling the input is hacky. This is better accomplished with a multi-criteria sort. This technique maps each individual value to an array of sort criteria. Ruby will compare the arrays only until it finds unequal elements; this means you can mix integers and strings in the second field, so long as the first field distinguishes them.

For our problem, the first field will be 0 for integers else 1. The second field is the value itself.

Although this approach will never compare integers to strings—if the first criteria distinguishes the two elements, the comparison is done—the second criteria must be a string anyway, to satisfy the "sort alphabetically" requirement.

It's not necessary to sort the entire array or store a full copy of it. Instead, count duplicates in a hash table. Traverse the values of the hash to find a maximum. Traverse again to extract the corresponding keys.

def highest_occurrence(arr)
    return arr if arr.size <= 1
    count = Hash.new(0)
    arr.each { |k| count[k] += 1 }
    max = count.max_by{|k,n| n}[1]
    return count.select { |k,n| n==max }.keys.sort_by { |k| [ k.is_a?(Integer)?0:1, k.to_s ] }
end
\$\endgroup\$
  • \$\begingroup\$ Thanks for your answer and your very helpful example. I've stepped through it, and it's entirely clear. Very nice upgrade to mine! Two things I don't quite understand: the spec says to return integers sorted in ascending order, followed by strings sorted in ascending order. Why, then, should [9,11] return 11,9]? Also, why can't you just do .sort_by { |k| k.is_a?(Integer)?0:1 }? What test cases would fail to that? None of miine do. \$\endgroup\$ – BobRodes Mar 13 at 1:26
  • 1
    \$\begingroup\$ I answered my second question, once I went to the trouble of reading the link that you posted and doing a few other test cases. All my test cases happen to have the max values in the proper sorted order already! I switched them around and they failed. So, that's how you do a nested sort: put the criteria in an array. I'll put that in the file. Also, now that I look at it, I think that's what you were trying to tell me up front. Is it possible that you intended to say that [11, 9] should return '[9,11]`? \$\endgroup\$ – BobRodes Mar 13 at 1:43
  • \$\begingroup\$ One more thing. I don't think that return [] unless arr.length will ever return a [], since 0 evaluates to true in Ruby. Is this a carry-over pattern from some other language such as JS? I would put return [] if arr.size.zero? myself. \$\endgroup\$ – BobRodes Mar 13 at 1:50
  • 1
    \$\begingroup\$ You post said "sort result alphabetically" which to me means "lexically," implying 9 vs 11 should sort the same way "9" vs "11" does: with 11 first. It's an odd phrasing and maybe just sloppiness on the part of the problem's author. If this were a contract I'd ask the client if that's what they really wanted. To sort the integers numerically, simply remove .to_s at the very end. \$\endgroup\$ – Oh My Goodness Mar 13 at 2:46
  • 1
    \$\begingroup\$ Aha, good point. Yes, so would I! I'll mention this in the comments section to the problem. Thanks again for your help; this has been very instructive. \$\endgroup\$ – BobRodes Mar 13 at 7:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.