問題＃7：ITトレーニング-主要企業の現在の問題と課題

ご質問

1. 8個のビー玉
   

   8つのビー玉と2つのパンのバランスがあるとします。
   すべてのビー玉は同じように見えます。 大理石の重量はそれぞれ2.0グラムですが、1つは2.05グラムでわずかに重いです。
   バランススケールを使用してビー玉の重量を2回しか測定できない場合、どのようにして最も重いビー玉を見つけますか？
   

   
   
   翻訳

   8個のガラス玉とカップスケールがあるとします。 すべてのボールは同じように見えます。 それぞれがわずかに重いものを除いて、2グラムの重さ-2.05グラムです。
   2つの計量しか許可されていない場合、最も重いボールを見つける方法は？
   
   
   
2. 落ちてくるクマ
   

   クマが地面に10メートルの高さから√2秒で落ちました。 しかし、どういうわけか、それはけがをしませんでした。 クマの色は何ですか？

   
   
   翻訳

   熊は10mの高さから落下し、√2秒で地面に着き、何らかの理由で損傷することなく残ります。 クマは何色ですか？
   
   注：しばらく考えましたが、まだ振り返りました。 質問はちょっとしたトリックですが、答えることができます。 これがインタビューで見つかった場合、ここに持って行くことにしました。
   

タスク

1. 2つの配列の最大と最小の積
   

   整数の2つの配列が与えられた場合、タスクは最初の配列の最大要素と2番目の配列の最小要素の積を計算することです。
   
   例：
   入力：arr1 [] = {5、7、9、3、6、2}、
   arr2 [] = {1、2、6、-1、0、9}
   出力：最初の配列の最大要素
   2番目の配列の9およびmin要素
   -1です。 これら2つの積は-9です。
   
   入力：arr1 [] = {1、4、2、3、10、2}、
   arr2 [] = {4、2、6、5、2、9}
   出力：20。
   

   
   
   翻訳

   整数の2つの配列を指定します。 タスクは、最初の配列の最大要素と2番目の配列の最小要素の積を計算することです。
   
   例：
   指定：arr1 [] = {5、7、9、3、3、6、2}、arr2 [] = {1、2、6、-1、0、9}
   回答：最初の配列の最大要素は9、2番目の配列の最小要素は-1です。 製品-9。
   
   与えられた：arr1 [] = {1、4、2、3、10、2}、
   arr2 [] = {4、2、6、5、2、9}
   回答：20。
   
   
   
2. 最大チョコレート
   

   あなたはあなたと15ドルを持っています。 あなたは店に行き、店主はチョコレートごとに1ドルの価格を教えてくれます。 彼はまた、3つのラッパーの見返りにチョコレートを手に入れることができると言っています。 チョコレートは何個まで食べられますか？
   
   変数入力の解決策を見つけるプログラムを作成します。 次の3つの値が与えられた場合、タスクは、食べられるチョコレートの最大数を見つけることです。
   
   お金：チョコレートを買わなければならないお金
   価格：チョコレートの価格
   wrap：余分なチョコレートを1つ取得するために返されるラッパーの数。
   
   与えられた値はすべて正の整数であり、1より大きいと想定される場合があります。
   

   
   
   翻訳

   15ドルあります。 ストアでは、売り手からのチョコレートバーの価格がわかります-1ドル。 また、売り手は、3枚のラッパーで別のチョコレートバーが提供されると報告しています。 期待できる最大のチョコレートは何ですか？
   
   最大のチョコレートを見つけることがタスクである変数入力データ用のプログラムを作成します。
   
   お金：利用可能なお金
   価格：チョコレートバーの価格
   wrap：別のチョコレートバーを入手するのに必要なラッパーの数。
   
   すべての入力データは整数であり、1より大きいと仮定できます。
   
   
   
3. RAMより大きい配列を並べ替える
   

   それぞれが64 GBのRAMを持ち、すべての整数（8バイト）を含む2台のマシンがあるとします。 128 GBデータ全体をソートする必要があります。 少量の追加RAMを想定できます。

   
   
   翻訳

   2つのコンピューターがあり、それぞれ64 GBのRAMがあり、整数（8バイト）で占められています。 128 GBのデータすべてをソートする必要があります。 少量の追加RAMメモリを使用できます。
   
   
   

解決策

1. 質問1

   コメントで正しい答えを見つけました：
   1.ボウルごとに3つのボールを6つ取る
   2.ボウルが等しい場合、残りの2つのボール
   3.等しくない場合、最も簡単な3つを捨てる
   4.残りの3つのうち2つを計量します-問題は解決しました:)
   
   
   
2. 質問2

   オリジナルでは、クマは10m / s2の加速度で落ちたため、クマの色は白です。 正しい解決策が見つかり、いくつかの代替案が提案されました:)
   
   
   
3. タスク1

   
   アレイソートソリューションは最適ではありません。 min / maxを検索する配列の単純なパスの方が優れています：
   

   // C++ program to find the to calculate // the product of max element of first // array and min element of second array #include <bits/stdc++.h> using namespace std; // Function to calculate the product int minMaxProduct(int arr1[], int arr2[], int n1, int n2) { // Initialize max of first array int max = arr1[0]; // initialize min of second array int min = arr2[0]; int i; for (i = 1; i < n1 && i < n2; ++i) { // To find the maximum element // in first array if (arr1[i] > max) max = arr1[i]; // To find the minimum element // in second array if (arr2[i] < min) min = arr2[i]; } // Process remaining elements while (i < n1) { if (arr1[i] > max) max = arr1[i]; i++; } while (i < n2) { if (arr2[i] < min) min = arr2[i]; i++; } return max * min; } // Driven code int main() { int arr1[] = { 10, 2, 3, 6, 4, 1 }; int arr2[] = { 5, 1, 4, 2, 6, 9 }; int n1 = sizeof(arr1) / sizeof(arr1[0]); int n2 = sizeof(arr1) / sizeof(arr1[0]); cout << minMaxProduct(arr1, arr2, n1, n2) << endl; return 0; } 

   
   
   
   
4. タスク2

   この場合、再帰ソリューションは最良のソリューションではありません。 元のソリューションでは、観察により、式totalChoc =（choc-1）/（wrap-1）が導出され、この場合のプログラムは次の形式を取りました。
   

    // Efficient C++ program to find maximum // number of chocolates #include <iostream> using namespace std; // Returns maximum number of chocolates we can eat // with given money, price of chocolate and number // of wrapprices required to get a chocolate. int countMaxChoco(int money, int price, int wrap) { // Corner case if (money < price) return 0; // First find number of chocolates that // can be purchased with the given amount int choc = money / price; // Now just add number of chocolates with the // chocolates gained by wrapprices choc = choc + (choc - 1) / (wrap - 1); return choc; } // Driver code int main() { int money = 15 ; // total money int price = 1; // cost of each candy int wrap = 3 ; // no of wrappers needs to be // exchanged for one chocolate. cout << countMaxChoco(money, price, wrap); return 0; } 

   
   
   
   
5. タスク3

   この問題の解決策として、 外部マージソートが提案されています。
   
   

    // C++ program to implement external sorting using // merge sort #include <bits/stdc++.h> using namespace std; struct MinHeapNode { // The element to be stored int element; // index of the array from which the element is taken int i; }; // Prototype of a utility function to swap two min heap nodes void swap(MinHeapNode* x, MinHeapNode* y); // A class for Min Heap class MinHeap { MinHeapNode* harr; // pointer to array of elements in heap int heap_size; // size of min heap public: // Constructor: creates a min heap of given size MinHeap(MinHeapNode a[], int size); // to heapify a subtree with root at given index void MinHeapify(int); // to get index of left child of node at index i int left(int i) { return (2 * i + 1); } // to get index of right child of node at index i int right(int i) { return (2 * i + 2); } // to get the root MinHeapNode getMin() { return harr[0]; } // to replace root with new node x and heapify() // new root void replaceMin(MinHeapNode x) { harr[0] = x; MinHeapify(0); } }; // Constructor: Builds a heap from a given array a[] // of given size MinHeap::MinHeap(MinHeapNode a[], int size) { heap_size = size; harr = a; // store address of array int i = (heap_size - 1) / 2; while (i >= 0) { MinHeapify(i); i--; } } // A recursive method to heapify a subtree with root // at given index. This method assumes that the // subtrees are already heapified void MinHeap::MinHeapify(int i) { int l = left(i); int r = right(i); int smallest = i; if (l < heap_size && harr[l].element < harr[i].element) smallest = l; if (r < heap_size && harr[r].element < harr[smallest].element) smallest = r; if (smallest != i) { swap(&harr[i], &harr[smallest]); MinHeapify(smallest); } } // A utility function to swap two elements void swap(MinHeapNode* x, MinHeapNode* y) { MinHeapNode temp = *x; *x = *y; *y = temp; } // Merges two subarrays of arr[]. // First subarray is arr[l..m] // Second subarray is arr[m+1..r] void merge(int arr[], int l, int m, int r) { int i, j, k; int n1 = m - l + 1; int n2 = r - m; /* create temp arrays */ int L[n1], R[n2]; /* Copy data to temp arrays L[] and R[] */ for(i = 0; i < n1; i++) L[i] = arr[l + i]; for(j = 0; j < n2; j++) R[j] = arr[m + 1 + j]; /* Merge the temp arrays back into arr[l..r]*/ i = 0; // Initial index of first subarray j = 0; // Initial index of second subarray k = l; // Initial index of merged subarray while (i < n1 && j < n2) { if (L[i] <= R[j]) arr[k++] = L[i++]; else arr[k++] = R[j++]; } /* Copy the remaining elements of L[], if there are any */ while (i < n1) arr[k++] = L[i++]; /* Copy the remaining elements of R[], if there are any */ while(j < n2) arr[k++] = R[j++]; } /* l is for left index and r is right index of the sub-array of arr to be sorted */ void mergeSort(int arr[], int l, int r) { if (l < r) { // Same as (l+r)/2, but avoids overflow for // large l and h int m = l + (r - l) / 2; // Sort first and second halves mergeSort(arr, l, m); mergeSort(arr, m + 1, r); merge(arr, l, m, r); } } FILE* openFile(char* fileName, char* mode) { FILE* fp = fopen(fileName, mode); if (fp == NULL) { perror("Error while opening the file.\n"); exit(EXIT_FAILURE); } return fp; } // Merges k sorted files. Names of files are assumed // to be 1, 2, 3, ... k void mergeFiles(char *output_file, int n, int k) { FILE* in[k]; for (int i = 0; i < k; i++) { char fileName[2]; // convert i to string snprintf(fileName, sizeof(fileName), "%d", i); // Open output files in read mode. in[i] = openFile(fileName, "r"); } // FINAL OUTPUT FILE FILE *out = openFile(output_file, "w"); // Create a min heap with k heap nodes. Every heap node // has first element of scratch output file MinHeapNode* harr = new MinHeapNode[k]; int i; for (i = 0; i < k; i++) { // break if no output file is empty and // index i will be no. of input files if (fscanf(in[i], "%d ", &harr[i].element) != 1) break; harr[i].i = i; // Index of scratch output file } MinHeap hp(harr, i); // Create the heap int count = 0; // Now one by one get the minimum element from min // heap and replace it with next element. // run till all filled input files reach EOF while (count != i) { // Get the minimum element and store it in output file MinHeapNode root = hp.getMin(); fprintf(out, "%d ", root.element); // Find the next element that will replace current // root of heap. The next element belongs to same // input file as the current min element. if (fscanf(in[root.i], "%d ", &root.element) != 1 ) { root.element = INT_MAX; count++; } // Replace root with next element of input file hp.replaceMin(root); } // close input and output files for (int i = 0; i < k; i++) fclose(in[i]); fclose(out); } // Using a merge-sort algorithm, create the initial runs // and divide them evenly among the output files void createInitialRuns(char *input_file, int run_size, int num_ways) { // For big input file FILE *in = openFile(input_file, "r"); // output scratch files FILE* out[num_ways]; char fileName[2]; for (int i = 0; i < num_ways; i++) { // convert i to string snprintf(fileName, sizeof(fileName), "%d", i); // Open output files in write mode. out[i] = openFile(fileName, "w"); } // allocate a dynamic array large enough // to accommodate runs of size run_size int* arr = (int*)malloc(run_size * sizeof(int)); bool more_input = true; int next_output_file = 0; int i; while (more_input) { // write run_size elements into arr from input file for (i = 0; i < run_size; i++) { if (fscanf(in, "%d ", &arr[i]) != 1) { more_input = false; break; } } // sort array using merge sort mergeSort(arr, 0, i - 1); // write the records to the appropriate scratch output file // can't assume that the loop runs to run_size // since the last run's length may be less than run_size for (int j = 0; j < i; j++) fprintf(out[next_output_file], "%d ", arr[j]); next_output_file++; } // close input and output files for (int i = 0; i < num_ways; i++) fclose(out[i]); fclose(in); } // For sorting data stored on disk void externalSort(char* input_file, char *output_file, int num_ways, int run_size) { // read the input file, create the initial runs, // and assign the runs to the scratch output files createInitialRuns(input_file, run_size, num_ways); // Merge the runs using the K-way merging mergeFiles(output_file, run_size, num_ways); } // Driver program to test above int main() { // No. of Partitions of input file. int num_ways = 10; // The size of each partition int run_size = 1000; char input_file[] = "input.txt"; char output_file[] = "output.txt"; FILE* in = openFile(input_file, "w"); srand(time(NULL)); // generate input for (int i = 0; i < num_ways * run_size; i++) fprintf(in, "%d ", rand()); fclose(in); externalSort(input_file, output_file, num_ways, run_size); return 0; }