A社には、売り手に課税するために使用する独自のシステムがあります。税金は漸進的に計算されます。たとえば。もし売り手が25ドルの商品を最初の10ドルの税金= 8％、残りの15ドルの税金= 7％の商品を売っていれば、累進的税金を計算するのに適したデータ構造
データ構造あなたはこのテーブルとどのように希望を格納するのに使用する$0 - $10 8%
$11 - $50 7%
$51 - $500 6%
$501 - $10000 5%
$10001 -$1000000 4% and so on.
を次のように、彼らは税を計算するために使用するテーブルがある15
の25 + 7％= 8％だから、合計税そのデータ構造を使用して関数をコーディングします。 float computeTaxableAmount(float amount) {}
構造体の配列を使用します。考えてみましょう：
fields: from to percentage cumulative
values: 0 10 0.08 0
10 50 0.07 0.80 (= (to-from)*percentage from row above)
50 500 0.06 0.80 + (50-10)*0.07 = 4.00
500 10000 0.05 4.00 + (500-50)*0.06 = 31.00
...
お知らせ累積フィールド：単純に問題の税ブラケットに達したことにより、暗黙の組み合わせ税の累計を。その後、あなたはXドルのいくつかの販売のための税をしたいと言う、あなたは行がX（すなわちfrom <= X < to）を包含する見つけ、合計税額は次のようになります。
(X - from) * percentage + cumulative
以前の税ブラケットの組み合わせ税の事前計算が無意味セーブプログラム実行中の数学の繰り返し。
1つの税金括弧Xが入るのをバイナリ検索することができますが、要素が非常に少ないため、プロービング位置の計算/移動のオーバーヘッドは、「ミス」よりも線形検索の方が高くなります。 （必死の場合や退屈な場合は、最悪の場合のミスを最小限に抑えるために中間行から始めたり、入力値が類似している場合は最後にマッチした行から開始するなど、いくつかの最適化があります）
トニーに感謝します。インタビュー中に、私は累積パーセンテージも保存することができなかった。私は毎回それを計算していたので、複雑になっていました。 – kag
@kag：ようこそ。これについてあまり気にしないでください。この場合、パフォーマンスの差はごくわずかです。このような最適化についての事前知識があっても、再計算する可能性が高くなります。 –