(cache)GAFAコーディング面接こんな感じでした

このあいだ、GAFA数社のコーディング面接を受けて全落ちしました。後続のため、オンサイト面接がこんな感じだったよ、というのをストーリー風に仕立てて公開します。問題と会話はダミーですが、雰囲気はかなり近くできたと思います。なお実際の会話はすべて英語で、バーチャルでの実施でした。

メイン問題はLeetCodeのNo.1472をもとに作成。
https://leetcode.com/contest/weekly-contest-192/problems/design-browser-history/

ちなみに「ぼく」はIQ+30くらいの設定です。それではどうぞ。

入室と自己紹介
面接官「やあ！わたしはシンディ。会えて嬉しいよ！」
ぼく「こんにちは、シンディ。ぼくはyambe2002。調子はどう？」
面「超いい感じだよ。きみは？」
ぼ「ぼくも超いい感じさ」
面「それはよかった。わたしは部署Aのソフトウェアエンジニアで3年目なんだ。社内ツールを作ってるよ。AI関係のツールで、超クールでExcitingなやつなんだ」
ぼ「それはクールだね」
面「簡単な自己紹介をお願いしていいかな？」
ぼ「うん。ぼくは経験豊富なソフトウェアエンジニアで…〇〇で貢献して…リーダー経験が……」
面「Cool（たぶん聴いてない）。じゃ、問題に入ろうか。わたしからの問題はね…」
ぼ「あ、はい」

出題と質疑
面「Webブラウザの履歴を管理するコードを書いて」
ぼ「Webブラウザの履歴…」
面「そう。Webブラウザってさ、『戻る』ボタンで前のページに戻っていけるでしょ？あれを実現するの。『進む』ボタンもあるから注意して」
ぼ「なるほど。えーと、それはChromeみたいな普通のブラウザだよね。えーとえーと」
面「…」
ぼ「えーと、そうだ、APIとか決まってる？」
面「決まってないよ。好きに決めていいよ」
ぼ「うーん。じゃあ履歴って何を保持したらいい？URLとサイト名、タイムスタンプ？」
面「いい質問だね。ここでは簡単のため、そうだね、サイト名だけにしようか」
ぼ「ならサイト名のリストを持つする感じかな」
面「多分そうだね」
ぼ「えーと、そして、『進む』の時に遷移するサイト名、『戻る』のときに遷移するサイト名を返すAPIが要る」
面「うん。あと新しいサイトに遷移したときも」
ぼ「そうだね。じゃあ内部的には、サイト名の履歴を文字列リストで持って、Indexで現在の位置を管理する感じかな…」
面「それで行けそう？」
ぼ「待って。それで、APIはVisit()、Back()、Forward()でいい？」
面「うん、そうだね。とりあえずAPIはそれで良いよ」
ぼ「OK。あ、Back()やForward()で次に行けないときは、どうする？」
面「それもいい質問だ。そうだね、今のサイト名を返すようにしようか」
ぼ「あと何かあるかな…」
面「…」
ぼ「ブラウザだと、履歴一覧を表示したり、そこからサイトにジャンプしたりできるけど…」
面「あとで必要になるかもね」
ぼ「だよね。速度は…当然すべてO(1)でやらないといけない」
面「速いほうがいいね」
ぼ「あとは、えーと、履歴クリアもあとで付けそうだな。まあこれは簡単か」
面「そうだね」
ぼ「まとめると、履歴は文字列のリストで持ち、現在位置をIndexで管理する。Back()、Forward()が呼ばれたら、Indexをデクリメントかインクリメントする。Visit()のときは、Indexをインクリメントして、そこに新しいサイト名を書き込む」
面「Visit()でリストの長さが足りなかったら？」
ぼ「そのときはリストにAdd()する。あ、リストって可変長の配列のことね」
面「それで良さそう？」
ぼ「うーん、多分…なにかあるかな…」
面「『戻る』を何度かしたあと、新しいサイトを訪れたらどうなる？」
ぼ「ん？……あ、だめだ！そうか、『戻る』『戻る』『訪ねる』『進む』で過去のサイトに飛んでしまう！つまり、Visit()が呼ばれたら、それより後ろの履歴はクリアしないと！」
面「そう！ならどうする？」
ぼ「うーん。変数MaxIndexを足せばいいかな。MaxIndexより大きなIndexは無効。Visit()が呼ばれたら更新する」
面「なるほど。大丈夫そうだね」
ぼ「あとはOKかな？…よし、じゃあコード書いてみるよ（マーカーを手に取る）」

コーディング
ぼ「まずクラス外観はこんな感じかな…（カキカキ）」

public class BrowserHistory {
    public void Visit(string name) { }    
    public string Back() { }    
    public string Forward() { }
}

面「ん？これ何の言語？」
ぼ「C#だよ。ぼくはC#使いなんだ（自己紹介で言ったけど…）」
面「Cool」
ぼ「そして、履歴は文字列のリストで持つよ。名前は_historyでいいか」
面「OK」
ぼ「それと現在位置を表す_indexと、有効な最大Indexを保持する_maxIndexが要るね」

public class BrowserHistory {
    int _index = -1;
    int _maxIndex = -1;
    List<string> _history = new List<string>();

    public void Visit(string name) { }    
    public string Back() { }    
    public string Forward() { }
}

面「なんで_indexを-1で初期化したの？」
ぼ「これは『いまの位置』だから。初めはどこのサイトも表示してないのを想定してる」
面「なるほど」

public class BrowserHistory {
    int _index = -1;
    int _maxIndex = -1;
    List<string> _history = new List<string>();

    public void Visit(string name) { 
        if(_index == _maxIndex)
            _history.Add("");
        _history[++_index] = name;
        _maxIndex = _index;
    }

    public string Back() { 
        if(_index == -1) return "";
        _index = Math.Max(0, _index-1);
        return _history[_index];
    }   

    public string Forward() { 
        if(_maxIndex == -1) return "";
        _index = Math.Min(_maxIndex, _index+1);
        return _history[_index];
    }
}

ぼ「Visit()、Back()、Forward()も書くとこんな感じかな…」
面「Back()、Foward()で履歴がないときはブランクを返すようにしたんだね」
ぼ「そう。ちょっと手動テストしてみるね…。えーと履歴が無いときのBack()、Forward()は大丈夫そうかな…。初回のVisit()で_historyのサイズが1になって…そのあとBack()したら…Forward()は……」
面「大丈夫そう？」
ぼ「うん…たぶん…」
面「じゃいくつか聞くよ」

コードについての質疑１
面「まず、それぞれの関数の計算量を教えて」
ぼ「えーと、Visit()、Back()、Forward()すべてO(1)だね」
面「本当に？」
ぼ「え？……あ！Visit()の最悪ケースがO(N)か！リストのAdd()がO(N)になる場合がある！」
面「そうだね。その場合の問題点は？」
ぼ「まれにVisit()の実行が遅い。しかも、履歴がたまるとどんどん遅くなる」
面「その通り」
ぼ「これは大問題だ…」
面「まあ、一般的な使い方なら大丈夫だろうけどね。これを解決するにはどうする？」
ぼ「うーん、データ構造を変えないとダメな気がする…Doubly Linked ListかDequeueあたりかな…」
面「どうして？」
ぼ「Linked ListもDequeueも追加がO(1)だから。リストじゃなくてこっちを使うべきだったか…」
面「まあ良し悪しだけどね。ところでDequeueだと『戻る』『進む』の実装に困らない？」
ぼ「いや、それは２つDequeueを使えば出来るかな。でもDoubly Linked Listのほうが素直に実装できそう」

コードについての質疑２
面「ところで、仕様追加をしたいんだけど」
ぼ「う、うん」
面「古い履歴は自動で捨てるようにしたい」
ぼ「えーと、古い、っていうのは時間で？それとも何回分前かで？」
面「そうだね。じゃ何回分前かでやろう」
ぼ「LRUキャッシュみたいに？」
面「お、そうそう。じゃ、ついでだから、LRUキャッシュについて説明してくれる？」
ぼ「LRUはLeast Recently Usedのことで、容量が閾値を超えたときに『いちばん訪れてない』キャッシュを捨てていくもの。LinkedListを使った実装が一般的」
面「そうだね。君の実装はリストだけど、それで実現できる？」
ぼ「難しいと思う。たとえば『最小の有効Index』を持てば見た目は実現するけど、これ結局メモリを解放してないので意味がない。メモリ解放するためにリストを作り直すと、こんどは実行時間が遅くなる」
面「わたしもそう思う」
ぼ「うーん、Linked Listで実装したほうがいい？」
面「きみがそうしたほうがいいと思うなら」
ぼ「了解（あ、あと15分しか無いじゃん！！急げ！）」

public class BrowserHistory {
    int THRES = 1000;
    LinkedListNode<string> _current;
    LinkedList<string> _history = new LinkedList<string>();

    public void Visit(string name) { 
        var node = new LinkedListNode<string>(name);
        if(_current?.Next == null)
            _history.AddLast(node);
        else
            _current.Next = node;
        _current = node;

        CheckSize();
    }

    void CheckSize(){
        while(_history.Count > THRES)
            _history.RemoveFirst();
    }

    public string Back() { 
        if(_current == null) return "";
        if(_current.Previous != null) 
            _current = _current.Previous;
        return _current.Value;
    }   

    public string Forward() { 
        if(_current == null) return "";
        if(_current.Next != null) 
            _current = _current.Next;
        return _current.Value;
    }
}

ぼ「で、できたよ…（ぜえぜえ）」
面「OK。ちょっと時間がないから、細かいチェックは省こうか」

コードについての質疑３
面「ああ、あと3分で次の面接が始まっちゃうね。じゃ最後にもう一個だけ聞こうか」
ぼ「」
面「このコードはLeast Recent Usedにしたけど、訪れた時間が古いもの、たとえば1日以上前のものを随時クリアする、ならどう実装する？」
ぼ「えーとえーと、サイト名と合わせて時間も保存して…」
面「うんうん」
ぼ「CheckSize()で、サイズの代わりに現在時との差をチェックすればいい…？」
面「それで問題ない？」
ぼ「……いや、ダメか。『戻る』があるから、古い順にソートされてるとは限らないね」
面「『戻る』『進む』で時間も更新するならそうだね」
ぼ「えーっと、あ、これはSortedDictionaryを使えばできる、かな？」
面「SortedDictionaryっていうのは？」
ぼ「Key-ValueのMapなんだけど、Keyがソートされてるんだ。キーの実装はたしかBalanced-BSTだったと思う。Javaで言うTreeMap」
面「ああ、なるほど」
ぼ「これに、更新時間をキー、値をLinkedListNodeで保存してあげれば。キーの小さいほうから、値を取り出して、1日以上前ならそのNodeを削除する。1日未満ならBreakかな」
面「行けそうだね。もしそうしたら、計算量はどうなる？」
ぼ「Back()、Forward()、Visit()がすべてO(LogN)になる。毎回BSTへの更新が発生するから」
面「それは確実？」
ぼ「…いや、古い履歴がたくさんあると、クリアに時間がかかる場合があるか。極端な話、全部が古いとO(NLogN)かかる」
面「一つ一つ消したらそうだろうね」
ぼ「うーん、キーのBalanced-BSTをうまく作れば二分探索で…いや、ちょっと分からないや」
面「難しいね。もしかしたら、完ぺきじゃないかもしれないけど、CheckSize()で単純にFirst()から日付をチェックするほうがベターかもしれないよ。実装も単純だしね」
ぼ「なるほど…」

次の面接へ
面「ああ、時間がなくなっちゃった。きみのほうから何か質問ある？」
ぼ「えーっとえーっと、（何かひねり出さないと…あれっ、この人名前なんだっけ？）あなたは社内ツールを作ってるんだっけ、AI関連の」
面「そうだよ！これはとてもチャレンジングな仕事で~~機械学習がうんぬんかんぬん~」
面２「（前触れなく）ハロー！」
面「やあマイク！紹介するよ、こちらはマイク。こちらはyambe2002」
面２「会えて嬉しいよyambe2002！僕は部署Bで働いてるバックエンドエンジニアだよ！」
ぼ「やあマイク！」
面２「それじゃ、ここからぼくが引き継ぐね。ありがとうシンディ！」
面「ありがとう。それじゃあねyambe2002。Good Luck!」
面２「じゃあ早速だけど、ぼくからの問題はこれ。ミュージシャン名で検索すると、コンサートや開始時間・料金なんかを表示するWebサイトをデザインしてほしいんだ！近くのコンサートを優先してね。細かい要件はね…」
ぼ「」（すでに疲労困憊）

こんな感じのが4~5連続