今週、DELLの開発エンジニアとして、面接中に求職者が遭遇する質問とタスクを選択しました。
オペレーティングシステムの構造とハードウェアの操作の複雑さ（一部は非常に複雑）に関する予想される質問に加えて、DELLのインタビューでは、ロジックに関するタスクとアルゴリズムの使用能力を聞くことができます。 ここでそれらのいくつかを紹介します-通常の複雑さは、単純なものから複雑なものまでさまざまです。
ご質問
- アイスバケットチャレンジ
目の前には容量8、5、3リットルのバケツが3つあります。 容量8のバケットには氷水が完全に満たされています。 上記の3つのバケットを使用して、8リットルをそれぞれ4リットルの2つの部分に分ける必要があります。
翻訳容量が8、5、および3リットルの3つのバケットになる前。 8リットルのバケツ 冷水で完全に満たされています。 8リットルを2サービングの4リットルに分ける必要があります。 これら3つのバケットを使用します。
- トーチとブリッジ
夜に橋を渡りたい4人（A、B、C、D）がいます。
Aが橋を渡るのに1分かかります。
Bは橋を渡るのに2分かかります。
Cは橋を渡るのに5分かかります。
Dは橋を渡るのに8分かかります。
トーチは1つしかなく、トーチなしでは橋を渡ることはできません。 いつでも2人以上が橋の上にいることはできず、2人が一緒に橋を渡るときは、遅い人のペースで移動する必要があります
彼らは全員15分で橋を渡ることができますか？
翻訳4人（A、B、C、D）が夜に橋を渡りたい。
そして、橋を渡るのに1分かかります。
Bには2分かかります。
Cには5分かかります。
Dには8分かかります。
ランタンは1つしかないので、それなしでは橋を渡ることはできません。 また、橋の上には2人しか入ることができず、2人が橋に沿って歩いているとき、最も遅い歩行者の速度で歩いています。
彼らは15分で渡ることができますか？
タスク
- 0、1、2xの配列を並べ替える
0、1、2で構成される配列A []が与えられた場合、A []をソートする関数を記述します。 関数は、最初にすべて0を配置し、次にすべて1と2を最後に配置する必要があります。
例：
入力：{0、1、2、0、1、2}
出力：{0、0、1、1、2、2}
入力：{0、1、1、0、1、2、1、2、0、0、0、0、1}
出力：{0、0、0、0、0、1、1、1、1、1、1、1、2、2}
翻訳0、1、および2で構成される配列A []が与えられた場合、A []をソートする関数を記述します。 関数は最初に0、次に1、最後に2を持たなければなりません。
例：
入力：{0、1、2、0、1、2}
出力：{0、0、1、1、2、2}
入力：{0、1、1、0、1、2、1、2、0、0、0、1}
出力：{0、0、0、0、0、1、1、1、1、1、1、1、2、2}
- 固定スペースを使用して、ストリームから乱数を選択します
乱数を生成するジェネレーターがあるとします。 O（1）スペースのみを使用でき、入力はストリームの形式であるため、以前に表示された数値を保存できません。
それでは、どのような数字を選ぶ確率が1 / nになるように、ストリーム全体から乱数を選択するのでしょうか。 O（1）余分なスペースがある？
翻訳ダン乱数ジェネレーター。 O（1）メモリのみが許可され、入力データはストリームとして提示されるため、以前の数値を保存する方法はありません。
タスクは、O（1）追加メモリのみを使用して、着信ストリームから乱数を選択し、1 / nの確率を提供することです。
- 選択した数の合計を最大化する
N個の数字の配列が与えられた場合、選択した数字の合計を最大化する必要があります。 各ステップで、番号A iを選択し、配列からA i -1（存在する場合）、A i +1（存在する場合）、およびA iを 1つずつ削除する必要があります。 配列が空になるまでこれらの手順を繰り返します。 問題は、選択した数値の合計を最大化することです。
注：A i +1およびA i -1要素が配列に存在し、A i + 1およびA i-1ではない場合、それらを削除する必要があります。
例：
入力：[] = {1、2、3}
出力：4
説明：最初のステップで1を選択します。そのため、シーケンスから1と2が削除され、3が残ります。
次に、シーケンスから3を選択して削除します。 したがって、選択した数値の合計は1 + 3 = 4です。
入力：a [] = {1、2、2、2、3、4}
出力：10
説明：配列から2のいずれかを選択すると、2、2-1、2 + 1が削除され、1と3が削除されるため、{2、2、4}が残ります。 次の2つのステップで2を選択し、最後のステップで4を選択します。 可能な最大値である2 + 2 + 2 + 4 = 10の合計を取得します。
翻訳N個の数値の配列が与えられた場合、最大量の要素を選択する必要があります。 要素（A i ）を選択するたびに、要素の出現を1つ減らし、要素の出現をもう1つ（A i -1）および（A i +1）あれば削除し、要素自体を削除する必要があります。 これらの手順は、配列が空になるまで繰り返されます。 タスクは、選択されたアイテムの最大量を提供することです。
位置A i-1およびA i + 1ではなく、値A i +1およびA i -1の要素を削除する必要があります。
例：
入力：[] = {1、2、3}
出力：4
説明：最初のステップで1を選択します。したがって、アレイから1と2が削除されます。 次のステップでは、残りの3を使用します。選択した要素の合計1 + 3 = 4。
入力：a [] = {1、2、2、2、3、4}
出力：10
説明：配列から2を1つ選択します-1および3が削除され（それぞれ2-1および2 + 1）、{2、2、4}が残ります。 次の2つのステップで、残りの2つを選択し、最後のステップとして4を選択します合計金額は2 + 2 + 2 + 4 = 10で、最大値です。
回答は来週以内に行われます-決定する時間があります。 頑張って
解決策
質問1コメントで正しい解決策が提案されています：
8-> 5（3、5、0）
5-> 3（3、2、3）
3-> 8（6、2、0）
5-> 3（6、0、2）
8-> 5（1、5、2）
5-> 3（1、4、3）
3-> 8（4、4、0）
タスク1彼らは正しい解決策を提案しました-カウントによるソート。 コードは、たとえば次の
ようになります 。
タスク2決定アルゴリズムは、
解説で正しく説明されました。 コードは次のようになります。
// An efficient C program to randomly select a number from stream of numbers.
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
// A function to randomly select a item from stream[0], stream[1], .. stream[i-1]
int selectRandom(int x)
{
static int res; // The resultant random number
static int count = 0; //Count of numbers visited so far in stream
count++; // increment count of numbers seen so far
// If this is the first element from stream, return it
if (count == 1)
res = x;
else
{
// Generate a random number from 0 to count - 1
int i = rand() % count;
// Replace the prev random number with new number with 1/count probability
if (i == count - 1)
res = x;
}
return res;
}
// Driver program to test above function.
int main()
{
int stream[] = {1, 2, 3, 4};
int n = sizeof(stream)/sizeof(stream[0]);
// Use a different seed value for every run.
srand(time(NULL));
for (int i = 0; i < n; ++i)
printf("Random number from first %d numbers is %d \n",
i+1, selectRandom(stream[i]));
return 0;
}
タスク3たとえば、正しい解決策が
ここに提案され
ました 。 コード：
// CPP program to Maximize the sum of selected
// numbers by deleting three consecutive numbers.
#include <bits/stdc++.h>
using namespace std;
// function to maximize the sum of selected numbers
int maximizeSum(int a[], int n) {
// stores the occurrences of the numbers
unordered_map<int, int> ans;
// marks the occurrence of every number in the sequence
for (int i = 0; i < n; i++)
ans[a[i]]++;
// maximum in the sequence
int maximum = *max_element(a, a + n);
// traverse till maximum and apply the recurrence relation
for (int i = 2; i <= maximum; i++)
ans[i] = max(ans[i - 1], ans[i - 2] + ans[i] * i);
// return the ans stored in the index of maximum
return ans[maximum];
}
// Driver code
int main()
{
int a[] = {1, 2, 3};
int n = sizeof(a) / sizeof(a[0]);
cout << maximizeSum(a, n);
return 0;
}