選択には、Microsoftインタビューからのタスクが含まれます。 難易度は、伝統的に、単純なものから少し反省する必要があるものまでさまざまです。 インタビュー中の時間的なプレッシャーよりもリラックスした雰囲気の中でこれを行うことを好みます。そして、あなたのインタビューが静かに、リラックスして建設的に開催されることを望みます:)
ご質問
- チェス盤上のドミノ
対角線上の2つの角が切り取られた8 x 8のチェス盤があります。 31のドミノが与えられ、1つのドミノでちょうど2つの正方形をカバーできます。 31個のドミノを使用してボード全体をカバーできますか？
翻訳通常のチェス盤は、対角線上にある2つのセルを切り取ります。 31のドミノが与えられました。 1つの骨がちょうど2つのチェス細胞を覆っています。 これらの種でフィールド全体をカバーできますか？
- 仕事のための金
あなたは7日間あなたのために働いている人とそれらを支払う金の延べ棒を持っています。 毎日の終わりに労働者に仕事の代金を支払わなければなりません。 金の延べ棒で2回だけ休憩することが許されている場合、労働者にどのように支払いますか？ （毎日同じ量の作業が行われると仮定すると、毎日同じ賃金が必要になります）
翻訳誰かが金地金での仕事の支払いで7日以内にあなたのために働きます。 その日の終わりに従業員に毎日支払う必要があります。 2回しかバーを壊せない場合、労働者にどのように支払いますか？ （同じ量の作業が毎日行われ、同じ支払いが必要であると想定されます）
タスク
- リンクリストを逆にする
リンクリストのヘッドノードへのポインターを指定すると、タスクはリンクリストを逆にすることです。 ノード間のリンクを変更して、リストを逆にする必要があります。
例：
入力：次のリンクリストのヘッド
1-> 2-> 3-> 4-> NULL
出力：リンクリストを変更する必要があります。
4-> 3-> 2-> 1-> NULL
入力：次のリンクリストのヘッド
1-> 2-> 3-> 4-> 5-> NULL
出力：リンクリストを変更する必要があります。
5-> 4-> 3-> 2-> 1-> NULL
入力：NULL
出力：NULL
入力：1-> NULL
出力：1-> NULL
翻訳リンクされたリストのヘッドノードへのポインターが与えられます。タスクはリストを逆のリストに変換することです。 ノード間のポインターを変更する必要があります。
例：
入力：ヘッドノードへのポインター、およびリスト自体-1-> 2-> 3-> 4-> NULL
出力：4-> 3-> 2-> 1-> NULL
入力：1-> 2-> 3-> 4-> 5-> NULL
出力：5-> 4-> 3-> 2-> 1-> NULL
入力：NULL
出力：NULL
入力：1-> NULL
出力：1-> NULL
- 最長バイニックサブシーケンス
n個の正の整数を含む配列arr [0 ... n-1]が与えられた場合、arr []のサブシーケンスは、最初に増加し、次に減少する場合、Bitonicと呼ばれます。 引数として配列を取り、最長のバイニックサブシーケンスの長さを返す関数を作成します。
昇順で並べ替えられたシーケンスは、減少した部分が空のバイトニックと見なされます。 同様に、減少する順序シーケンスは、増加する部分が空であるバイトニックと見なされます。
例：
入力arr [] = {1、11、2、10、4、5、2、1};
出力：6（長さ6の最長バイニックサブシーケンスは1、2、10、4、2、1）
入力arr [] = {12、11、40、5、3、1}
出力：5（長さ5の最長バイニックサブシーケンスは、12、11、5、3、1です）
入力arr [] = {80、60、30、40、20、10}
出力：5（長さ5の最長バイニックサブシーケンスは80、60、30、20、10です）
翻訳n個の正の整数を含む配列arr [0 ... n-1]を指定します。 サブシーケンスの要素が最初に増加し、次に減少する場合、サブシーケンスをarr []「Bitonic」と呼びます。 引数として配列を取り、最長のビット単位のサブシーケンスの長さを返す関数を作成します。
昇順でソートされたシーケンスは、減少部分のないバイトニックと見なされます。
同様に、降順で並べ替えられたシーケンスは、ビットが1であると見なされ、増加部分はありません。
例：
入力：arr [] = {1、11、2、10、4、5、2、1};
出力：6（最大のbitoneサブシーケンスの長さは6 {1、2、10、4、2、1}です）
入力：arr [] = {12、11、40、5、3、1}
出力：5（12、11、5、3、1）
入力：arr [] = {80、60、30、40、20、10}
出力：5（80、60、30、20、10）
- インプレース変換
文字列を指定して、すべての偶数要素を文字列の最後に移動します。 要素を移動するとき、すべての偶数要素と奇数要素の相対的な順序を、O（1）スペースとO（n）時間と同じにします。
つまり、このような[a1b2c3d4]のような交互の要素（数字と文字）を持つ文字列が与えられた場合、[abcd1234]に変換する必要があります。
翻訳行が与えられた場合、偶数位置にあるすべての要素を行の最後に移動する必要があります。 要素を移動する場合、要素の相対的な順序（偶数と奇数）を保持する必要があります。 制限は、O（1）メモリとO（n）ランタイムです。
つまり、たとえば[a1b2c3d4]のように、要素（数字と文字）が交互に並んだ文字列は[abcd1234]に変換する必要があります。
解決策
-
- 質問2
- タスク1コメントは正しい解決策を提案しました。 元のバージョン：
void ReverseRecursive(struct Node** head_ref) { struct Node* first; struct Node* rest; /* empty list */ if (*head_ref == NULL) return; /* suppose first = {1, 2, 3}, rest = {2, 3} */ first = *head_ref; rest = first->next; /* List has only one node */ if (rest == NULL) return; /* reverse the rest list and put the first element at the end */ recursiveReverse(&rest); first->next->next = first; /* tricky step -- see the diagram */ first->next = NULL; /* fix the head pointer */ *head_ref = rest; }
- タスク2ソリューションオプション：
using System; class LBS { /* lbs() returns the length of the Longest Bitonic Subsequence in arr[] of size n. The function mainly creates two temporary arrays lis[] and lds[] and returns the maximum lis[i] + lds[i] - 1. lis[i] ==> Longest Increasing subsequence ending with arr[i] lds[i] ==> Longest decreasing subsequence starting with arr[i] */ static int lbs(int[] arr, int n) { int i, j; /* Allocate memory for LIS[] and initialize LIS values as 1 for all indexes */ int[] lis = new int[n]; for (i = 0; i < n; i++) lis[i] = 1; /* Compute LIS values from left to right */ for (i = 1; i < n; i++) for (j = 0; j < i; j++) if (arr[i] > arr[j] && lis[i] < lis[j] + 1) lis[i] = lis[j] + 1; /* Allocate memory for lds and initialize LDS values for all indexes */ int[] lds = new int[n]; for (i = 0; i < n; i++) lds[i] = 1; /* Compute LDS values from right to left */ for (i = n - 2; i >= 0; i--) for (j = n - 1; j > i; j--) if (arr[i] > arr[j] && lds[i] < lds[j] + 1) lds[i] = lds[j] + 1; /* Return the maximum value of lis[i] + lds[i] - 1*/ int max = lis[0] + lds[0] - 1; for (i = 1; i < n; i++) if (lis[i] + lds[i] - 1 > max) max = lis[i] + lds[i] - 1; return max; } // Driver code public static void Main() { int[] arr = { 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15 }; int n = arr.Length; Console.WriteLine("Length of LBS is " + lbs(arr, n)); } }
- タスク3ソリューションオプション：
#include <stdio.h> #include <string.h> #include <math.h> // A utility function to swap characters void swap ( char* a, char* b ) { char t = *a; *a = *b; *b = t; } // A utility function to reverse string str[low..high] void reverse ( char* str, int low, int high ) { while ( low < high ) { swap( &str[low], &str[high] ); ++low; --high; } } // Cycle leader algorithm to move all even positioned elements // at the end. void cycleLeader ( char* str, int shift, int len ) { int j; char item; for (int i = 1; i < len; i *= 3 ) { j = i; item = str[j + shift]; do { // odd index if ( j & 1 ) j = len / 2 + j / 2; // even index else j /= 2; // keep the back-up of element at new position swap (&str[j + shift], &item); } while ( j != i ); } } // The main function to transform a string. This function mainly uses // cycleLeader() to transform void moveNumberToSecondHalf( char* str ) { int k, lenFirst; int lenRemaining = strlen( str ); int shift = 0; while ( lenRemaining ) { k = 0; // Step 1: Find the largest prefix subarray of the form 3^k + 1 while ( pow( 3, k ) + 1 <= lenRemaining ) k++; lenFirst = pow( 3, k - 1 ) + 1; lenRemaining -= lenFirst; // Step 2: Apply cycle leader algorithm for the largest subarrau cycleLeader ( str, shift, lenFirst ); // Step 4.1: Reverse the second half of first subarray reverse ( str, shift / 2, shift - 1 ); // Step 4.2: Reverse the first half of second sub-string. reverse ( str, shift, shift + lenFirst / 2 - 1 ); // Step 4.3 Reverse the second half of first sub-string and first // half of second sub-string together reverse ( str, shift / 2, shift + lenFirst / 2 - 1 ); // Increase the length of first subarray shift += lenFirst; } } // Driver program to test above function int main() { char str[] = "a1b2c3d4e5f6g7"; moveNumberToSecondHalf( str ); printf( "%s", str ); return 0; }