プログラマの採用面接で聞かれる、データ構造とアルゴリズムに関する50以上の質問 | POSTD
情報科学科の卒業生やプログラマの中には、UberやNetflixのような新興企業や、 Amazon 、 Microsoft 、 Google のような大企業や、InfosysやLuxsoftのようなサービスを基本とする企業で、プログラミング、コーディング、ソフトウェア開発の仕事に就きたいと考える人が大勢います。しかし、実際にそういった企業で面接を受ける場合、大半の人が プログラミングに関してどのような質問をされるか 見当もつきません。 この記事では、 新卒生からプログラマになって1〜2年までの 経験値が異なる人たち向けに、それぞれの プログラミングの面接でよく聞かれる質問 をいくつか紹介していきます。 コーディングの面接では、主に データ構造とアルゴリズムに基づいた質問 がされますが、 一時変数を使わずにどのように2つの整数をスワップするのか 、というような論理的な質問もされるでしょう。
類似画像検索について簡単にまとめてみた - Qiita
類似画像検索手法について簡単にまとめました。 はじめに 画像検索には主に2種類の手法がある。 TBIR (Text Based Image Retrieval) 画像にテキストデータが紐付けられていて、テキストを元に検索する CBIR (Content Based Image Retrieval) 画像の特徴量を基盤として検索する ライブラリ Feature Extraction Library - FELib http://appsrv.cse.cuhk.edu.hk/~jkzhu/felib.html 下記の５つの特徴を持つ画像から特徴量を抽出できるライブラリである。 Color histogram, color moments. カラーヒストグラム・色統計) Edge histogram. 輪郭のヒストグラム Gabor wavelets transform. Wavelet tra
簡単な画像の類似度計算手法「Average Hash」 » Untitled Blog
画像の類似度を計算する方法を調査していたところ、面白い手法を紹介している方がいたので、この場でシェアしたいと思います。 この手法は「Perceptual Hash」という、「比較可能なハッシュ」を生成するための一手法です。 一般的にMD5やSHA1などのハッシュ値は、1バイトでもデータが違えば、まったく違うハッシュ値を返してきますが、「Perceptual Hash」は似たようなデータには似たようなハッシュ値を返してきます。 元ネタのブログによれば、これから紹介する手法のことを、ブログのオーナーであるDr. Neal Krawetzさんは「Average Hash」と呼んでいるようです。 元ネタのブログ記事は、以下のリンクからたどることができます。 Looks Like It – The Hacker Factor Blog いたってシンプルな手法ではありますが、例えば高速で「それなりの精
病みつきになる「動的計画法」、その深淵に迫る
数回にわたって動的計画法・メモ化再帰について解説してきましたが、今回は実践編として、ナップサック問題への挑戦を足がかりに、その長所と短所の紹介、理解度チェックシートなどを用意しました。特に、動的計画法について深く掘り下げ、皆さんを動的計画法マスターの道にご案内します。 もしあなたが知ってしまったなら――病みつきになる動的計画法の集中講義 前回の『アルゴリズマーの登竜門、「動的計画法・メモ化再帰」はこんなに簡単だった』で動的計画法とメモ化再帰を説明しましたが、前回の説明ではまだ勘所をつかめていない方がほとんどでしょう。そこで、これらを完全にマスターするため、今回はもう1つ具体例を挙げながら練習したいと思います。 どういった問題を採用するかは悩みましたが、非常に有名な「ナップサック問題」を取り上げて説明します。 ナップサック問題とは以下のような問題です。 幾つかの品物があり、この品物にはそれぞ
任意の色とその補色: やむえむのExcel VBAメモ
記事「色を反転する」の中で パソコンソフトのイラストレーターの機能「反転」について 書きました。 「反転」という機能の下に 「補色」という機能が付いています。 この「補色」は、どんな仕組みになっているか調べてみました。 まずは、分かっていること… 赤の補色がシアンになることを確かめる。 RGB(255, 0, 0) → RGB(0, 255, 255) これは、「反転」と同じ結果です。 次に、R255に加えてG100を加えてみる。 RGB(255, 100, 0) → RGB(0, 155, 255) これも、「反転」と同じ結果です。 今度は、R255G100に加えてB50も加えてみる。 RGB(255, 100, 50) → RGB(50, 205, 255) これは、「反転」と違います。 なぜなら、 赤が255 + 50 =305、 緑が100 + 205 = 30
迷路を最短経路で(ry - 月の塵
Scheme気が向いたので、例の迷路を最短経路で解く問題を Gauche で書いてみた。 (use srfi-1) (define *maze* '( "**************************" "*S* * *" "* * * * ************* *" "* * * ************ *" "* * *" "************** ***********" "* *" "** ***********************" "* * G *" "* * *********** * *" "* * ******* * *" "* * *" "**************************" )) (define (maze-at pos) (string-ref (list-ref *maze* (inexact->exact (real-p
迷路生成アルゴリズム
Article: 迷路生成アルゴリズム 迷路を用いたものはゲームに限らず色々ありますが、どのように作られているか考えた事はないでしょうか。実はこのロジック、とても単純なものになっていて、知っているだけで楽に作れるようになります。何種類か方法がありますが、ここでは一番楽な「棒倒し法」を紹介していきます。 - 棒倒し法による迷路生成アルゴリズム。 Article Written: 99/7/4 壁の用意 （図１） まずはこのように、四角の外壁の中に、さらに等間隔に内壁を配置します。色分けされているのは便宜上のもので実際はどうでも良く、０（壁がある）と１（壁がない）の情報でも構成する事ができます。この壁を用意するのに気を付けなければならない事は、外壁を大きめに取っておく事です。多くのゲームではこの全体像が見える事はなく、スクロールという概念を用いたりして一部しか見えないようになっています。その際
迷路作成プログラムの製作
[応用編・立体迷路ゲームDL] No001 迷路作成プログラムの製作 コンパイラ ： ＶＣ＋＋ ６．０ プログラム種類 ： Ｗｉｎｄｏｗｓコンソールアプリケーション はじめに 私が最初に作った本格的なプログラムが高校生のころに作った迷路ゲームでした。 迷路の中に実際にいるような立体表示で、迷路のなかを歩き回って出口にたどりつくという単純でありがちなゲームでしたが、 迷路を作成するロジックも自分でいろいろ研究して考えたものです。 そこで、第１回はこの迷路を作るプログラムを製作しようと思います。 図１に示すような迷路を作成します。迷路の特徴は ・全体が長方形の平面、プログラムではサイズを指定できるようにします。 ・通路と壁の幅は同じ長さ。厚さが２つ分以上の通路や壁は存在しません。 ・通路のどの地点からどの地点まででも到達するルートが１つだけあります。 言い換えれば、スタートとゴールを
クラスタリングによる迷路作成アルゴリズム
はじめに クラスタリングアルゴリズムにより、解くと絵が浮かび上がる 迷路を作成する方法を紹介する。 クラスタリングとは ウェブのリンク情報や、mixiの友人関係など、ネットワークの性質を 知りたいことがよくある。このとき、ネットワークの性質として このネットワークにおいて任意に選んだ要素Aと要素Bはつながっているか？ このネットワークは全体がつながっているか？ つながっていないとしたらいくつのグループに分かれるか？ 要素数最大のグループはどれか？ などの情報が欲しくなる。このような解析をするときに 必要となるのがクラスタリングである。 クラスタリングとは、同値関係のリストが与えられたときにグループ分けを することである。たとえば、 友達の友達は友達である と定義すると、友人関係は同値関係を作る。 その上で、 A君とB君は友達 C君とE君は友達 B君とD
穴掘り法
ここで、 迷路作成のアルゴリズムの一つである穴掘り法について簡単に説明する。 先ず、縦横それぞれ奇数個サイズのマスを想定する。 左上を原点として、 偶数座標のマスが迷路の壁となり、奇数座標が迷路の通路として使用される。 最初に全てのマスを「壁」として初期化する。 以降の例では、■を壁、□を通路として表示する。 ■■■■■■■■■ ■■■■■■■■■ ■■■■■■■■■ ■■■■■■■■■ ■■■■■■■■■ ■■■■■■■■■ ■■■■■■■■■ ■■■■■■■■■ ■■■■■■■■■ 縦横それぞれ奇数座標のマスをランダムに選択する。 下図では、左上を原点(0,0)として右に3、下に3の地点を選択したものとする。 (「○」を現在の注目点を意味する) ■■■■■■■■■ ■■■■■■■■■ ■■■■■■■■■ ■■■○■■■■■ ■■■■■■■■■ ■■■■■■■■■ ■■■■■■■■■ ■
知れば天国、知らねば地獄――「探索」虎の巻
いよいよ今回から、具体的なアルゴリズムの紹介に入っていきます。今回は、プログラミングにおける重要な概念である「探索」について考えます。グラフに変換し、探索する、という流れを知るとともに、そのグラフを効率よく探索する方法について紹介します。 今後紹介していくアルゴリズムについて お待たせしました！ 「最強最速アルゴリズマー養成講座」という連載タイトルのとおり、今回の連載からいよいよ具体的なアルゴリズムの紹介に入っていきたいと思います。 しかし、それを読んでいただく前に、1つ注意してもらいたいことがあります。連載第3回でもお伝えしたように、「問題を、既存の適当なアルゴリズムに当てはめる」という考え方は、非常に危険である、ということです。 筆者の経験上、TopCoderでRedCoder以上を目指すのであれば、回答時間短縮のために、いままでのパターンを利用するのも方法の1つなのですが、本連載では
ダイクストラ法（最短経路問題）
ダイクストラ法 (Dijkstra's Algorithm) は最短経路問題を効率的に解くグラフ理論におけるアルゴリズムです。 スタートノードからゴールノードまでの最短距離とその経路を求めることができます。 アルゴリズム 以下のグラフを例にダイクストラのアルゴリズムを解説します。 円がノード，線がエッジで，sがスタートノード，gがゴールノードを表しています。 エッジの近くに書かれている数字はそのエッジを通るのに必要なコスト（たいてい距離または時間）です。 ここではエッジに向きが存在しない（＝どちらからでも通れる）無向グラフだとして扱っていますが， ダイクストラ法の場合はそれほど無向グラフと有向グラフを区別して考える必要はありません。 ダイクストラ法はDP（動的計画法）的なアルゴリズムです。 つまり，「手近で明らかなことから順次確定していき，その確定した情報をもとにさらに遠くまで確定していく
人材獲得作戦・４ 試験問題ほか - 人生を書き換える者すらいた。
さて試験問題です。 内容は、壁とスペースで構成された迷路が与えられたとき、スタート地点からゴール地点に至る最短経路を求めよ、というものです。 たとえば、S:スタート G:ゴール *:壁 $:解答の経路 としたとき、 ************************** *S* * * * * * * ************* * * * * ************ * * * * ************** *********** * * ** *********************** * * G * * * *********** * * * * ******* * * * * * ************************** という入力に対し、 ************************** *S* * $$$ * *$* *$$*$ ************
アルゴリズムの紹介
ここでは、プログラムなどでよく使用されるアルゴリズムについて紹介したいと思います。 元々は、自分の頭の中を整理することを目的にこのコーナーを開設してみたのですが、最近は継続させることを目的に新しいネタを探すようになってきました。まだまだ面白いテーマがいろいろと残っているので、気力の続く限りは更新していきたいと思います。 今までに紹介したテーマに関しても、新しい内容や変更したい箇所などがたくさんあるため、新規テーマと同時進行で修正作業も行なっています。 アルゴリズムのコーナーで紹介してきたサンプル・プログラムをいくつか公開しています。「ライン・ルーチン」「円弧描画」「ペイント・ルーチン」「グラフィック・パターンの処理」「多角形の塗りつぶし」を一つにまとめた GraphicLibrary と、「確率・統計」より「一般化線形モデル」までを一つにまとめた Statistics を現在は用意していま
アルゴリズム - 同じ文字列のn回繰り返しをlog n回で作る方法 : 404 Blog Not Found
2009年01月31日01:00 カテゴリLightweight LanguagesMath アルゴリズム - 同じ文字列のn回繰り返しをlog n回で作る方法 これなのですが.... 同じ文字列のn回繰り返しを作る最速の方法を探求してみた - muddy brown thang ちょっとした事情により、ある文字列のn回繰り返しを作る関数 (PHPでいうところのarray_repeat(), Perlで言うところの「"..." x n」、RubyやPythonで言うところの「"..." * n」) を高速に実装しなければならない状況に遭遇したのでベンチマークをとってみたところ、その結果がとても新鮮で驚いたので、これを共有しつつもダメ出ししてもらえないかなーと思って晒してみることに。 なぜかもっとシンプルな奴がなかったので。 以下、比較。初期値はIEにあわせてあります。Firefox/Saf
定番アルゴリズムを徹底理解！ - 今からでも遅くない！アルゴリズム入門：selfup
このパートでは，プログラミングを勉強するうえで欠かせないアルゴリズムの中でも定番中の定番を紹介します。ソート（並べ替え）やサーチ（検索）などの機能は今では標準のライブラリとして提供されています。実用的なプログラムを作るときにそのものずばりをいちいち書く機会は少ないかもしれません。しかし定番のアルゴリズムは，様々に形を変えて普段のプログラミングに登場します。 解説を読んで仕組みがわかったら，ぜひそれをプログラムにしてみてください。読んだだけではプログラムを書けるようにはなりませんし，プログラムを書いてみて初めて，実は十分に理解できていなかったと気付くことがよくあります。しかもアルゴリズムは特定のプログラミング言語に依存しないので，一度身に付ければ，後でどんな言語を学ぶ場合でも役に立ちます。 1番目から6番目まではソートのアルゴリズム，7番目から9番目まではサーチのアルゴリズムです。一つひとつ
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
http://ja.doukaku.org/