#7/20 Trees: Is This a Binary Search Tree? [Cracking the Coding Interview Challenges]

#7 Trees: Is This a Binary Search Tree?

www.hackerrank.com

データ構造が二分探索木になっているかどうかをチェックする問題。

• The value of every node in a node’s left subtree is less than the data value of that node.
• The value of every node in a node’s right subtree is greater than the data value of that node.

つまり、与えられたデータ構造が二分木探索木(左の子の値 < 親の値 < 右の子の値)となっているかどうかをチェックする。 チェックして、データ構造が二分探索木になっていれば、trueを、それ以外はfalseを返せばよい。

solution

python3での解

def check(root, min, max):
    if root == None:
        return True
    if root.data <= min or max <= root.data:
        return False
    return check(root.left, min, root.data) and check(root.right, root.data, max)
    
def checkBST(root):
    return check(root, float('-inf'), float('inf'))

github.com

Binary Tree とは

二分木（binary tree; 二進木、バイナリツリー）は、データ構造の1つである。根付き木構造の中で、あるノード（節点 node）が持つ子の数が高々2であるものをいう。典型的には2つの子はそれぞれ「左」「右」と呼ばれる。 たとえば、二分探索や二分ヒープを実装するために使われる。

二分木 - Wikipedia

Binary Search Tree とは

二分探索木（にぶんたんさくぎ、英: binary search tree）は、コンピュータプログラムにおいて、「左の子孫の値 ≤ 親の値 ≤ 右の子孫の値」という制約を持つ二分木である。探索木のうちで最も基本的な木構造である。

二分探索木 - Wikipedia

メアリと魔女の花を観た

*以下の内容はネタバレを含みます。

「メアリと魔女の花」を観てきた。

www.maryflower.jp

以前映画館で予告を観た時、とても面白そうだと思った。

予告を見る限り、どう観てもジブリ作品にしか見えないが、スタジオポノックというアニメ制作会社の作品らしい。

www.ponoc.jp

この制作会社はジブリの意思を受け継いだ人たちによって立ち上げられた会社のようだ。 まあそれはどうでもよくて、とにかく興味が湧いたので見ることにした。

イントロの赤毛の魔女

いきなり謎の赤毛の魔女が追手に追われるところから始まる。 この時点では何もわからないので、この赤毛の魔女が主人公なのかな？と思った。

花を奪って地上に墜落するまで、疾走感があって惹きつけられた。 思い返すとこのイントロが一番テンションが上った場面だった。

メアリは赤毛の魔女ではなかった。

赤毛の魔女のイントロが終わるとメアリが登場。あれ、同じ赤毛だけどさっきの魔女より幼いし顔も違う。 さっきの魔女が主人公の話ではないのか。

しばらくはメアリの日常パートが続く。良くも悪くも、使い古されたジブリっぽさのあるキャラクターアニメーション。

メアリのおっちょこちょい表現が割りと度を越していて、注意欠陥ではないかと疑うレベルに酷いのが気になった。

赤毛を気にしているところから、「赤毛」というのがキーワードでこの世界では特別だということが理解できる。

なぜギブ(黒猫)はメアリを夜間飛行へ案内した？

西洋の御伽話や寓話には、黒猫がしばしば魔女の使い魔として登場する。この映画も例外ではなく、黒猫が登場する。

ギブはメアリを夜間飛行まで案内するが、どうもここが腑に落ちない。 ギブにはティムを助けるという動機があることが後にわかるが、初回の案内時にはまだティムは攫われていなかったはずだ。

なぜギブはメアリを夜間飛行へ連れて行った？

ティムはなぜ変身実験台として攫われた？

これが一番の謎。 変身実験台に地上の動物が使われていたので、ティムも変身実験台の対象となることはわかるが、なぜティムが選ばれた？

箒に掘られていた文字は何？

なんだったんだろう？持ち主の名前でなければ、あれは魔法陣のようなものか？

夜間飛行によって烙印された手の紋章は何？

あの紋章は何だったのか？

エンドワ大学

実質、あの学校に存在しているのは、マダムとドクター、佐藤二朗(箒管理者)の3人だけしかない。

学校がこの物語に本当に必要だったのか疑問だ。

魔女という神秘的なワード使っておきながら、規格化された明るい大学で勉強するというあまりにも平凡なバックグラウンドが明らかになり一気に醒めてしまった。 魔女というのは、魔女狩りの文脈の魔女ではなく、ハリポタ文脈の魔法使い少女だったか。

ピーターとの関係

ピーターは恋人でもなんでもないし、そういうストーリーもない。 助けに行く動機として考えられるのは、完全に自分の失敗の尻拭いである。

再会後の恋心を頂いていると勘違いさせるような描写は本当に余計だったと思うし、中途半端だった。

シャーロットおばあちゃん

シャーロットおばあちゃんが実は謎の赤毛の魔女だったことが明かされる。

シャーロットおばあちゃんが、メアリに夜間飛行を取り返してくるようお願いするが、 おばあちゃん何も手助けができずにメアリに全てを託すことになる。

もう魔法を使えないと言っていたのは、歳を取ったから？それとも墜落するときに、髪が黒髪に戻っていたのでそのときに魔法の力を失った？

力が使えないにせよ、優しいおばあちゃんが、メアリに死ぬかもしれないような危険なことを丸投げするのはちょっと信じられなかった。 夜間飛行の力を使って1日だけまた魔法使いに(若返って)戻って、メアリと一緒にピーターを助けに行くぐらいの展開があってもよかったんじゃないかな。

メアリはただの赤毛少女だった

メアリは赤毛であり何かしら、シャーロットから魔女の血を受け継いでいると容易に予想できるが、魔女の力に目覚める、なんてことはなく、一度もその設定は生かされなかった。 そのため、メアリはただの平凡な赤毛少女、で終わってしまった。

これはメアリの成長物語ではない

魔女の力も、箒の修理も、呪文の解除も、全て他力で、メアリ自身の成長によって解決されたものではない。

結局このストーリーが何を伝えたかったのか、エンドロール中に色々思い返してみたが、何もわからなかった。

まとめ

魔女の宅急便、という映画はとても優れた作品であるということを再認識した。

#8/20 Heaps: Find the Running Median [Cracking the Coding Interview Challenges]

#8 Heaps: Find the Running Median

www.hackerrank.com

以下のような入力が与えられる。 1行目は、データの数、2行目以下はデータリストに追加する数となっている。

6
12
4
5
3
8
7

上記の入力が与えられた場合、1行毎にデータリストへ値を追加し、その時点でのデータリストの中央値を計算し以下のフォーマットで出力する。

12.0
8.0
5.0
4.5
5.0
6.0

solution

rubyで解いた。 rubyのsortメソッドを使えばarrayのソートについては何も考える必要はないが、本問題はそれではパスできないテストケースが用意されている(timeoutを起こす)。そのため、処理速度を考慮したコードを書く必要がある。 この問題では、1行毎にデータがリストへ追加されるため、ソートアルゴリズムとして挿入ソートを採用した。

def insertSort(ary, num)
    if ary.empty?
        ary << num
    else
        left, right, mid = 0, ary.length - 1, 0
        while left < right do
            mid = right <= 0 ? 0 : (left + right) / 2
            if num < ary[mid]
                right = mid - 1
            else
                left = mid + 1
            end
        end
        if num < ary[left]
            ary.insert(left, num)
        else
            ary.insert(left + 1, num)
        end
    end
    return ary
end

input = $stdin.read.split("\n").map(&:to_i)
n, nums, ary = input.shift, input, []
nums.each do |num|
    ary = insertSort(ary, num)
    len = ary.length
    puts (ary[(len - 1) / 2] + ary[len / 2]) / 2.0
end

github.com

中央値とは

中央値（ちゅうおうち、英: median）とは、代表値の一つで、有限個のデータを小さい順に並べたとき中央に位置する値。たとえば5人の人がいるとき、その5人の年齢の中央値は3番目に年寄りな人の年齢である。ただし、データが偶数個の場合は、中央に近い2つの値の算術平均をとる。中央値の事を、メディアン、メジアン、中間値とも呼ぶ。ただし、「中間値の定理」の中間値はこの意味ではない。

中央値 - Wikipedia

挿入ソートとは

挿入ソート（インサーションソート）は、ソートのアルゴリズムの一つ。整列してある配列に追加要素を適切な場所に挿入すること。平均計算時間・最悪計算時間がともにO(n2)と遅いが、アルゴリズムが単純で実装が容易なため、しばしば用いられる。安定な内部ソート。基本挿入法ともいう。in-placeアルゴリズムであり、オンラインアルゴリズムである。

挿入ソート - Wikipedia

感想

中央値算出は単純に見えて、案外嵌りやすい気がする。良問。

#6/20 Queues: A Tale of Two Stacks [Cracking the Coding Interview Challenges]

#6 Queues: A Tale of Two Stacks

www.hackerrank.com

キュー操作を行う問題。以下のような入力を受け取る。

6
1 42
2
1 14
3
1 28

1行目はデータの数。2行目以下は、1つもしくはスペース区切りで2つの数値が入力される。

最初の数値をtype、2つめの数値をx と呼ぶ。以下のような3タイプの操作を行う。

• type 1: x をキュー(enqueue)に追加する
• type 2: キュー値を１つ取り出す(dequeue)
• type 3: キューの先頭の値を表示する

solution

input = $stdin.read.split("\n")
n, lines, queue = input.shift.to_i, input, []

lines.each do |l|
    t, x = l.split(" ")
    case t
    when "1" then
        queue.push(x)
    when "2" then
        queue.shift
    when "3" then
        puts queue.first
    end
end

github.com

キューとは

キュー（英: queue）、あるいは待ち行列はコンピュータの基本的なデータ構造の一つ。データを先入れ先出し[1]のリスト構造で保持するものである。キューからデータを取り出すときには、先に入れられたデータから順に取り出される。キューにデータを入れることをエンキュー、取り出すことをデキューという。

キュー (コンピュータ) - Wikipedia

#5/20 Stacks: Balanced Brackets [Cracking the Coding Interview Challenges]

#5 Stacks: Balanced Brackets

www.hackerrank.com

括弧記号のみで構成される文字列が入力として渡される。 {, }, (, ), [, ] 文字列の括弧が均衡していれば、YES、それ以外は NO を出力する。

例えば{[(])}は均衡していない。なぜなら閉じていない([) 部分の(が閉じられていないから。

{[(])} # NO
{[()]} # YES

solution

table = {"[" => "]", "(" => ")", "{" => "}"}
input = $stdin.read.split("\n")
n, l = input.shift.to_i, input

l.each do |str|
    stack = []
    str.split("").each do |c|
        if !stack.empty? && "])}".include?(c)
            break if table[stack.last] != c
            stack.pop
        else
            stack.push(c)
        end
    end
    puts stack.empty? ? "YES" : "NO"
end

github.com

スタックとは

この類いの問題は上記のように配列でスタックを実現することによって簡単に解くことができる。

スタックは、コンピュータで用いられる基本的なデータ構造の1つで、データを後入れ先出し（LIFO: Last In First Out; FILO: First In Last Out）の構造で保持するものである。抽象データ型としてのそれを指すこともあれば、その具象を指すこともある。

スタック - Wikipedia

#4/20 Linked Lists: Detect a Cycle [Cracking the Coding Interview Challenges]

#4 Linked Lists: Detect a Cycle

www.hackerrank.com

linked lists(連結リスト)を題材にした問題。 リストを走査中にいずれかのノードが1回以上訪問された場合、trueを、それ以外の場合はfalse を返す。

solution

解答可能な言語選択にrubyがなかったため、今回はpythonで解いた。

def has_cycle(head):
    s = set()
    while head:
        if head in s:
            return True
        s.add(head)
        head = head.next

    return False

github.com

Linked Lists(連結リスト)とは

一連のノードが、任意のデータフィールド群を持ち、1つか2つの参照（リンク）により次（および前）のノードを指している。連結リストの主な利点は、リスト上のノードを様々な順番で検索可能な点である。連結リストは自己参照型のデータ型であり、同じデータ型の別のノードへのリンク（またはポインタ）を含んでいる。連結リストは場所が分かっていれば、ノードの挿入や削除を定数時間で行うことができる（場所を探すのにかかる時間はリスト上の順番の条件などにも依存するし、後述する片方向リストなのか双方向リストなのかにも依存する）。連結リストにはいくつかの種類があり、片方向リスト、双方向リスト、線形リスト、循環リストなどがある。

連結リスト - Wikipedia

#3/20 Hash Tables: Ransom Note [hacker rank / Cracking the Coding Interview Challenges]

#3 Hash Tables: Ransom Note

www.hackerrank.com

3行の入力が与えられる。

• 1行目: スペース区切りで、magazineの単語数、ransom note の単語数がそれぞれ数値で指定。
• 2行目: magazine の単語がスペース区切り
• 3行目: ransom note の単語がスペース区切り

上記の入力から、magazine の単語の集合を使ってransom noteの単語の集合を複製することができれば、"Yes" を出力、それ以外の場合は、"No" を出力する。

解

l1, l2, l3 = $stdin.read.split("\n")
m, n = l1.split(" ").map(&:to_i)
magazine, ransom = l2.split(" ").sort, l3.split(" ").sort

ransom.each do |v|
    i = magazine.index(v)
    if !i
        puts "No"
        exit
    end
    magazine.delete_at(i)
end
puts "Yes"

github.com

まとめ

単純にransom note の単語を1つずつ magazine 内の単語と照会、ヒットしたらmagazineから当該単語を削除して次の単語へ、ヒットしなければ、No を出力しプログラムを終了する。 ruby の index は配列の頭から検索するため、 最初にmagazine, ransom noteの単語配列を予めsortしておくことで検索を高速化した。