【コーディング面接】ハッシュテーブルに関する問題と解説

ハッシュテーブルとは

ハッシュデーブル(「辞書」や「ハッシュマップ」とも呼ばれます) を使うと、「値」に対して「キー」を割り当てることができます。このキーは多くの場合、数字または文字列です。値はどんなタイプのオブジェクトでもかまいません。
これはとても便利なデータ構造です。きわめて高速に探索できるからです。面接では通常、100% 真でないとしても、ハシシュテーブルに要素を挿入して探索する実行時間は、O(1)(データ数を問わず、一定時間)と仮定します。
ハッシュテーブルの実装がお粗末だと、探索にO(N)時間かかります。 ハッシュテーブルを使って、個人のID番号からほかの情報を持つ何らかのオブジェクトにマップしたりします。

問題1

ユニークな文字列のリストが2つ(AとB)があります。AがBのサブセットであるかどうかを決定するプログラムを書きなさい。つまり、Aのすべての要素がBに含まれているかどうかを確認しなさい。

問題2

売上データに関して2次元の配列があります。先頭の列がプロダクトID，2列目が数量です。このデータのリストから、プロダクトIDごとの売上合計を示す新しい2次元の配列を返す関数を書きなさい。

例: 入力:
211, 4
262, 3
211，5
216，6

出力:
211, 9
262，3
216, 6

問題1の解答

2つのリストにユニークな文字列が含まれていると提示されているので、一方のリストのすべての要素がもう一方に含まれているかどうかをチェックするだけです。

アプローチ1：総当たり

Aの中のある要素がBの中にはないとわかったら、その時点でAがBのサブセットでないことがわかるので、Falseを返します。Aの最後の要素まで実行して戻り値がなければ、すべての要素がBの中にあったことがわかるので、Trueを返します。

def is_subset_brute_force(bigger, smaller):
    for s in smaller:
        found = False
        for b in bigger:
            if s == b:  # 要素発見
                found = True
                break
        if not found:  # sが見つからない -> サブセットではない
            return False

    return True  # 全ての要素が見つかった

bigger = ["apple", "lemon", "orange"]
smaller = ["apple", "grape"]
print(is_subset_brute_force(bigger=bigger, smaller=smaller))  # => False

smaller = ["apple", "lemon"]
print(is_subset_brute_force(bigger=bigger, smaller=smaller))  # => True

このアルゴリズムでは、O(a*b)の時間がかかります。aはAの長さ、bはBの長さです。

アプローチ2：ハッシュテーブル

先ほどのアプローチが遅い理由は、Aの中にある要素の数だけ、Bを探さなければならないからです。単に、 ある要素がBにあるかどうかを確認できたらいいと思いませんか? ハッシュテーブルを使うと、このようなことができます。Bの中のすべての要素のハッシュテーブルを作ります。その後、ある要素がBの中にあるかどうかを探索したいときに、そのハッシュテーブルを使うだけです。

def is_subset(bigger, smaller):
    hash_table = {}
    # 大きい方のリストの中にあるすべての要素を記録する
    for b in bigger:
        hash_table[b] = True

    # 大きい方のハッシュテーブルにすべての文字列が含まれているかどうかチェックする
    for s in smaller:
        if not hash_table.get(s, False):
            return False

    return True

このアルゴリズムでは、O(a+b)の時間がかかります。aはAの長さ、bはBの長さです。ハッシュテーブルを保持するために、追加でO(b)のメモリが必要です。

問題2の解答

このメソッドの出力として、プロダクトIDとそれぞれの売上合計がリストになっていることが求められています。これは、ハッシュテーブルを使って素直な方法で実現できます。 (プロダクトID, 数量)のリストを順に処理していきます。それぞれの値について、ハッシュテーブルのエントリを増やすか、まだ存在しない場合には挿入します。最後に、ハッシュテーブルを配列に戻します。

def total_sales(data):
    hash_table = {}

    # 各プロダクトの売上合計を計算する
    for id_, quantity in data:
        hash_table[id_] = quantity + hash_table.get(id_, 0)

    # ハッシュテーブルをリストに戻す
    totals = [(k, v) for k, v in hash_table.items()]
    return totals

data = [(211, 4), (262, 3), (211, 5), (216, 6)]
print(total_sales(data))  # => [(211, 9), (262, 3), (216, 6)]

このアルゴリズムでは、O(N)の時間がかかります。Nはインプットの行数です。

世界で闘うプロダクトマネジャーになるための本 ~トップIT企業のPMとして就職する方法~