Kuehar's Blog

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策として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

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day90「1011. Capacity To Ship Packages Within D Days」 次回 まだ Twitter やってます。 問題 153. Find Minimum in Rotated Sorted Array 難易度はMedium。 コーディング面接対策のために解きたいLeetCode 60問 からの抜粋です。 問題としては、昇順にソートされた配列を，あらかじめ知らないピボットで回転させたとします。（[0,1,2,4,5,6,7]が[4,5,6,7,0,1,2]になるといったような例を思い浮かべていただけると分かりやすいかもしれません。） そのリストの中から最小の要素を探します。 なお、配列の中に重複した要素はないと考えてよい。 Example 1: Input: [3,4,5,1,2] Output: 1 Example 2: Input: [4,5,6,7,0,1,2] Output: 0 解法 class Solution : def findMin ( self , nums : List [ int ] ) - > int : low , high = 0 , len ( nums ) - 1

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day88「139. Word Break」 次回 ゼロから始めるLeetCode Day90「1011. Capacity To Ship Packages Within D Days」 Twitter やってます。 問題 62. Unique Paths 難易度はMedium。 コーディング面接対策のために解きたいLeetCode 60問 からの抜粋です。 問題としてはユニークな経路の数を求める、というものです。 ロボットが m x n のグリッドの左上隅に位置しています（下図では「スタート」と表示されています）。 なお、ロボットはどの時点でも下か右にしか移動できません．ロボットはグリッドの右下隅に到達しようとしています（下図では「Finish」と表示されています）。 今回は図を載せないので、噛み砕いて考えたい方は直接問題のリンクで確認してください。 Example 1: Input: m = 3, n = 2 Output: 3 Explanation: From the top-left corner, there are a total of 3 ways to reach the bottom-right corner: Right -> Right -> Down Ri

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day87 「 1512. Number of Good Pairs」 次回 ゼロから始めるLeetCode Day89 「62. Unique Paths」 Twitter やってます。 問題 139. Word Break 難易度はMedium。 コーディング面接対策のために解きたいLeetCode 60問 からの抜粋です。 問題としては、空ではない文字列 s と、空ではない単語のリストを含む辞書 wordDict が与えられた場合、 s が1つ以上の辞書単語のスペースで区切られたシーケンスに分割できるかどうかを判断する、というものです。 Example 1: Input: s = “leetcode”, wordDict = [“leet”, “code”] Output: true Explanation: Return true because “leetcode” can be segmented as “leet code”. Example 2: Input: s = “applepenapple”, wordDict = [“apple”, “pen”] Output: true Explanation: Return true because “applepenapple”

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day86 「33. Search in Rotated Sorted Array」 次回 ゼロから始めるLeetCode Day88「139. Word Break」 Twitter やってます。 問題 1512. Number of Good Pairs 難易度はEasy。 問題としては、整数の配列 nums が与えられます。 nums[i] == nums[j] で i < j の場合，ペア (i,j) を有効とし、有効であるペアの数を返すアルゴリズムを設計してください。 Example 1: Input: nums = [1,2,3,1,1,3] Output: 4 Explanation: There are 4 good pairs (0,3), (0,4), (3,4), (2,5) 0-indexed. Example 2: Input: nums = [1,1,1,1] Output: 6 Explanation: Each pair in the array are good. Example 3: Input: nums = [1,2,3] Output: 0 解法 class Solution : def numIdentic