Most efficient way to compare 9 numeric values using Ruby?

Question

I was recently at an interview and was asked to solve a problem similar to this one, how would you code this for efficiency, I have a feeling my answer was not the best way to do this:

Nine nickels and a traditional balance are sitting in front of you.

All nickels have the same weight except for one counterfeit, which is slightly heavier than the others.

Using Ruby, how would you code this so that it uses the balance the lowest number of times possible to guarantee you've found the counterfeit nickel?

Answer 1

Two answers.

1. First, the traditional answer. Split the coins into 3 piles, A,B,C. Put A and B on opposite sides of the balance. The lower pile has the heavy coin. If they balance C has the heavy coin.

   Take the heavy pile and put one coin on each side of the balance. The heavier coin is the counterfeit. If they balance the coin that you left off is the fake.

2. If they want you to use ruby they probably gave you some kind of data or an API. You can probably use the inspect method or some other reflection techniques to find the heavy item without using the balance class at all.

Answer 2

Here's some Ruby code that follows the algorithm defined in answer 1 by paulrubel. For reference, that algorithm is:

Split the coins into 3 piles, A,B,C. Put A and B on opposite sides of the balance. The lower pile has the heavy coin. If they balance C has the heavy coin.

Take the heavy pile and put one coin on each side of the balance. The heavier coin is the counterfeit. If they balance the coin that you left off is the fake.

class Scale
  def self.weigh(lhs, rhs)
    weight(Array(lhs)) <=> weight(Array(rhs))
  end

  def self.weight(coins)
    coins.inject(0) {|sum, c| sum + c.weight}
  end
end

class Coin
  # To satisfy the rules of the game, this should not be called directly
  attr_reader :weight

  def initialize(weight)
    @weight = weight
  end
end

starting_coins = ([Coin.new(6)] + ([Coin.new(5)] * 8)).shuffle

# Puzzle begins here.

def heavier(coins)
  idx = case Scale.weigh(coins[0], coins[1])
        when -1 then 1
        when  0 then 2
        when  1 then 0
        end
  coins[idx]
end

p heavier(heavier(starting_coins.enum_slice(3).map))

Answer 3

Assuming that you're talking about an array of numbers, the easiest is to use the portions of ruby that are coded in C (MRI) or Java (Jruby). Lets say that we have a list of weights, and counterfeit money weighs less than 5, and real money weighs 5. There are a number of different approaches to split out the contents of the array efficiently:

moneys = Array.new(100) { rand(5) + 1 }

# This now contains all the counterfeit money:
counterfeits = moneys - [5]

# If we're not able to use direct equality, then we can just use a plain old delete_if, sending a message to the money (forgive the equality message here, imagine it's something else)
real = 5
counterfeits = moneys.delete_if { |m| m.==(real) }

# In some cases you want to first reduce the workload for delete_if, although this would often be preoptimization:
moneys.compact.delete_if { |m| m == real }

# So, for many (but definately by no means all workloads) the most efficient method to do this might be:
counterfeits = moneys.compact! - [5]

This keeps what are (under MRI at least) the number of dynamic method dispatches and temporary objects and/or block invocations to a minimum. Using compact when memory bound (for large sets) and/or using self mutating methods (Enumerable#!) also helps avoid excess GC load.

Finally, I just have to say, that asking about micro-optimizations without good context (size of input at the very least) is an awful interview question, unless the expected answer is a question about context and constraints.