Madogiwa Blog

主に技術系の学習メモに使っていきます。

クックパッドマートさんのエンジニア採用試験が公開されているみたいなのでやってみた🥞

Ruby 開発

以下のTweetを見かけて気になり、勉強がてら自分でも解いてみたので自分の回答がいい感じかはわからないですがメモしておきます📝

以下の環境でやってみました💻

$ ruby -v
ruby 3.0.0p0 (2020-12-25 revision 95aff21468) [x86_64-darwin18]

コードはGitHubに公開してみたのでこちらまで🐙

github.com

Q1 大きさは同じで重さが異なる商品が複数あるとします。この商品N個を、以下の条件にそって...

大きさは同じで重さが異なる商品が複数あるとします。この商品N個を、以下の条件にそって3つのトラックに分配するアルゴリズムを実装してください。

  1. すべての商品は同一の大きさ、重さの箱に入り、箱は個別のIDを持つものとする
  2. プログラム実行時は、コマンドライン引数で「箱ID」と「重さ」の情報を与え、プログラムの結果には各トラックに積載する「箱ID」を出力してください。たとえば 1:50 の文字列をコマンドライン引数で渡したときは、箱ID=1, 重さ=50kg の商品とする
  3. 商品は箱に入った状態で列となって連続で運び込まれ、重さは持ち上げるまでわからず、尚且つ同時に1つしか持ち上げられない
  4. それぞれのトラックには、なるべく重さが均等になるように分配する必要がある
  5. それぞれのトラックの積載可能重量に制限はない

実行例

$ ruby solve.rb 1:50 2:30 3:40 4:10
truck_1:1
truck_2:2,4
truck_3:3

自分の実装の実行結果

$ ruby exam_1/main.rb 1:50 2:30 3:40 4:10
truck_1:1
truck_2:2,4
truck_3:3

以下のような感じで実装してみました。

  • 実行時に渡されたid:重さ形式で渡された引数をsplit(':')でidとweightに分割し、idとweightをもとに荷物オブジェクトを生成
  • 3台のトラックのオブジェクトを生成
  • 荷物オブジェクトの配列をトラックに割り当てる
    • 重量は持ち上げるまでわからないということなので、とりあえず一番積載量の少ないトラックに乗せるようなロジックで実装してみた・・・！
  • 整形して結果を出力

荷物のトラックへの割当処理を行うクラス

class TruckAllocator
  def self.call(baggages:, trucks:)
    new(baggages: baggages, trucks: trucks).call
  end

  def initialize(baggages:, trucks:)
    @baggages = baggages
    @trucks = trucks
  end

  attr_reader :baggages, :trucks

  def call
    allocate
    result_text
  end

  private

  def result_text
    trucks.map(&:info_text)
  end

  def allocate
    baggages.each { |baggage| target_truck.baggages << baggage }
  end

  def target_truck
    # NOTE: 積載重量が一番少ないトラックをターゲットにする
    trucks.min { |a, b| a.weight <=> b.weight }
  end
end

Q2 任意の数のモンスターがいます。APIサーバーにそのうちの2匹を指定すると...

任意の数のモンスターがいます。APIサーバーにそのうちの2匹を指定すると、対戦をさせた結果を得ることができます。モンスターの強さは決まっていて、同じモンスター同士であれば、対戦の結果は常に変わりません。また、三すくみのような状態は考えないものとします。このAPIサーバーをつかって、モンスターを強い順に並べてください。

APIレスポンスの例

$ curl https://ob6la3c120.execute-api.ap-northeast-1.amazonaws.com/Prod/battle/dragon+griffin
{"winner":"dragon","loser":"griffin"}

実行例

ruby solve.rb griffin vampire dragon troll medusa

自分の実装の実行結果

$ ruby exam_2/main.rb griffin vampire dragon troll medusa
==== RESULT ====
No.1: troll
No.2: dragon
No.3: medusa
No.4: griffin
No.5: vampire

以下のような感じで実装してみました。

  • 実行時に渡されたモンスター(文字列)の配列を取得
  • 渡されたモンスターの配列をもとに順位付け
    • 最初のモンスターと次のモンスターを戦わせていき、最終的に勝ち残ったモンスターを1位で確定させて、2位以降も同様に行うような、勝ち抜け方式で順位付けするような形で実装してみましたが(バブルソートライクっぽい)、もうちょっといい方法がありそうな・・・！
  • 整形して結果を出力

以下が渡されたモンスターの配列をもとに順位付けを行うClassです。

require_relative './judge'

class Arena
  def initialize(monsters)
    @monsters = monsters
    @challengers = monsters.dup
    @results = []
  end

  attr_reader :monsters, :challengers, :results

  def call
    knockout_competition
    results_info
  end

  private

  # NOTE: 勝ち抜け方式でモンスターの順位付けを行うメソッド
  # ※ deleteを使っているので重複したモンスター(文字列)が渡された場合、名寄せされる
  # 例) dragon, dragon, troll => troll, dragon
  def knockout_competition
    until challengers.empty?
      champion = battle(challengers)
      results << champion
      challengers.delete(champion)
    end
    results
  end

  def battle(monsters)
    # NOTE: モンスターが1体の場合は、不戦勝で渡されたモンスターを勝ちとする
    return monsters[0] if monsters.length < 2
    judge = ->(winner, monster) { Judge.new(winner, monster).call['winner'] }
    champion, challengers = monsters[0], monsters[1..-1]
    challengers.inject(champion) { |winner, monster| judge.call(winner, monster) }
  end

  def results_info
    text = "==== RESULT ====\n"
    results.each_with_index do |result, index|
      text << "No.#{index + 1}: #{result}\n"
    end
    text
  end
end

以下がモンスター同士の勝敗判定を行うClassです。開発時にAPIにリクエストを投げるのは検証にも時間がかかるのと先方のサーバーに負荷を書けてしまうので、ローカルで検証出来る開発用ロジックも用意して切り替え可能にしました。

require_relative './judge/api_strategy'
require_relative './judge/develop_strategy'

class Judge
  def initialize(blue, red)
    @red = red
    @blue = blue
  end

  attr_reader :blue, :red

  def call
    DevelopStrategy.call(red, blue) # NOTE: 開発用のMockストラテジ
    # ApiStrategy.call(red, blue) # NOTE: APIを実際に呼び出すストラテジ
  end
end

Q3 APIサーバーのアプリケーションに性能改善を目的としてキャッシュを導入...

APIサーバーのアプリケーションに性能改善を目的としてキャッシュを導入するとします。アプリケーションのどの部分に、どのような手法でキャッシュを導入するのか記述したうえで、なぜその手法を導入するのか、メリットやデメリットを挙げて説明してください。

今回のQ2のケースで考えるとして、以下のようなキャッシュ等が考えられるかなと思いましたけど、どうなんだろう・・・🤔

  • モンスター同士の対戦結果を対戦するモンスター名のペアをキーにKVストア等にキャッシュ
    • メリット: DBへのアクセス + 勝敗判定処理の時間を削減
    • デメリット: モンスターのパラメータ変更等による同一モンスターの勝敗結果が変わる場合にキャッシュのリフレッシュが必要。KVストア等を導入する + 運用していくコストが掛かる。
  • モンスター単位の強さの計算結果をテーブルにキャッシュしそれを利用して判定を行う
    • メリット: 勝敗判定前にモンスターの強さを計算する処理を行っている場合には、その処理時間を削減
    • デメリット: モンスターのパラメータ変更等、強さに影響がある変更が入った場合には再計算が必要

おわりに

あまりアルゴリズムとかはちゃんと勉強したことがないので、あまり自信ないですが、こういう企業が採用に使っている問題を使って勉強出来ると一石二鳥感があってありがたいですね🙏

cookpad-mart-careers.studio.site