maximum80の日記

「Empower Engineering!」をテーマに自立自走エンジニア組織によって日本を元気にするため日々奔走している事業家のブログ

新卒エンジニア向け オンライン技術選考(Online Coding Interview)の傾向と対策 - アルゴリズム編

f:id:maximum80:20200212120733p:plain

新田(@maximum_80)です。 前回の記事に引き続き、今回は具体的にオンライン技術選考でどのような問題が出題されて、どのような評価基準でみられていることが多いのかについて解説したいと思います。

前回の記事はこちら。

blog.maximum80.me

もっとも定番のアルゴリズム問題

オンライン技術問題にも様々な種類がありますが、今回は、世界的にも国内でも定番の出題問題となっているのアルゴリズム問題についての具体的な問題の内容や対策方法などについてお話したいと思います。

アルゴリズム問題の基本仕様

まず、アルゴリズム問題の仕様としては、

  • 与えられる入力値(主には文字列)
  • 期待される出力値

が用意されていて、入力値を標準入力で受け取り、 なにがしかのアルゴリズムや計算をすることによって、期待する結果を標準出力として出力するプログラムを自分の好きなプログラミング言語を用いて記述する形式になっています。

解答するのに必要な最低限の能力

問題にはほぼ必ず入力値と出力値が用意されているため、以下の様な能力や理解が必要です。

標準入出力の理解

まずはスタートラインとして、問題のフォーマットである標準入出力についての理解をする必要があります。

問題として与えられる値を扱うことができないとそもそも問題を解答することができません。 問題や出題サービスによっては、入力値を引数として扱うケースもあるため、内容をよく確認する必要があります。 標準入出力の仕組みに関しては、以下の記事も参考にしてみてください。

qiita.com

型変換・文字列操作・配列操作の理解

値を受け取ることができたとして、次に必要なのが型変換です。 言語によって入力の受け取り方は多少異なりますが、大概の場合、文字列(String)や文字列型の配列として受け取り、それらを数字型(Int等)に変換してから操作をおこなう、という作業が必要になります。

また、言語によっては文字列内に含まれるスペースや改行を切り取って、複数の数値として扱う様に分解するなどの文字列操作が必要なケースもあります。

ここまでできて問題のスタートラインという感じです。 そのため、この扱いに慣れていないと、問題の本質的な実装をする時間がなくなってきてしまいますので、ある程度自分の中でテンプレート化しておいたり、 頻出としてある入力値の処理方法については、覚えておくと良いと思います。

オススメの練習方法

まずはじめに、標準入出力をどの様に扱うかや型変換して操作をする流れにある程度慣れておく必要があります。

yukicoderで言語別の標準入出力方法をチェック

言語別に操作方法がまとまっている以下のページでチェックしておくと良いかと思います。

yukicoder.me

Aizu Online JudgeやAtCoderで実際の問題を解いてみる

また、上記をチェックした上で、どのような出題形式か実際に問題を解いて試してみたい場合は、以下の問題から初めて見るのがおすすめです。

onlinejudge.u-aizu.ac.jp

基本的な、Hello Worldの実装から、受け取った値をもとに計算処理を加えたり、簡単なアルゴリズムを実装するような問題に自由に挑戦することができます。

また、競技プログラミングのコンテストサイトのAtCoderでは、過去問がアーカイブされていて、実際に解いてみることや、他人の提出結果を閲覧したり、問題の解説をみることができます。

まずはAtCoder Beginner Contest を選んで解いてみるのがいいかもしれません。

atcoder.jp

ここまで理解をすることができれば、あとは基本的なプログラミングの操作能力があれば初級程度の問題を解答することができると思いますので、ぜひ挑戦してみてください。

評価のポイント

問題は定量的なスコアや実装内容によって評価されますが、特に評価対象とされるケースは以下の内容です。

問題の仕様通りの実装ができているか(テストケースの通過数)

まず難易度に関わらず一番基本的な評価指標としては、問題で与えられている全てのケースを満たすことができているか、という観点です。

テストケースは問題文で与えられている仕様を具体的な入力と出力で確かめるためのものになっているので、 「問題で与えた仕様を正しく理解をして実装をする」ことができているかが問われています。

ソースコードの可読性や保守性

点数が全く取れなかった場合や全問正解ではなかった場合でも、実際にどのような実装をしているのかを目で確認して判断する場合があります。

この辺りは競技プログラミングコンテストとは異なる性質の部分ではあるのですが、採用側からすると、エンジニアとして共に働けるかどうかを判断する上で、質の高いソースコードをかけているかが重要であり、可読性や保守性をみることがあります。 具体的には、

  • 読みやすさ

    • コードの一貫性(インデントやスペース)
    • 命名規則がわかりやすく一般的(英語として成立)
  • 汎用性

    • ロジックの簡潔さ
    • 冗長な記述がない

などの観点があります。以下の記事などが参考になります。

qiita.com

www.casleyconsulting.co.jp

アルゴリズムの精度(大規模なケース、実行速度)

特に難易度の高い問題になってくると、物凄い大量のデータセットが入力値として与えられて、for文をネストして使って一つ一つ処理をしていると物凄い実行時間がかかってしまい、正答することができないような問題もあります。 このような問題には、高度なアルゴリズムやデータ構造を用いて高速に処理をおこなうプログラムを書くことが求められます。

例えば企業においても規模の大きなサービスになってくると、ユーザのリストを表示したりデータを保存したりするときに、とてつもなく大量のデータを扱うことになります。

その際に、効率的な処理ができているかとそうではないかで、どんどん実行時間に差が生まれてしまい、非効率な処理だとサーバに極端な負荷がかかってしまったり下手するとダウンしてしまう、なんてこともあったります。こういった状態を避けるために、より高度なアルゴリズム実装能力が求められています。

実際に難易度の高いアルゴリズム問題を出題する企業は、規模の大きなシステムやサービスを運用している会社の傾向があります。

また、これらのアルゴリズムや高速化を理解する上で、「計算量」という概念を勉強しておくといいかもしれません。

qiita.com

qiita.com

おまけ:アルゴリズム問題を解いて、エンジニアとしての基礎体力・運動神経を養おう

よく競技プログラミングの業界とWeb業界の間では、 アルゴリズムは実務に不要だし、できなくても良い」

というような議論が話題になったりします。 確かに、一般的な開発の場面で複雑で高度なアルゴリズムの実装能力を求められるか、でいうとその場面は少ないかもしれません。

しかしながら、例えば新しい機能を実装しようとなったとき、アルゴリズムを知っていると知っていないでは実装の「発想力」が変わってきたります。

知らなかった場合にはとんでもなく仕様を明確化する上で時間がかかってしまう場合も、パッと実装イメージを膨らませることにつながったり、より中長期的にも使われ続ける保守性の高いコードをかけるようになったりします。

小さな規模のプロトタイプぐらいのシステムではそこまで力を発揮しないアルゴリズムですが、サービスが大きくなればなるほど、その力がジワジワと重要になってくるので、基礎体力を養う感覚で、是非一度学んでみてはいかがでしょうか。