概要

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

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

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

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

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

Leetcode

Python3で解いています。

ゼロから始めるLeetCode 目次

前回
ゼロから始めるLeetCode Day94 「929. Unique Email Addresses」

Twitterやってます。

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

お知らせ

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

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

問題

82. Remove Duplicates from Sorted List II
難易度はMedium。
コーディング面接対策のために解きたいLeetCode 60問からの抜粋です。

問題としては、ソートされた連結リストが与えられた場合、重複した番号を持つすべてのノードを削除し、元のリストとは異なる番号のみを残します。
同様にソートされた連結リストを返します。

Example 1:

Input: 1->2->3->3->4->4->5
Output: 1->2->5

Example 2:

Input: 1->1->1->2->3
Output: 2->3

解法

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        if not head:
            return
        node = pre = ListNode(0)
        node.next = cur = head
        while cur.next:
            nex = cur.next
            if cur.val == nex.val:
                while(nex.next and nex.val == nex.next.val):
                    nex = nex.next
                pre.next = cur = nex.next
                if not cur:
                    return node.next
            else:
                pre,cur,nex = cur,nex,nex.next
        return node.next
# Runtime: 48 ms, faster than 42.22% of Python3 online submissions for Remove Duplicates from Sorted List II.
# Memory Usage: 14 MB, less than 18.49% of Python3 online submissions for Remove Duplicates from Sorted List II.

ランナーをいくつか用意してそれをひたすらずらして仮に一致した場合に異なる要素が出るまでずらし続ける、という方法を取りました。

連結リストは結構パターンが決まっていて解くに連れてすんなりいくことが多くて好きです。
ただ、面接などにおいては単方向か双方向かなどを聞いたり前提条件を整理しておかないとめちゃくちゃになりそうですね。

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