エンジニアとして世界の最前線で働く選択肢 という本にあったコーディング面接の問題を、勉強がてらHaskellで解いてみた。
ちなみに原文ではJavaを使って3パターンの実装方法を示している。
その中で最も単純な、二重ループを使った o(n^2) の解法を再現した。
お題
入力として、intからなる配列と、ターゲットとなる数が一つ与えられます。
和がターゲット数となるような2つの数を配列から取り出す関数を書いて下さい。
補足
- 返り値は、整数値(Int) 。片方がわかればもう片方は自明だから
- 複数ある場合も、一つを返せば良い
- 無かった場合は 0 を返す
- 同じ値は使えない
- 入力の配列はソートされていない
実装
main.hs
hasPartner :: Int -> Int -> [Int] -> Bool
hasPartner _ _ [] = False
hasPartner t x (y:ys)
| x + y == t = True
| otherwise = hasPartner t x ys
getPair :: Int -> [Int] -> Int
getPair _ [] = 0
getPair t (x:xs)
| hasPartner t x xs = x
| otherwise = getPair t xs
main :: IO ()
main = do
print $ hasPartner 5 2 [2, 3] -- => True
print $ hasPartner 10 2 [2, 3] -- => False
print $ getPair 6 [3, 2, 1, 3] -- => 3
print $ getPair 10 [1, 2, 3, 2, 5, 3] -- => 0
[追記]
@hirakata さんに教えて頂きました！
わずか3行、一つの関数だけで処理が書けます。
こちらの方が簡潔で、めっちゃいいと思います。
import Data.List (tails)
getPair :: Int -> [Int] -> Int
getPair t xs = case [n | (n:ns) <- tails xs, n' <- ns, n + n' == t] of
(n:_) -> n
[] -> 0
main = do
print $ getPair 6 [3, 2, 1, 3] -- => 3
print $ getPair 10 [1, 2, 3, 2, 5, 3] -- => 0
[/追記]
メモ・感想
- for文が無くてもプログラムって書けるんだな
- 再帰が書けるようになってくると楽しい
- 原文では見つからなかった時に
ValueNotFoundExceptionを投げている。例外の投げ方は後で勉強しよう - もっと良い書き方がある気がするので教えてもらえたら非常に喜びます