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

投稿の2番目の部分では、前の投稿を読んでいないか、トピックのリストを「記憶」したい場合は、 「アルゴリズムと概念」が考慮されます 。

アルゴリズムと概念

並べ替えと検索

よく知られているソートアルゴリズムを理解/知ることは非常に重要です。ソートまたは検索に関連する多くの決定は、穏やかに言えば、これらのアルゴリズムの知識を必要とするからです。 ソートするタスクが与えられたときにあなたの知識をインタビュアーに示す良い方法は、既知のアルゴリズムを「実行」し、この問題を解決するのに最適なアルゴリズムを見つける/見つけることです。 同じ問題を解決する「異なる」方法に満足するためのソリューションとインタビュアーの両方を受け取ります。

たとえば、「 従業員オブジェクトの大きな配列があり、従業員を年齢で並べ替えます 。」



ここでは、少なくとも2つのことに注意する必要があります。 第一に、配列は大きいため、まず第一に効率性を意味します。第二に、ソートは年齢に基づいています。つまり、値が短い間隔にあることはすでに明らかです。 ブロックソートアルゴリズムを安全に使用できます。

既知のアルゴリズム（これらの「既知の」もの）：

• バブルソート
• 選択順に並べ替えます。
• ソートをマージします。
• クイックソート
• ブロックソート（バケットソート）。

例

「 2つのソートされた配列AとBがあり、Aのサイズは配列Bを含むのに十分な大きさです 。 ソート順序を維持しながらBをAにマージするメソッドを記述します 。」

void merge(int a[], int b[], int n, int m) { int k = m + n - 1; int i = n - 1; int j = m - 1; while (i >= 0 && j >= 0) { if (a[i] > b[j]) { a[k--] = a[i--]; } else { a[k--] = b[j--]; } } while (j >= 0) { a[k--] = b[j--]; } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

あなたがより「有利な」立場にいることに気付いた検索では、線形アルゴリズムとバイナリアルゴリズムを知るだけで十分です。

「 各行と各列が並べ替えられた配列を指定して、配列内の要素を見つける関数を作成します 。」

以下のソリューションを見て、最適なソリューションを提案してください。

 bool find_element(int** mat, int elem, int M, int N) { int row = 0; int col = N - 1; while (row < M && col >= 0) { if (mat[row][col] == elem) { return true; } else if (mat[row][col] > elem) { --col; } else { ++row; } } return false; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

投稿のコードがC ++であることは実際には重要ではないことに注意してください。ほとんどの場合、同じコードは、JavaやC＃コードなどの大きな変更なしで構文的に同等です。

リフレクションのタスク：

「 バイナリ検索アルゴリズムを実装します 。」

「 100万個の浮動小数点数のソートを整理する方法は？ 「。

「 従業員オブジェクトの配列を給与でソートします（従業員には名前、年齢、給与、住所のフィールドが含まれていると想定しています） 。」

再帰

再帰を伴うタスクは非常に多く、多くのタスクはパターンに従います。 タスクをサブタスクに分割できる場合、これはすでにタスクが「再帰的」であるというヒントです。 「 最初のn ...を表示するコードを書く 」、「 すべてを考慮する関数を実装する ... 」などのタスクを聞いたら、まず 、少なくとも再帰的な解決方法の使用を検討してください。

すべての場合において、練習はあなたの親友であり、あなたが解決するタスクの数であり、新しいものを解決するだけでなく、問題自体を解決する方法に集中することも簡単になります。

そのため、最初にサブタスクを認識してみてください。 再帰が停止する「基本的な」問題を解決/見つけます（基本的にこれはハードコードされた値です）。 2番目のサブタスクの問題を解決し、2番目のサブタスクに基づいて3番目のサブタスクを解決する方法を理解します。 n番目のサブタスクのソリューションを要約します。

再帰の助けを借りて解決されたタスクには、反復的な解決策もあることを忘れないでください。 それでも、再帰的なアルゴリズムは、空き領域の点で非常に効率が悪い場合があります。

“ n番目のフィボナッチ数を生成する関数を書きます。 ”

再帰オプション：

 int fibonacci(int n) { if (0 == n) { return 0; } if (1 == n) { return 1; } //    if(0 == n || 1 == n) { return n; } if (n > 1) { return fibonacci(n - 1) + fibonacci(n - 2); } return -1; //    }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

反復オプション：

 int fibonacci(int n) { if (n < 0) { return -1; } if (n == 0) { return 0; } int a = 1, b = 1; for (int i = 3; i <= n; ++i) { int c = a + b; a = b; b = c; } return b; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

考えてみて：

「 上記の問題の解決策をどのように改善しますか？ 」

「 セットのすべてのサブセットを返す関数を作成します 。」

“ 女王様の仕事を解決してください ”

ビット操作

ビットを操作することは多くの候補者にとって恐ろしいことですが、そうすべきではありません。

これらの問題を解決する際に間違いを犯すだけで十分なので、注意するか、むしろ注意してください。 記述するコードの各行を慎重に検討してください。

シフトについて忘れないでください。x<< y （左シフト）は、xがそれぞれ右にビット単位でyビットとx >> y （右シフト）だけ左にシフトされることを意味します。

かなり一般的なタスクが1つあります。自分で解決してみてください（「逆側」から引用）-「 次のコードを説明してください：（（n＆（n-1））== 0） 」。

「 2つの32ビット数、NとMが与えられます。さらに2つのビット位置、iとjがあります。 iとjの間のすべてのビットをMに等しいNに設定する関数を作成します（つまり、MはNの部分文字列になります）

例：

入力：N = 100000000、M = 101、i = 2、j = 3

出力：N = 100010100 "。

 int update_bits(int n, int m, int i, int j) { int max = ~0; //  1' // 1'   j,  0' int left = max - ((1 << j) - 1); //1'   i int right = ((1 << i) - 1); // 1'    i  j int mask = left | right; //""  i  j   m return (n & mask) | (m << i); }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

考えてみてください：「 浮動小数点数を文字列として指定すると、バイナリ表現を出力します。 」

オブジェクト指向設計

OOPの質問（ここではPはデザインです）は非常に重要です。少なくともそう思います。 OOPの知識は、インタビュアーにある程度の自信があります。なぜなら、候補者は、彼が取り組むプロジェクトのクラス図を「理解」することが明らかになるからです。 これはほんのわずかなプラスに過ぎず、候補者に有利なPLOのその他の重要な利点があります。 しかし、知識の欠如は、インタビュアーに「次は誰？」という感覚を引き起こします。 もちろん、これはOOP関連の投稿にも当てはまります。そうでなければ、私の意見では、ドライバー開発者がOOPについて質問されることはほとんどありません。 ただし、インタビュー中に、特定のアプリケーション、またはテレビなどの「非アプリケーション」を設計するように求められる準備をしてください。 たとえば、リモコンとテレビの関係について話すように求められます。 「has-aとは」「is-aはどう違いますか」などの質問に備えてください



チャットサーバーを設計します 。

 enum status_type { online, offline, away }; struct status { status_type m_status_type; std::string m_status_message; }; struct add_request; class user { private: std::string m_username; std::string m_display_name; std::list<user*> m_contact_list; std::list<add_request*> requests; public: bool update_status(status_type stype, const std::string& msg); bool add_user_with_username(const std::string& name); bool approve_request(const std::string& username); bool deny_request(const std::string& username); bool remove_contact(const std::string& username); bool send_message(const std::string& username, const std::string& message); }; struct add_request { user* m_from_user; user* m_to_user; }; class server { user* get_user_by_username(const std::string& username); };
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

これは簡単な例です;実際には、質問/タスクは「良質」です。

考えるために：「 オンラインブックリーダーのデータ構造を設計する 」



これで十分だと思います。以下の投稿では、プログラミング言語についてだけでなく、より複雑なインタビューに関連する他のトピック/質問についても書こうとしています。