[B! データ構造] indicationのブックマーク

コーディングインタビューの対策とその意義 (1/2) - 16bitのメモランダム

１．コーディングインタビューとは何かコーディングインタビュー（Coding Interview、またはProgramming Interview）とは、1時間ほどの制限時間内に小さなプログラミング問題を解かせる面接形式のことをいう。プログラマー、またはデータサイエンティストなどの採用試験として、米国を含むいくつかの国で用いられている。「物理的なホワイトボード上にプログラムを書く」という形式で実施されることが多い。「オンライン上の共有エディタで書く」といった形式のこともある。Googleなどは自社のYoutubeチャンネル動画でも説明している。出題される問題としては、例えば、「複数の数字numbersと整数kが与えられたとき、合計がkとなる数字の組を1つ出力せよ」といったものがある。この問題は有名なので通称が付いており、Two Sumと呼ばれる。 Two Sumの一例。与えられた数値の並

indication 2021/12/28

リンク

興味深いデータ構造：BK木 | POSTD

BK木とは、距離空間内のデータをインデックス化する目的に特化した、木構造を指します。距離空間は基本的に、要素の組 $ (a,b) $ 全てについて距離関数 $ d(a,b) $ を持つオブジェクトの集合です。この距離関数は正しく動作することを保証するために、一連の公理を満たしていなければなりません。これが必要になる理由は、後述の「検索」のセクションできちんと説明します。 BK木のデータ構造は、一連のキーを検索し、与えられた検索キーの値に最も近いキーを見つける問題の解決策として、 1973年にBurkhardとKellerが提案したものです。この問題を解決する素朴な方法は、要素の組に含まれる各要素と検索キーの値を単純に比較することです。一定の時間内に比較が完了した場合、この検索の解は $ O(n) $ となります。一方、BK木を採用すると、この時実行する比較の回数を減らせる可能性が高く

indication 2017/05/11

リンク

ハクビシンにもわかる全文検索 - Qiita

高速な全文検索アルゴリズムであるFM-indexについて解説する。理解しがたい点や間違っている点があれば是非コメントで指摘してほしい。概要 FM-indexはリニアな文字列に対して検索をするアルゴリズムで、主に簡潔データ構造とBWT(およびLF mapping)という二つのアイデアから成り立っている。BWTはBurrows-Wheeler変換のことで、文字列を特殊な並び順に変換するという可逆関数である。BWTされた文字列を簡潔データ構造固有の操作をすることで、クエリ文字列の長さに比例した短い時間で文字列を探し出すのがFM-indexだ。簡潔データ構造簡潔データ構造に関してはFM-indexで必要となる二つの関数だけ説明して、詳細は次の機会に譲るとする。さて、二つの関数はともに文字列のある位置より前の部分に含まれている文字の数を数え上げるというものでrank()とrankLessTha

indication 2015/07/21

リンク

後悔しないもんごもんごの使い方〜サーバ編〜

Akihiro KuwanoExperienced server engineer, Solution Architect of cloud computing at Amazon Web Services Japan

indication 2013/08/01

リンク

Algorithm - 連想配列の実装としてのハッシュはオワコン? : 404 Blog Not Found

2012年01月17日11:45 カテゴリアルゴリズム百選Tips Algorithm - 連想配列の実装としてのハッシュはオワコン? 珠玉のプログラミング Jon Bentley / 小林健一郎訳つまり「終わったコンテナ」。以前からうすぼんやりと考えて来た危惧が、すこしはっきりと見えてきた。徳丸浩の日記: Webアプリケーションに対する広範なDoS攻撃手法(hashdos)の影響と対策もうそろそろハッシュ(テーブル)以外の手段の連想配列の実装手段を本格的に模索するべきではないか、と。そのデータ構造は、君の魂を差し出すに足るものかい? 連想配列(Associative array)がコレクション(Collection)、すなわち数多のデータ構造をまとめるデータ構造としての覇者となったのはもはや疑いようがない事実でしょう「配列で実装されるデータ構造ではなくて、配列を実装するデータ構

indication 2012/01/17

適材適所を大切に。

リンク

2011-02-18 - ITは芸術だレガシープログラマかどうかを判断する10項目

※2011.3.30追記 11個目の判断項目を追加しました。また、「昔はね...」の補足説明を各項目に追加しました。レガシープログラマ = モダンな言語のおいしい機能をうまく使いこなせていないプログラマおいらは時々社内システムのコードレビューなんかをやっているのですが、「なんかちょっと前時代的だな〜」とか「ちょっと修正したらC言語でもコンパイルできそうだな〜」って思うことがよくあります。おいらがレビューする言語は主にC#です。C#やJavaのような比較的モダンな言語のおいしい機能をうまく使いこなせていないプログラマを、ここでは「レガシープログラマ」と呼ぶことにします*1。そこで、おいらがこれまでに見てきたコードの中から「これはレガシープログラマっぽい」と思った典型的な症例を10個11個挙げてみます。レガシープログラマの判断項目使われるローカル変数をすべてメソッドの最初に宣言す