Clever Geek Handbook

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

Luxoftでのインタビュー中に尋ねられるいくつかの興味深い質問とアルゴリズムの問​​題を選択しました。



KDPV



Luxoftでの仕事に応募する際、技術所有者のレベルをチェックするなど、技術的な質問がよく寄せられます。 それでも、ロジックとアルゴリズムの問​​題に関連する質問があります。 以下はそれらの中で最も興味深いものです。その中で、さまざまな難易度の質問を選択しようとしました。



ご質問



  1. 3川を渡る旅行者

    3人の旅行者は川を渡る必要があります。 各旅行者は、バッグに一定量の金貨を保管しています。

    トラベラーAには1000個の金貨があります

    トラベラーBには700個の金貨があります

    トラベラーCには300枚の金貨があります



    川を渡るには、一度に最大2つのオブジェクトを運ぶことができるボートがあります。つまり、最大2人の旅行者が川を渡れるか、かばんを持った旅行者が川を渡ることができます。 問題は、川を渡るこのプロセスで、旅行者が自分のコインよりも多くのコインを残された場合、彼はそれで逃げてしまうことです。 同じルールが2人の旅行者に適用されます。合計金額以上の金貨が残っている場合、そのお金で逃げます。

    彼らがすべて適切に川を渡ることを保証する戦略は何ですか？
    翻訳
    3人の旅行者が川を渡る必要があります。 それらのそれぞれは、バックパックに一定量の金貨を持っています。

    トラベラーAには1000個のコインがあります

    トラベラーBには700枚のコインがあります

    トラベラーCには300枚のコインがあります



    川を渡るには、最大2つのオブジェクトを収容できるボートがあります。2人の旅行者またはバックパックを持った旅行者です。 問題は、旅行者が自分の金よりも多くの金を残した場合、すべてのお金を手に入れて逃げてしまうことです。 同じことは、2人の旅行者にも当てはまります。彼らが総準備金を超えて金を持ち続けるなら、彼らは金で逃げます。

    誰もが川を渡ってお金を使うことができる戦略は何ですか？



  2. ボートの重い岩

    あなたは湖で手rowぎボートに乗っています。 大きな重い岩も船の中にあります。 あなたは岩を船外に持ち上げます。 湖の底に沈みます。 湖の水位はどうなりますか？ 上昇、下降、または同じままですか？
    翻訳
    あなたは湖の真ん中で手boatぎボートに乗っています。 ボートには重い石もあります。 あなたは力で石を持ち上げて、それを船外に投げます。その結果、石は湖の底に行きます。 湖の水位はどうなりますか？ 上昇、下降、または同じままですか？





タスク



  1. 3の倍数

    数値が3の倍数であるかどうかを確認する効率的なメソッドを作成します。
    翻訳
    数値がトリプルの積であるかどうかを確認する効果的なプログラムを作成します。



  2. 馬を書く

    クインは、独自のコピーを唯一の出力として印刷するプログラムです。 クインは入力を取りません。 プログラムのファイルを使用、開いてから印刷することはできません。 クインは、アメリカの数学者および論理学者ウィラード・ヴァン・オーマン・クイン（1908–2000）にちなんで名付けられました。

    翻訳
    ソースコードを出力するプログラムであるquineを作成します。 Quineは入力を受け入れません。 ファイルを使用してその内容を表示することは許可されていません。 クヤンは、アメリカの数学者で論理学者のウィラード・ヴァン・オーマン・クイン （1908-2000）にちなんで名付けられました。



  3. 分岐なしの最小/最大

    分岐が高価な一部のまれなマシンでは、分岐を使用するため、最小値を見つけるための以下の明らかなアプローチは遅くなる可能性があります。 



    /* The obvious approach to find minimum (involves branching) */ int min(int x, int y) { return (x < y) ? x : y }


    分岐せずに最小2つの整数を見つけるプログラムを作成します。

    翻訳
    分岐が高価な一部のマシンでは、最小値を見つけるための次のアプローチは遅くなります。 



     /* The obvious approach to find minimum (involves branching) */ int min(int x, int y) { return (x < y) ? x : y }


    分岐を使用せずに最小2つの数値を見つけるプログラムを作成します。



回答は来週以内に行われます-決定する時間があります。 頑張って



解決策



  1. 質問1 
     0.（1000）（700）（300）ABC ---- 
 1.（1000）（300）AC ----（700）B
 2.（1000）（300）ABC ----（700）
 3.（1000）BC ----（700）（300）A
 4.（1000）ABC ----（700）（300）
 5.（1000）A ----（700）（300）紀元前
 6.（1000）（300）AC ----（700）B
 7.（300）C ----（700）（1000）AB
 8.（700）（300）BC ----（1000）A
 9.（700）（300）----（1000）ABC
 10.（700）（300）A ----（1000）紀元前
 11.（700）----（300）（1000）ABC
 12.（700）B ----（300）（1000）AC
 13. ----（300）（1000）（700）ABC




  2. 質問2
    水の量が減ります。 コメントで正しい答えが見つかりました。たとえば、 このコメントで説明を見つけることができます。



  3. タスク1
    数字の数字を合計し、3で割り切れるかどうかをチェックすることは、最も効果的なアプローチではありません。

    コメントで正しいパターンが提案されました。偶数ビットと奇数ビットの合計の差を3で割った場合。 ビットをカウントする古典的な例とほぼ同じように合計を考慮します。



    元のソリューション： 



     // CPP program to check if n is a multiple of 3 #include<bits/stdc++.h> using namespace std; /* Function to check if n is a multiple of 3*/ int isMultipleOf3(int n) { int odd_count = 0; int even_count = 0; /* Make no positive if +n is multiple of 3 then is -n. We are doing this to avoid stack overflow in recursion*/ if(n < 0) n = -n; if(n == 0) return 1; if(n == 1) return 0; while(n) { /* If odd bit is set then increment odd counter */ if(n & 1) odd_count++; n = n>>1; /* If even bit is set then increment even counter */ if(n & 1) even_count++; n = n>>1; } return isMultipleOf3(abs(odd_count - even_count)); } /* Program to test function isMultipleOf3 */ int main() { int num = 24; if (isMultipleOf3(num)) printf("%d is multiple of 3", num); else printf("%d is not a multiple of 3", num); return 0; }




  4. タスク2
    コメントでは、解決策が提案されました。



    C ++の元のバージョン： 

     main(a){printf(a="main(a){printf(a=%c%s%c,34,a,34);}",34,a,34);}




  5. タスク3
    コメントは、いくつかの正しい解決策を示唆しています。 ソース： 

     y ^ ((x ^ y) & -(x < y))






More articles:


All Articles