Amazonの電話面接（技術）を受けました

前に書いたエントリと同じ問題を出してきました。これはまずいんじゃないかという気もします。面接担当者の名前は事前に知っていますので、その名前で検索して問題例を見て、それが同じ問題を使いまわしているとしたらあとから受けた人が有利になります。

実際には問題に続きがあり、使用済みのIPアドレスが10億個あったとします。メモリは100MBしか使えません。さてどうしますか？という話に続きました。

これは有名な

の10.3に

40億個の整数からなる入力ファイルが与えられたとき、ファイルの中にない整数を見つけるアルゴリズムを考えてください。作業には1GBのメモリが使用できるとします（訳注：整数は32bit）

発展問題
10MBのメモリしか使用できないとすれば、どのようにしますか？

という問題があり、これとほぼ同じと言っていいと思います。

面接担当者には、あなたの過去の出題を見たことがありますとは伝えていません。それほど熟考して完璧な解答を用意して臨んだわけでもないし、また追加の課題については初見でした。ただ、あとでリクルーターにその旨は伝えました。どのように評価されるかわかりませんが、正直であると好意的に評価されることを願います。