Kuehar's Blog

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day74 「12. Integer to Roman」 次回 ゼロから始めるLeetCode Day76「3. Longest Substring Without Repeating Characters」 Twitter やってます。 問題 15. 3Sum 難易度はMedium。 問題としては、n個の整数の配列 nums があるとすると、 nums に a + b + c = 0 となる要素 a, b, c があるかどうかを確認するアルゴリズムを設計し、0の和を与える配列の中のすべてのユニークな三重項を求めよ。 Example: Given array nums = [-1, 0, 1, 2, -1, -4], A solution set is: [ [-1, 0, 1], [-1, -1, 2] ] 解法 3つ選び、0になる組み合わせを選べ、というものです。 組み合わせの鉄則とも言えるかもしれませんが、先に何を固定するかを決めたほうが良いと思います。 今回は以下のように書きました。 class Solution : def threeSum ( self , nums : List [ int ] ) - > List [ List [ int ] ]

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day72 「1498. Number of Subsequences That Satisfy the Given Sum Condition」 次回 ゼロから始めるLeetCode Day74 「12. Integer to Roman」 Twitter やってます。 問題 1491. Average Salary Excluding the Minimum and Maximum Salary 難易度はEasy。 今日はかなり軽めの問題です。 問題としては、 salary[i] が従業員iの給与である一意の整数 salary の配列が与えられます。 最小給料と最大給料を除いた従業員の平均給料を返します。 Example 1: Input: salary = [4000,3000,1000,2000] Output: 2500.00000 Explanation: Minimum salary and maximum salary are 1000 and 4000 respectively. Average salary excluding minimum and maximum salary is (2000+3000)/2= 2500 Example 2: Input: salary

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day73 「1491. Average Salary Excluding the Minimum and Maximum Salary」 次回 ゼロから始めるLeetCode Day75 「15. 3Sum」 Twitter やってます。 問題 12. Integer to Roman 難易度はMedium。 なんかBadの方が多いので嫌な予感がしてました・・・ ローマ数字は7つの異なる記号で表されます。I、V、X、L、C、D、Mの7つの異なる記号で表されます。 この問題では、以下のように変換されています。 Symbol Value I 1 V 5 X 10 L 50 C 100 D 500 M 1000 例えば、2はローマ数字でIIと書かれていますが、これは単に2つの1を足しただけです。12はXIIと書かれていますが、これは単にX + IIです。二十七という数字は、XXVIIと書かれていますが、これはXX + V + IIです。 ローマ数字は通常、左から右に大きい方から小さい方へと書かれています。しかし、4という数字はIIIIではありませ

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day71 「1496. Path Crossing」 次回 ゼロから始めるLeetCode Day73 「1491. Average Salary Excluding the Minimum and Maximum Salary」 Twitter やってます。 問題 1498. Number of Subsequences That Satisfy the Given Sum Condition 難易度はMedium。 問題としては、整数の配列 nums と整数 target が与えられます。 numsの最小値と最大値の和が目標値以下になるような、空ではない部分列の数を返します。 答えが大きすぎるかもしれないので、10^9 + 7の剰余演算を返します。 Example 1: Input: nums = [3,5,6,7], target = 9 Output: 4 Explanation: There are 4 subsequences that satisfy the condition. [3] -> Min value + max value <= target (3 + 3 <= 9) [3,5] -> (3 + 5 <= 9) [3,5,6] -> (

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day72 「1498. Number of Subsequences That Satisfy the Given Sum Condition」 次回 まだ Twitter やってます。 問題 1491. Average Salary Excluding the Minimum and Maximum Salary 難易度はEasy。 今日はかなり軽めの問題です。 問題としては、 salary[i] が従業員iの給与である一意の整数 salary の配列が与えられます。 最小給料と最大給料を除いた従業員の平均給料を返します。 Example 1: Input: salary = [4000,3000,1000,2000] Output: 2500.00000 Explanation: Minimum salary and maximum salary are 1000 and 4000 respectively. Average salary excluding minimum and maximum salary is (2000+3000)/2= 2500 Example 2: Input: salary = [1000,2000,3000] Output: 2000.00000 Ex

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day70 「295. Find Median from Data Stream」 次回 ゼロから始めるLeetCode Day72 「1498. Number of Subsequences That Satisfy the Given Sum Condition」 Twitter やってます。 問題 1496. Path Crossing 難易度はEasy。 一番新しく追加されたEasyの問題です。 問題としては、path[i] = ‘N’, ‘S’, ‘E’, ‘W’ のような文字列のパスが与えられたとき，それぞれ1単位の移動を表す．2 次元平面上の原点 (0, 0) を起点とし、path で指定されたパス上を歩きます。 パスが任意の点で交差している場合、つまり以前に訪れたことのある場所にいる場合はTrueを返します。それ以外の場合は False を返します。 画像の関係で例を貼れないので各自確認をよろしくお願いいたします。 解法 x,yで座標を管理して最初の座標をdictで管理する、という方法を取りました。 うーん。 あまりスマートではないと思うのですが、pathをfor文で回して各文字列と一致するならば座標を変更するというものです。 しかしこれでも回答数が少ないせいかスピード自体は上位なんですよね・・

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day69 「279. Perfect Squares」 次回 ゼロから始めるLeetCode Day71 「1496. Path Crossing」 Twitter やってます。 問題 295. Find Median from Data Stream 難易度はHard。 Top 100 Liked Questionsからの抜粋です。 問題としては、クラスの実装になります。 中央値は、順序付き整数リストの中間値です。リストのサイズが偶数の場合、中間値はありません。したがって、中央値は2つの中間値の平均値となります。 例えば、 [2,3,4] 中央値は3 [2,3] 中央値は(2 + 3) / 2 = 2.5 以下の2つの操作をサポートするデータ構造体を設計します。 void addNum(int num) - データストリームからデータ構造体に整数値を追加します。 double findMedian() - これまでのすべての要素の中央値を返します。 Example: addNum(1) addNum(2) findMedian() -> 1.5 addNum(3) findMedian() -> 2 解法 平均値ではなく中央値であることを念頭において、その部分を

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day68 「709. To Lower Case」 次回 ゼロから始めるLeetCode Day70 「295. Find Median from Data Stream」 Twitter やってます。 問題 279. Perfect Squares 難易度はMedium。 Top 100 Liked Questionsからの抜粋です。 正の整数nが与えられたとき、足してnになる完全な平方数の最小数（例えば、1, 4, 9, 16, …）を求めよ、という問題です。 Example 1: Input: n = 12 Output: 3 Explanation: 12 = 4 + 4 + 4. Example 2: Input: n = 13 Output: 2 Explanation: 13 = 4 + 9. #解法 class Solution : def numSquares ( self , n : int ) - > int : dp = [ i for i in range ( n + 1 ) ] for i in range ( 2 , n + 1 ) : for j in

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day67 「1486. XOR Operation in an Array」 次回 ゼロから始めるLeetCode Day69 「279. Perfect Squares」 Twitter やってます。 問題 709. To Lower Case 問題としては文字列パラメータ str を持ち、同じ文字列を小文字で返す関数 ToLowerCase() を実装する、という問題です。 Example 1: Input: “Hello” Output: “hello” Example 2: Input: “here” Output: “here” Example 3: Input: “LOVELY” Output: “lovely” 解法 class Solution : def toLowerCase ( self , str : str ) - > str : return str . lower ( ) # Runtime: 24 ms, faster than 91.12% of Python3 online submissions for To Lower Case. # Memory Usage: 14 MB, less th

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 ゼロから始めるLeetCode 目次 前回 [ゼロから始めるLeetCode Day66「438. Find All Anagrams in a String」](( https://kueharx.blogspot.com/2020/06/leetcode-day66438-find-all-anagrams-in.html ) 次回 ゼロから始めるLeetCode Day68 「709. To Lower Case」 Twitter やってます。 問題 1486. XOR Operation in an Array 問題としては、整数 n と整数 start が与えられます。 nums[i] = start + 2*i (0-indexed) で n == nums.length の配列 nums を定義します。 nums の全要素のビット単位の XOR を返します。 Example 1: Input: n = 5, start = 0 Output: 8 Explanation: Array nums is equal to [0, 2, 4, 6, 8] where (0 ^ 2 ^ 4 ^ 6 ^ 8) = 8. Where “^” corresponds to bitwise XOR operator. Example 2: Input: n =

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day65「560. Subarray Sum Equals K」 次回 [ゼロから始めるLeetCode Day67 「1486. XOR Operation in an Array」](( https://kueharx.blogspot.com/2020/06/leetcode-day67-1486-xor-operation-in.html ) Twitter やってます。 問題 438. Find All Anagrams in a String 難易度はMedium。 Top 100 Liked Questionsからの抜粋です。 文字列 s と空でない文字列 p が与えられたとき、 s の中の p のアナグラムの開始インデックスをすべて求めなさい、という問題です。 Stringsは英小文字のみで構成され、 s と p の長さはともに20,100を超えてはいけません。 なお、出力の順番は関係ありません。 Example 1: Input: s: “cbaebabacd” p: “abc” Output: [0, 6] Explanation: The substring with start index = 0 is “cba”, which is an anagram of “a

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day64「287. Find the Duplicate Number」 次回 ゼロから始めるLeetCode Day66「438. Find All Anagrams in a String」 Twitter やってます。 問題 560. Subarray Sum Equals K 難易度はMedium。 Top 100 Liked Questionsからの抜粋です。 整数の配列と整数 k が与えられたとき，和が k に等しい連続部分配列の総数を求めよ、という問題です。 Example 1: Input:nums = [1,1,1], k = 2 Output: 2 Constraints: The length of the array is in range [1, 20,000]. The range of numbers in the array is [-1000, 1000] and the range of the integer k is [-1e7, 1e7]. 解法 import collections class Solution : def subarraySum ( self , nums : List [ int ] , k : int )

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day63 「195. Tenth Line」 次回 まだ Twitter やってます。 問題 287. Find the Duplicate Number 難易度はMedium。 Top 100 Liked Questionsからの抜粋です。 問題としては、各整数が1からnまでの間にあるn + 1の整数を含む配列 nums が与えられたとき，少なくとも1つの重複した数が存在しなければならないことを証明してください。 重複する数が1つしかないと仮定して，重複する数を求めるアルゴリズムを設計してください。 Example 1: Input: [1,3,4,2,2] Output: 2 Example 2: Input: [3,1,3,4,2] Output: 3 Note: 配列を変更してはいけません（配列は読み取り専用と仮定してください）。 定数，O(1) の余分な空間のみを使用しなければなりません。 実行時の複雑さは，O(n2)以下でなければなりません。 配列の中に重複する数は1つだけですが，それが複数回繰り返される可能性があります。 解法 読み取り専用であり、ソートできないという制約があるのを見落とさずに確認しておきましょう。 class Solution : def

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day62「83. Remove Duplicates from Sorted List」 次回 まだ Twitter やってます。 問題 195. Tenth Line 嗜好を少し変えて今回はshellについての問題です。 問題としては、テキストファイルである file.text が与えられます。10行目を出力してください。 Line 1 Line 2 Line 3 Line 4 Line 5 Line 6 Line 7 Line 8 Line 9 Line 10 Your script should output the tenth line, which is: Line 10 解法 awkコマンドを使って以下のように叩けば問題の条件を満たすことができます。 # Read from the file file.txt and output the tenth line to stdout. awk 'NR == 10' file.txt 実はLeetCodeの問題はアルゴリズムだけではなく、データベースなどについての問題もあります。（数は少ないですが・・・） 今後はアルゴリズムだけではなく、こういった問題もたまには乗せていけると良いかなぁと思います。 では今回はここ