開発面接Hash面接試験問題
hash関連面接問題1.Hash Top検索 内容説明 要求 分析 補足 まとめ 2.SimHashアプリケーション 内容説明 要求 分析 まとめ Hash部分は3つの部分に分かれており、各観光客は分類に応じてブログを読むことができます.開発面接Hash原理詳細 面接Hash一般アルゴリズム を開発開発面接Hash面接試験問題
1.Hash Top検索
コンテンツの説明
1)検索エンジンは,ユーザが検索するたびに使用するすべての検索列をログファイルを介して記録し,各検索列の長さは1−255バイトである.2)現在、1千万件の記録があると仮定する(これらのクエリ列の重複度は比較的高く、総数は1千万であるが、重複を除いた場合、3百万個を超えない.2)1つのクエリ列の重複度が高いほど、クエリのユーザーが多ければ多いほど、つまり人気がある.
要求
最も人気のある10個のクエリー列を統計してください.使用するメモリは1 Gを超えてはいけません.
ぶんせき
ソートを使用するシナリオとhashを使用する方法の2つの考え方があります.
1.ソート法1)まず最初に思いついたアルゴリズムはソートであり,まずこのログ内のすべてのQueryをソートし,次にソートされたQueryを巡り,各Queryが出現した回数を統計する.
2)しかし、タイトルには明確な要求があります.それはメモリが1 Gを超えてはいけません.1千万個の記録があります.各記録は255 Byteで、2551000,000,000/(10241024)=2.37 Gサイズのメモリによると.
3)データ量が多くてメモリが入らない場合は,外部ソート法を用いてソートすることができ,ここでは集計ソートを用いることができ,集計ソートには比較的良好な時間複雑度O(nlogn)がある.
4)順序付けが完了した後,順序付けされたQueryファイルを遍歴し,各Queryが出現した回数を統計し,再びファイルに書き込まれ,その時間的複雑度O(n)である.
5)全体時間複雑度O(n)+O(nlogn)=O(nlogn)
2.Hash Table法はデータの統計に対して並べ替えより良い案があり、それはhash tableを使用する方法である.
タイトルには1千万個のQueryがありますが、重複度が高いため、実際には300万個のQuery量しかなく、その大きさは2.37*0.3=0.71 Gで、1 Gのメモリ要求に満足しています.Hash Tableのルックアップ速度はO(1)に非常に速い.
このように私たちのアルゴリズムは、KeyがQuery文字列であることを維持し、ValueがそのQueryの出現回数のHashTableであることを維持し、毎回1つのQueryを読み取り、その文字列がTableにない場合、その文字列を加え、Value値を1にする.文字列がTableにある場合は、文字列のカウントを1つ加算すればよい.最終的に,O(n)の時間的複雑さの中でこの大量データの処理を完了した.
比較:Hash Tableは並べ替え法に対して時間的複雑さにおいてO(n)の1桁増加した.またhash Tableの方式はIOデータ操作を一度だけ行う必要があり、操作性においてより優れている
補足
アルゴリズム:一部のソート問題はTop 10を求めることを要求しているので、私たちはすべてのQueryをソートする必要はありません.私たちは10個の大きさの配列を維持し、初期化して10個のQueryを入れ、各Queryの統計回数によって大きくから小さくソートし、この300万個の記録を遍歴し、1本の記録を読むたびに配列の最後のQueryと比較します.このQueryより小さい場合は、ループを続けます.そうしないと、配列の最後のデータを淘汰し、現在のQueryに追加します.
最後に、すべてのデータが遍歴された後、この配列の10個のQueryは私たちが探しているTop 10です.このように,アルゴリズムの最悪時間複雑度はN*Kであり,Kはtopの多少を指す.
アルゴリズム:一部のアルゴリズム2に積み上げられ、比較が完了するたびに必要な操作の複雑さはKであり、要素を線形テーブルに挿入し、順序比較を採用するためである.
ここでは,この配列は秩序化されており,一度に検索するたびに二分的な方法で検索することができ,操作の複雑さはlogKに下がったが,それに伴う問題はデータ移動であり,移動データの回数が増えたためである.しかし、このアルゴリズムはアルゴリズム2よりも改善された.
以上の分析に基づいて、要素を迅速に検索し、迅速に移動できるデータ構造を考えてみましょう.答えは肯定的で、それは山です.スタック構造により、logレベルの時間内に検索および調整/移動できます.そこでここまで,我々のアルゴリズムは,K(この問題では10)サイズの小さなルートスタックを維持し,次いで300万のQueryを遍歴し,それぞれルート要素と比較するように改良できる.
一部のアルゴリズムと比較して,配列の代わりに最小スタックというデータ構造を採用し,ターゲット要素を検索する時間的複雑さをO(K)からO(logK)に低減した.スタックデータ構造を採用すると,最終的な時間複雑度はN‘logKに低下する.
まとめ
最適な方法は,まずHashテーブルを用いてQueryごとに出現する回数O(N)を統計し,その後スタックデータ構造を用いて上位10を探し出し,時間複雑度はN*O(logK)であるため,総時間複雑度はO(N)+N
2.SimHash応用
コンテンツの説明
2つの文章の類似度を比較するアルゴリズムをどのように設計しますか?
要求
2つの文章の類似度を最も速く最も効果的な方法で比較した.
ぶんせき
私たちが最も考えやすい2つの案はの1つのスキームは、2つの文章をそれぞれ分詞し、一連の特徴ベクトルを得た後、特徴ベクトル間の距離(それらの間のオーステナイト距離、海明距離、または角を挟んだ余弦などを計算することができる)を計算し、距離の大きさによって2つの文章の類似度を判断することである. のもう1つのスキームは、従来のhashであり、各ウェブドキュメントに対してhashによって指紋(finger print)を生成することを考慮する.
2つの法案を比較する+1つ目の方法を採用し、2つの文章の類似性だけを比較すればいいが、大量のデータであれば、数百万から億万のページがあり、これらのページの類似度を計算するように要求されている.任意の2つのページ間の距離や角の余弦を計算しますか?君はもうできないだろう.
+第2の態様でいう従来の暗号化方式md 5は、分布全体をできるだけ均一にすることを目的としているが、入力内容がわずかに変化するとhash値が大きく変化する.1文字だけ変えるとHash値の差が大きく比較しにくい.H^md5(“the cat sat on the mat”)=415542861 H^md5(“the cat sat on the mat”)=668720516
理想的なhash関数は、ほぼ同じ入力内容に対して、同じまたは近いhash値を生成する必要がある.言い換えれば、hash値の類似度は入力内容の類似度を直接反映しなければならないので、md 5などの従来のhash方法も私たちのニーズを満たすことができない.
GoogleMoses Charikarが発表した論文「detecting near-duplicates for web crawling」からsimhashアルゴリズムが提案され、億万級のウェブページの重任を解決するために使用されている.具体的には極原理を使って私のブログ「開発面接Hashよくあるアルゴリズム」を見てください.
まとめ
Simhashを使用すると、Webページの再判断処理を完璧かつ迅速に解決できます.
関連リンク開発面接Hash原理詳細 面接Hash一般アルゴリズム を開発 ARTとDalvik、JVMの関係は分かりましたか? 熱更新はどれらを知っていますか?
， ， 、 ^ _ ^ ! 1.Hash Top検索
コンテンツの説明
1)検索エンジンは,ユーザが検索するたびに使用するすべての検索列をログファイルを介して記録し,各検索列の長さは1−255バイトである.2)現在、1千万件の記録があると仮定する(これらのクエリ列の重複度は比較的高く、総数は1千万であるが、重複を除いた場合、3百万個を超えない.2)1つのクエリ列の重複度が高いほど、クエリのユーザーが多ければ多いほど、つまり人気がある.
要求
最も人気のある10個のクエリー列を統計してください.使用するメモリは1 Gを超えてはいけません.
ぶんせき
ソートを使用するシナリオとhashを使用する方法の2つの考え方があります.
1.ソート法1)まず最初に思いついたアルゴリズムはソートであり,まずこのログ内のすべてのQueryをソートし,次にソートされたQueryを巡り,各Queryが出現した回数を統計する.
2)しかし、タイトルには明確な要求があります.それはメモリが1 Gを超えてはいけません.1千万個の記録があります.各記録は255 Byteで、2551000,000,000/(10241024)=2.37 Gサイズのメモリによると.
3)データ量が多くてメモリが入らない場合は,外部ソート法を用いてソートすることができ,ここでは集計ソートを用いることができ,集計ソートには比較的良好な時間複雑度O(nlogn)がある.
4)順序付けが完了した後,順序付けされたQueryファイルを遍歴し,各Queryが出現した回数を統計し,再びファイルに書き込まれ,その時間的複雑度O(n)である.
5)全体時間複雑度O(n)+O(nlogn)=O(nlogn)
2.Hash Table法はデータの統計に対して並べ替えより良い案があり、それはhash tableを使用する方法である.
タイトルには1千万個のQueryがありますが、重複度が高いため、実際には300万個のQuery量しかなく、その大きさは2.37*0.3=0.71 Gで、1 Gのメモリ要求に満足しています.Hash Tableのルックアップ速度はO(1)に非常に速い.
このように私たちのアルゴリズムは、KeyがQuery文字列であることを維持し、ValueがそのQueryの出現回数のHashTableであることを維持し、毎回1つのQueryを読み取り、その文字列がTableにない場合、その文字列を加え、Value値を1にする.文字列がTableにある場合は、文字列のカウントを1つ加算すればよい.最終的に,O(n)の時間的複雑さの中でこの大量データの処理を完了した.
比較:Hash Tableは並べ替え法に対して時間的複雑さにおいてO(n)の1桁増加した.またhash Tableの方式はIOデータ操作を一度だけ行う必要があり、操作性においてより優れている
補足
アルゴリズム:一部のソート問題はTop 10を求めることを要求しているので、私たちはすべてのQueryをソートする必要はありません.私たちは10個の大きさの配列を維持し、初期化して10個のQueryを入れ、各Queryの統計回数によって大きくから小さくソートし、この300万個の記録を遍歴し、1本の記録を読むたびに配列の最後のQueryと比較します.このQueryより小さい場合は、ループを続けます.そうしないと、配列の最後のデータを淘汰し、現在のQueryに追加します.
最後に、すべてのデータが遍歴された後、この配列の10個のQueryは私たちが探しているTop 10です.このように,アルゴリズムの最悪時間複雑度はN*Kであり,Kはtopの多少を指す.
アルゴリズム:一部のアルゴリズム2に積み上げられ、比較が完了するたびに必要な操作の複雑さはKであり、要素を線形テーブルに挿入し、順序比較を採用するためである.
ここでは,この配列は秩序化されており,一度に検索するたびに二分的な方法で検索することができ,操作の複雑さはlogKに下がったが,それに伴う問題はデータ移動であり,移動データの回数が増えたためである.しかし、このアルゴリズムはアルゴリズム2よりも改善された.
以上の分析に基づいて、要素を迅速に検索し、迅速に移動できるデータ構造を考えてみましょう.答えは肯定的で、それは山です.スタック構造により、logレベルの時間内に検索および調整/移動できます.そこでここまで,我々のアルゴリズムは,K(この問題では10)サイズの小さなルートスタックを維持し,次いで300万のQueryを遍歴し,それぞれルート要素と比較するように改良できる.
一部のアルゴリズムと比較して,配列の代わりに最小スタックというデータ構造を採用し,ターゲット要素を検索する時間的複雑さをO(K)からO(logK)に低減した.スタックデータ構造を採用すると,最終的な時間複雑度はN‘logKに低下する.
まとめ
最適な方法は,まずHashテーブルを用いてQueryごとに出現する回数O(N)を統計し,その後スタックデータ構造を用いて上位10を探し出し,時間複雑度はN*O(logK)であるため,総時間複雑度はO(N)+N
O(logK)。 N=1000 ，N=300万である.2.SimHash応用
コンテンツの説明
2つの文章の類似度を比較するアルゴリズムをどのように設計しますか?
要求
2つの文章の類似度を最も速く最も効果的な方法で比較した.
ぶんせき
私たちが最も考えやすい2つの案は
2つの法案を比較する+1つ目の方法を採用し、2つの文章の類似性だけを比較すればいいが、大量のデータであれば、数百万から億万のページがあり、これらのページの類似度を計算するように要求されている.任意の2つのページ間の距離や角の余弦を計算しますか?君はもうできないだろう.
+第2の態様でいう従来の暗号化方式md 5は、分布全体をできるだけ均一にすることを目的としているが、入力内容がわずかに変化するとhash値が大きく変化する.1文字だけ変えるとHash値の差が大きく比較しにくい.H^md5(“the cat sat on the mat”)=415542861 H^md5(“the cat sat on the mat”)=668720516
理想的なhash関数は、ほぼ同じ入力内容に対して、同じまたは近いhash値を生成する必要がある.言い換えれば、hash値の類似度は入力内容の類似度を直接反映しなければならないので、md 5などの従来のhash方法も私たちのニーズを満たすことができない.
GoogleMoses Charikarが発表した論文「detecting near-duplicates for web crawling」からsimhashアルゴリズムが提案され、億万級のウェブページの重任を解決するために使用されている.具体的には極原理を使って私のブログ「開発面接Hashよくあるアルゴリズム」を見てください.
まとめ
Simhashを使用すると、Webページの再判断処理を完璧かつ迅速に解決できます.
， ， 、 ^ _ ^ ! 関連リンク