#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 メソッドを使ったのはちょっとチートだったかも…

目黒でイスラエル人と熟成肉ステーキを食べる

同僚のイスラエル人の誘いで仕事終わりに、イスラエル料理を食べにいくことになった。

目黒にある Pink camila というお店。

www.pinkcamila.com

雑居ビルの2階にあるこじんまりとしたお店で、店内はテーブルが4つほど、イスラエル人シェフが１人で料理を作っている。

店内はテーブルが全て埋まっていて、賑わっていた。

熟成肉ステーキのショートロインとディップセット、さらにイスラエルの赤ワインYARDENを注文する。

Instagram

熟成肉がとても美味い。高かったけど、このボリュームと旨さなら納得できる値段だ。

ディップセットは、中東の味がした。中東独特の香辛料が入っていたからかな。写真はとっていないけど、とても綺麗な盛りつけで感動した。

イスラエル人の同僚と、シェフがなんとイスラエルの同郷出身で同じ歳、さらに2人とも奥さんが日本人という偶然で話が盛り上がった。

あとやはり宗教が絡む話はとても興味深い。

Apache Kafkaインストールからチュートリアルまで

Apache Kafkaとは？

Apache Kafka is an open-source stream processing platform developed by the Apache Software Foundation written in Scala and Java. The project aims to provide a unified, high-throughput, low-latency platform for handling real-time data feeds. *1

Apache Kafkaは、ScalaとJavaで書かれたApacheソフトウェア財団によって開発されたオープンソースのストリーム処理プラットフォームである。このプロジェクトは、リアルタイムのデータフィードを処理するための、高スループット、低レイテンシのプラットフォームを提供することを目指している。

What is Kafka good for?

It gets used for two broad classes of application:

• Building real-time streaming data pipelines that reliably get data between systems or applications

• Building real-time streaming applications that transform or react to the streams of data

Kafkaを使うことで

• システムまたはアプリケーション間で確実にデータを取得するリアルタイムのストリーミングデータパイプラインの構築が可能
• データストリームを変換または反応するリアルタイムのストリーミングアプリケーションを構築が可能

GitHub

github.com

Installing Kafka

Download the code

$ wget http://ftp.riken.jp/net/apache/kafka/0.10.2.0/kafka_2.11-0.10.2.0.tgz
$ tar -zxf kafka_2.11-0.10.2.0.tgz
$ cd kafka_2.11-0.10.2.0

Install java

$ yum search openjdk
$ yum install java-1.8.0-openjdk-devel

Tutorial

Kafkaのコマンドラインクライアントから、メッセージをKafkaクラスタに送信する。

Start the server

# start ZooKeeper server
$ bin/zookeeper-server-start.sh config/zookeeper.properties
# start Kafka server
$ bin/kafka-server-start.sh config/server.properties

Create a topic

$ bin/kafka-topics.sh --create --zookeeper localhost:2181 --replication-factor 1 --partitions 1 --topic test
# see the topic
$ bin/kafka-topics.sh --list --zookeeper localhost:2181

Send messages

$ bin/kafka-console-producer.sh --broker-list localhost:9092 --topic test

上記コマンド実行後、以下のメッセージをコンソールに続けて入力する。

$ bin/kafka-console-producer.sh --broker-list localhost:9092 --topic test
This is a message
This is another message

Receive messages(start a consumer)

メッセージ送信したクライアントとは別のクライアントを立ち上げ、以下のコマンドを実行する

$ bin/kafka-console-consumer.sh --bootstrap-server localhost:9092 --topic test --from-beginning

すると、メッセージ送信で入力したメッセージが受信される。

$ bin/kafka-console-consumer.sh --bootstrap-server localhost:9092 --topic test --from-beginning
This is a message
This is another message

references

• Apache Kafka

導入事例など

• LinkedIn http://sites.computer.org/debull/A12june/pipeline.pdf
• Yahoo! JAPAN ストリーム処理プラットフォームにおけるKafka導入事例 #kafkajp

*1:Apache Kafka - Wikipedia