新年の最初の選択には、アルカテル-ルーセント（ノキア）からの質問とタスクが含まれます。
難易度の異なるタスクをピックアップしようとしました。 いくつかの（そしておそらくすべての）質問はインターネットで回答できますが、これは私たちのやり方ではありませんよね？
私たちは知的にストレッチを提供し、上記の問題を独立して解決しようとします。
ご質問
- 体外細菌
レトルト内でバクテリアが増加するという論理的なタスク。 1個のバクテリアが1分間でそれを満たしますが、開始時に4個のバクテリアが存在する場合、レトルトを満たすのにどれくらい時間がかかりますか？ 各バクテリアは毎秒2つの同じサイズのバクテリアに分かれます。
翻訳論理的なタスク-分割ごとに1つの細菌が1分でチューブを満たします。 4つのバクテリアが開始された場合、チューブを満たすのにどれくらい時間がかかりますか？ 各細菌は、毎秒同じサイズの2つの細菌に分けられます。
- 25頭の馬
あなたは25頭の馬を持っています。トップ3を見つけることができるレースの最小数は何ですか。1つのレースでは5頭の馬をレースでき、タイマーはありません。
翻訳25頭の馬の中で上位3人の勝者を特定できる最小のレース数を決定する必要があります。 1レースで最大5頭の馬が許可されますが、ストップウォッチは提供されません。
タスク
- サブセットを含む行を作成する
2つの文字列s1とs2が指定されています。 サブストリングの1つとしてs1とs2の両方を持ち、s3の長さが最小になるように、新しいストリングs3を作成しました。
例：apple pear => applear
翻訳2つの行s1およびs2から、s1およびs2をサブセットとして含む新しい行s3を収集します。 s3は最小長でなければなりません。
例：apple pear => applear
- 数字の辞書ソート
整数を文字列に変換せずにどのように辞書ソートしますか？
例：1 2 10 20 100 110 => 1 10 100 110 2 20
翻訳整数を文字列にキャストせずに、辞書順に並べるにはどうしますか？
例：1 2 10 20 100 110 => 1 10 100 110 2 20。
- 配列内の余分な要素を見つける
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多くの解説者が正解-58秒。 論理的な方法で答えを出すことは可能でしたが、誰かが対数的に決定しました:)
- 質問2多くの人が適切なソリューションを見つけました。 答えは7回です。
馬に番号を付けましょう。 最初の5つのレース：
1. 1 2 345
2. 6 7 8910
3.11 12 131415
4. 16 17 181920
5.2122.23.24.25
10頭の馬は、上位3位に入らなかったため引退しました。
第6レースでは、絶対的なリーダーを明らかにします。
6. 1 6 111621
現在、図は次のとおりです。
1 2 345
6 78910
1112131415
1617181920
2122232425
別の10頭の馬-リーダーが4と5に来たすべての競走馬、賞品の資格がないため、すべての競走馬、3番目のグループの馬（リーダーが3位で4+を数えることができるため）、および2番目のグループの3番目の馬、絶対的なリーダーとして1位になった馬だけでなく、4 +以上の場所にしか依存できないためです。
第7レースでは、最強の最初のペアを明らかにします-彼らはトップ3の場所のプライドを取るでしょう：
7.2 36711
すべての強い馬が同じグループに属している場合のケースを調べましたが、全体像の再編成は変わりません。
- タスク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); } }
- タスク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)); } }
- タスク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; }