面接で聞かれた技術問題

未経験で転職活動中に聞かれた技術質問を復習も兼ねてまとめておきます。
何か不備やこうした方がいいなど、ご指摘いただければ幸いです。

#アルゴリズム
###フィボナッチ数列
（1, 1, 2, 3, 5, 8, 13, 21 ,,,のように第n+2項が、第n+1項と、第n項の和になるよう数列）

何番目の数字を求めるかを、コンソールに入力し、その番号の数字を返すプログラムを考える。

fib.rb

def fib(n)
  if n == 0 || n == 1
    return 1
  end
  fib(n - 2) + fib(n - 1)
end


puts "何番目の数字を求めますか？"
input = gets.chomp.to_i
puts fib(input)

こんな感じ。
一応動くけど、30番目くらいからめちゃくちゃ遅くなる。

###原因
例えばn=5を求めようとすると、

fib.rb

fib(5) = fib(3) + fib(4) #fib(3)とfib(4)が定義されていないので再計算
 fib(3) = fib(1) + fib(2)
  fib(2) = fib(0) + fib(1) = 2
 fib(4) = fib(2) + fib(3)
  fib(3) = fib(1) + fib(2)
   fib(2) = fib(0) + fib(1) = 2

n=5とかだとなんとかなるけど、数字が大きくなるにつれて時間がかかる。

###解決策
配列に保存してしまう

fib.rb

def fib(n)
  f = []
  f[0] = f[1] = 1
  if n >= 2
    (2..n).each do |i| #2〜nまでeachで回す
      f[i] = f[i-1] + f[i-2]  #2〜nのfib[i]を保存
    end
  end
  f[n]
end

puts "入力してください"
input = gets.chomp.to_i
puts fib(input)

これが直感的でわかりやすいように思う。

#SQL

以下のようなテーブルがあったとする。

生徒テーブル

id	名前
1	田中
2	山田
3	中田
教科テーブル

id	教科
1	数学
2	国語
3	英語
テストテーブル

id	生徒ID	教科ID	点数
1	1	1	40
2	1	2	50
3	1	3	70
4	2	1	60
5	2	2	50
6	2	3	80
7	3	1	80
8	3	2	70
9	3	3	50

問１
各生徒の名前と平均点を求めよ
（例　田中：◯点）

SELECT b.名前, AVG(点数)  --生徒の名前と平均点を表示
FROM テスト a                  --テストテーブルを「a」と名前をつける（任意）
INNER JOIN 生徒 b
ON a.生徒ID = b.id        --生徒テーブルのidとテストテーブルの生徒IDをくっつける
GROUP BY 生徒ID           --student_idでグループ化

問２
６０点未満の生徒と教科を表示

select b.名前, c.教科, a.点数
from テスト a 
inner join 生徒 b 
on a.生徒ID = b.id 
inner join 教科 c
on c.id = a.教科ID
where 点数 > 60

inner join で結合した後のテーブルのイメージはこんな感じ

id	生徒ID	教科ID	点数	id	名前	id	教科
1	1	1	40	1	田中	1	数学
2	1	2	50	1	田中	2	国語
3	1	3	70	1	田中	3	英語
4	2	1	60	2	山田	1	数学
5	2	2	50	2	山田	2	国語
6	2	3	80	2	山田	3	英語
7	3	1	80	3	中田	1	数学
8	3	2	70	3	中田	2	国語
9	3	3	50	3	中田	3	英語

外部キーなどを扱う時は便利

#まとめ
両方とも基本的な問題だが、結構あやふやにしているところもあり、
100%答えることができなかった・・・

webスクール等で簡単なwebアプリケーションなら作れるようにはなったが、
上記のようなアルゴリズムやSQLはフレームワークがうまくやってくれたりするので、理解していなくても作れてしまうのが現状です。

こういった言語に依らない基礎をもう一度やり直す必要があると思いました。

##因みに
フィボナッチ数列の問題は小学6年生で取り上げるレベルだそうです。
ぼやぼやしていたらあっという間に置いていかれるという危機感・・・