Kuehar's Blog

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 Twitter やってます。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day42「2. Add Two Numbers」 次回 ゼロから始めるLeetCode Day44「543. Diameter of Binary Tree」 Twitter やってます。 問題 5. Longest Palindromic Substring 難易度はMedium。 Top 100 Liked Questionsからの抜粋です。 文字列である s が与えられるのでその文字列の中で最も長い回文（どちらから読んでも同じになる）を探し出すようなアルゴリズムを設計してください。 Input: “babad” Output: “bab” Note: “aba” is also a valid answer. Input: “cbbd” Output: “bb” 以前解いた、 ゼロから始めるLeetCode Day30「234. Palindrome Linked List」 こちらに似ていますが、前回はあくまで与えられた連結リストが回文であるかをチェックするだけであったのに対し、今回は文字列でその中から最長のものを抽出するというものに変わっており、少し複雑になっています。 解法 とはいえ、回文の問題のオーソドックスな考え方は前回のような要素をひっくり返した

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 Twitter やってます。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day40「114. Flatten Binary Tree to Linked List」 次回 ゼロから始めるLeetCode Day42「2. Add Two Numbers」 Twitter やってます。 問題 394. Decode String 問題としては、エンコードされた文字列を指定すると、そのデコードされた文字列を返すようなアルゴリズムを設計しましょう、というものです。 エンコーディングルールは、k[encoded_string]です。角かっこ内のencoding_stringは、正確にk回繰り返されます。 kは正の整数であることが保証されていることに注意してください。 入力文字列は常に有効であると想定できます。余分な空白はなく、角括弧は整形式などです。 さらに、元のデータに数字が含まれておらず、数字はこれらの繰り返し番号kのみに対応していると想定することもできます。たとえば、3aや2[4]のような入力はありません。 例としては以下の通りです。 s = "3[a]2[bc]", return "aaabcbc". s = "3[a2[c]]", return "accaccacc". s =

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 Twitter やってます。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day39「494. Target Sum」 次回 ゼロから始めるLeetCode Day41「394. Decode String」 Twitter やってます。 問題 114. Flatten Binary Tree to Linked List 難易度はMedium。 Top 100 Liked Questionsからの抜粋です。 二分木が与えられるので、フラットなリストに変換するようなアルゴリズムを設計してください。 これだけでは分かりづらいので例を見てみましょう。 1 / \ 2 5 / \ \ 3 4 6 The flattened tree should look like: 1 \ 2 \ 3 \ 4 \ 5 \ 6 やはり例を見ると分かりやすいですね。 解法 # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 Twitter やってます。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day38「208. Implement Trie (Prefix Tree)」 次回 ゼロから始めるLeetCode Day40「114. Flatten Binary Tree to Linked List」 Twitter やってます。 問題 494. Target Sum 自然数の配列 nums と自然数 S が与えられます。 +と-が与えられるので、配列を全て足すか引いてSの値と一致させるような組み合わせの数を返してください。 Input: nums is [1, 1, 1, 1, 1], S is 3. Output: 5 Explanation: -1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3 There are 5 ways to assign symbols to make the sum of nums be target 3. こんな感じです。 言いたいことは例から分かると思います。 解法 class Solution : def calc ( self , nums , index , sums , S ) :

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 Twitter やってます。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day37「105. Construct Binary Tree from Preorder and Inorder Traversal」 次回 ゼロから始めるLeetCode Day39「494. Target Sum」 今はTop 100 Liked QuestionsのMediumを解いています。 Easyは全て解いたので気になる方は目次の方へどうぞ。 Twitter やってます。 問題 208. Implement Trie (Prefix Tree) 難易度はMedium。 Top 100 Liked Questionsからの抜粋です。 問題としては、insert関数、search関数、startsWith関数をTrieというクラスにまとめて実装してください、というものです。 なお、それぞれの挙動としては、 Trie trie = new Trie(); trie.insert(“apple”); trie.search(“apple”); // returns true trie.search(“app”); // returns false trie.startsWith(“app”); // returns true trie.insert(

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 Twitter やってます。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day36「155. Min Stack」 次回 ゼロから始めるLeetCode Day38「208. Implement Trie (Prefix Tree)」 問題 105. Construct Binary Tree from Preorder and Inorder Traversal 難易度はMedium。 Top 100 Liked Questionsからの抜粋です。 前回でEasyが全て解き終わったので今回からはMediumを解いていきます。 問題としては、木の構造として、 inorder と preorder が引数として与えられるので、それらを元に二分木を構築するようなアルゴリズムを書いてください、というものです。 preorder = [3,9,20,15,7] inorder = [9,3,15,20,7] Return the following binary tree: 3 / \ 9 20 / \ 15 7 解法 # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None,

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 Twitter やってます。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day35「160. Intersection of Two Linked Lists」 次回 ゼロから始めるLeetCode Day37「105. Construct Binary Tree from Preorder and Inorder Traversal」 問題 難易度はeasy。 Top 100 Liked Questionsのeasyはこれが最後の問題になります。 問題としては、push,pop,top,getMinという関数を持つMinStackクラスを実装してくださいというものです。 なお、それぞれの関数の仕様は以下の通り。 push(x) – Push element x onto stack. pop() – Removes the element on top of the stack. top() – Get the top element. getMin() – Retrieve the minimum element in the stack. Input [“MinStack”,“push”,“push”,“push”,“getMin”,“pop”,“top”,“getMin”] [[],[-2],[0],[-3],[],[],[],[]]