概要

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

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

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

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

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

Leetcode

Python3で解いています。

ゼロから始めるLeetCode 目次

前回
ゼロから始めるLeetCode Day93 「49. Group Anagrams」

Twitterやってます。

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

お知らせ

Day 100でQiitaでの投稿はひとまず区切りを付けようかと思います。
タグの記事が僕の記事ばかりになってしまうのもいかがなものかと思いましたし、他に有益な情報を提供している方の邪魔になってしまうこともあると考えたので、こうすることにしました。
至らない部分は多々ありましたが、今までお付き合い頂きありがとうございました。

問題を解いて記事を書く、というのは上記の個人ブログで続けるつもりですし、興味ある方はたまにそちらを覗いていただけると嬉しいです。
Twitterの方のアカウントはほとんど更新通知用と化しているので、Leetcodeを解く記事について気になる方はそちらも合わせてフォローいただくと良いかもしれません。

問題

929. Unique Email Addresses
難易度はEasy。
コーディング面接対策のために解きたいLeetCode 60問からの抜粋です。

問題としては、すべての電子メールは、@記号で区切られたローカル名とドメイン名で構成されています。
例えば、[email protected] では、alice がローカル名で、leetcode.com がドメイン名です。
小文字の他に、これらの電子メールには '.'や'+'が含まれている場合があります。
メールアドレスのローカル名の一部の文字の間にピリオド('.')を追加すると、ローカル名のドットがない同じアドレスに送信されたメールが転送されます。 例えば、「[email protected]」と「[email protected]」は同じメールアドレスに転送されます。 (この規則はドメイン名には適用されませんのでご注意ください)。
ローカル名にプラス('+')を追加した場合、最初のプラス記号以降はすべて無視されます。これにより、特定のメールをフィルタリングすることができます。例えば、[email protected] は [email protected] に転送されます。 (繰り返しになりますが、このルールはドメイン名には適用されません)。
これらのルールを同時に適用することも可能です。
仮に電子メールのリストが与えられた場合、リスト内の各アドレスに1つの電子メールを送信します。 実際にメールを受信するアドレスはいくつあるでしょうか?

Example 1:

Input: ["[email protected]","[email protected]","[email protected]"]
Output: 2
Explanation: "[email protected]" and "[email protected]" actually receive mails

解法

class Solution:
    def numUniqueEmails(self, emails: List[str]) -> int:
        fixed_email = set()
        for lists in emails:
            local,domain = lists.split("@")
            local = local.split("+")[0].replace(".","")
            fixed_email.add(local + "@" + domain)
        return len(fixed_email)
# Runtime: 52 ms, faster than 77.31% of Python3 online submissions for Unique Email Addresses.
# Memory Usage: 14.2 MB, less than 5.16% of Python3 online submissions for Unique Email Addresses.

実装の面で苦労する、というよりは問題を噛み砕いて考える方が難しいかもしれませんね。
集合を管理する場合、Pythonではset()を使うと和集合や積集合などを簡単に取り扱うことができるのでおすすめです。

流れとしてはfor文で全てのリストを網羅するというのが大前提にあり、その中でどういった処理を行うかがこの問題の核となるでしょう。
僕はsplit()を使ってlocal部分とdomain部分に分け、問題文で書かれているように最初の+以外は無視して良いので最初の+で分割し、全ての.を無くすことで判別を行いました。
最終的に集合の長さを返せばきちんと実際にメールを受信するアドレスの数、となるといった仕組みです。

この問題は集合の知識が必要かと最初は思うかもしれませんが、実質的には数え上げに近く、Hashmap的な問題だとリンク先では紹介されていました。

初見だと面食らうかもしれないので実際に解くことをお勧めします。

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