code interview

#19/20 Recursion: Davis' Staircase [Cracking the Coding Interview Challenges]

#19 Recursion: Davis' Staircase www.hackerrank.com 1 o 2 or 3段を一度に登れる人間が、n段の階段を登る際に、何通りの登り方が存在するか計算する問題。 以下のような入力が与えられる。 3 1 3 7 最初の行が階段の数。2行目以下は、階段のステップ数。 …

#18/20 Recursion: Fibonacci Numbers [Cracking the Coding Interview Challenges]

#18 Recursion: Fibonacci Numbers www.hackerrank.com 入力される数値nに対して、n項のフィボナッチ数を求めて出力する問題。 solution 問題文の通りに実装すると以下のようになる。 def fib(n) return n if n <= 1 return fib(n-1)+fib(n-2) end puts fib(…

#17/20 Time Complexity: Primalityh [Cracking the Coding Interview Challenges]

#17 Time Complexity: Primality www.hackerrank.com 素数判定を行う問題。 以下のような入力が与えられる。 3 12 5 7 一行目はデータの数。それ以降の数に対して、素数かどうか判定を行い、素数であれば'Prime'、そうでなければ'Not prime'を出力する。 上…

#16/20 BFS: Shortest Reach in a Graph [Cracking the Coding Interview Challenges]

16 BFS: Shortest Reach in a Graph www.hackerrank.com 以下の形式の入力が与えられる。 2 4 2 1 2 1 3 1 3 1 2 3 2 最初の行には、クエリの数を示す整数が示される。後続の行は、各クエリを次の形式で示す。 最初の行には、グラフ内のノードの数nとエッジ…

#15/20 DFS: Connected Cell in a Grid [Cracking the Coding Interview Challenges]

#15 DFS: Connected Cell in a Grid www.hackerrank.com 以下のような入力が与えられる。 4 4 1 1 0 0 0 1 1 0 0 0 1 0 1 0 0 0 1行目にn行、2行目にm列、それ以降はn行m列分のマトリックスがスペース区切りで与えられる。 マトリックス内で、1のセルが隣接…

#14/20 Binary Search: Ice Cream Parlor [Cracking the Coding Interview Challenges]

#14 Binary Search: Ice Cream Parlor www.hackerrank.com アイスクリーム屋で、持っているお金を全てを使い切って2個のアイスクリームを購入したい。 その組み合わせを見つける、という問題。 アイスクリーム屋には、様々なフレーバーのアイスがあり、それ…

#13/20 DP: Coin Change [Cracking the Coding Interview Challenges]

#13 DP: Coin Change www.hackerrank.com タイトルどおり、Dynamic Programming で解く問題。 以下のような入力が与えられる。 4 3 1 2 3 4 3 # {コインの組み合わせで達成したい値} {コインの種類数} 1 2 3 # コインの種類。この場合、価値が1, 2, 3の3種類…

#12/20 Merge Sort: Counting Inversions [Cracking the Coding Interview Challenges]

#12 Merge Sort: Counting Inversions www.hackerrank.com 以下のようなインプットが与えられる。 2 5 1 1 1 2 2 5 2 1 3 1 2 1行目はデータセットの総数 2行目以降はデータセットの総数分だけ以下の入力の繰り返し データの要素の数が整数で与えられる スペ…

#11/20 Sorting: Comparator [Cracking the Coding Interview Challenges]

#11 Sorting: Comparator www.hackerrank.com solution python3 での解答。 from functools import cmp_to_key class Player: def __init__(self, name, score): self.name = name self.score = score def comparator(a, b): if a.score > b.score: return -…

#10/20 Sorting: Bubble Sort [Cracking the Coding Interview Challenges]

#10 Sorting: Bubble Sort www.hackerrank.com solution 与えられた数値をバブルソートアルゴリズムを使って昇順にソートし、スワップ回数、ソートの最初と最後を指定のフォーマットで出力する問題。 以下、rubyでの解答。 def bubbleSort(n, elements) tota…

#9/20 Tries: Contacts [Cracking the Coding Interview Challenges]

#9 Tries: Contacts www.hackerrank.com シンプルなコンタクトリスト管理アプリケーションを作成する問題。 以下のフォーマットの入力が与えられる。 4 add hack add hackerrank find hac find hak 1行目はオペレーション数、2行目以下は、スペース区切りで…

#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…

#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行毎にデータリストへ値を追加し、その時点…

#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 …

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

#5 Stacks: Balanced Brackets www.hackerrank.com 括弧記号のみで構成される文字列が入力として渡される。 {, }, (, ), [, ] 文字列の括弧が均衡していれば、YES、それ以外は NO を出力する。 例えば{[(])}は均衡していない。なぜなら閉じていない([) 部分…

#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がなかったため、…

#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 の単語がスペース区切り …

#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)…

#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.hackerra…