概要

海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。

どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。

早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。

と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。

ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。

Leetcode

Python3で解いています。

ゼロから始めるLeetCode 目次

前回
ゼロから始めるLeetCode Day79「1282. Group the People Given the Group Size They Belong To」

Twitterやってます。

技術ブログ始めました！！
技術はLeetCode、Django、Nuxt、あたりについて書くと思います。こちらの方が更新は早いので、よければブクマよろしくお願いいたします！

＃問題
703. Kth Largest Element in a Stream
難易度はEasy。

問題としては、ストリーム内のk番目に大きい要素を見つけるクラスを設計してください．これは、ソートされた順番の中でk番目に大きい要素であって、k番目の異なる要素ではないことに注意してください。

KthLargestは、整数kとストリームの初期要素を含む整数配列numsを受け入れるコンストラクタを持ちますKthLargest.addメソッドを呼び出すたびに、ストリーム内のk番目に大きい要素を表す要素を返します。

Example:

int k = 3;
int[] arr = [4,5,8,2];
KthLargest kthLargest = new KthLargest(3, arr);
kthLargest.add(3); // returns 4
kthLargest.add(5); // returns 5
kthLargest.add(10); // returns 5
kthLargest.add(9); // returns 8
kthLargest.add(4); // returns 8

要はコンストラクタとaddメソッドを実装してくださいね、ってことですね。

この問題を取り扱ったのは、Googleのコーディング面接をパスした人がおすすめしているLeetCodeの問題集に載ってたからです。

コーディング面接対策のために解きたいLeetCode 60問

面白そうなので一通り解いてみようかなーと思います。
最近新しい問題ばかり解いていましたし、久々に面白そうな取り組みになりそうです。

解法

ヒープの問題ってことで、大人しくヒープを使います。
優先度付きキューとも言いますね。

一見この問題簡単そうに見えますよね。

毎回要素を追加した後にソートしてその中からk-1の要素を返してあげれば良くね？となりそうですが、ソートという処理は重いので普通に時間切れになると思います。

例えば、以下のような処理ですね。

def add(val):
    lists.append(val)
    self.lists.sort()
    return self.lists[self.num-1]

これではaddが呼ばれる度にソートがかかり、要素が増えれば増えるほど重くなっていきます。

なので最初から要素を追加する時に優先度付きのキューを使って管理してしまえばわざわざソートしなくてもいいよね？ってことです。

ヒープを使ったものとして以下のコードを書きました。

import heapq

class KthLargest:
    def __init__(self, k: int, nums: List[int]):
        self.lists,self.num = [],k
        for i in nums:
            self.add(i)

    def add(self, val: int) -> int:
        heapq.heappush(self.lists, val)
        if len(self.lists) > self.num: 
            heapq.heappop(self.lists)
        return self.lists[0]

# Your KthLargest object will be instantiated and called as such:
# obj = KthLargest(k, nums)
# param_1 = obj.add(val)
# Runtime: 136 ms, faster than 45.40% of Python3 online submissions for Kth Largest Element in a Stream.
# Memory Usage: 17.6 MB, less than 78.45% of Python3 online submissions for Kth Largest Element in a Stream.

こうすることで最初に与えられた要素から全ての要素をヒープとして扱い、listsの長さの値がnumと同値になるまでひたすらpop、すなわちリストから最小値を取り出すため、非常にスムーズに処理が行われます。

書いてて思ったのですが、ヒープで書いたことほとんどなかったような気がするので復習がてらいい勉強になりました。

では今回はここまで。お疲れ様でした。