#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しておくことで検索を高速化した。

GitHub pages でnode_modules下のファイルが404で読み込めない

問題

GitHub pages に置いてたページがwebで表示するとなぜか崩壊していた。

いつの間にか(何も変更してないのに!)、node_modules/ 下のファイルが404で読み込まなくなっていて、node_mosules/下のcssやjsファイルを読み込めむことができず、崩壊に至った様子。

解決

stackoverflow.com

どうやら、Githubページはデフォルトでnode_modulesフォルダを無視するJekyllのバージョンを使用するようになったとのこと。

Create an empty .nojekyll text file in the root of the gh-pages branch.

空の .nojekyll ファイルをルートに作成して解決。

$ touch .nojekyll

#2/20 Strings: Making Anagrams [Cracking the Coding Interview Challenges]

#2 Strings: Making Anagrams

www.hackerrank.com

2つも文字列を受け取って、両者がアナグラムになるまで不要な文字列を削除して削除した文字数を返す、という問題。

a = gets.strip.split("").sort
b = gets.strip.split("").sort

deletion = 0
until (a+b).empty? do
    if a.empty? || b.empty?
        deletion += (a.length + b.length)
        break
    end
    
    if a[0] == b[0]
        a.shift
        b.shift
    elsif a[0] < b[0]
        a.shift
        deletion += 1
    else
        b.shift
        deletion += 1
    end
end

puts deletion

感想

文字列をソートして、頭から順に1文字ずつ照合して削除数をカウントするやり方で解いた。 意外と素直にかけなかった。もっと良い解がありそう。

#1/20 Arrays: Left Rotation [Cracking the Coding Interview Challenges]

暇つぶしに、hacker rankの Cracking the Coding Interview Challenges を初めた。

平日毎日1題ずつ解けば20日で終わる程度のボリュームで良さそう。基本的にはrubyで解くつもり。

• DATA STRUCTURES 9題
• ALGORITHMS 6題
• TECHNIQUES/CONCEPTS 5題

www.hackerrank.com

#1 Array: Left Rotations

www.hackerrank.com

l1, l2 = $stdin.read.split("\n")
n, k = l1.split(" ").map(&:to_i)
a = l2.split(" ").map(&:to_i)

a.rotate!(k)
a.each do |v|
    print v
    print " "
end

hackerRank/LeftRotation.rb at master · tic40/hackerRank · GitHub

感想

最初だし易しめ。rotate メソッドを使ったのはちょっとチートだったかも…