面接メモ：面経-サルガイダンス-二面

記事の目次

一、自己紹介

、Javaバックグラウンド

2.1オペレーティングシステム

2.1.1アプリケーション実行プロセス

.C言語コンパイル実行プロセス

2.1.3コンパイル中に未定義変数が発生した理由

.コンピュータネットワーク

.2.1 http要求全プロセス

.2.2 Hostsファイルの役割

.2.3 DNSはTCPを使用しますか？それともUDP

を使用しますか？

.TCPとUDPは同じポートを同時に使ってもいいですか？

.2.5 serverとclient通信中にserverを切ったらどうなりますか？

、アルゴリズム問題（手裂き）

3.1一本の二叉樹が完全二叉樹であると判断した

3.2配列の誘拐点

を見つけました。

、アルゴリズム問題（口述）

4.1迷路を歩く歩き方の総数（ダイナミック企画）

4.2分治法と動態計画の違い

一、自己紹介
個人背景、プロジェクト経歴、実習経歴。
二、Java楽屋
2.1オペレーティングシステム
2.1.1アプリケーション実行プロセス
Windowsでは、アプリケーションが起動されると、システム呼び出しCreateFile がディスク上の.exe を開いて、システム呼び出しcreateFileMapping がファイルマッピングオブジェクトを作成し、最後にシステムが作成したプロセス呼び出しMapViewOfFileEx を表して、.exe をプロセスのアドレス空間にマッピングする。その後、システムは、プロセスのメインスレッドを作成し、実行可能コードの最初のバイトのアドレスをスレッドの命令ポインタにマッピングし、CPUはコードの実行を開始する。
2.1.2 C言語のコンパイル実行プロセス

第一段階：前処理は正式なコンパイル段階の前に行われる。前処理段階では、ファイルに置いた前処理コマンドに従ってソースファイルの内容を変更します。前処理コマンドとして、ヘッドファイルの内容を.cppファイルに追加します。

第二段階：コンパイル最適化は、等価の中間コード表現またはアセンブリコードに変換し、最適化を実行する。

第三段階：アセンブラ言語コードを対象機器指令に翻訳する。

第4段階：リンク例えば、あるソースファイルの関数は、変数や関数呼び出しなどの他のソースファイルで定義されている記号を参照することができます。プログラムでは、ライブラリファイルの関数などを呼び出すことができます。これらのすべての問題は、リンクされたプログラムの処理によって解決されます。

2.1.3コンパイル中に未定義変数が発生した理由
変数、関数が宣言されていない、またはヘッダファイルが含まれていないためです。
2.2コンピュータネットワーク
2.2.1 http要求の全過程

第一歩：ブラウザがhttp要求情報（セッション層）（1）分解url（2）を生成するhttp要求メッセージ（3）ドメイン名解析（4）委託オペレーティングシステムがhttp要求

を送信する。

第二ステップ：TCPモジュール送信要求（トランスポート層）（1）ソケット作成（2）接続サーバ（3）送信データ

第3ステップ：IPモジュール送信要求（ネットワーク層）（1）IPヘッダを生成する（2）MACヘッダを生成する

第4ステップ：MACモジュール送信要求（データリンク層）（1）ヘッダ生成（2）チェックシーケンス生成（3）電気信号生成

第5ステップ：PHYモジュール送信要求（物理層）最終ネットワークカードのPHYモジュールは、汎用電気信号をネットワーク送信に必要なフォーマットに変換して、回線を介して送信する。ネットワーク転送後、最終的にサーバに到着します。

2.2.2 hostsファイルの役割
いくつかのよく使われているドメイン名と対応するIPアドレスを関連付けられた「データベース」として作成します。ユーザーがブラウザに登録したいURLを入力すると、まず自動的にhostsファイルから対応するIPアドレスを探します。見つけたら、すぐに該当ページを開きます。見つけられなかったら、システムは、DNSドメイン名解析サーバーにURLを提出し、IPアドレスの解析を行います。
2.2.3 DNSはTCPを使用しますか？それともUDPを使用しますか？

エリア転送時にTCP：1を使用してサブドメイン・サーバのタイミング（一般的には3時間）でホストドメイン・サーバに照会し、データの変動があるかどうかを確認する。変動があれば、一度エリア転送を行い、データ同期を行います。領域転送はUDPではなくTCPを使用します。データ同期転送のデータ量は要求と応答のデータ量よりずっと多いです。2）TCPは信頼できる接続であり、データの正確性を保証している。

ドメイン名解析にはUDPを使用します。クライアントはDNSサーバにドメイン名を照会します。一般的に戻る内容は512バイトを超えず、UDPで送信すればいいです。TCPの3回の握手を経ないでください。このようにDNSサーバーの負荷はより低くて、応答はより速いです。理論的には、クライアントはDNSサーバに照会する際にTCPを使用するよう指定することもできますが、実際には多くのDNSサーバが構成する場合、UDPクエリパケットのみがサポートされます。

2.2.4 TCPとUDPは同じポートを同時に使ってもいいですか？
はい、TCPとUDPはIPヘッダ情報が異なり、システムによって区別されます。
2.2.5 serverとclient通信中にserverを切ったらどうなりますか？
三、アルゴリズムの問題（手で引き裂く）
3.1一本の二叉樹が完全二叉樹であると判断する。
ステップオーバーの方式を採用して、ノードを判断する時、次のような判断根拠があります。

このノードの左のサブツリーがnullであり、右のサブツリーがnullでないと、完全な二叉の木ではないに違いない。

は、このノードの左右のサブツリーがnullであるか、またはこのノードの左のサブツリーがnullではないが、右のサブツリーがnullである場合、現在の層または次の層は、左右のツリーを含むノードを再び出現させることができない。

は、現在のノードの左右のサブツリーがnullでない場合、次のノードを観察する。

private static boolean isCompleteTree(Node node) {
    if (node == null) {
        return false;
    }
    boolean hasLeaf = false;
    Queue<Node> queue = new ArrayDeque<>();
    queue.add(node);
    while (!queue.isEmpty()) {
        Node tmp = queue.poll();
        if (tmp.left() == null) {
            if (tmp.right() != null) {
                return false;
            }
            if (tmp.right() == null) {
                hasLeaf = true;
            }
        } else {
            if (hasLeaf) {
                return false;
            }
            if (tmp.right() == null) {
                hasLeaf = true;
                queue.add(tmp.left());
            }
            if (tmp.right() != null) {
                queue.add(tmp.left());
                queue.add(tmp.right());
            }
        }
    }
    return true;
}

3.2配列の曲がり点を見つける
二分割ルックアップを採用すると、曲がり点要素は左側の要素よりも大きいか、右側の要素よりも大きいか、すなわちnums[i] > nums[i - 1] && nums[i] > nums[i + 1]です。検索した要素が右側より大きい場合、左半分の部分に曲がります。検索した要素が左より大きい場合は、右半分に曲がります。

private int findPeak(int[] nums) {
    if (nums != null && nums.length > 0) {
        if (nums.length == 1) {
            return 0;
        }
        if (nums[0] > nums[1]) {
            return 0;
        }
        int index = nums.length - 1;
        if (nums[index] > nums[index - 1]) {
            return index;
        }
        int i = 0, j = index;
        int mid = 0;
        while (i < j) {
            mid = (i + j) / 2;
            if (nums[mid] > nums[mid - 1] && nums[mid] > nums[mid + 1]) {
                return mid;
            } else if (nums[mid] > nums[mid + 1]) {
                j = mid - 1;
            } else if (nums[mid] > nums[mid - 1]) {
                i = mid + 1;
            }
        }
    }
    return -1;
}

四、アルゴリズムの問題（口述）
4.1迷路の歩き方の総数（動態計画）
4.2分治法と動態計画の違い

分法：問題をいくつかの独立したサブ問題に分割して、再帰的に各サブ問題を解いて、その後の統合子問題の解によって元の問題の解を得る。

ダイナミックプラン：サブ問題が独立して重なっている場合に適用されます。つまり、各サブ問題は公共のサブ問題を含んでいます。

サブ問題が独立して重複している場合、分割法則を用いると多くの不必要な作業を行い、すなわち公共のサブ問題を繰り返し解決する。動的計画アルゴリズムは各サブ問題に対して一回だけ解を求め、その結果を一枚の表に保存し、サブ問題が発生するたびに答えを再計算することを避ける。