Kuehar's Blog

概要 問題 解法 概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day110「1535. Find the Winner of an Array Game」 次回 その内 Twitter やってます。 問題 682. Baseball Game 難易度はEasy。 久しぶりでいろいろ忘れているのでひとまずEasy の問題を潰そうかなと思います。 問題としては、あなたは野球の試合に出場することになりました。このゲームはいくつかのラウンドで構成されており、過去のラウンドの得点が将来のラウンドの得点に影響を与える可能性があります。 ゲームの最初に、あなたは空のレコードで開始します。ops[i]はレコードに適用しなければならない第一の操作であり，以下のいずれかである． 整数 x - x の新しいスコアを記録します。 “+” - 前の2つのスコアの合計を新しいスコアとして記録します。前の 2 つのスコアが常に存在することが保証されています。 “D” - 前のスコアの2倍の新しいスコアを記録します。これは、常に前のスコアが存在することを保証します。 “C” - 前回のスコアを無効にし、記録から削除します。これは、常に前のスコアが存在することを保証するものです。 レコード上のすべてのスコアの合計を返します。 Example 1: Input: ops

Elements of Programming Interviews in Python C++とかJavaとかで解説をしている本はあったけどPythonで解説している本はなかったので5000円ちょい出して本を買ってみた。 この本は以下の記事でたまたま知ったのだが、 【21新卒SWE】 私はこうしてGoogleに落ちた ~Googleに挑んだ120日~ 個人的にPythonを使ってLeetCodeを解いていた時期があったので読んでおいて損はないのだろうと思い、本にしては高いが楽しく時間が潰せそうだったので海外から取り寄せた。(上の記事の人のスペックが高すぎて初めて読んだ時に驚いた) もちろん英語なのでパラパラっと読むのにも時間はかかったけども、ざっと読んで見た感じアルゴリズムとデータ構造だけではなくてPythonの言語的な仕様について触れていたり、オブジェクト指向はなんぞやとかシステムデザインについてだったりとかこれ一冊を読んで場数を踏めば面接の通過率がかなり上がりそうな感じ。 今の所そういう面接とかを受けたりする予定はないけど、将来どうなるかなんて分からないし、何より面接で必要とされるということはITエンジニアとして知っておいておかないとまずいということだから格闘しながら詳細まで読んでいくべきなのかなー、と思いました。 それにしても、今の段階でもあー、Pythonでコーディング面接受けるならこれ読んどけば大丈夫そうだなって感じがするくらいデカくて分厚い。 もちろん面接に臨む以上、問題との相性の運とか募集しているポジションに合う人材とかその他諸々の要素はあるんだろうけども、僕はその場の機転が効くタイプではないのでコツコツ勉強して地道に実力を伸ばしていくしかない。 コツコツ読んでハマりそうな部分をメモって直前に思い出すだけでも全然違うし、何より業務、もしくは趣味で触ったことがあっても僕の劇弱記憶装置では覚えていても正確に説明できるか分からないので、そう言った所で自信を持って臨めるようにするためにも頑張ろ〜って感じで！ あ、ちなみにPythonを書いて競技プログラミングとかやられてる人にも良い本だとは思うのですが、英語の壁、そして日本語の本( Ｐｙｔｈｏｎで学ぶアルゴリズムとデータ構造 (データサイエンス入門シリーズ )  )とかで十分だと思うのでそういった所に不安を感

 久しぶりにLeetCodeを開いたらヘッダーにこんな物が。 ん？こんなのあったっけ？ って思って開いてみると どうやら実際に面接形式で時間を測って問題に挑戦でき、他の人とスコアを競いあったりできるらしい。 ということでひとまず試しに一番最初の問題に挑戦してみた。 問題が二つ出題されて、片方は数字の配列が与えられて両隣の値よりも大きい値(ここではPeakと呼んでいた)のインデックスを返してね！っていう問題。 もう片方は文字列が与えられて、文字列が繰り返しになっていればTrueを、それ以外だったらFalseを返す問題。 うろ覚えだけどこんな感じでした。 これから解く人もいるかもしれないので解き方は割愛。 ちなみに僕は解いたことがあった問題だったので比較的スムーズに解けました。 解いたらこんな感じでスコアが出て、へぇー、ってなる(小並感) こういう形式で解く練習はかなり慣れるために良いのでは？と感じたので時間があるときに解いていこうと思った。 ただ、いきなり行き当たりばったりでコードを書いたりするのではなくて、しっかり紙とかに疑似コード的な奴を書きながらの方がより良い練習になりそうな気がするので次回からはそんな感じで。 にしても僕が見てなかっただけで、もともとあったのかもしれませんがとてもいい機能だと思います。なかなか制限時間ありのこういうので勉強することはなさそうですし。 では今回はここまで。

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 リンク集 この記事をストックしておくと新しい記事の追加時に通知されます。 コードだけ見たい方はこちらの Github をご覧ください。 番号はLeetCodeの問題へのリンク、問題のリンクは解説記事についてのリンクです。 間違えているリンク等あればコメント頂けると幸いです。 Day 番号 問題 難易度 1 1389 Create Target Array in the Given Order Easy 2 1108 Defanging an IP Address Easy 3 1313 Decompress Run-Length Encoded List Easy 4 938 Range Sum of BST Easy 5 1266 Minimum Time Visiting All Points Easy 6 1342 Number of Steps to Reduce a Number to Zero Easy 7 104 Maximum Depth of Binary Tree Easy 8 1302 Deepest Leaves Sum Medium 9 701 Insert into a Binary Search Tree Medium 10 1431 Kids

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day97 「349. Intersection of Two Arrays」 次回 ゼロから始めるLeetCode Day99 「112. Path Sum」 Twitter やってます。 問題 39. Combination Sum 難易度はMedium。 コーディング面接対策のために解きたいLeetCode 60問 からの抜粋です。 問題としては、候補番号（候補）（重複なし）と目標番号（目標）の集合が与えられたとき、候補番号の和が目標になるような、候補の中のすべてのユニークな組み合わせを求めなさい、というものです。 なお、同じ繰り返し数は何度でもいいとします。 Example 1: Input: candidates = [2,3,6,7], target = 7, A solution set is: [ [7], [2,2,3] ] Example 2: Input: candidates = [2,3,5], target = 8, A solution set is: [ [2,2,2,2], [2,3,3], [3,5] ] 解法 class Solution : def combinationSum ( self , candidates

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day95「82. Remove Duplicates from Sorted List II」 次回 ゼロから始めるLeetCode Day97 「349. Intersection of Two Arrays」 Twitter やってます。 問題 78. Subsets 難易度はMedium。 コーディング面接対策のために解きたいLeetCode 60問 からの抜粋です。 問題としては、異なる整数の集合 nums が与えられます。 その中の可能なすべての部分集合を返します。 なお、解の集合には重複した部分集合を含んではいけません。 Example: Input: nums = [1,2,3] Output: [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ] 解法 class Solution : def subsets ( self , nums : List [ int ] ) - > List [ List [ int ] ] : ans = [ ] def dfs ( temp , end ) : ans . append (

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day96 「78. Subsets」 次回 ゼロから始めるLeetCode Day98「39. Combination Sum」 Twitter やってます。 問題 349. Intersection of Two Arrays 難易度はEasy。 コーディング面接対策のために解きたいLeetCode 60問 からの抜粋です。 問題としては、2つの配列が与えられたとき，その交点を計算する関数を書いてくださいというものです。 Example 1: Input: nums1 = [1,2,2,1], nums2 = [2,2] Output: [2] Example 2: Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4] Output: [9,4] 解法 class Solution : def intersection ( self , nums1 : List [ int ] , nums2 : List [ int ] ) - > List [ int ] : set1 , set2 = set ( nums1 ) , set ( nums2 ) return list ( set1 &a

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day94 「929. Unique Email Addresses」 次回 ゼロから始めるLeetCode Day96 「78. Subsets」 Twitter やってます。 問題 82. Remove Duplicates from Sorted List II 難易度はMedium。 コーディング面接対策のために解きたいLeetCode 60問 からの抜粋です。 問題としては、ソートされた連結リストが与えられた場合、重複した番号を持つすべてのノードを削除し、元のリストとは異なる番号のみを残します。 同様にソートされた連結リストを返します。 Example 1: Input: 1->2->3->3->4->4->5 Output: 1->2->5 Example 2: Input: 1->1->1->2->3 Output: 2->3 解法 # Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val #

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day93 「49. Group Anagrams」 次回 まだ Twitter やってます。 問題 929. Unique Email Addresses 難易度はEasy。 コーディング面接対策のために解きたいLeetCode 60問 からの抜粋です。 問題としては、すべての電子メールは、@記号で区切られたローカル名とドメイン名で構成されています。 例えば、alice@leetcode.com では、alice がローカル名で、 leetcode.com がドメイン名です。 小文字の他に、これらの電子メールには ‘.‘や’+‘が含まれている場合があります。 メールアドレスのローカル名の一部の文字の間にピリオド(’.’)を追加すると、ローカル名のドットがない同じアドレスに送信されたメールが転送されます。 例えば、「alice.z@leetcode.com」と「alicez@leetcode.com」は同じメールアドレスに転送されます。 (この規則はドメイン名には適用されませんのでご注意ください)。 ローカル名にプラス(’+’)を追加した場合、最初のプラス記号以降はすべて無視されます。これにより、特定のメールをフィルタリングすることができます。例えば、m.y+name@email.com は my@email.co

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day92 「4. Median of Two Sorted Arrays」 次回 まだ Twitter やってます。 問題 49. Group Anagrams 難易度はMedium。 コーディング面接対策のために解きたいLeetCode 60問 からの抜粋です。 問題としてはアナグラムである文字列の入った配列が与えられます。 Example: Input: [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”], Output: [ [“ate”,“eat”,“tea”], [“nat”,“tan”], [“bat”] ] 解法 class Solution : def groupAnagrams ( self , strs : List [ str ] ) - > List [ List [ str ] ] : ans = collections . defaultdict ( list ) for s in strs : sorted_word = '' . join ( sorted ( s ) ) ans [ sort

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day91「153. Find Minimum in Rotated Sorted Array」 次回 まだ Twitter やってます。 問題 4. Median of Two Sorted Arrays 難易度はHard。 問題としては、サイズ m と n の2つのソートされた配列 nums1 と nums2 がある。2つの並べ替え配列の中央値を求めよ。 なお、全体の実行時間の複雑さは， O(log (m+n)) でなければならず、 nums1 と nums2 はどちらも空ではないと仮定してもよい。 Example 1: nums1 = [1, 3] nums2 = [2] The median is 2.0 Example 2: nums1 = [1, 2] nums2 = [3, 4] The median is (2 + 3)/2 = 2.5 解法 O(log(m+n)) である、ということは二分探索が使えますね。 ただ、難易度がHardということで、扱うリストが二つになっています。 これで書くコードの量が増えますし、書く量が増えるということは凡ミスも増える可能性が高くなります。 そして、二つとも同じ大きさのリストとは限らないのでその点もきちんと頭に入れておきましょう。

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day89 「62. Unique Paths」 次回 ゼロから始めるLeetCode Day91「153. Find Minimum in Rotated Sorted Array」 Twitter やってます。 問題 1011. Capacity To Ship Packages Within D Days 難易度はMedium。 コーディング面接対策のために解きたいLeetCode 60問 からの抜粋です。 コンベアベルトには，ある港から別の港へD日以内に出荷しなければならない荷物がある． コンベヤベルト上のi番目の荷物には重み[i]がある． 毎日，コンベヤベルト上の荷物を船に積み込む（重さで与えられた順序で）．船の最大重量容量を超える重量を積むことはできない． コンベヤベルト上のすべての荷物がD日以内に出荷されるようになる船の最小重量容量を返します。 Example 1: Input: weights = [1,2,3,4,5,6,7,8,9,10], D = 5 Output: 15 Explanation: A ship capacity of 15 is the minimum to ship all the packages in 5 days like this: 1st day: 1