Ruby 昨天有面试的算法题目,当抛砖引玉了

shooter · July 27, 2013 · Last by mok replied at June 30, 2016 · 16189 hits
Topic has been selected as the excellent topic by the admin.

第一个是 打印 斐波那契数,像 0 1 1 2 3 5 8 13 21 这样的

第二个 是找零算法

假设要用 50、20、10、5、1(元)找出 87 元来 make_change(87, [50,20,10,5,1)

#斐波那契数
#直接用递推,把之前的结果放在数组里面
def fibonacci step
  arr = [0,1]

  result = if step.to_i == 1
    0
  elsif step.to_i == 2
    arr
  else
    temp = step.to_i - 2
    temp.times do |i|
       size = arr.size
       arr << arr[size - 1] + arr[size - 2]
    end
      arr
  end

  puts result
end

第二个确实麻烦, 我的思路是从最大额的零钱开始,需要多少张, 再取余重复以上过程 (这个应该先排除上一个匹配的零钱,重新获取范围,我的没有做) 代码捉急啊

这种算法明显不是最优解,看计算出的结果就是了

def make_change money, coins = [50,20,10,5,1]
  result = if money == 0
    []
  elsif coins.include? money
    [money]
  else
    coins_count = []
    valid_coins = coins.select{ |coin| coin < money } #小于
    remainder = money

    valid_coins.each do |coin|

      num = remainder/coin
      remainder = remainder % coin

      next if num == 0 #余数小于当前的匹配值 进行下一论匹配
      num.times{ coins_count << coin }
      break if remainder == 0 || remainder < valid_coins.min #匹配完毕或者没有合适结果

    end
  end
    coins_count
end

各位具体说下找零的想法吧

PS 睡了段时间,去面的, 不知哪根神经抽抽儿 把公交卡放在家里 揣了个鼠标装包里就奔去了 都没弄出来,就当马后跑了

假设每人39美分的零钱

这 39 美分是干什么用的啊

~/sandbox  ruby change.rb
50
20
10
5
1
1

这还不是最优解,怎么才是最优解啊

第二题没看懂,什么叫没人 39 美分,然后用 50,20,10,5,1 找出 87?

去哪家公司面试啊?我记得我们公司就出过这两道题目。

好简单的题目,第一个,递归 recursion,当然应该用 dynamic programming,就是把已经计算过的数据计算出来,当然也可以使用迭代来实现。第二个,greedy algorithm 的一般案例了

这个解很好啊,就是可以写的更短点。如果 hr 还不满意,你用二进制移位来试试看。

def fib(step, initial = [0, 1], results = [0])
    i, j = initial
    return fib(step-=1, [j , i + j ], results << j) if step > 0
    results
end

fib(10)
# =>  [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
def make_change(money, coins = [50,20,10,5,1], results = [])
    change  = coins.find { |i| money - i >= 0 }
    left    = money - change
    results << change
    return make_change(left, coins, results) if left > 0
    results
end

#1 楼 @blacktulip #2 楼 @Ryan

那个多出来的 已经去除了

#3 楼 @hmilym 广联达 估计是你们公司了 ^_^

看题觉得好熟悉,似乎和 SICP 第一章里的题很相似。

第二题的确是是 SICP 里面的,

13 Floor has deleted

#11 楼 @luikore 这算是辗转相除的思路么

#14 楼 @staticor 跟 lZ 的思路一样,不过更简洁了

#14 楼 @staticor 算是个长除法,没辗转...

@luikore 二题优解,我来个第一题。

def p_fib(len)
   (0..len).map { |pos| (f = ->(x) { x < 2 ? x : f[x-1] + f[x-2] })[pos] }
end 

我也来贴个结果 17l @recurlamlisp 的迭代方式 最优雅肯定妥妥的 但是效率惨不忍睹... 35 个数字就要跑 11 秒 而且全部是 CPU 100% 我自己用了个笨办法 用数组递归 跟 6l @hysios 的思路类似 虽然不优雅 但是效率很快 500 个数字 a = [];(0..500).each{|i| r= (i<2 ? i : (a[-1]+a[-2]));a.push(r)};a 不知道各位喜欢代码优雅的 还是效率更快的...

如果面额是 [50,30,1] 需要找 60 块?所以说面额的设置是很有讲究的。Coursera 上有个相应的课程挺不错的 https://class.coursera.org/optimization-001/class/index

#11 楼 @luikore 为啥你总能写出这么变态的代码...

第二题参见 http://quake.iteye.com/blog/175886 。这个题目是有优化条件的,要求返回的零钱数尽可能少。否则有 1 分的话,直接写个循环给 39 或者 87 个就 ok 了。

只从第一个开始减不一定会得到最优解。 比如 make_change(14, [10, 7, 1]) ,的最优解是 [7, 7] ,只用 2 个单位。如果粗陋地从最大数开始,就会得出需要 1 个 10 和 4 个 1 的结果,那就是要用 5 个单位了。

#8 楼 @shooter 恩,的确是滴

虽然不是 ruby, 但是第一个我觉得可以贴一下文档里的例子..

import scala.math.BigInt
lazy val fibs: Stream[BigInt] = BigInt(0) #:: BigInt(1) #:: fibs.zip(fibs.tail).map { n => n._1 + n._2 }
fibs.take(1000).toList // 前1000个

@zj0713001 要效率那个那么写哦,玩 ruby 语法糖和 lambda 去了,完全只图好看哈!下面来个效率的

def fib(len)
  arr, a, b = [], 0, 1
  len.times do
    arr << a
    a,b = b, a+b
  end
  arr
end

@zj0713001 再来个经济适用型男的,嘿嘿

fib = Hash.new do |f, n|
  f[n] = if n <= -2
            (-1)**(n+1) * f[n.abs]
          elsif n <= 1
            n.abs
          else
            f[n-1] + f[n-2]
          end
end

这里还有个适用男,哈哈

def fib
    phi = (1 + Math.sqrt(5)) / 2
    ((phi**self - (-1 / phi)**self) / Math.sqrt(5)).to_i
end

#11 楼 @luikore 记得找零算法有个高难度的版本,就是限制各种面值的货币数目的情况,比如找 $160,但是货币只有这些:$100 => 1, $50 => 1, $20 => 3, $5 => 1。有没有好的方法?

还有个我喜欢的

def fib
   a, b = 1, 1
   lambda {ret, a, b = a, b, a+b; ret}
end

fib_gen = fib
10.times {  p fib_gen.call } 

=> 1
=> 1
=> 2
=> 3
=> 5
=>  8
=> 13
=> 21

#11 楼 @luikore

必须 Prolog 啊,输入一遍题目就可以了

#!/usr/bin/swipl -q -g main -f

:- use_module(library(simplex)).

coins -->
    constraint(integral(c(50))),
    constraint(integral(c(20))),
    constraint(integral(c(10))),
    constraint(integral(c(5))),
    constraint(integral(c(1))),
    constraint([c(50)] >= 0),
    constraint([c(20)] >= 0),
    constraint([c(10)] >= 0),
    constraint([c(5)] >= 0),
    constraint([c(1)] >= 0),
    constraint([50*c(50), 20*c(20), 10*c(10), 5*c(5), 1*c(1)] = 87),
    minimize([c(50), c(20), c(10), c(5), c(1)]).

main :-
    gen_state(S0),
    coins(S0, S),
    variable_value(S, c(50), C50),
    variable_value(S, c(20), C20),
    variable_value(S, c(10), C10),
    variable_value(S, c(5),  C5),
    variable_value(S, c(1),  C1),
    io:format("~w*50 ~w*20 ~w*10 ~w*5 ~w*1~n", [C50, C20, C10, C5, C1]),
    halt.

#19 楼 @doitian

Prolog 无压力

#!/usr/bin/swipl -q -g main -f

:- use_module(library(simplex)).

coins -->
    constraint(integral(c(50))),
    constraint(integral(c(30))),
    constraint(integral(c(1))),
    constraint([c(50)] >= 0),
    constraint([c(30)] >= 0),
    constraint([c(1)] >= 0),
    constraint([50*c(50), 30*c(30), 1*c(1)] = 60),
    minimize([c(50), c(30), c(1)]).

main :-
    gen_state(S0),
    coins(S0, S),
    variable_value(S, c(50), C50),
    variable_value(S, c(30), C30),
    variable_value(S, c(1),  C1),
    io:format("~w*50 ~w*30 ~w*1~n", [C50, C30, C1]),
    halt.

#21 楼 @swachian

Prolog

#!/usr/bin/swipl -q -g main -f

:- use_module(library(simplex)).

coins -->
    constraint(integral(c(10))),
    constraint(integral(c(7))),
    constraint(integral(c(1))),
    constraint([c(10)] >= 0),
    constraint([c(7)] >= 0),
    constraint([c(1)] >= 0),
    constraint([10*c(10), 7*c(7), 1*c(1)] = 14),
    minimize([c(10), c(7), c(1)]).

main :-
    gen_state(S0),
    coins(S0, S),
    variable_value(S, c(10), C10),
    variable_value(S, c(7),  C7),
    variable_value(S, c(1),  C1),
    io:format("~w*10 ~w*7 ~w*1~n", [C10, C7, C1]),
    halt.

#27 楼 @gihnius

#!/usr/bin/swipl -q -g main -f

:- use_module(library(simplex)).

coins -->
    constraint(integral(c(100))),
    constraint(integral(c(50))),
    constraint(integral(c(20))),
    constraint(integral(c(5))),
    constraint([c(100)] >= 0),
    constraint([c(50)] >= 0),
    constraint([c(20)] >= 0),
    constraint([c(5)] >= 0),
    constraint([c(100)] =< 1),
    constraint([c(50)] =< 1),
    constraint([c(20)] =< 3),
    constraint([c(5)] =< 1),
    constraint([100*c(100), 50*c(50), 20*c(20), 5*c(5)] = 160),
    minimize([c(100), c(50), c(20), c(5)]).

main :-
    gen_state(S0),
    coins(S0, S),
    variable_value(S, c(100), C100),
    variable_value(S, c(50),  C50),
    variable_value(S, c(20),  C20),
    variable_value(S, c(5),   C5),
    io:format("~w*100 ~w*50 ~w*20 ~w*5~n", [C100, C50, C20, C5]),
    halt.

#21 楼 @swachian

是的... 不过对一般货币如现在的人民币/美元的面额配置是最优解:

如果一个解法是最优解, 那其中除了最大面额外,1,5,10,50,100,500,...等面额都最多是 1 张 (如果有 2 张,可以抽出来替换成 x2 的面额). 而其中 2,20,200,...等面额最多是 2 张 (如果有 3 张 2,可以抽出来替换成 1 张 5 和 1 张 1). 所以最优解里,每一十进位上的和最多是 1+2*2+5 = 10, 但 = 10 就能替换成 1 张 10, 不算最优解了,所以和最多是 9. 于是最优解里小面额的总和不超过 999... , 还是小于 1 张最大面额. 综上,对于人民币/美元,粗鄙解得出来的结果和最优解一致。

@gihnius 粗鄙改造 luikore 的解法,不一定是最优结果,但是满足要求。

def make_change r, coins = {50 =>1, 20=>2, 10=>3, 5=>4, 1=>5}, result=[]

  coins.each do |c, amount|
    try = r.divmod(c)

    if try.first <= amount
      coins.delete(c)

      result << try.first
      result << make_change(try.last, coins)

    else
      r = r-c*amount
      coins.delete(c)

      result << amount
      result << make_change(r, coins)

    end
  end
  result.flatten
end

#32 楼 @bhuztez 这应该是 ruby 职位的面试题,呵呵。Prolog 的语法太烦人,而且可以看出只是输入逻辑表达式的代码,都比用 ruby 实现整个过程的代码多。

算法题有用过程式描述的,有用函数式的,逻辑型编程语言无法考察做题人员懂不懂算法的。

#33 楼 @luikore 是啊,所以我看这道题后最大的感触是设计货币面值的人真牛。10 5 2 1 的配置是很有学问的。

#35 楼 @swachian 等你想明白为什么你的 Ruby 代码该怎么写的时候,我的 Prolog 都输入完毕了,而且仅凭目测就能知道对不对了...

@bhuztez Prolog 是挺好玩的,再来一个解法总数的例子。我来个 ruby 的:

def make_change2(amount, coins)
  n, m = amount, coins.size
  table = Array.new(n+1){|i| Array.new(m, i.zero? ? 1 : nil)}
  for i in 1..n
    for j in 0...m
      table[i][j] = (i<coins[j] ? 0 : table[i-coins[j]][j]) +
                    (j<1        ? 0 : table[i][j-1])
    end
  end
  table[-1][-1]
end

#38 楼 @recurlamlisp 你总得说一下题目是什么吧

#39 楼 @bhuztez 就是求所有可以行的通的找钱方法总数

#40 楼 @recurlamlisp

#!/usr/bin/swipl -q -g main -f

:- use_module(library(clpfd)).
:- use_module(library(aggregate)).

coins([C50, C20, C10, C5, C1]) :-
    Vars = [C50, C20, C10, C5, C1],
    Vars ins 0 .. sup,
    50*C50 + 20*C20 + 10*C10 + 5*C5 + C1 #= 87,
    labeling([], Vars).

main :-
    aggregate_all(count, coins(_), Count),
    io:format("~w~n", [Count]),
    halt.

#30 楼 @bhuztez 这是开挂啊。看了下 Ruby 下也有些现成的 CP solver 的封装,比如这个 http://gecoder.rubyforge.org/documentation/index.html

#42 楼 @doitian gecoder 太复杂,amb 就可以了,不过推断其实没有 prolog 做得细致,prolog 可以选回溯策略的

除了感慨 还是感慨,尼麦还让人活么

#42 楼 @doitian 原生功能不算开挂吧

@shooter 如果加上分,0.50 0.20 0.10 0.05 0.02 0.01,还有各零钱种类的剩余数量,应该会更好玩。

@luikore @bhuztez @doitian 玩 Constraint 这种 Logic,用不好玩了,写个或者扩展个才 hacking. 看这里,看这里,http://minikanren.org/

#37 楼 @bhuztez 逻辑式语言处理有些问题确实轻松。受得了 Prolog 的语法就好。我是一看这东西的语法长的像 erlang,就闪人了。

#48 楼 @swachian 是 Erlang 像 Prolog 好不好...

#47 楼 @recurlamlisp 你看明白 minikanren 的实现了么?

@bhuztez 学习 ing, -_-

@swachian 语法不长, λProlog 可以参考

#47 楼 @recurlamlisp mark 挖出不少好东西

#11 楼 @luikore 你这是正解吗?看很多人都说你那是优解,我怎么看不懂?求解释

[22] pry(main)> def make_change r, coins = [50,20,10,5,1]
[22] pry(main)*   coins.map do |c|  
[22] pry(main)*     q, r = r.divmod c    
[22] pry(main)*     q    
[22] pry(main)*   end    
[22] pry(main)* end  
=> nil
[23] pry(main)> make_change 87
=> [1, 1, 1, 1, 2]

Ruby2.0

我也玩一个简单的,DP 算法:找零钱需要最小零钱数量。

def make_change(par, changes)
  change_used = []
  change_used[0] = 0

  1.upto(par) do |cur| #从1块钱开始算
    min_change = cur
    changes.each do|value|
      if value <= cur
        temp = change_used[cur - value] + 1  #已知的动态规划找零问题递推式
        min_change = temp if temp < min_change
      end
    end

    change_used[cur] = min_change

    puts "找#{cur}块零钱最少需要#{min_change}张零钱"
  end
end

make_change(87, [50, 20, 10, 5, 1])

看来 LZ 挺喜欢用 result = if ... 这类结构的。看大神们写的方法要琢磨好久。。真是智捉。我还是用最基本方法好了。

def fib(n) 
  return n if n <= 1
  fib(n-1) + fib(n-2)
end
(0...9).each { |n| p fib(n).to_s+' ' }

@doitian 喜欢?如果还是个 schemer 的话,看这里 http://docs.racket-lang.org/racklog/

#6 楼 @hysios 这递归漂亮。 #32 楼 @bhuztez 这算作弊吗

#55 楼 @blackanger

make_change(87, [50, 20, 10, 5, 1]) => [1, 1, 1, 1, 2] 是 50*1 +20*1+10*1+5*1+1*2 = 87 差了点东西

第二个不是动规么

def make_change(money, coins)
  dp = [0]
  path = []
  result = {}

  coins.each_with_index do |coin, index|
    coin.upto(money) do |i|
      if !dp[i - coin].nil? && (dp[i].nil? || dp[i - coin] + 1 < dp[i])
        dp[i] = dp[i - coin] + 1
        coins[index] += 1
        path[i] = i - coin
      end
    end
  end

  if path[money].nil?
    puts "impossible." and return
  end

  i = money
  loop do
    break if path[i].nil?
    result[i - path[i]] ||= 0
    result[i - path[i]]  += 1
    i = path[i]
  end

  p result                # 具体解
  puts dp[money]    # 硬币数
end

这个和 @blackanger 的算法相同,多了记录具体解

#56 楼 @nickelchen @blackanger 这个递归看上去比较好,但实际上复杂度是O(2^n)的。 @shooter 的斐波那契的复杂度是 O(n) 的 实际上用矩阵乘法,复杂度是可以到 O(logn) 的 如下

require 'matrix'

def fab(n)
  return 0 if n == 0
  m = Matrix[[1, 1], [1, 0]]
  mul([m] * n)[0, 1]
end

def mul(matrices)
  return matrices[0] if matrices.size == 1
  mid = matrices.size / 2
  return mul(matrices[0, mid]) * mul(matrices[mid..-1])
end

(1..10).each { |n| puts fab(n) }

# 1
# 1
# 2
# 3
# 5
# 8
# 13
# 21
# 34
# 55
def count_with_record(money,money_kinds,used,way = [],ways)
    if money == 0
        ways << way
        return 1
    elsif money < 0 or money_kinds.empty?
        return 0
    end
    way1 = copy(way)
    way1 << money_kinds[0]
    way2 = way
    return count_with_record(money - money_kinds[0],money_kinds,money_kinds[0],way1,ways) + count_with_record(money,money_kinds[1..-1],0,way2,ways)
end

def copy(arr)
    r = []
    arr.each do |e|
        r << e
    end
    return r 
end

money_kinds = [3,2,1]
money = 5
ways = []
way = []
puts count_with_record(money,money_kinds,way,ways)
puts "should be 5"

puts "all the combination"
puts ways.inspect

写的丑了些。。。

fib,可以一边递归,一遍记录(放到 hash 里面),这样复杂度应该可以。

@xranthoar @blackanger @nickelchen @shooter 请看 26 楼,效率高?一看明了!

@blackanger @xranthoar 前面人用了 Greedy approach 解,后面大家又用 Dynamic Programming . 我也在来个 dp,Greedy approach 太短了确实精简了,还是挺喜欢 Greedy approach

def make_change(amount, coins = [25, 10, 5, 1])
  coins.sort! { |a, b| b <=> a }

  optimal_change = Hash.new do |hash, key| 

    hash[key] = if key < coins.min        
      []
    elsif coins.include?(key)
      [key]
    else
      coins.
      reject { |coin| coin > key }.

      inject([]) {|mem, var| mem.any? {|c| c%var == 0} ? mem : mem+[var]}.

      map { |coin| [coin] + hash[key - coin] }.

      reject { |change| change.inject(&:+) != key }.

      min { |a, b| a.size <=> b.size } || []
    end
    puts hash
    hash[key]
  end

  optimal_change[amount]
end

#65 楼 @recurlamlisp 可惜 n 次幂的复杂度是 O(log(n)), 另外由于根号结果是浮点数结果不准...

#67 楼 @luikore O logn 已经很低了啊,还能搞成 O 1 不成...

#68 楼 @blacktulip fib 通项公式同样是 O(logn), 计算比矩阵法多...

浮点求幂也有 O(1) 的实现,方法是利用 x86 上的两个浮点指令 FYL2X (求 2 为底的对数), F2XM1 (求 2 为底的幂), 把 x**n 转换成 2 ** (n * log2(x)), 每步操作都是常数级,那就 O(1) 了... 但实际上这两个指令耗费大量的时钟周期,比求整数次幂的 O(logn) 算法慢...

第一题这么做可以么?

def f t
  a, b = 0, 1
  t.times do 
    print a, " "
    a, b = b, a + b
  end
end

f 200

第二题就这么干吧

def make_carge money
  choice = [50, 20, 10, 5, 1]
  result = [0,  0,  0,  0, 0]

  point = 0

  while money != 0
    if(money >= choice[point])
      money -= choice[point]
      result[point] += 1
    else
      point += 1
    end
  end

  5.times do |i|
    print choice[i], ' : ',  result[i], "\n"
  end
end

make_carge 87

或者干掉一个数组


def make_carge money
  choice = [50, 20, 10, 5, 1]
  result = 0

  point = 0

  while money != 0
    if(money >= choice[point])
      money -= choice[point]
      result += 1
    else
      point += 1
      print result, "  "
      result = 0
    end
  end
  puts result
end

make_carge 4201

#69 楼 @luikore 通项公式有浮点精度问题

update:不好意思没看到之前的回复,你已经提出了精度问题

#71 楼 @davidqhr 这个不能得最优解噢

#73 楼 @xranthoar 我本来还想写个二分矩阵,居然是你给出了..

#74 楼 @sqrh 啊,胡总!

@xranthoar @sqrh @luikore @blacktulip 算法效率确实都是 O(log(n)), 不错! 这个两个算法应该都是对大数据计算来说的吧,浮点计算不精确这个说法应该就忽略了吧。而且,在现代计算机的浮点计算不是 x86 的两条指令 FYL2X 和 F2XM1 可以概括的吧!从下面这个结果可以看出,我们的 Two-Term CRT 和 The Lucas Numbers 在现在的计算机的表现是相近的吧(虽然这个结果 The Lucas Numbers 更胜一筹),就是不知道更多的大型机上的那个表现更加的完美。

@recurlamlisp 大神不说话,一说就是经典啊。

#37 楼 @bhuztez 复杂问题都交给计算机做吧!想问题伤大脑啊。

#32 楼 @bhuztez prolog 看上去的确很牛啊,这几天开始看 prolog 了。ruby 真不方便干这些事,这是我的 ruby 方案,有点费劲:

def make_changes(need, coins, feed = {})
  valid_coins  = coins.keys.select{|c| c <= need && coins[c] > 0 }.sort.reverse
  valid_coins.each do |c|
    feed[c] ||= 0
    feed[c] += 1
    return feed if c == need
    coins[c] -= 1
    f = make_changes( need - c, coins, feed)
    return f if f
  end
end

#> make_changes 160, { 1 => 4, 5 => 1, 10 => 1, 50 => 1, 100 => 1}
=> {100=>1, 50=>1, 10=>1}

#> make_changes 160, { 1 => 4,5 => 2, 10 => 0, 50 => 1, 100 => 1}
=> {100=>1, 50=>1, 5=>2}

关于第一题:

def fibonacci(n, cache=Hash[[[0,0],[1,1]]])
    return cache[n] if cache[n]
    cache[n] = fibonacci(n-2, cache) + fibonacci(n-1, cache)
end
puts (1...1000).to_a.collect{|t| fibonacci(t) }.join(', ')

斐波那契函数的经典解决方案是使用递归 (太精深的数学实在不懂,比如 26 楼的方案), 常规的方法在小数字上很容易,但一旦数字过大,计算量就相当恐怖,这里用了个缓存 Hash, 即使数字达到 1000, 基本上一运行就能得出结论。

为什么我不能够发帖呢

我为什么不能发帖呢

学习中…

斐波那契数 arr = [0, 1] step = 8 (1..step).each {|i| arr << arr[-2] + arr[-1]} ==> [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

You need to Sign in before reply, if you don't have an account, please Sign up first.