Sorting an assortment of strings and integers together, while keeping them separate

Question

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.

Answer 1

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