Software Archaeology Code Screen Exercise

Archaeology.md

The cryptic Ruby function takes an array as an argument and returns an array of the items that occur more than once in the original array.

It does this using the inject method specifying an empty Hash as the accumulator. It iterates over each item in the array by referencing the item index position, and passes the resulting item into the accumulator. This builds up a hash of key/value pairs with the key being the item from the initial collection and the value representing the number of times the item appears in the array. It then uses the reject method on the resulting hash and iterates over the hash returning a new array containing the items in self for which the given block is false.

Using idiomatic Ruby a cleaner way to write this function would be:

def show_duplicates(collection)
  collection.select { |element| collection.count(element) > 1 }.uniq
end

Notes:

1. Testing: Since this is a refactoring exercise, it is important to write tests to make sure that expected behavior does not change during the refactor. While refactoring I expanded the original function using meaningful method & variable names as an intermediate step. I ran all of these against a small test suite. For the sake of completeness these files are available as a GitHub Gist at: http://cl.ly/aXJ4

2. Performance: The original function appears to be linear, i.e. O(2n), while the refactored example is, I believe, exponential, i.e. O(n^2 + n). Depending on the use case, this may be an important consideration.

legitscript.rb

class LegitScript
  # Original "cryptic" method
  def function(a)
    a.inject({}){ |a,b| a[b] = a[b].to_i + 1; a}.
      reject{ |a,b| b == 1 }.keys
  end

  # Refactor 1: Use meaningful names
  def find_multiples_in(collection)
    collection.inject({}) do |item, index|
      item[index] = item[index].to_i + 1
      item
    end.reject do |_key, value|
      value == 1
    end.keys
  end

  # Final idiomatic Ruby expression
  def show_duplicates(collection)
    collection.select { |element| collection.count(element) > 1 }.uniq
  end
end

legitscript_spec.rb

require "rspec"
require_relative "legitscript"

RSpec.describe LegitScript do
  let(:list1) { [] }
  let(:list2) { [1] }
  let(:list3) { [1, 2] }
  let(:list4) { [1, 1] }
  let(:list5) { %w(cat dog dog) }
  let(:list6) { %w(cat dog dog bird fish dog bird) }

  context "The original #function" do
    describe "initial results" do
      it "returns empty array for an empty collection" do
        expect(LegitScript.new.function(list1)).to eq([])
      end

      it "returns empty array for a single element collection" do
        expect(LegitScript.new.function(list2)).to eq([])
      end

      it "returns an empty array for two different elements in collection" do
        expect(LegitScript.new.function(list3)).to eq([])
      end

      it "returns any element that appears more than once in collection" do
        expect(LegitScript.new.function(list4)).to eq([1])
        expect(LegitScript.new.function(list5)).to eq(["dog"])
        expect(LegitScript.new.function(list6)).to eq(%w(dog bird))
      end
    end
  end

  context "Refactor 1: #find_multiples_in" do
    describe "with meaningful names" do
      it "returns empty array for an empty collection" do
        expect(LegitScript.new.find_multiples_in(list1)).to eq([])
      end

      it "returns empty array for a single element collection" do
        expect(LegitScript.new.find_multiples_in(list2)).to eq([])
      end

      it "returns an empty array for two different elements in collection" do
        expect(LegitScript.new.find_multiples_in(list3)).to eq([])
      end

      it "returns any element that appears more than once in collection" do
        expect(LegitScript.new.find_multiples_in(list4)).to eq([1])
        expect(LegitScript.new.find_multiples_in(list5)).to eq(["dog"])
        expect(LegitScript.new.find_multiples_in(list6)).to eq(%w(dog bird))
      end
    end
  end

  context "Final solution: #show_duplicates" do
    describe "using idiomatic ruby" do
      it "returns empty array for an empty collection" do
        expect(LegitScript.new.show_duplicates(list1)).to eq([])
      end

      it "returns empty array for a single element collection" do
        expect(LegitScript.new.show_duplicates(list2)).to eq([])
      end

      it "returns an empty array for two different elements in collection" do
        expect(LegitScript.new.show_duplicates(list3)).to eq([])
      end

      it "returns any element that appears more than once in collection" do
        expect(LegitScript.new.show_duplicates(list4)).to eq([1])
        expect(LegitScript.new.show_duplicates(list5)).to eq(["dog"])
        expect(LegitScript.new.show_duplicates(list6)).to eq(%w(dog bird))
      end
    end
  end
end