LINEの新卒採用試験ズバリ問題解説~アルゴリズム問題編~

(2月5日 16:30追記)

SNS等で多くのご指摘をいただき、再度掲載していたコードや表現について社内で議論いたしました。それを踏まえて以下の通り、補足および訂正させていただきます。

エラトステネスのふるいの実装方法については、高速化のための実装ではなく、アルゴリズムなどの勉強をしっかり行ってきたか、ということを示すための1例として紹介しましたが、あたかも高速化を目指したコードとしての例示となり、誤解を招く表現でした。上記の意図を明確にするために、本文中に高速化するための実装ではないことを明記しました。

また、”個性がない”という表現も、上記と同様に”アルゴリズムなどの勉強をしっかり行ってきたという実績や経験がコードから判断できない”という意図で記載しておりました。また、簡潔に実装すべき箇所にも独自性のある実装を求めたものではありませんでした。表現・説明が不足しており不適切な記載内容でした。”技術力や知識をアピールできていない”と同様の意図となりますので、削除しております。

Python2での実装は、今後多くの方が本ブログを参考にされることを考えると不適切であると考え、すべてのコードをPython3 で動作するようにコードを修正いたしました。

最後に、コーディングテストは応募者と評価者とのコミュニケーションであり、個人の能力をアピールする場でもあると考えています。もちろんその能力の中には高速で動作されたコードを書ける能力も含まれています。

評価するときには多面的な角度からコードを見て、個人の能力をできる限り汲み取るように努力をしています。応募者においては、自己表現の一つだと思って取り組んでもらえるとありがたく思います。また、コーディングテストだけでは汲み取れなかった部分はその後の面接等でしっかりとコミュニケーションできればと考えています。

補足・訂正は以上となります。改めてコーディングテストおよび採用面接の意義について考える良い機会となりました。ご指摘いただいた皆さまに感謝いたします。

はじめに

LINEのAI技術「LINE CLOVA」の開発を担当している橋本です。

2014年からLINEの新卒採用のコーディングテストの監修をしています。新卒採用イベントで、「どういった点を評価していますか?」や「なにをすれば合格できますか?」といった質問がよくあります。一言でこの質問に答えることは難しいのですが、この記事を読んでどんなコードがよいコードだと考えているかわかってもらえたらなぁとおもいます。ということで、今回はコーディングテストのアルゴリズム問題について解説をしていきたいと思います。

関連記事:LINEの新卒採用試験ズバリ問題解説 〜2021年開発コース(実装問題)版〜

エンジニア=アスリート、サービス開発=チームスポーツ

機械学習(Machine Learning)、人工知能(AI)、IoT(Internet of Things)、ブロックチェーン(Blockchain)などの高度な技術が根幹となるインターネットサービスが次々と生まれています。新しいインターネットサービスを生み出しているのがエンジニアたちです。当然、優秀なエンジニアなくては新たなサービスを生み出すことができません。そのため、全世界的にエンジニアの価値は急上昇しています。

プロとしてのエンジニアは、プロのスポーツ選手(アスリート)と類似する部分が多くあります。トップアスリートの特徴として、

  • 身体能力が高い
  • 賢い
  • 適応力

などが挙げられます。トップアスリートには非常に高い個人の能力が求められるように、エンジニアにもプログラミングスキルなどの個人の能力の高さが求められます。素晴らしい能力を持ったエンジニアは素晴らしいサービスを開発することができます。

また、LINEのサービス開発は複数のエンジニアが協力して行い、ただ一人のエンジニアがサービスを生み出すことはまれです。つまり、サービス開発はサッカーやバスケットボールのようなチームスポーツにとても似ています。そのため、エンジニアは、

  • コミュニケーション
  • リーダーシップ
  • 協力

といったチームプレイをする上で重要なことを実現できなければいけません。

そして、エンジニアとアスリートがもっとも類似していることは、

  • トップエンジニア(アスリート)はトップエンジニア(アスリート)を尊敬する
  • トップエンジニア(アスリート)とともにプレイすることを強く求める

ことです。だから、一緒に仕事をしてくれる優秀なエンジニアを探し求めています。

コーディングテストについて

新卒採用やインターン採用におけるコーディングテストは募集領域によって若干異なります。開発コースの問題は、実装問題とアルゴリズム問題の2つにに分けることができます。

コーディングテストは、応募者が優秀なエンジニアとなりうる可能性を持っているのか評価するための一つの指標です。指定された入出力をもつプログラムを制限時間内(主に60分~120分)に作成してもらいます。そのプログラムの動作チェックとコードの内容を見て評価します。主にチェックしているポイントは、以下のとおりです。

  • プログラミングに慣れているか?
  • コンピュータサイエンスの知識を持っているか?
  • エラー処理などの実用的な処理に対処できるか?
  • 他の人が理解できるようなコードを書いているか?

大前提として、確実に動作するプログラムのみを評価します。高度なアルゴリズムを用いていてもプログラムが動かなければ意味がありません。不完全でもいいので、制限時間内に動作するプログラムを提出することが重要です。加えて、個人のプログラミングスキルの高さや知識の量などをプログラミングを通じて、アピールすることも重要です。限られた枠の中に自分が選出されるために、他の人よりも優れていることを示すことはたいへん重要なことです。

問題の難易度は、大学のコンピュータサイエンスの講義(1年~3年)で教えているであろうデータ構造やアルゴリズムを使った問題になっています。他の専攻の学生にとっては少し難しいかもしれませんが、コンピュータサイエンスとしては基礎的な課題です。

あるアルゴリズム問題

  • 例題:N番目の素数

それでは、私が監修した過去のアルゴリズム問題とその回答例から、どのようなプログラミングが評価されるのかを見ていきましょう。

N番目の素数を探せ

1から昇順で数えたときに、N番目にあたる素数を出力するコマンドラインツールを作成してください。
入力:出力したい素数の順番 N
出力:N番目の素数

例:
$ app 5
11

素朴に計算する

import sys
 
def main(argv):
    n = int(argv[0])
 
    i = 0
    for p in range(2, 1000000):
        for q in range(2, p):
            if p % q == 0:
                break
        else:
            i += 1
 
        if i == n:
            print(p)
            return
 
if __name__ == '__main__':
    main(sys.argv[1:])

素直でシンプルなプログラミングができています。インデントもしっかりできてよい印象です。しかし、いくつかの課題があります。

  • ロジックがメイン関数にすべて集約されている
  • 無駄な計算がある

すべてのロジックを一箇所に含めると、コードの理解がしにくくなります。他人がコードを見たときに、すぐに処理内容が理解できるようにすることはとても重要です。また、素数であるかどうかの計算方法にも改善の余地があります。Nの値が小さい場合には問題になりませんが、大きくなると処理に時間がかかるようになることが問題です。

素数をキャッシュする

import sys
 
primes = []
 
def is_prime(num):
    for p in primes:
        if num % p == 0:
            return False
 
    primes.append(num)
    return True
 
def main(argv):
    n = int(argv[0])
 
    i = 0
    for p in range(2, 1000000):
        if is_prime(p):
            i += 1
 
        if i == n:
            print(p)
            return
 
if __name__ == '__main__':
    main(sys.argv[1:])

前のプログラムを少し改良しました。素数かどうかを判定する処理を関数化しました。こうすることで、ロジックが以前より見やすくなりました。加えて、発見した素数を保存しておき、素数の判定処理を効率化しています。以前のものよりも高速に動作することができています。しかし、このぐらいのプログラミングだと、多くの人が回答してきそうです。

  • 個性がない
  • 技術力や知識をアピールできていない

エラトステネスのふるい

import sys
import math
 
def eratosthenes(limit):
    nums = [i for i in range(2, limit+1)]
    primes = []
 
    while True:
        p = min(nums)
 
        if p > math.sqrt(limit):
            break
 
        primes.append(p)
 
        i = 0
        while i < len(nums):
            if nums[i] % p == 0:
                nums.pop(i)
                continue
            i += 1
 
    return primes + nums
 
def main(argv):
    n = int(argv[0])
    limit = 1000
 
    while True:
        primes = eratosthenes(limit)
 
        if len(primes) > n:
            print(primes[n-1])
            break
 
        limit *= 2
 
if __name__ == '__main__':
    main(sys.argv[1:])

素数を高速に発見するアルゴリズムの一つに「エラトステネスのふるい」というアルゴリズムがあります。このアルゴリズムを採用したプログラムになります。でも、このコードはエラトステネスのふるいのアイデアを用いていますが実質的な高速化に寄与しませんし、もっと高速化できる実装方法もあります。ただ、こうすることで、自身がコンピュータ・サイエンスへの知識を持ち合わせていることやアルゴリズムを理解し実装することができることがアピールすることができます。しかし、まだまだ課題はありそうです。

  • 正常系の処理は問題ないが、異常系の処理に対して対処できていない

エラー処理

import sys
import math
 
def eratosthenes(limit):
    nums = [i for i in range(2, limit+1)]
    primes = []
 
    while True:
        p = min(nums)
 
        if p > math.sqrt(limit):
            break
 
        primes.append(p)
 
        i = 0
        while i < len(nums):
            if nums[i] % p == 0:
                nums.pop(i)
                continue
            i += 1
 
    return primes + nums
 
def main(argv):
    if not argv[0].isdigit():
        print("error")
        return
 
    n = int(argv[0])
 
    if n < 1:
        print("error")
        return
 
    limit = 1000
    while True:
        primes = eratosthenes(limit)
 
        if len(primes) > n:
            print(primes[n-1])
            break
 
        limit *= 2
 
if __name__ == '__main__':
    main(sys.argv[1:])

入力値が必ずしも数字である、0よりも大きな整数であることは保証していません。そのため、入力値をチェックするようにしました。そうすることで、異常系にも考慮したプログラムになりました。

まとめ

現在のインターネットサービスを開発するエンジニアは優秀なトップアスリートであり、サービス開発はチームスポーツです。優秀なアスリートが集まって、お互いにリスペクトしながら開発を行うことが、よいサービスを生み出すことにつながります。そのような優秀なエンジニアを見つけるために、コーディングテストを実施しています。

コーディングテストは、単に出された課題を解くプログラムを作成するだけではなく、応募者と評価者とのコミュニケーションです。正解を導き出すプログラムを作成することは大前提ですが、その中にプログラミング能力の高さ、コンピュータ・サイエンスに関する知識の深さ、様々な条件を考慮するといった注意深さなど、個人の能力をアピールする場でもあります。どんなコードを提出すると興味を持ってもらえるか考えながらテストにトライしてもらえるとうれしいです。