この質問は、ある大手ソフトウェア会社で行われました。私は簡単な解決策を思いついたので、その解決策について他の人がどう感じているか知りたい.
都市に住む人々に電話番号を割り当てることができるシステムの API とバックエンドを設計することになっています。電話番号は 111-111-1111 から始まり、999-999-9999 で終わります。API は、クライアント (都市の人々) が次のことを実行できるようにする必要があります。
- クライアントが電話番号を要求すると、使用可能な番号の 1 つが割り当てられます。
- 一部のクライアントは派手な番号が必要な場合があるため、割り当てられる番号を具体的に要求できます。要求された番号が利用可能な場合、システムはそれをそれらに割り当てます。それ以外の場合、システムは利用可能な番号を割り当てます。
システムは、どの番号がどのクライアントに割り当てられているかを知る必要はありません。同じクライアントが連続して要求を行い、複数の電話番号を取得する場合がありますが、システムは問題になりません。どの時点でも、システムはどの電話番号が割り当てられ、どの電話番号が空いているかだけを知っています。
111-111-1111 から 999-999-9999 までの数字は、およそ 80 億の数字に相当します。メモリが制約でないと仮定すると、次の 2 つのアプローチが考えられます (ほぼ同じです)。
長さ 80 億の巨大なブール配列を維持
nextし、配列インデックスを指すポインターを持ちます (nextゼロに初期化されます)。が指す値が空きでない場合は、空き番号が見つかるまでnext転送します。nextファンシー番号が要求された場合は、対応するインデックス位置が空いているかどうかを確認して、番号を返します。このアプローチの欠点は、通常の方法で数値を割り当てる場合、派手な割り当てによって割り当てられた巨大なチャンク (たとえば 10 億) の数値が途中にある場合、nextポインターを 10 億回移動する必要があることです。前の設計で述べた問題を克服するために、リンクされたハッシュマップのようなものを使用できます。二重にリンクされたリスト (これは前の設計の配列を置き換えます) と、配列の各要素がリスト内の対応する要素を指すリストと同じ長さの別の配列を維持します。そのため、通常の方法で数値を割り当てるときは、リンクされたリスト内のポインターを進め、割り当てるときにノードをマークします (前の方法と同じ)。ファンシーな番号を割り当てるとき、最初に配列にインデックスを付けてポインタをたどることで、要求された特別な番号に対応するリスト内のノードを直接見つけることができます。ノードが識別されると、
私が正しい軌道に乗っているかどうか教えてください。私が見逃している重要な詳細を教えてください。