スキップしてメイン コンテンツに移動

ゼロから始めるLeetCode Day70 「295. Find Median from Data Stream」

概要

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

どうやら多くのエンジニアはその対策として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

解法

平均値ではなく中央値であることを念頭において、その部分をどう実装するかがかなり重要な部分になりそうですね。

他の部分はこの問題を解こうと思った人にとってはそこまで大変ではなさそうです。

class MedianFinder:

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.sorted_list = []
        self.length = 0
        

    def addNum(self, num: int) -> None:
        low,high = 0,self.length-1
        while high >= low:
            mid = (high+low)//2
            if self.sorted_list[mid] > num:
                high = mid-1
            else:
                low = mid+1
        self.sorted_list.insert(low,num)
        self.length += 1
        

    def findMedian(self) -> float:
        if self.length % 2 == 0:
            median = self.length//2
            return (self.sorted_list[median]+self.sorted_list[median-1])/2.0
        else:
            return self.sorted_list[self.length//2]


# Your MedianFinder object will be instantiated and called as such:
# obj = MedianFinder()
# obj.addNum(num)
# param_2 = obj.findMedian()
# Runtime: 296 ms, faster than 30.86% of Python3 online submissions for Find Median from Data Stream.
# Memory Usage: 25.2 MB, less than 18.26% of Python3 online submissions for Find Median from Data Stream.

addNumの部分で二分探索を使い、リストの長さを保存しておくことでfindMedianの中でその長さを使ってスムーズに書くことにしました。
見返してみると基本的なことの集合問題みたいな感じですね。

それぞれの断片的な知識をしっかりと覚えていれば書けますが、そこまで速度が出ない、というジレンマに陥るタイプです。ここからどうやって改善していくか、という点についてですが、二分探索の部分が少し重くなってしまっている、というのが以下の解答例で分かります。

from heapq import *

class MedianFinder:

    def __init__(self):
        self.heaps = [], []

    def addNum(self, num):
        small, large = self.heaps
        heappush(small, -heappushpop(large, num))
        if len(large) < len(small):
            heappush(large, -heappop(small))

    def findMedian(self):
        small, large = self.heaps
        if len(large) > len(small):
            return float(large[0])
        return (large[0] - small[0]) / 2.0
# Runtime: 200 ms, faster than 82.39% of Python3 online submissions for Find Median from Data Stream.
# Memory Usage: 24.6 MB, less than 98.20% of Python3 online submissions for Find Median from Data Stream.

https://leetcode.com/problems/find-median-from-data-stream/discuss/74044/Very-Short-O(log-n)-%2B-O(1)

リストを二つ用意し、それぞれをヒープとして扱うことで軽量化していますね。

僕に先の解答からこちらのように変換できる能力があれば良かったのですが、わからなかったために今回はdiscussから引っ張ってきました。

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

コメント

このブログの人気の投稿

Braveブラウザの同期機能をiPhoneで設定した話。

Braveブラウザを使い始めて結構経った 設定 1 .同期ページを開く 2.QRコードの表示 3.iPhoneで読み取る Braveブラウザを使い始めて結構経った Google Domainsで独自ドメインを持っているBloggerをBrave Creatorsに登録した話。 この記事を書いた頃から僕はBraveしか使わなくなっちゃいましたね〜。 広告がないとネットサーフィンが捗りますし、Braveの直接クリエイターに貢献できるような仕組みが特に気に入っています。Blogger,ひいてはGoogle的にどうなんだって話もありそうですけど、ただのユーザなのでそんなのは気にせず便利なものは使います。 それで本題です。 タイトルのように今回同期機能を設定しました。 余計なことをしていたせいで少しハマったので設定ついでに誰かが困ったときに役に立つように設定方法を残しておこうかと思います。 ちなみにこちらの記事はPCの同期にiPhoneを追加するという設定方法についての解説です。iPhone→PCの同期方法などはまた別の話のようです。 設定 1 .同期ページを開く ブラウザのタブの右上にある上矢印のマークをクリックすると以下のような項目が表示されます。 こちらの同期という欄をクリックします。 すると以下のページが表示されます。 自動的に設定ページの中の同期欄が表示されるわけですね。 2.QRコードの表示 同期欄に同期済みのデバイスを管理という欄があるのでそちらをクリックします。 すると以下のようなページが表示されるのでそちらの中の新たなデバイスを追加、スマホ/タブレットという順にクリックしていくとQRコードが表示されます。 これでこのステップは完了です。 3.iPhoneで読み取る このQRコードをiPhoneで読み取っていく訳ですが、このQRコードはプリインストールされているQRコードで読み取っても正しく処理してくれません。 書いてある通り、iPhoneのBraveブラウザで読み取って上げる必要があります。 なのでひとまずiPhoneでBraveブラウザを開き、画面右下の**•••**という所をタップしてください。 すると上から二番目に歯車アイコンの設定が表示されますのでそちらをタップします。 初期表示で画面中部に表示さ

JavaのindexOf関数はナイーブ法で実装されているらしい

indexOf関数とは 実際のソースを見よう ナイーブ法ってなんぞや indexOf関数とは ドキュメント はここ。 indexOf の細かい使い方は説明はしないが、簡単にいうと二つの文字列を比較して重複する箇所がある場合にその開始部分のインデックスを返すというもの。 実際のソースを見よう どのように実装されているのかが気になったので jdkの中に存在するsrc.zipを解凍して確認してみることに。 public int indexOf ( String str ) { return indexOf ( str , 0 ) ; } public int indexOf ( String str , int fromIndex ) { return indexOf ( value , 0 , value . length , str . value , 0 , str . value . length , fromIndex ) ; } static int indexOf ( char [ ] source , int sourceOffset , int sourceCount , char [ ] target , int targetOffset , int targetCount , int fromIndex ) { if ( fromIndex >= sourceCount ) { return ( targetCount == 0 ? sourceCount : - 1 ) ; } if ( fromIndex < 0 ) { fromIndex = 0 ; } if ( targetCount == 0 ) { return fromIndex ; } char

djoserを使ったDjango REST Frameworkでのカスタムユーザーモデル認証機能の実装

djoserとは 使い方 djoserとは djoser とはDjango REST Framework上での基本的なユーザー認証や登録などの認証周りをサポートしてくれるライブラリです。 カスタムモデルに対しても使え、Djangoのコードを再利用するような形をとるのではなく、Single Page Application(以下SPA)によりフィットするようなアーキテクチャを目指して作られています。 今回はdjoserの最もシンプルな認証機能の実装について書きます。 なお、この認証はセキュリティの面などから実際に使用するべきではなく、以下のJWT認証のようなより強固なセキュリティの設定があります。 あくまでお手軽な認証として紹介します。 ソースコードは こちら なお、以下の全てが導入後にエンドポイントとして使えます。 /users/ /users/me/ /users/confirm/ /users/resend_activation/ /users/set_password/ /users/reset_password/ /users/reset_password_confirm/ /users/set_username/ /users/reset_username/ /users/reset_username_confirm/ /token/login/ (Token Based Authentication) /token/logout/ (Token Based Authentication) /jwt/create/ (JSON Web Token Authentication) /jwt/refresh/ (JSON Web Token Authentication) /jwt/verify/ (JSON Web Token Authentication) Getting started djoser関連の記事を他にも書いています。 djoserを使ったDjango REST Frameworkでの認証機能の実装 djoserを使ったDjango REST FrameworkでのJWT認証機能の実装 なお、今回はJWT認証を用いたユーザー認証を実装することとします。 使い方 途中