私は最近インタビューを受けましたが、そこで失敗し、最終的に彼らのために働くのに十分な経験がないと言われました。
位置は組み込みCソフトウェア開発者でした。ターゲットプラットフォームは、ある種の非常に単純な32ビットアーキテクチャであり、これらのプロセッサは浮動小数点数とその操作をサポートしていません。したがって、倍精度数と浮動小数点数は使用できません。
タスクは、このアーキテクチャ用のCルーチンを開発することでした。この1つの整数を取り、それがフィボナッチ数であるかどうかを返します。ただし、メモリから追加の1K一時スペースのみを使用できます。 実行中。つまり、たとえ非常に大きな整数をシミュレートしたとしても、シーケンスを構築してやり直すことはできません。
私の知る限り、正の整数はフィボナッチ数です。
(5n ^ 2) + 4
または
(5n ^ 2) − 4
完璧な正方形です。したがって、私は質問に答えました。それは簡単です。ルーチンがそうであるかどうかを判断する必要があるからです。
その後、彼らは応答しました：現在のターゲットアーキテクチャでは、浮動小数点のような操作はサポートされていません。したがって、stdlibの
sqrt
を使用して平方根番号を取得することはできません。関数。また、アーキテクチャの制限により、除算やモジュラスなどの基本操作も機能しない可能性があることも言及されました。
次に、私は言った、大丈夫、私たちは256までの正方形の数で配列を構築することができます。それから、私たちは繰り返して、式で与えられた数と比較することができます（上記参照）。彼らは言った：これはうまくいくとしても、これは悪いアプローチです。したがって、彼らはその答えを受け入れませんでした。
最後に私はあきらめました。他にアイデアがなかったので。解決策は何だろうと私は尋ねました。しかし、自分で探してみることを勧めました。私の最初のアプローチ（2つの式）が重要ですが、平方根を代わりに行うこともできます。
私は家で何度もグーグルで検索しましたが、「代替」平方根カウンターアルゴリズムは見つかりませんでした。どこでも浮動小数点数の使用が許可されました。
除算やモジュラスなどの操作では、いわゆる「整数除算」を使用できます。しかし、平方根に使用されるものは何ですか？
インタビューテストに失敗した場合でも、浮動小数点演算が許可されていないアーキテクチャで作業することは、私にとって非常に興味深いトピックです。
したがって、私の質問：
- 浮動小数点数はどのようにシミュレートできますか（整数のみが使用できる場合）？
- 上記の問題に対してCで考えられるsoultionは何でしょうか？コード例は大歓迎です。
プログラミングポジションのインタビュアーがフィボナッチ数列の特定のプロパティの知識をテストすることはほとんどありません。したがって、テスト対象のプロパティを提示しない限り、この種の問題に対する候補者のアプローチとアルゴリズムの一般的な知識を調査しています。特に、正方形のテーブルを反復処理するという考え方は、いくつかの面で反応が悪いです。
少なくとも、テーブル検索の最初の考えはバイナリ検索です。また、find-first-set-bit命令を使用してテーブルにインデックスを付けるなど、いくつかの計算されたルックアップアプローチを提案することもできます。
特に効率的なカスタマイズされたハッシュが構築される可能性があるため、ハッシュは検討する価値のある別のアイデアかもしれません。
テーブルを使用することに決めたら、フィボナッチ数の直接テーブルの方が、正方形のテーブルよりも便利です。
このタイプのインタビューのポイントは、新しい問題にどのようにアプローチするかを確認することです。すでに答えを知っている場合、それは間違いなくあなたの信用にありますが、それは実際に質問に答えていません。インタビュアーにとって興味深いのは、問題に取り組むことです。
このため、インタビュアーが追加の制約を追加して、あなたを快適ゾーンから連れ出し、あなたがどのように対処するかを見ようとするのが一般的です。
フィボナッチ数を認識することについてその事実を知っていたことは素晴らしいと思います。ウィキペディアに相談しなければ知りませんでした。興味深い事実ですが、実際には問題の解決に役立ちますか？
どうやら、
5n²±4を計算する必要があります 、平方根を計算し、それらの1つが整数であることを確認します。十分な精度で浮動小数点実装にアクセスできれば、これはそれほど複雑ではありません。しかし、それはどのくらいの精度ですか？nの場合 任意の32ビットの符号付き数値を指定でき、その後n²明らかに32ビットに収まりません。実際、5n²+4符号ビットを含まない65ビットの大きさになる可能性があります。それはdoubleの精度をはるかに超えています （通常52ビット）、さらにはlong doubleの 、 可能な場合は。そのため、正確な平方根の計算には問題があります。もちろん、正確な計算は実際には必要ありません。近似から始めて、それを二乗し、それが
5n²よりも4つ多いか4つ少ないかを確認できます。 。そして、良い推測を計算する方法を見るのは簡単です：n×√5に非常に近いでしょう 。√5の事前計算済みの近似値を使用する 、浮動小数点、除算、およびsqrt関数なしで、この計算を簡単に実行できます。 （近似が正確でない場合、結果を上下に調整する必要があるかもしれませんが、それはアイデンティティ(n+1)² = n²+2n+1を使用して簡単に行うことができます ;n²ができたら 、(n+1)²を計算できます 追加のみ。精度の問題を解決する必要があるため、66ビット整数を処理する何らかの方法が必要になります。しかし、正の整数の加算と乗算を実装するだけで、本格的なbignumパッケージよりもかなり簡単です。実際、平方根の推定値が十分に近いことを証明できれば、2³¹を法とする検証を安全に行うことができます。
そのため、分析ソリューションを機能させることができますが、それに飛び込む前に、それが最良のソリューションであるかどうかを確認する必要があります。準最適プログラミングの非常に一般的な注意事項の1つは、その複雑さがますます明らかになったとしても、最初に思いついたアイデアに必死にしがみついていることです。これは、面接担当者があなたについて知りたいことの1つです。新しい情報や新しい要件が提示されたとき、あなたはどの程度柔軟になりますか。
nかどうかを知るために他にどのような方法がありますか フィボナッチ数です。興味深い事実の1つは、nはFib(k)です 、次にklogφ(k×√5 + 0.5)のフロア 。logφからlog2から簡単に計算されます 、これは単純なビット単位の操作で近似できるため、kの近似を見つけることができます。 そして、古典的なO(log k)を使用して検証するFib(k)を計算するための再帰 。上記のいずれにも、32ビットの符号付きタイプの容量より大きい数値は含まれていません。さらに簡単に言えば、フィボナッチ数列をループで実行し、ターゲット番号に到達したかどうかを確認するだけです。必要なループは47だけです。または、これらの47個の数値を事前に計算して、許可されている1kバイトよりはるかに少ないバイナリ検索で検索することもできます。