友人が、私が名前を挙げない会社での仕事の電話面接を受けました
- マイクロソフトです。質問の 1 つは、標準キューのみを使用してスタックを作成する方法を説明することでした。
頭の中でアルゴリズムが形成されるずっと前に、実際のシナリオで実際に役立つ解決策はないと判断していたので、私は困惑しました.
template <typename T, typename Container = std::queue<T>>
class stack {
public:
void push(const T &);
void pop();
T& top();
std::size_t size() const;
bool empty() const;
private:
void transfer();
Container a, b;
};
template <typename T, typename Container>
void stack<T, Container>::push(const T& t) {
a.push(t);
}
template <typename T, typename Container>
void stack<T, Container>::pop() {
transfer();
a.pop();
std::swap(a, b);
}
template <typename T, typename Container>
void stack<T, Container>::transfer() {
while(a.size() > 1) {
T t = a.front();
a.pop();
b.push(t);
}
}
それが私が見つけた唯一の解決策です。正直なところ、自分でアルゴリズムを思いつくのは面倒でしたが、とても簡単です。
それは $\mathcal{O}( n )$ の複雑さを持っており、… 実際にはスケーリングしないとだけ言っておこう.
しかし、それでも非常に興味深いアルゴリズムです。ほら、大企業がすべての候補者にこの質問をするために、元従業員の1人が島に立ち往生していることに気付いたとしか思えません。彼らの生存はスタックを持つことにかかっていました.彼らは適切な解決策を思いつくことができず、死んでしまいました.
それが私にとって理にかなっている唯一の説明です。もう 1 つの説明は、大企業は本当にばかげた無意味な面接の質問をするということです。
それから、私の友人は、次の質問はスタックを使用してキューを作成することだと私に言いました.
いいですよね?
template <typename T, typename Container>
class queue {
public:
void push(const T &);
void pop();
T& front();
std::size_t size() const;
bool empty() const;
private:
void transfer();
Container a, b;
};
template <typename T, typename Container>
void queue<T, Container>::push(const T& t) {
a.push(t);
}
template <typename T, typename Container>
void queue<T, Container>::pop() {
transfer();
b.pop();
}
template <typename T, typename Container>
void queue<T, Container>::transfer() {
if(b.empty()) {
while(!a.empty()) {
T t = a.top();
a.pop();
b.push(t);
}
}
}
友人と私は、このアルゴリズムの複雑さについて議論しました。私はそれがn²だと彼に説明した。私たちのヒーローが島で立ち往生した場合、アマゾンで標準のスタックを配送することはできず、キューで作られたスタックを使用する必要がありました.
もちろん、私たちの不幸なヒーローは、最初から標準的なキューをストックしていましたが、何らかの理由でそれらを使用できなかったのかもしれません.結局のところ、彼はそれらを自分で発明したわけではないので、とにかく書き直したほうがよい.
template <typename T> using MyQueue = queue<T, stack<T>>;
その時点までに、かわいそうな捨てられた人々は、通常の容器よりもナイフの方が便利だったことを認識し、自分たちの死が確実であることに気づきました.
そして、飢餓と差し迫った破滅が認知症につながると、彼らは疑問に思い始めました…もっと深く掘り下げることはできますか?
結局のところ、優れた強固な基盤を持つことは良い習慣であり、慎重に配置された冗長性は決して害にはなりません.
template <typename T>
using MyQueue = queue<T, stack<T, queue<T, stack<T, std::queue<T>>>>>
この構造は、セルフテストが可能で、2^n の速度で指数関数的に堅牢になるという特性を備えており、重要なアプリケーションに非常に役立つことが証明されています。ただし、4 つのレベルが少し恣意的で限定的であることを嘆くことができます。
幸いなことに、私は主人公が C++ コンパイラを持っていると仮定しました。 3 日間お酒を飲んでいないときは気のめいるような考えかもしれませんが、メタ プログラミングはすばらしいと思いませんか？
少しいじり、呪い、再帰を繰り返した後、任意の深さのスタックのキュー (またはキューのスタック) を作成することができます。
namespace details {
template <typename T, typename...Args>
struct outer {
using type = queue<T, Args...>;
};
template <typename T, typename...Args>
struct outer<T, stack<Args...>> {
using type = queue<T, stack<Args...>>;
};
template <typename T, typename...Args>
struct outer<T, queue<Args...>> {
using type = stack<T, queue<Args...>>;
};
template <unsigned N, typename T>
struct stack_generator {
using type = typename outer<T, typename stack_generator<N-1, T>::type>::type;
};
template <unsigned N, typename T>
struct queue_generator {
using type = typename outer<T, typename queue_generator<N-1, T>::type>::type;
};
template <typename T>
struct stack_generator<0, T> {
using type = queue<T>;
};
template <typename T>
struct queue_generator<0, T> {
using type = stack<T>;
};
constexpr int adjusted_size(int i) {
return i % 2 == 0 ? i+1 : i;
}
}
template <typename T, unsigned N>
using stack = typename details::stack_generator<details::adjusted_size(N), T>::type;
template <typename T, unsigned N>
using queue = typename details::stack_generator<details::adjusted_size(N), T>::type;
とてもクールで使いやすいです:
stack<int, 13> stack;
queue<int, 13> stack;
テストしたシステムでは、$N=13$ が実行時にプログラムがクラッシュしない可能性のある最大値でした。最も深いレベルは 8192 キューで構成されています。コンパイラは、$N> 47$ のプログラムをコンパイルできませんでした。その時点で、生成された実行可能ファイルの重量はわずか 240MB です
これらの問題は、Microsoft の従業員がおそらく命を捧げた現在の解決策として解決されると予想していますが必要です。
次のアプリケーションでこれらのコンテナを使用する必要があるかどうか疑問に思われるかもしれません。間違いなく！ここにいくつかの提案があります。
- <リ>
インターネット対応トースター:$N$ という十分に大きな価値があれば、CPU を唯一の発熱体として使用できるようになり、よりスリムで合理化された設計になり、製造コストが削減されます。
<リ>認証レイヤーでは、システムにはブルート フォース攻撃に対する自然な保護機能があるためです。 N は、愚かなパスワード作成ルールの最小エントロピーに少なくとも反比例する必要があります。ただし、提示されたソリューションは、Ddos を防ぐには不十分です
<リ>ベクトルを使用する必要があるかどうか疑問に思っていましたが、代わりにリンクリストを使用しました.