ささやかなインタビューガイド：パート1

プログラマーがプログラミングインタビューの準備をするのに役立つ投稿が用意されています。 少なくとも、インタビューの前に知ることが望ましいすべての主要なトピックを網羅しています。 私たちは、同僚の経験、経験、物語、専門文学を使用しました。

ここで説明するトピックの一部は、一部のプログラマにとってはまったく役に立たない場合もあれば、必要となる場合もあります。 私のアドバイスは、ここで言及されているトピック/セクション/側面をできるだけ勉強することです。

そして、必要な知識として：

• データ構造
• アルゴリズムと「概念」
• プログラミング言語

もちろん、上記のリストは、それらに関連するすべてを知ることを強制するものではなく、現実的でもありません。 少なくとも初心者プログラマー向け。 著者と一部のかなり適格なインタビュアーの意見で知っておく必要のある最低限のものがあります。



データ構造

• 配列と文字列
• 関連リスト
• スタックとキュー
• 木とグラフ

アルゴリズムと「概念」

• 並べ替えと検索
• 再帰
• ビット操作
• オブジェクト指向設計

プログラミング言語

• 基本的なコンポーネント
• 「ホーム」完成プロジェクト
• 可能な限り

そして今、棚に、何、どのように、そしてなぜ？

データ構造

配列と文字列

「状況」の一般的な考え方を示す質問：

「 特定の文字列ですべての文字が繰り返されていないかどうかを判断する関数を実装します 。」

簡単にするために、ASCII文字セットがあることを想像してください（ない場合は、「コンテナー」のサイズを変更する必要がありますが、ロジックはまったく変更されません）。

bool are_unique_characters(const std::string& str) { std::vector<bool> char_set(256, false); for (int i = 0; i < str.size(); ++i) { int val = str.at(i); if (char_set[val]) { return false; } char_set[val] = true; } return true; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

この場合の複雑さはO（n）です。nは入力文字列の長さです。 面接中に複雑さについて言及し、特定のアルゴリズムの複雑さを実際に/正しく計算できることが非常に重要です。

文字列が「a」から「z」までの文字（小文字）のみで構成されていると仮定した場合、ベクトルなしで実行できるため、次のコードの方が適切なソリューションになります。

 bool are_unique_characters(const std::string& str) { int checker = 0; for (int i = 0; i < str.size(); ++i) { int val = str.at(i) - 'a'; if ((checker & (1 << val)) > 0) { return false; } checker |= (1 << val); } return true; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

リフレクションのために、これは古典的なタスクです：「 C行を裏返します（つまり、「abcd」は5文字で、5番目は終端のヌル文字「\ 0」です） 。」

あなたの決定をこれと比較し、質問に答えてください、なぜあなたのコードは良いですか？

 void reverse_c_string(char* str) { char* end = str; char tmp; if (str) { while (*end) { ++end; } --end; while (str < end) { tmp = *str; *str++ = *end; *end-- = tmp; } } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

宿題として、この問題の解決を試みてください。「 NxN配列の形式の画像が与えられます。各要素は1ピクセルで、各ピクセルの重量は4バイトです。 画像を90度反転する関数を作成します 。

関連リスト

リンクリストに関する質問は、控えめに言っても、かなり一般的です。 質問は、単純な「リンクされたリストからノードを削除する」ものから、より精神的に煩わしいものまであります。 リンクリストについて尋ねられたら、問題のリストを指定してください-単独または二重接続。 繰り返しますが、リストを作成する方法と、単一リンクリストからノードを削除する方法を知っている必要があります。



タスクの例：

「 並べ替えられていないリンクリストから重複するアイテムを削除するコードを記述してください 。」

持っている

 struct list_node { int data; list_node* next; };
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

解決策は次のようになります（そしてあなたの？）：

 void delete_duplicates(list_node* head) { if (NULL == head) { return; } list_node* previous = head; list_node* current = previous->next; while (NULL != current) { list_node* runner = head; while (runner != current) { if (runner->data == current->data) { list_node* tmp = current->next; previous->next = tmp; current = tmp; break; } runner = runner->next; } if (runner == current) { previous = current; current = current->next; } } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

「 単純に接続されたリストの中央からノードを削除するアルゴリズムを実装します 。 そのノードのみがアクセスできます 。」

解決策は簡単ですが、削除されたノードがリストの最後のノードであり、インタビュアーがそれを聞きたい場合、タスクは解決できないことを理解することが重要です。

 bool delete_node(list_node* nd) { if (NULL == nd || NULL == nd->next) { return false; // whatta..? } list_node* nxt = nd->next; nd->data = nxt->data; nd->next = nxt->next; return true; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

考えるべき質問、別名宿題：

「 リンクリストの形式で表示される2つの数値があり、各ノードには1桁が含まれます。数値は逆の順序で格納されます。これらの数値の合計を減算し、リンクリストの形式で返す関数を記述します。

例：合計で295と513の場合、808が得られます。

入力：（5-> 9-> 2）、（3-> 1-> 5）

終了：（8-> 0-> 8） 。 "



「 リンクリストの中央を検索します 。」

スタックとキュー

必要な知識は、スタックとキューを実装する能力です。 実装されたクラスメソッドのすべての入力値と「境界ケース」を必ず確認してください。



「 2つのスタックを使用してキューを実装するクラスmy_queueを作成します 。」

「 以下は前の問題の解決策です。このコードの何が問題になっていますか？ 」

 template <typename T> class my_queue { private: std::stack<T> m_stack1; std::stack<T> m_stack2; int size() const { return m_stack1.size() + m_stack2.size(); } void add(const T& value) { m_stack1.push(value); } T peek() { if (!m_stack2.empty()) { return m_stack2.top(); } while (!m_stack1.empty()) { m_stack2.push(m_stack1.top()); m_stack1.pop(); } return m_stack2.top(); } T remove() { if (!m_stack2.empty()) { T tmp = m_stack2.top(); m_stack2.pop(); return tmp; } while (!m_stack1.empty()) { m_stack2.push(m_stack1.top()); m_stack1.pop(); } return m_stack2.top(); } };
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

考えてみて：

「 スタックを昇順でソートするプログラムを作成します 。」

木とグラフ

ツリーとグラフに関する質問は、主に次の形式で「利用可能」です。

• ツリーの実装/ノードの検索/ノードの削除/その他の重要なアルゴリズム
• 既知のアルゴリズムの修正版を実装する

インタビューの前にツリーとグラフの準備を注意深く行い、「すべてのバイナリツリーがバイナリ検索ツリーであるとは限らない」ことを忘れないでください。

次のアルゴリズムを簡単に実装できるはずです。

• 直接ツリーウォーク（先行予約）
• 対称バイパス（順序どおり）
• リバースバイパス（ポストオーダー）
• ノードを挿入

グラフの必須知識：

• 深さ優先検索
• 幅優先検索

「 ソートされた（昇順で）配列を指定して、最小の高さのバイナリツリーを作成するアルゴリズムを記述します 。」

アルゴリズム：

1. 配列の中央の要素をツリーに挿入します
2. 「左サブアレイ」の要素を（左サブツリーに）挿入します
3. 「右サブアレイ」の要素を（右サブツリーに）挿入する
4. そして、再帰的に

 tree_node* add_to_tree(int arr[], int start, int end) { if (end < start) { return NULL; } int mid = (start + end) / 2; tree_node* n = new tree_node(arr[mid]); n->left = add_to_tree(arr, start, mid - 1); n->right = add_to_tree(arr, mid + 1, end); return n; } tree_node* create_min_BST(int arr[]) { //... SIZE   //... arr   return add_to_tree(arr, 0, SIZE - 1); }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

考えてみて：

「 非再帰的な対称ツリーウォークを実装します。」



UPD ： Shedalが指摘したように、このガイドは（主に）学生/ジュニア向けです。



UPD 2 ： パート2。