URL - インタビュー

Question

参照してください - https://stackoverflow.com/a/742047/161243

アルゴ上記は、我々はデータを格納するDBを使用することを言います。面接官はDBを使用できないと言っています。そして、その場合には、我々はstuctureを持つことができます。そして、

struct st_short_url{ 
    char * short_url; 
    char * url; 
} 

ハッシュテーブル - st_short_url* hashTable[N];

今、私たちは、それぞれの時間やbase62に変換される乱数生成されたIDをインクリメントさint idを持つことができます。私が見

問題：

- このプロセスが終了した場合、私はRAMからint idのトラックと完全なハッシュテーブルを失います。だから私はそれが永続化されるようにディスクにhashTableを書き続けるのですか？はいの場合は、Bツリーが使用されますか？また、IDをディスクに書き込む必要がありますか？

P.S.ハッシュテーブル+ディスクへの書き込みはデータベースですが、DBMSを使用できない場合はどうすればよいですか？自分の実装を考え出す必要がある場合はどうすればよいですか？

お考えください...

別の質問：一般的に

、我々はURL短縮で無限のリダイレクトを処理する方法は？

Answer 1

データベースは、アイテムの挿入、削除、および検索をサポートするデータ構造です。 OPへのコメントで指摘されているように、ほぼすべてがデータベースなので、この制約はいくらか情報がないようです。

既存のDBMSを使用することができない場合は、tmpnam()または競合状態に陥らない同様の手法を使用して、アイテムをディスクに格納することができます。 tmpnam()は一意のIDを生成し、関連付けられたファイルを使用して情報を格納することができます。

Answer 2

DBを使用できない場合（つまり、永続ストレージがない場合、ファイルシステムはプリミティブなDBです）、唯一の方法は、可逆圧縮+許可文字。圧縮アルゴリズムは、URLについての知識を使用することができます（例えば、http://またはhttps://で始まる可能性が非常に高く、多くの場合、www.で続き、ドメイン名はほとんどの場合.com、.orgまたは.netで終わることがあります）。ホスト名の後にスラッシュ（http://example.orgとhttp://example.org/が等価であるため）URLには有効な文字と特殊な場合があります（URLが頻繁にリンクするドメインや既知の特定のサイトの名前付けスキーム）。圧縮スキームには、バージョンフィールドがあり、使用パターンが変化したときにアルゴリズムを更新できるようにする必要があります（新しいWebサイトが普及し、あなたが特別に扱うURLパターンを変更する）古いリンクが無効になる危険性があります。

このようなスキームは、拡張機能を介してブラウザで直接サポートされ、サーバー帯域幅を節約することもできます（ブラウザ拡張機能がないサーバーでも、拡張機能がまだ最新でない場合はフォールバックする必要があります圧縮データ）。

Answer 3

要件は実用的ではありませんが、実用的な回答は必要ありません。ファイルシステムを使用するだけで、彼はそれを認識しません。ストアへ

：

1. 例えば文字列に入力されたURLに変換しますベース64変換。
2. その名前のファイル
3. リターンなどの短いURLとしてinode番号（例えばLS -iファイル名）またはSTAT（）

を取得するには作る：

1. を取得ユーザーからのiノード番号。
2. find/-inum n -printまたはその他のメカニズム。
3. これをファイル名からURLに変換し直します。