コーディング面接で必要なPythonの学習 - Coding InterviewCat | InterviewCat

コーディング面接で使われる構文、データ構造、標準関数などは実はある程度限定されています。ここに書いてある事を理解するだけでコーディング面接における（体感）8 ~ 9割くらいのPythonの必要な知識を学習できます。

例えば、辞書やセットは頻繁に活用しますが、ジェネレーター・デコレータなどはコーディング面接ではそこまで登場しません。つまり必要なものだけ集中して学習し、残りの要素はその都度調べる形が効率良いでしょう。コーディング面接では万が一忘れた時は相手が自分の代わりにググってくれたり、擬似コードとして書くことも許される場合があります。

ここでは詳しいデータ構造やアルゴリズムの知識の話はせず、Pythonの構文やデータ構造の使い方にのみフォーカスをして話していきます。

変数（Variable）

Pythonは動的型付け言語で、変数を宣言するときにその型を明示する必要はありません。したがって、n = 0といった宣言を行うときに、型は指定されません。変数の型は実行時に決定されるため、同一の変数に違う型の値を再代入することが可能です。


# 変数の宣言と再代入
n = 0
print(n)  # Output: 0
n = "ABC"
print(n)  # Output: ABC

複数の変数を一行で代入することも可能です。例えば、a, b = 1, 2といった形で代入を行います。


# 複数変数への一行での代入
a, b = 1, 2
print(a, b)  # Output: 1 2

2つの変数をスワップ（交換）もPythonではa, b = b, aと書くことで簡単にできるようになっています。


# 変数のスワップ
a, b = 1, 2
a, b = b, a
print(a, b)  # Output: 2 1

複数の変数に一括で同じ値を代入する事もできます。


# 複数の変数への一括代入
a = b = c = 0
print(a, b, c)  # Output: 0 0 0

n += 1およびn -= 1は、インクリメント（加算）とデクリメント（減算）を表しています。例えば、Javaのようにn++とは書けないので注意しましょう。


# インクリメント、デクリメント
n = 0
n += 1
print(n) # Output: 1
n -= 1
print(n) # Output: 0

PythonではNoneはNull値を表し、変数が何も値を持たないことを示します。これは変数が初期化されたがまだ値が割り当てられていない、または明示的にその変数の値を消去したい場合などに使用されます。


# None (Null)
n = None
print(n) # Output: None

If文（if statement）

Pythonのif文は他の言語と比べて独特な書き方をしています。Pythonでは、if文を書く際に条件式を括弧で囲む必要はありません。また、ブロックを表現するためにはカーリーブラケット（{}）ではなく、インデント（通常はスペース4つ）を使用します。また、else ifの代わりにelifを使用します。


n = 5
# if文の使用
if n > 0:
    print("n is positive") # Output: n is positive
elif n < 0:
    print("n is negative")
else:
    print("n is zero")

Pythonではand、or、notブール演算子です。これらは、真偽値（TrueまたはFalse）を持つ式の評価に用いられます。例えば、n > 0 and m > 0の場合、nとmが共に0より大きい場合はTrueを返し、そうでなければFalseを返します。


n, m = 5, 10

# 'and' 演算子の使用
if n > 0 and m > 0:
    print("Both n and m are positive.") # Output: Both n and m are positive.

# 'or' 演算子の使用
n = -5
if n < 0 or m > 0:
    print("Either n is negative or m is positive.") # Output: Either n is negative or m is positive.

# 'not' 演算子の使用
if not n > 0:
    print("n is not positive.") # Output: n is not positive.

# Pythonでは範囲を条件にする時に以下のようにできます
if 0 < n < 10:
    print("n is between 0 and 10")  # Output: n is between 0 and 10

Pythonでは行末にバックスラッシュ（\）をつけるか、括弧（()）内に条件式を記述することで条件式を複数行に分割できます。


# 複数行のif文
n, m = 2, 3
if ((n > 1 and 
     n != m) or n == m):
    n += 1
print(n) # Output: 3

while文（while statement）

Pythonのwhile文は、条件が真（True）である限り繰り返し処理（ループ）を実行します。そのため、while文のブロック内のコードは、指定した条件が偽（False）になるまで何度でも実行されます。


# while文の使用
n = 5
while n > 0:
    print(n) # Output: 5 4 3 2 1
    n -= 1

while文の中にbreak文を記述することで、条件が真である場合でも強制的にループを抜け出すことが可能です。また、continue文を使うと、ループの残りの部分をスキップして次のイテレーションに移行します。


# break文とcontinue文の使用
n = 10
while n > 0:
    n -= 1
    if n == 5:
        break
    if n % 2 == 0:
        continue
    print(n) # Output: 9 7

for文（for statement）

Pythonでは、for文を使用してシーケンス（リストや文字列など）を繰り返すことができます。特定の回数だけ繰り返すためにはrange()関数を用います。例えば、for i in range(5):は0から4までのシーケンスを作成し5回の繰り返し処理を行います。なお、rangeは厳密にはクラスだが、組み込み関数の一種として呼ばれているのでここでは関数と呼びます。


# for文の使用
for i in range(5):
    print(i)  # Output: 0 1 2 3 4

range()関数には2つまたは3つの引数を渡すことも可能で、それぞれ開始値、終了値、ステップ数を指定することができます。例えば、for i in range(2, 5):は2から4まで繰り返し、for i in range(5, 1, -1):は5から2まで逆順に繰り返します。また、revsersedを使って逆順に繰り返し処理を行う事もできます。


# for文の使用
for i in range(5):
    print(i)  # Output: 0 1 2 3 4

for i in range(2, 5):
    print(i)  # Output: 2 3 4

for i in range(5, 1, -1):
    print(i)  # Output: 5 4 3 2 

for i in reversed(range(5)):
	  print(i)  # Output: 4 3 2 1 0

Pythonのfor文でも、breakとcontinueのキーワードを使用することができます。


# breakの使用例
for i in range(10):
    if i == 5:
        break
    print(i)  # Output: 0 1 2 3 4

# continueの使用例
for i in range(10):
    if i % 2 == 0:
        continue
    print(i)  # Output: 1 3 5 7 9

また、for文のelseブロックは抑えておきたい特徴の一つです。これはforループが完全に終了した後に実行されるブロックです。ただし、break文によってループが途中で終了した場合は、elseブロックは実行されません。


# for-else
for i in range(5):
  print(i)　 # Output: 0 1 2 3 4
else:
  print("Finish")　# Output: Finish

# for-elseとbreak
for i in range(5):
    if i == 3:
        break
    print(i)  # Output: 0 1 2
else:
    print("Finish")  # この行は実行されない

Math

Pythonでは、様々な数学的な演算が可能です。例えば、/演算子を使うと、浮動小数点数による除算ができます。一方、//演算子を使うと、整数による除算（切り捨て除算）ができます。負の数に対して//を使うと、結果は小数点以下を切り捨てて整数にします。


print(5 / 2)   # Output: 2.5
print(5 // 2)  # Output: 2

また、%演算子を使うと、剰余（余り）を計算できます。負の数に対する剰余計算では、Pythonは負の値を返さず、代わりに剰余に最も近い非負の値を返します。しかし、math.fmod()関数を使うと、剰余計算で負の数が正確に扱われます。つまり、第一引数が負の場合、結果も負となりま doす。


print(10 % 3)  # Output: 1
print(-10 % 3)  # Output: 2 Pythonの%演算子は非負の結果を返します。

import math
print(math.fmod(-10, 3)) # Output: -1.0 math.fmod()は第一引数の符号を保持します。

Pythonのmathモジュールには、他にも多くの数学関数が含まれています。math.floor()関数は引数以下の最大の整数を、math.ceil()関数は引数以上の最小の整数をそれぞれ返します。math.sqrt()関数は平方根を、math.pow()関数はべき乗を計算します。また、**演算子もべき乗を計算します。


import math

print(math.floor(3 / 2))  # Output: 1
print(math.ceil(3 / 2))  # Output: 2
print(math.sqrt(2))  # Output: 1.4142135623730951
print(math.pow(2, 3))  # Output: 8.0
print(2 ** 3)  # Output: 8

Pythonには無限大を表現するための特殊な値があり、float("inf")とfloat("-inf")を使って正の無限大と負の無限大を作成できます。これらの値は、他の浮動小数点数と同様に演算できます。たとえば、非常に大きな数を計算してもオーバーフローすることなく、無限大と比較することができます。


float("inf")
float("-inf")

import math
# オーバーフローしない
print(math.pow(2, 200)) # 1.6069380442589903e+60
# float("inf")よりは小さい
print(math.pow(2, 200) < float("inf")) # Output: True

配列（Array）

Pythonには配列として機能する組み込みのデータ型がいくつかありますが、最も一般的に使用されるのはlist型です。リストは[]で定義され、その中に任意の数と種類の要素を含めることができます。例えば、numbers = [1, 2, 3, 4, 5]は整数のリストであり、strings = ["hello", "world"]は文字列のリストです。


# リストの定義とアクセス
numbers = [1, 2, 3, 4, 5]

リストにはlen()関数を用いる事で長さを取得できます。


numbers = [1, 2, 3, 4, 5]
print(len(numbers)) # Output: 5

リストの要素にはインデックス（0から始まる）でアクセスします。負のインデックスを指定すると、リストの終端から逆方向に要素を参照できます。


numbers = [1, 2, 3, 4, 5]
print(numbers[0])  # Output: 1
print(numbers[-1])  # Output: 5

スライス機能は配列から一部の要素を取り出すための機能です。numbers[1:4]は2番目から4番目までの要素を取得します。


# sequence[start:end:step]
# start：スライスの開始位置を指定します。この位置の要素を含みます。
# end：スライスの終了位置を指定します。この位置の要素は含みません。
# step（省略可）：スライスのステップ数を指定します。デフォルトでは1です。

numbers = [1, 2, 3, 4, 5]

# 2番目から4番目の要素を取得
print(numbers[1:4])  # Output: [2, 3, 4]

# 最初から3番目の要素まで取得
print(numbers[:3])  # Output: [1, 2, 3]

# 3番目以降の要素を取得
print(numbers[2:])  # Output: [3, 4, 5]

# 全ての要素を取得（スライスを使わない場合と同じ、全ての要素がコピーされます）
print(numbers[:])  # Output: [1, 2, 3, 4, 5]

# ステップ数を指定して要素を取得
print(numbers[::2])  # Output: [1, 3, 5]

# ステップ数にマイナスを指定すると逆順になります
print(numbers[::-1])  # Output: [5, 4, 3, 2, 1]

Pythonのリストは動的であり、append()を用いて新たな要素をリストの終端に追加することができます。pop()を使うとリストの終端の要素を削除します。insert()を使うと特定の位置に新たな要素を挿入することができます。次章以降で詳しく解説しますが、Pythonのリストは動的配列で実装されておりinsert() はO(N)の時間計算量となり非効率なので使う場合には注意しなければなりません。


numbers = [1, 2, 3, 4, 5]

numbers.append(6)
numbers.append(7)
numbers.append(8)
print(numbers)  # Output: [1, 2, 3, 4, 5, 6, 7, 8]

numbers.pop()
print(numbers)  # Output: [1, 2, 3, 4, 5, 6, 7]

numbers.insert(1, 0)
print(numbers)  # Output: [1, 0, 2, 3, 4, 5, 6, 7]

また、in演算子を用いて、特定の要素がリストに含まれているかどうかを調べることができます。この演算子は、指定した要素がリスト内に存在すればTrueを、存在しなければFalseを返します。しかし先頭から要素を線形探索する事になるので、こちらも時間計算量的には非効率的です。


numbers = [1, 2, 3, 4, 5]

print(1 in numbers) # Output: True
print(2 in numbers) # Output: True
print(9 in numbers) # Output: False

また配列が空判定するときにはlen関数を使わずに以下のように書く事もできます。


numbers = []
if numbers: # 空でない場合
    print('numbers is not empty')

if not numbers: # 空の場合
    print('numbers is empty')

文字列（String）

Pythonの文字列はシングルクォート（'）またはダブルクォート（"）で囲むことで定義します。例えば、s = 'hello'またはs = "hello"のように記述します。文字列の要素にはインデックスでアクセスします。


# 文字列の定義
s = "hello"
print(s[0])  # Output: h

文字列にはlen()関数を用いる事で長さを取得できます。


s = "hello"
print(len(s)) # Output: 5

文字列を結合するには+演算子を使用します。またフォーマット済み文字列リテラル（f-string）を使う事もできます。


# 文字列の結合
s = "hello" + " " + "world"
print(s)  # Output: hello world

# f-string
s = "hello"
s = f"{s} world"
print(s)  # Output: hello world

配列と同じように、スライス機能を使用して、文字列の一部を取り出すことができます。例えば、s[0:2]は文字列sの1番目から2番目の要素を取得します。


# sequence[start:end:step]
# start：スライスの開始位置を指定します。この位置の要素を含みます。
# end：スライスの終了位置を指定します。この位置の要素は含みません。
# step（省略可）：スライスのステップ数を指定します。デフォルトでは1です。

s = "hello"
# 1番目から2番目の要素を取得
print(s[0:2])  # Output: he

# 最初の3文字を取得
print(s[:3])  # Output: hel

# 3番目以降の文字を取得
print(s[2:])  # Output: llo

# ステップ数2で文字を取得
print(s[::2])  # Output: hlo

# ステップ数にマイナスを指定すると文字列を逆順に取得
print(s[::-1])  # Output: olleh

文字列はイミュータブル（変更不能）なので、一度定義した文字列の要素を直接変更することはできません。例えば、s[0] = "H"のようなコードは例外を引き起こします。


s = "hello"
# 文字列イミュータブルなので変更できない
s[0] = "H" # TypeError: 'str' object does not support item assignment

int()関数を使用して、文字列を整数に変換することができます。また、str()関数を使用して、数値を文字列に変換することができます。


# 文字列を数値に変換できる
print(int("123") + int("123")) # Output: 246

# 数値を文字列に変換できる
print(str(123) + str(123)) # Output: 123123

ord()関数を使用して、文字列を対応するASCIIコードに変換することができます。例えば、ord("a")は97を返し、ord("b")は98を返します。この機能は、例えば小文字の英字の位置関係を調べる際に役立ちます。


# 文字列をASCIIコードに変換
print(ord("a")) # Output: 97
print(ord("b")) # Output: 98
# これを活用して例えば小文字の英字の位置関係を調べる際に役立ちます
print(ord("b") - ord("a")) # Output: 1

join()メソッドを使用して、複数の文字列を一つの文字列に結合することができます。


# カンマ区切りで出力
strings = ["ab", "cd", "ef"]
print(",".join(strings)) # Output: ab,cd,ef

# 文字列を結合させる
strings = ["ab", "cd", "ef"]
print("".join(strings)) # Output: abcdef

split()メソッドを使用して、文字列を特定の区切り文字に基づいて複数の部分に分割することができます。これは、特定の文字で区切られたデータを個別の要素に分解する際に便利です。


# 文字列を分割
sample_string = "a,b,c"
print(sample_string.split(",")) # Output: ['a', 'b', 'c']

リスト内包表記（List comprehension）

Pythonのリスト内包表記は、リストを生成するコードをより短く、より読みやすくするための方法です。例えば、0から9までのすべての数字の平方を含むリストを作るには、通常のforループを使用するよりもリスト内包表記を使用した方がコードは短くなります。

他のプログラミング言語にはなかなかない機能ですが、例えば、JavaScriptのmapやfilterなどと同じような使い方ができると思って問題ないと思います。


# 通常のforループを使用
squares = []
for i in range(10):
    squares.append(i ** 2)
print(squares)  # Output: [0, 1, 4, 9, 16, 25, 36, 49, 64, 81]

# リスト内包表記を使用
squares = [i ** 2 for i in range(10)]
print(squares)  # Output: [0, 1, 4, 9, 16, 25, 36, 49, 64, 81]

# リスト内包表記にif文を使うこの場合偶数の数字以外はフィルタリングされる
squares = [i ** 2 for i in range(10) if i % 2 == 0]
print(squares)  # Output: [0, 4, 16, 36, 64]

2次元配列（2d array）

Pythonのリストを使用すると、多次元配列（例えば、2次元配列）も作成できます。2次元配列は「配列の配列」と考えることができ、行列などを表現するのに使われます。リスト内包表記を使うと、指定したサイズの2次元配列を簡単に作成することができます。以下に3x3の2次元配列を生成する例を示します。


# 2次元配列の定義
two_d_array = [[0] * 3 for i in range(3)]
print(two_d_array)  # Output: [[0, 0, 0], [0, 0, 0], [0, 0, 0]]

しかし、次のように*演算子を使用して直接リストを複製すると、すべての内側のリストが同じ参照（つまり同じオブジェクト）を指すことになります。そのため、一つの内側のリストを変更すると、他のすべての内側のリストも同様に変更されてしまいます。このため、2次元配列を作成する際にはこの方法を避けるべきです。


# これは駄目
two_d_array = [[0] * 3] * 3

キュー（Queue）

Pythonのcollectionsモジュールのdequeクラスは、効率的な先入れ先出し（FIFO）データ構造（キュー）を提供します。要素をキューの最後（右側）に追加するには、appendメソッドを使用します。キューの先頭（左側）から要素を取り出すには、popleftメソッドを使用します。

なお、Pythonのdequeクラスは双方向リストで実装されており、スタック（LIFO）としての機能も備えていますが、こちらは普通にPythonのリスト（配列）を用いてもほぼ同様の時間計算量を期待できるため、あえてこちらを使う必要はありません。dequeクラスの詳しい実装内容は次章以降で説明します。


from collections import deque

queue = deque()
queue.append(1)
queue.append(2)
print(queue) # Output: deque([1, 2])

queue.popleft()
print(queue) # Output: deque([2])

セット（Set）

Pythonのセット（set）は重複する要素を許さないコレクションです。新しい要素を追加するにはadd()メソッドを使用します。


# ハッシュセットの定義
hash_set = set()

hash_set.add(1)
hash_set.add(2)
print(hash_set) # Output: {1, 2}
print(len(hash_set)) # Output: 2

要素がセットに存在するかどうかを確認するには、inキーワードを使用します。これは時間的計算量がO(1)であるため、要素の存在確認には非常に効率的です。


# このように初期化もできる
hash_set = {1, 2}

print(1 in hash_set) # Output: True
print(2 in hash_set) # Output: True
print(3 in hash_set) # Output: False

セットから要素を削除するには、remove()メソッドを使用します。このメソッドは指定した要素がセットに存在しない場合、例外が投げられます。


hash_set = {1, 2}

# 2の要素を削除
hash_set.remove(2)
print(2 in hash_set) # Output: False

# 4の要素を削除しようとするが、例外を投げられる
hash_set.remove(4) # KeyError: 4

リストと同様にセット内包表記を使用することができます。これにより、ある範囲や条件に基づく要素を含むセットを簡単に生成することができます。


hash_set = { i for i in range(3) }
print(hash_set) # Output: {1, 2, 3}

辞書（Dict - HashTable）

Pythonの辞書（dict）はハッシュテーブルとして機能します。キーと値のペアを保存することができ、キーを使用して値を迅速に取得することができます。辞書型は {} を用いて定義され、以下のように要素を追加したり、既存の要素の値を更新したりできます。


# 辞書の定義
hash_table = {}

hash_table["apple"] = 1
hash_table["banana"] = 2
print(hash_table)  # Output: {'apple': 1, 'banana': 2}
print(len(hash_table))  # Output: 2

hash_table["banana"] = 3
print(hash_table)  # Output: {'apple': 1, 'banana': 3}

また、Pythonの辞書はキーを指定してその存在を確認することも可能です。これは in 演算子を使うことで行うことができます。


# このように初期化もできる
hash_table = {"apple": 1, "banana": 2, "orange": 3}

print("apple" in hash_table)  # Output: True
print("banana" in hash_table) # Output: True
print("grape" in hash_table)  # Output: False

if "banana" in hash_table:
    print("'banana' exists in hash_table") # Output: 'banana' exists in hash_table

pop()メソッドを使うと、指定したキーの要素を削除することができます。


hash_table = {"apple": 1, "banana": 2, "orange": 3}

hash_table.pop("apple")
print("apple" in hash_table) # Output: False

また、リストと同様に辞書内包表記を用いることで、より複雑なハッシュテーブルを生成することもできます。


hash_set = { i: i * 2 for i in range(3) }
print(hash_set) # Output: {0: 0, 1: 2, 2: 4}

辞書型の要素は、keys()、values()、items()メソッドを使って取得できます。これらのメソッドを使用して辞書型のキーだけ、値だけ、またはキーと値のペアを取得することができます。


hash_table = {"apple": 1, "banana": 2, "orange": 3}

for key in hash_table:
    print(key, hash_table[key]) # 全てのキーとそれに対応するバリューをprintする

for value in hash_table.values():
    print(value)　# 全てのキーを表示

for key, value in hash_table.items():
    print(key, value)　# 全てのキーとバリューのペアを表示

Pythonでは、標準のdictの他に、collectionsモジュールのdefaultdictを利用することができます。defaultdictは、キーが存在しない場合にデフォルトの値を生成する機能があります。これにより、キーが未定義である場合にエラーを防いだり、初期化の手間を省くことができます。


from collections import defaultdict

# int型のデフォルト値を持つdefaultdictを作成する
# ここでは、存在しないキーに対して自動的に0が割り当てられる
hash_table = defaultdict(int)

hash_table["apple"] += 1  # "apple"がなければ、デフォルトの0に1を足して1になる
hash_table["banana"] += 1
hash_table["apple"] += 1  # "apple"の値が更新され、2になる

print(hash_table["apple"])  # Output: 2
print(hash_table["banana"])  # Output: 1
print(hash_table["cherry"])  # "cherry"は存在しないのでデフォルト値の0を返す

# defaultdictを利用して、リストをデフォルト値とすることもできます
hash_list = defaultdict(list)
hash_list["fruits"].append("apple")
hash_list["fruits"].append("banana")
hash_list["vegetables"].append("carrot")

print(hash_list)  # Output: defaultdict(<class 'list'>, {'fruits': ['apple', 'banana'], 'vegetables': ['carrot']})

Counter クラスも非常に便利なので覚えておきましょう。これは辞書のサブクラスで、ハッシュ可能なオブジェクトを数えるのに特化しています。Counter オブジェクトは、要素をキーとして、その要素の出現回数を値として保持します。これにより、要素のカウントを効率的に行うことができます。


from collections import Counter

# リスト内の要素の出現回数をカウント
fruits = ["apple", "banana", "apple", "orange", "banana", "apple"]
fruit_counter = Counter(fruits)

print(fruit_counter)  # Output: Counter({'apple': 3, 'banana': 2, 'orange': 1})

# キーを指定して個別の要素の出現回数を取得
print(fruit_counter["apple"])  # Output: 3
print(fruit_counter["cherry"])  # 出現していない要素のカウントは0を返す

# 最も出現回数が多い要素を取得
most_common = fruit_counter.most_common(1)
print(most_common)  # Output: [('apple', 3)]

# 文字列に対しても各文字ごとに出現関数をカウントできる
string_counter = Counter("banana")
print(string_counter) # Counter({'a': 3, 'n': 2, 'b': 1})

タプル（Tuple）

Pythonのタプルは、一度作成したら変更できない（イミュータブルな）シーケンス型です。タプルは通常、異なるタイプの項目をグループ化するために使用されます。タプルはカンマで区切られた値の並びで、オプションで丸括弧 () で囲まれます。


# タプルの定義
my_tuple = (1, 2, 3)
print(my_tuple)  # Output: (1, 2, 3)

# タプルの要素へのアクセス
print(my_tuple[0])  # Output: 1
print(my_tuple[-1])  # Output: 3

タプルのはイミュータブルで、一度タプルが作成されると、その要素を変更することはできません。


# タプルの定義
my_tuple = (1, 2, 3)

# タプルの要素は変更できない
my_tuple[0] = 0  # TypeError: 'tuple' object does not support item assignment

タプルは辞書のキーとして使用したり、ハッシュセットの要素としても使用できます。一方、リストは辞書のキーとして使用することはできません。


# タプルは辞書のキー、またはハッシュセットの要素としても使える
hash_table = {(1, 2): 3}
print(hash_table[(1, 2)])  # Output: 3

hash_set = {(1, 2)}
print((1, 2) in hash_set)  # Output: True

# リストはキーとして使えない
hash_table[[1, 2]] = 5  # TypeError: unhashable type: 'list'

ヒープ（Heap）

Pythonのheapqモジュールを使うと、リストを効率的にヒープとして扱うことができます。ヒープは、データ構造の一つで、特定の順序（通常は大小）でデータを保存します。このモジュールは最小ヒープを実装します。つまり、ヒープの最小の要素が常にルート、すなわち、インデックス0に存在します。


import heapq

# 最小ヒープの定義
min_heap = []
heapq.heappush(min_heap, 3)
heapq.heappush(min_heap, 2)
heapq.heappush(min_heap, 4)

# 最小値は常にindex 0にある
print(min_heap[0]) # Output: 2

while min_heap:
    print(heapq.heappop(min_heap)) # Output: 2, 3, 4

一方、Pythonのheapqモジュールには最大ヒープを直接実装する機能はありません。しかし、値をネガティブにすることで最大ヒープを実現できます。つまり、ヒープに値を追加するときにはマイナス記号をつけて、ヒープから値を取り出すときにはマイナス記号を再度つけて値を元に戻します。


import heapq

# 最大ヒープはないので、マイナス記号を利用して値を逆にする
max_heap = []
heapq.heappush(max_heap, -3)
heapq.heappush(max_heap, -2)
heapq.heappush(max_heap, -4)

# 最大値は常にindex 0にある
print(-max_heap[0])  # Output: 4

while max_heap:
    print(-heapq.heappop(max_heap))  # Output: 4, 3, 2

heapq.heapify()関数を使用すると、既存のリストをその場でヒープの形に変更することができます。


import heapq

# リストをヒープに変換
arr = [2, 3, 1, 6, 4, 8]
heapq.heapify(arr)

while arr:
    print(heapq.heappop(arr))  # Output: 1, 2, 3, 4, 6, 8

ソート（Sorting）

Pythonのsorted()関数を使うと、リストをソートすることができます。この関数は新しいソート済みリストを返すため、元のリストは変更されません。なおデフォルトでは昇順でソートされます。


# sorted関数の使用（デフォルトでは昇順）
numbers = [5, 3, 1, 4, 2]
sorted_numbers = sorted(numbers)
print(sorted_numbers)  # Output: [1, 2, 3, 4, 5]

sort()メソッドはリスト自体を破壊的にソートします（元の配列が書き換えられる）。また、sort()メソッドには引数があり、これを使用するとソートの順序を逆にすることができます。降順でソートするには、reverse=Trueを引数として指定します。


# sortメソッドの使用
numbers.sort()
print(numbers)  # Output: [1, 2, 3, 4, 5]
# 降順でソート
numbers.sort(reversed=True)
print(numbers)  # Output: [5, 4, 3, 2, 1]

文字列を含むリストもソートすることができます。デフォルトでは、辞書順（正確にはASCIIコード順）でソートされます。


strings = ["orange", "apple", "banana", "grape"]
# デフォルトでは辞書順でソート
strings.sort()
print(strings)  # Output: ["apple", "banana", "grape", "orange"]

sort()メソッドのkey引数を使用すると、ソートの基準をカスタマイズすることができます。例えば、リストの要素（文字列）を長さでソートするためには、key引数に長さを返す関数を指定します。


# ソートを文字列の長さでソートするようカスタマイズできる
strings.sort(key=lambda x: len(x))
print(strings)  # Output: ["apple", "grape", "orange", "banana"]

また、tupleは複数の要素でソートする時にとても便利なので覚えましょう。tupleの最初の要素から順に比較していきソートされます。例えば、出現回数順 -> 辞書順でソートしたい時になどに使える手法になります。ちなみにtupleの代わりにlistを使っても同様の結果が得られます。優先度付きキュー（heapq）などでも同様に評価されるので覚えておきましょう。なお、もちろん複数の要素をソートする際には先程紹介したkey引数を使う事もできます。


versions = [(1, 2, 3),(1, 2, 1),(1, 1, 4)]
# 最初の要素から順に評価されて、ソートされる
versions.sort()
print(versions) # Output: [(1, 1, 4), (1, 2, 1), (1, 2, 3)]

count_chars = [(2, "b"), (2, "a"), (1, "c")]
# 例えば、出現回数順->辞書順でソートしたい時に使える
count_chars.sort()
print(count_chars) # Output: [(1, "c"), (2, "a"), (2, "b")]

関数（Function）

Pythonでは、defキーワードを使用して関数を定義します。


# 関数の定義
def greet(name):
    print(f"Hello, {name}!")

greet("Alice")  # Output: Hello, Alice!

内部関数（Inner Function）

Pythonでは、関数の内部に別の関数を定義することができます。これを内部関数またはネストした関数と言います。また内部関数から外部関数の変数にアクセスする事ができます。


# 内部関数の定義
def outer_function(x):
    def inner_function(y):
        return x + y
    return inner_function(5)

print(outer_function(10))  # Output: 15

Pythonのnonlocalキーワードは、ネストした関数（内部関数）から外部関数（親関数）のローカル変数を参照または変更するために使用します。以下に一例を示します。またミュータブルな変数（リストや辞書等）だとオブジェクトが参照によって渡されるためnonlocalを使う必要ありません。


def outer_function():
    outer_var = "Outer variable"
    outer_list = [1, 2, 3]

    def inner_function():
        # nonlocalキーワードを使って外部関数のローカル変数を参照
        nonlocal outer_var
        outer_var = "Changed by inner function"
　　　　 　　　　　　　　　　# ミュータブルなオブジェクトは参照を通じて変更が可能です
        # nonlocalキーワードは必要ない
        outer_list[0] = 0

    print(f"Before: var='{outer_var}' list={outer_list}")
    inner_function()
    print(f"After: var='{outer_var}' list={outer_list}")

outer_function()
# Output: Before: var='Outer variable' list=[1, 2, 3]
# Output: After: var='Changed by inner function' list=[0, 2, 3]

クラス（Class）

Pythonのクラスは以下のように定義します。Pythonのコンストラクタは__init__メソッドで、これはクラスからインスタンスを作成する際に自動的に呼び出されます。この__init__メソッドを通じて、新しく作成されたインスタンスの初期設定が行われます。また、クラス内で定義された関数をインスタンスメソッドと呼びます。メソッドの最初の引数は通常selfと名付けられ、これがそのメソッドを呼び出したインスタンス自体を指します。

なお、一般的にLeetCode形式のコーディング面接では必要最小限のクラスの構文をまず優先的に覚える事をオススメしています。殆どの問題は関数実装で終わりますが、クラス全体の設計をするパターンもあるからです。最悪忘れたら面接官に「ここは疑似コードです」と言いましょう。私は過去に継承の方法が他のプログラミング言語と混同して忘れてしまい、面接官に確認した事があります。その時は面接官の方が優しかったので代わりにググって教えてくれました。


# クラスの定義
class MyClass:
    # コンストラクタメソッド
    def __init__(self, name):
        self.name = name

    # インスタンスメソッド
    def greet(self):
        print(f"Hello, {self.name}!")

my_object = MyClass("Alice")
my_object.greet()  # Output: Hello, Alice!

bisect

Pythonのbisectモジュールは、ソートされたリストに対して効率的な二分探索が可能となります。


from bisect import bisect_left, bisect_right

nums = [1, 3, 3, 4, 4, 4, 4, 4, 19]

# numsにおいて値が4のlower bound(4以上数値が出現する最小のインデックス)
# であるインデックスの3を返す
print(bisect_left(nums, 4)) # Output: 3

# numsにおいて値が4のupper bound + 1（4より大きい数値が出現する最小のインデックス）
# であるインデックスの8を返す
# 注意: upper bound + 1です！
print(bisect_right(nums, 4)) # Output: 8

# numsにおいて値が10以上の最小のインデックスの8を返す
print(bisect_left(nums, 10)) # Outout: 8

# numsにおいて値が10より小さい最小のインデックス + 1の8を返す
print(bisect_right(nums, 10)) # Output: 8

Sorted Containers

はじめにSorted ContainersはPythonの標準ライブラリではありません。C++ではstd::multisetなどに相当する機能を使うことができます。例えばSorted Containersの中にあるSortedListクラスの説明をします。コーディングテストの問題では既にソートされた配列に新しい要素をソート順を維持しながら追加する事が必要な問題があったとします。普通であればO(N)の時間計算量がかかりますが、SortedListではO(logN)で挿入する事ができます。

Pythonの標準ライブラリではありませんが、基本的にコーディング面接では言語における差は重要ではなくさらにエディタに書くだけで実行しないパターンもあるため、面接官と交渉して使えるかを確認しましょう。

ライブラリのインストールは↓


pip install sortedcontainers

Sorted Containersの使い方


from sortedcontainers import SortedList

sorted_list = SortedList([3, 1, 4, 2])
print(sorted_list)  # Output: SortedList([1, 2, 3, 4])

# 要素の追加 O(logN) 
sorted_list.add(5)
print(sorted_list)  # Output: SortedList([1, 2, 3, 4, 5])

# 要素の追加 O(logN) 
sorted_list.add(4)
print(sorted_list)  # Output: SortedList([1, 2, 3, 4, 4, 5])

# 要素の削除 O(logN) 
sorted_list.discard(3)
print(sorted_list)  # Output: SortedList([1, 2, 4, 4, 5])

# ソートされたリストに対して二分探索
print(sorted_list.bisect_left(4))  # Output: 2
print(sorted_list.bisect_right(4))  # Output: 4


from sortedcontainers import SortedSet

sorted_set = SortedSet([3, 1, 4, 2])
print(sorted_set)  # Output: SortedSet([1, 2, 3, 4])

# 要素の追加 O(logN)
sorted_set.add(5)
print(sorted_set)  # Output: SortedSet([1, 2, 3, 4, 5])

# 要素の追加を行うが既に要素が存在するので変わらない
sorted_set.add(4)
print(sorted_set)  # Output: SortedSet([1, 2, 3, 4, 5])

# 要素の削除 O(logN)
sorted_set.discard(3)
print(sorted_set)  # Output: SortedSet([1, 2, 4, 5])

# ソートされたSetに対して二分探索
print(sorted_set.bisect_left(4))  # Output: 2
print(sorted_set.bisect_right(4))  # Output: 3

# 存在の確認
print(4 in sorted_set)  # Output: True
print(6 in sorted_set)  # Output: False