半年ほど前だが、アメリカの超大手IT企業からスカウトが来て、そのくせ電話面談で落とされるという屈辱的な経験をしたので、戒めとして晒しておく。

 

• 4月下旬

LinkedIn経由でリクルーターからメッセージが届く。デトロイトで本社採用SDE(Software Development Engineer)の採用イベントがあるから、来ないか、という内容。まああの会社なら受けてもよいと思って、Resumeを送る。

ちなみに、ResumeはoDeskでフリーの方に添削してもらった。

そしたら、すぐに返答が来て数日後に電話面接が設定される。早い！準備をする時間がない！

 

• 電話面接(一回目)、3日前まで

この定石本をざっと眺める。ただし、実際のアルゴリズム質問集までやるのは無理なので、Behavioral Questionsの準備にとどめておく。

www.amazon.co.jp

あとは、以下について、Wikipediaレベルで軽く復習しておいた。

Linked Lists/Binary Trees/Tries/Stacks/Queues/Vectors(Array Lists)/HashTables/Merge Sort/Quick Sort/Singleton Design Pattern/Factory Design Pattern/Memory(Stack vs Heap)

 

• 電話面接(一回目)

西海岸との時差を利用し、業務終了後に会社から面接を受けることにしたが、これは正解だった。静かだし、机が広くて資料をばっと広げておける。

そして肝心の面接だが、電波が悪くてかなり聞き取りづらい！せめてヘッドセットを用意しておくべきだった。何度も何度も聞き返してしまった。

聞かれたのはこんなこと。

1. 今はどんな会社で、何をやってるのか。ポジションは
2. 使ってる言語は？Javaは使ったことがあるか
3. ビザステータスについて
4. SDE(SDET)の経験はあるか
5. この会社の仕事内容は知っているか

基本的な技術知識も聞かれる。（いずれも5択だった）

1. HashTableから要素を削除するときの計算量は？ → O(1)と回答
2. 親クラスからDeriveして子クラスを作った。これは何？ → 継承(Inheritance)と回答
3. ソートされたInt型の配列から要素を探すのに適した方法は？　→ Binary Searchと回答
4. 3の方法での計算量は？ → log(N)と回答
5. ソートされてないInt型の配列をソートするのに適した方法は？　→ 一般的にはQuickSortと回答
6. 5の方法での計算量は？ → N log(N)と回答
7. 正規表現は何に使う？ → インプットのバリデーション等と回答

これで、この面接はパスしたらしい。たぶん7問中5問正解でOKとかそういう基準なのだろう。次はエンジニアとの面談で、アルゴリズム・OOP・Problem Solvingの力を測るらしい。あと過去のこと、特にプロジェクトをリードして成功させた経験なども聞くかも、とのこと。怖い…。

数日後にHRの方からメール連絡があり、3日後に二回目の電話面談がセッティングされた。

この時点で、この会社の電話面談の内容とか、SDEの面談用チェックリストをもらう。A4で数ページにわたるもので、この短期間ではとても準備しきれない量だった。たとえば、ConputerScienceの知識を総復習しておくように、とかが書いてあった。

 

• 電話面談(二回目)

今回も業務終了後にオフィスでやることに。

相手は、LinkedInで検索したところ、プログラミングコンテストの世界大会で入賞したりしているバリバリのコーダーだった。すごい。

自己紹介もそこそこに、オンラインの共有エディタでコーディング開始。問題は、「バイナリツリーの２ノード間の距離を求めるメソッドを作成せよ」だった。冷静に考えればまあ解ける（はず）の問題でも、電話面談という特殊な場、かつ常に英語で説明しながらだと脳みそのオーバーヘッドが大きくてきつかった。

結局、アイデアを２つ出して、効率が悪い方をざっと実装して問題点を話し合い、次に効率が良い方を途中まで完了したところでタイムアップ。終了直後にアイデアが思いついて悔しかった。

当然だが、お祈りメールをいただいてしまった（日本企業みたいな定型文じゃないけど）。

教訓としては、もっとSRM的な問題でアルゴリズム・コーディングを鍛えたほうがよいことと、説明しながらコードを書く練習をするべき、といったところ。あとヘッドホンは絶対必要。ちなみに志望動機なんかはまったく聞かれなかった。

 

• 後日

面談で聞かれた、バイナリツリーの2ノード間の距離を求めるコードをC#で書いてみた。深さ優先で探索し、現ノードからのNode1、Node2までの深さを長さ2の配列で返す。探索中に配列のどちらにも有効値が入っていたら、その合計を最終的な距離の候補とする。O(N)。

    public class Node
    {
        public Node Left { get; set; }
        public Node Right { get; set; }

        public static int GetDistance(Node root, Node node1, Node node2)
        {
            var dist = Int32.MaxValue;
            Dfs(root, node1, node2, ref dist);
            return dist;
        }

        public static int?[] Dfs(Node cur, Node node1, Node node2, ref int dist)
        {
            if (cur == null) return new int?[] { null, null };

            var ret = Dfs(cur.Left, node1, node2, ref dist);
            var ret2 = Dfs(cur.Right, node1, node2, ref dist);

            ret[0]++;
            ret[1]++;
            ret2[0]++;
            ret2[1]++;

            ret[0] = ret[0] != null ? ret[0] : ret2[0];
            ret[1] = ret[1] != null ? ret[1] : ret2[1];

            if (cur == node1) ret[0] = 0;
            if (cur == node2) ret[1] = 0;

            if (ret[0] != null && ret[1] != null) dist = Math.Min(dist, (int)(ret[0] + ret[1]));

            return ret;
        }
    }

 

このサイトでは、２ノードの共通の親（LCA、Lowest Common Anscentor)を求めて解いている。なるほど。

http://www.geeksforgeeks.org/find-distance-two-given-nodes/