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

ご質問

1. 体外細菌
   

   レトルト内でバクテリアが増加するという論理的なタスク。 1個のバクテリアが1分間でそれを満たしますが、開始時に4個のバクテリアが存在する場合、レトルトを満たすのにどれくらい時間がかかりますか？ 各バクテリアは毎秒2つの同じサイズのバクテリアに分かれます。

   
   
   翻訳

   論理的なタスク-分割ごとに1つの細菌が1分でチューブを満たします。 4つのバクテリアが開始された場合、チューブを満たすのにどれくらい時間がかかりますか？ 各細菌は、毎秒同じサイズの2つの細菌に分けられます。
   
2. 25頭の馬
   

   あなたは25頭の馬を持っています。トップ3を見つけることができるレースの最小数は何ですか。1つのレースでは5頭の馬をレースでき、タイマーはありません。
   

   
   
   翻訳

   25頭の馬の中で上位3人の勝者を特定できる最小のレース数を決定する必要があります。 1レースで最大5頭の馬が許可されますが、ストップウォッチは提供されません。
   

タスク

1. サブセットを含む行を作成する
   

   2つの文字列s1とs2が指定されています。 サブストリングの1つとしてs1とs2の両方を持ち、s3の長さが最小になるように、新しいストリングs3を作成しました。
   
   例：apple pear => applear
   

   
   
   翻訳

   2つの行s1およびs2から、s1およびs2をサブセットとして含む新しい行s3を収集します。 s3は最小長でなければなりません。
   例：apple pear => applear
   
2. 数字の辞書ソート
   

   整数を文字列に変換せずにどのように辞書ソートしますか？
   例：1 2 10 20 100 110 => 1 10 100 110 2 20

   
   
   翻訳

   整数を文字列にキャストせずに、辞書順に並べるにはどうしますか？
   例：1 2 10 20 100 110 => 1 10 100 110 2 20。
   
3. 配列内の余分な要素を見つける
   

   2つの整数配列AとBが与えられた場合
   Bには、2つの追加の数字を除いて、Aとまったく同じ数字が含まれています。 最小限の時間と空間の複雑さで2つの要素を見つけます。
   例：A = {1、4、2、6、3}
   B = {4、0.7、6、3、2、1}
   ans：0 7

   
   
   翻訳

   配列AとBの配列が与えられ、配列Bには、A + 2個以上のすべての数値が含まれます。 速度とメモリサイズが最適なこれら2つの数値を見つけるためのアルゴリズムを提案する。
   例：
   A = {1、4、2、6、3}
   B = {4、0.7、6、3、2、1}
   結果：0 7
   

解決策

1. 質問1

   多くの解説者が正解-58秒。 論理的な方法で答えを出すことは可能でしたが、誰かが対数的に決定しました:)
   
   
   
2. 質問2

   多くの人が適切なソリューションを見つけました。 答えは7回です。
   
   馬に番号を付けましょう。 最初の5つのレース：
   1. 1 2 3 4 5
   2. 6 7 8 9 10
   3.11 12 13 14 15
   4. 16 17 18 19 20
   5.2122.23.24.25
   10頭の馬は、上位3位に入らなかったため引退しました。
   
   第6レースでは、絶対的なリーダーを明らかにします。
   6. 1 6 11 16 21
   
   現在、図は次のとおりです。
   1 2 3 4 5
   6 7 8 9 10
   11 12 13 14 15
   16 17 18 19 20
   21 22 23 24 25
   
   別の10頭の馬-リーダーが4と5に来たすべての競走馬、賞品の資格がないため、すべての競走馬、3番目のグループの馬（リーダーが3位で4+を数えることができるため）、および2番目のグループの3番目の馬、絶対的なリーダーとして1位になった馬だけでなく、4 +以上の場所にしか依存できないためです。
   
   第7レースでは、最強の最初のペアを明らかにします-彼らはトップ3の場所のプライドを取るでしょう：
   
   7.2 3 6 7 11
   
   すべての強い馬が同じグループに属している場合のケースを調べましたが、全体像の再編成は変わりません。
   
   
   
3. タスク1

   元のJavaサブシーケンスソリューション：
   

   public class GFG_1 { String a , b; // Prints super sequence of a[0..m-1] and b[0..n-1] static void printSuperSeq(String a, String b) { int m = a.length(), n = b.length(); int[][] dp = new int[m+1][n+1]; // Fill table in bottom up manner for (int i = 0; i <= m; i++) { for (int j = 0; j <= n; j++) { // Below steps follow above recurrence if (i == 0) dp[i][j] = j; else if (j == 0 ) dp[i][j] = i; else if (a.charAt(i-1) == b.charAt(j-1)) dp[i][j] = 1 + dp[i-1][j-1]; else dp[i][j] = 1 + Math.min(dp[i-1][j], dp[i][j-1]); } } // Create a string of size index+1 to store the result String res = ""; // Start from the right-most-bottom-most corner and // one by one store characters in res[] int i = m, j = n; while (i > 0 && j > 0) { // If current character in a[] and b are same, // then current character is part of LCS if (a.charAt(i-1) == b.charAt(j-1)) { // Put current character in result res = a.charAt(i-1) + res; // reduce values of i, j and indexs i--; j--; } // If not same, then find the larger of two and // go in the direction of larger value else if (dp[i-1][j] < dp[i][j-1]) { res = a.charAt(i-1) + res; i--; } else { res = b.charAt(j-1) + res; j--; } } // Copy remaining characters of string 'a' while (i > 0) { res = a.charAt(i-1) + res; i--; } // Copy remaining characters of string 'b' while (j > 0) { res = b.charAt(j-1) + res; j--; } // Print the result System.out.println(res); } /* Driver program to test above function */ public static void main(String args[]) { String a = "apple"; String b = "pear"; printSuperSeq(a, b); } } 

   
   
   
   
4. タスク2

   最初の解決策は、コンパレータを作成し、商の数と除算の残りの数を比較することでした。
   

    Algorithm: Compare quotients and reminders import java.util.Arrays; import java.util.Comparator; public class DictionarySort { public static void main(String[] args) { Integer[] array = new Integer[] { 1, 2, 10, 20, 100, 110 }; Arrays.sort(array, new Comparator<Integer>() { @Override public int compare(Integer o1, Integer o2) { // TODO Auto-generated method stub int quotient1 = o1 / 10; int reminder1 = o1 % 10; int quotient2 = o2 / 10; int reminder2 = o2 % 10; if (quotient1 != 0 && quotient2 != 0) { if (quotient1 == quotient2) return 0; int msd1 = 0; int msd2 = 0; if (quotient1 >= 10) msd1 = quotient1 / 10; else msd1 = quotient1; if (quotient2 >= 10) msd2 = quotient2 / 10; else msd2 = quotient2; if (msd1 == msd2) return quotient1 - quotient2; if (msd1 != msd2) return msd1 - msd2; } if (quotient1 == 0 && quotient2 == 0) return reminder1 - reminder2; if (quotient2 != 0 && quotient1 == 0) { while (quotient2 >= 10) quotient2 /= 10; return reminder1 - quotient2; } if (quotient1 != 0 && quotient2 == 0) { while (quotient1 >= 10) quotient1 /= 10; return quotient1 - reminder2; } return 1; } }); System.out.println(Arrays.toString(array)); } } 

   
   
   
   
5. タスク3

   元のソリューション：
   
   

    public int[] findTwo(int[] a, int[] b) { int sumA = 0, squareSumA = 0; for (int i = 0; i < a.length; i++) { sumA += a[i]; squareSumA += a[i] * a[i]; } int sumB = 0, squareSumB = 0; for (int i = 0; i < b.length; i++) { sumB += b[i]; squareSumB += b[i] * b[i]; } int twosum = sumB - sumA; int squareSum = squareSumB - squareSumA; int param1 = 2; int param2 = 2 * twosum; int param3 = twosum * twosum - squareSum; int[] res = new int[2]; int sqrtdiff = (int) Math.sqrt(param2 * param2 - 4 * param1 * param3); res[0] = (param2 - sqrtdiff) / (2 * param1); res[1] = (param2 + sqrtdiff) / (2 * param1); return res; }