interview_solution_approach.rb

#optimal is the actual count we want to maximize. {optimal: 4}
#means we want to find as many sets of 4s as possible.
#without optimal set, we will optimize for the biggest values possible.
def groups(books, optimal: nil)
  #convert list of books to list of counts of each book type
  #sort by descending order for optimal grouping
  #eg: [1,1,2,2,3,3,4,5] => [2,2,2,1,1]

  counts = books.inject({}) do |res, item|
    res[item] ||= 0
    res[item] += 1
    res
  end.values.sort.reverse

  results = []

  #we will extract the max or optimal set from the list of counts by decrementing
  #each count by 1 and we collect the count into results. The counts list get
  #smaller over time as we remove 0s from it until it becomes empty.
  while counts != []
    optimal_count = [counts.count, optimal].compact.min
    results << optimal_count
    counts = counts.map.with_index{|x, i| i < optimal_count ? x - 1 : x}
    counts -= [0]
  end

  results
end


groups([1,2,3,4,1,2,3,5]) # [5, 3]
groups([1,2,3,4,1,2,3,5], optimal: 4) # [4, 4]
groups([1,2,3,4,1,2,3,5], optimal: 3) # [3, 3, 2]
groups([1,2,3,4,1,2,3,5], optimal: 2) # [2, 2, 2, 2]