プログラマの採用面接で聞かれる、データ構造とアルゴリズムに関する50以上の質問 | POSTD
情報科学科の卒業生やプログラマの中には、UberやNetflixのような新興企業や、 Amazon 、 Microsoft 、 Google のような大企業や、InfosysやLuxsoftのようなサービスを基本とする企業で、プログラミング、コーディング、ソフトウェア開発の仕事に就きたいと考える人が大勢います。しかし、実際にそういった企業で面接を受ける場合、大半の人が プログラミングに関してどのような質問をされるか 見当もつきません。 この記事では、 新卒生からプログラマになって1〜2年までの 経験値が異なる人たち向けに、それぞれの プログラミングの面接でよく聞かれる質問 をいくつか紹介していきます。 コーディングの面接では、主に データ構造とアルゴリズムに基づいた質問 がされますが、 一時変数を使わずにどのように2つの整数をスワップするのか 、というような論理的な質問もされるでしょう。
計算量のはなし - 赤い黒歴史を蓄積する
どうも華麗なるキャッツパーです。キャットアッパーです。 この記事はCompetitive Programming Advent Calendar Div2013, 12/7の記事です。 私は過去に、暇に任せてこのようなスライドを作ってしまいました。 有名アルゴリズムとそれの計算量について列挙するのが楽しすぎて作ってしまいました。後悔しております。 本記事では「計算量ってどうやって計算するの？」みたいな話を競プロの観点からします。 計算量とはなんぞやということについては上のスライドを読んでください。 計算量の種類 競技プログラミングで気にする計算量は2種類あります。最悪計算量と償却計算量です。 最悪計算量というのは、ある処理にどのような入力を与えても、それ以上に速い計算量になる、というもので、一種の上界です。競技プログラミングでは作問者が最悪計算量になるテストケースをかならず入れてきますから
古くて新しい自動迷路生成アルゴリズム - やねうらおブログ(移転しました)
最近、ゲーム界隈ではプロシージャルテクスチャー生成だとか、プロシージャルマップ生成だとか、手続き的にゲーム上で必要なデータを生成してしまおうというのが流行りであるが、その起源はどこにあるのだろうか。 メガデモでは初期のころから少ないデータでなるべくど派手な演出をするためにプロシージャルな生成は活用されてきたが、ゲームの世界でプロシージャル生成が初めて導入されたのは、もしかするとドルアーガの塔(1984年/ナムコ)の迷路の自動生成かも知れない。 なぜ私が迷路のことを突然思い出したのかと言うと、最近、Twitterで「30年前、父が7年と数ヶ月の歳月をかけて描いたA1サイズの迷路を、誰かゴールさせませんか。」というツイートが話題になっていたからである。 この迷路を見て「ああ、俺様も迷路のことを書かねば！俺様しか知らない(?)自動迷路生成のことを後世に書き残さねば！」と誰も求めちゃいない使命感が
へ、変態っ！！読めないからやめてっ！bit使ったデータ構造・アルゴリズム実装集 - Negative/Positive Thinking
この記事はCompetitive Programming Advent Calendar Div2012の2日目の記事です。 12月20日追記： Darseinさんが20日目の記事で、ビット演算についての詳しい説明を紹介してくださっています！必読ですね！！！！：） はじめに Y＾´ ∨／／ ／,∠ ,. ' ／l／／／ ／, ' , '／ ! ｜ ｌ }´ 〈 〉 変 〈/ , ' ／／￣｀>< ／／／ ／／／ _,.=‐|'"´l ｌ〈 変 / 〈 態. ∨, '／l| ,.'-‐､｀/／｀7/ ／''"´__ ｜ ﾊ l丿 態 { 人） ! ! （／! |ヽ〈_ ・.ﾉ〃 〃 ／ '／⌒ヾ.! ,' !く ! ! （_ ト､__／ ヽ､_,.イ ／ｌ ｌ ｜:::::::｀｀`/:::::／...´..
サービス終了のお知らせ - NAVER まとめ
サービス終了のお知らせ NAVERまとめは2020年9月30日をもちましてサービス終了いたしました。 約11年間、NAVERまとめをご利用・ご愛顧いただき誠にありがとうございました。
情報系修士にもわかるダブル配列 - アスペ日記
最近話題の「日本語入力を支える技術」を途中まで読んだ。 3章がものすごく気合いが入っている。 trie（トライ）というデータ構造の2つの実装、「ダブル配列」と「LOUDS」について詳しく説明がされている。 ダブル配列については、ぼくは以前論文を読んで勉強しようとしたのだが、その時は難しくてあきらめた覚えがある。しかし、この本の説明を読むことで理解ができた。 ありがたい。 感銘を受けたので、この本を教材に友達と2人勉強会をした。 この2人勉強会というのは、ぼくが復習を兼ねて友達に教えるというのがだいたいのスタイル。 しかし、いざやってみるといろいろと難しい。 次のようなところでひっかかるようだ。 例のサイズが小さく、イメージを喚起するのが難しい。 最初の図のノード番号と、最終的なダブル配列上の位置が異なるため、混乱する。 単語終端について言及がないので、どのノードが単語を表しているかがわから
エラトステネスの篩 - Wikipedia
この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。出典を追加して記事の信頼性向上にご協力ください。（このテンプレートの使い方） 出典検索?: "エラトステネスの篩" – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL（2019年6月） エラトステネスの篩 (エラトステネスのふるい、英: Sieve of Eratosthenes) は、指定された整数以下の全ての素数を発見するための単純なアルゴリズムである。古代ギリシアの科学者、エラトステネスが考案したとされるため、この名がついている。 アルゴリズム[編集] 2 から 120 までの数に含まれる素数を探すGIFアニメーション 指定された整数x以下の全ての素数を発見するアルゴリズム。このアニメーションでは以下のステップにそって 2 から
高速な安定ソートアルゴリズム "TimSort" の解説 - Preferred Networks Research & Development
先日、TimSortというソートアルゴリズムが話題になりました。TimSortは、高速な安定ソートで、Python(>=2.3)やJava SE 7、およびAndroidでの標準ソートアルゴリズムとして採用されているそうです。 C++のstd::sort()よりも高速であるというベンチマーク結果1が話題になり(後にベンチマークの誤りと判明)、私もそれで存在を知りました。実際のところ、ランダムなデータに対してはクイックソート(IntroSort)ほど速くないようですが、ソートというシンプルなタスクのアルゴリズムが今もなお改良され続けていて、なおかつ人々の関心を引くというのは興味深いものです。 しかしながら、オリジナルのTimSortのコードは若干複雑で、実際のところどういうアルゴリズムなのかわかりづらいところがあると思います。そこで今回はTimSortのアルゴリズムをできるだけわかりやすく解
頻出典型アルゴリズムの演習問題としてよさげなやつ - kyuridenamidaのチラ裏
効率的な別解とか存在する問題もあるけど演習によさそうなやつをピックアップ。そのアルゴリズムじゃないと解けないわけではないって問題も多いので注意。(ただ演習するのには都合が良いかなと)※個人的難易度をつけてみました。とても主観的な難易度付けなので気にせず解いてみてください。深さ優先探索・Balls[☆]・Sum of Integers[☆]・The Number of Island[☆]・Block[★]幅優先探索・Mysterious Worm[★]・Cheese[★]・Seven Puzzle[★☆]・Stray Twins[★★]・Deven-Eleven[★★]・Summer of Phyonkichi[★★☆]ワーシャルフロイド法(For 全点対最短路問題)・Traveling Alone: One-way Ticket of Youth[★]・A reward for a Car
粒子群最適化 - Wikipedia
粒子群最適化（りゅうしぐんさいてきか、Particle Swarm Optimization、PSO）とは、群知能の一種。 昆虫の大群や魚群において、一匹がよさそうな経路を発見すると（すなわち、食料を発見したとか安全であるという場合）、群れの残りはどこにいても素早くそれに倣うことができる。 これは多次元空間において位置と速度を持つ粒子群でモデル化される。これらの粒子はハイパー空間を飛びまわり、最善な位置を探す。位置の評価は適応度関数で行う。群れのメンバーは良い位置について情報交換し、それに基づいて自身の位置と速度を調整する。このコミュニケーションは主に次の二種類の方法でなされる。 最も良い位置にいる粒子が全体に通知される。 ローカルなベストの位置にいる粒子が近傍の粒子群に通知される。 位置と速度の更新は以下の式で行われ、これが繰り返される。 は、慣性定数。多くの場合 1 より若干小さい値が
文書比較（diff）アルゴリズム
文書比較（diff）アルゴリズム 前のドキュメント 次のドキュメント ＶｉＶｉの文書比較（diff）機能で使用しているアルゴリズムについて解説する。 これらのアルゴリズムは Myers 氏らの論文によるもので、氏は筆者のためにわざわざ論文をＷｅｂサイトで入手可能な形式にしてくださった。この場を借りてお礼申し上げる。 オリジナル論文は以下のＷｅｂサイトから入手可能である。 http://www.cs.arizona.edu/people/gene [1] E.W.Myers, "An O(ND) Difference Algorithm and Its Variations", Algorithmica, 1 (1986), pp.251-266 [2] S. Wu, U. Manber, G. Myers and W. Miller, "An O(NP) Sequence Comparis
最長共通部分列問題 (Longest Common Subsequence) - naoyaのはてなダイアリー
部分列 (Subsequence) は系列のいくつかの要素を取り出してできた系列のことです。二つの系列の共通の部分列を共通部分列 (Common Subsecuence)と言います。共通部分列のうち、もっとも長いものを最長共通部分列 (Longest Common Subsequence, LCS) と言います。 X = <A, B, C, B, D, A, B> Y = <B, D, C, A, B, A> という二つの系列から得られる LCS は <B, C, B, A> で、その長さは 4 です。長さ 2 の<B, D> の長さ 3 の <A, B, A> なども共通部分列ですが、最長ではないのでこれらは LCS ではありません。また、LCS は最長であれば位置はどこでも良いので、この場合 <B, D, A, B> も LCS です。 LCS は動的計画法 (Dynamic Prog
アルゴリズムイントロダクション15章 動的計画法
4. 15 章の構成 例 題 １ 例 題 2 一 般 化 例 題 3 例 題 4 15.1 15.2 15.3 15.4 15.5
diffの動作原理を知る～どのようにして差分を導き出すのか | gihyo.jp
UNIXの基本的なコマンドの1つであるdiff。 これに実装されているアルゴリズムは実に興味深い世界が広がっています。 本稿では、筆者が開発した独自ライブラリ「dtl」をもとに「diffのしくみ」を解説します。 はじめに diffは2つのファイルやディレクトリの差分を取るのに使用するプログラムです。 ソフトウェア開発を行っている方であれば、SubversionやGitなどのバージョン管理システムを通して利用していることが多いかと思います。本稿ではそのdiffの動作原理について解説します。 差分の計算の際に重要な3つの要素 差分を計算するというのは次の3つを計算することに帰結します。 編集距離 2つの要素列の違いを数値化したもの LCS（Longest Common Subsequence） 2つの要素列の最長共通部分列 SES（Shortest Edit Script） ある要素列を別の要
Sorting Algorithms Animations
KEY Black values are sorted. Gray values are unsorted. A red triangle marks the algorithm position. Dark gray values denote the current interval (shell, merge, quick). A pair of red triangles marks the left and right pointers (quick). DISCUSSIONThese pages show 8 different sorting algorithms on 4 different initial conditions. These visualizations are intended to: Show how each algorithm operates.
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Chromeのなかのコンピュータ・サイエンス
あなたの知らないハッシュテーブルの世界
サービス終了のお知らせ