【コーディング面接】配列に関する問題と解説

配列とは

配列はデータを保持する最もシンプルな方法です。配列ではオブジェクトの簡単なリストが用意され、そこにデータが格納されます。インデックスがあれば素早く検索することができますが、そうでなければ遅くなります。たとえば「リストの中で12番目の人物のデータを読み出す」といった場合には高速で処理できるのですが、「"アレックス"という名前の人物をすべて見つける」といった場合には時間がかかるのです(データセッ ト内の全員を調べなければならないため)。 ほとんどの言語では、配列を作成した後で長さを「延ばす」ことはできません。前もって配列の長さを指定する必要があり、後から変更することはできません。

問題1

最後尾に空のスポット (ゼロ) をもつ正の整数のソート済みの配列があります。ある要素をソート順に従うように挿入しなさい。

問題2

配列中の要素の順番を逆転させなさい (新しい配列を作らずに)。

問題1の解答

以下のような配列(最後に空のスポットがある)を思い浮かべることができます。

[1, 4, 7, 8, 9, _]

たとえば6の要素を挿入するとしたら、最後に挿入するだけというわけにはいきません。順番に並べることが 前提だからです。

[1, 4, 6, 7, 8, 9]

このためには、すべての要素を「シフト」して、6が入るスペースを作ってから、6を挿入する必要があります。 この問題へのアプローチは、2通りあります。

アプローチ1：後ろへシフトしてから挿入する

1つめのアプローチは、すべての要素をシフトしてから、値xを挿入する方法です。挿入する際に値を上書きしてしまわないように注意しなくてはなりません。
前方からシフトするのではなく、後方から前方へ向かってシフトすることもできます。 まず、9を空のスポットにコピーします。次に、8を9があった場所にコピーします。さらに7を8があった場所 に、というふうに進めていきます。xを挿入する適切なスポットが見つかったらそこで停止し、xを挿入します。

def insert(input_li, x):
    # 入力が有効か確認
    if input_li[-1] is not None or x <= 0:
        return False

    """
    空でない最後の要素から始める
    次々に左隅の要素へと移動し、要素を一つずつコピーしていく
    配列の先頭がヒットした時に停止する
    """

    l = len(input_li)

    for i in range(l - 1)[::-1]:
        if input_li[i] > x:
            input_li[i + 1] = input_li[i]
        else:
            input_li[i + 1] = x
            return True

要素を挿入できたら真、エラーが発生したら偽を返します。

input_li = [1, 4, 7, 8, 9, None]
print(insert(input_li, x=6)) #=> True
print(input_li)  #=> [1, 4, 6, 7, 8, 9]

アプローチ2：要素をスワップして前方へ動かす

もうひとつの解法として、要素を配列の前方へと移動させることを繰り返すという方法が考えられます。配列のはじめのほうの要素(xより小さい要素)には何もしませんので、移動しません。 一方、xを挿入する場所を見つけたら、xと、配列中の現在の要素をスワップします。これで、xの値は配列中の元の要素と等しくなります。 次の要素へ行ったときに、xをその値とスワップします。最後に到達するまで、配列内の各要素についてこれを続けて実行します。

insert 6 into 2, 3, 7, 8, 9, _ 
set x = 6
start i at A[0]
move i to A[1]
move i to A[2]
swap A[2] and x.
    A = {2, 3, <u>6</u>, 8, 9, _}
    x = 7
swap A[3] and x.
    A = {2, 3, 6, <u>7</u>, 9, _}
    x = 8
swap A[4] and x.
    A = {2, 3, 6, 7, <u>8</u>, _}
    x = 9
swap A[5] and x.
    A = {2, 3, 6, 7, 8, <u>9</u>}
    x = _

def insert2(input_li, x):
    # 入力が有効か確認
    if input_li[-1] is not None or x <= 0:
        return False

    for i, e in enumerate(input_li):
        print(e, x)
        if not e or x < e:  # "None" を "not e" で扱う
            # x と input_li[i]をスワップする
            input_li[i], x = x, input_li[i]
    return True

if文の条件式のx < eがいったん真になったら、常に真になることに注意してください。

どちらのアルゴリズムも、O(N)の時間がかかります。

問題2の解答

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