目次
はじめに
下記の本を読んだのですが、
本の中に出てくる
コーディング面接の例題を
実際に解いてみたくなったので、
コーディングしてみることにしました。
エンジニアとして世界の最前線で働く選択肢 ~渡米・面接・転職・キャリアアップ・レイオフ対策までの実践ガイド
- 作者: 竜盛博
- 出版社/メーカー: 技術評論社
- 発売日: 2015/10/08
- メディア: 単行本(ソフトカバー)
- この商品を含むブログ (2件) を見る
問題の詳細は、
上記の本を参照下さい。
すべてのプログラマが楽しめる内容だと思います。
問題
入力として、int 配列と、
ターゲットとなる数が1つ与えられる。
和がターゲット数となるような2つの数を配列から取り出す関数を書きなさい。
前提条件
返り値の型はintで、インデックスではなく、2つの値のどちらか片方、 小さいほうでも大きいほうでも、返せばいい
条件を満たすペアが複数存在する場合でも、どれか1つ返せばいい
条件を満たすものが存在しないならば、自前の例外ValueNotFoundExceptionを投げる
ソートはされていない
intでありえる数すべてが存在しえる
nullチェックは省略していい
Pythonの場合
下記が自分が書いてみたコードです。
SearchOnONNは二重ループなので、O(NN)
SearchOnONlogNは一度リストをソートしているため、O(NlogN)
SearchOnONは、dict(連想配列)を使っているため、O(N)
になると思います。
#! /usr/bin/python # -*- coding: utf-8 -*- u""" author Atsushi Sakai """ import numpy import random def SearchOnONN(target,datalist): print("SearchOnONN") for data1 in datalist: for data2 in datalist: if (data1+data2) == target: print((data1,data2,target)) return(data1) raise ValueNotFoundException('ValueNotFoundException') def SearchOnONlogN(target,datalist): print("SearchOnONLogN") i=0 j=len(datalist)-1 datalist.sort() while i!=j: sumdata=datalist[i]+datalist[j] if sumdata>target: j-=1 elif sumdata<target: i+=1 else: print((datalist[i],datalist[j],target)) return (datalist[i]) raise ValueNotFoundException('ValueNotFoundException') def SearchOnON(target,datalist): print("SearchOnON") hashset={} for data in datalist: d=target-data if d in hashset: print(data,d,target) return (data) else: hashset[data]=data raise ValueNotFoundException('ValueNotFoundException') if __name__ == '__main__': target=70 datalist=numpy.arange(50) random.shuffle(datalist) print(SearchOnONN(target,datalist)) print(SearchOnONlogN(target,datalist)) print(SearchOnON(target,datalist))
C++の場合
C++でも書いてみました。
基本的には上記のPythonコードと同じです。
#include<iostream> #include<vector> #include<algorithm> #include<unordered_map> using namespace std; class ValueNotFoundException : public std::exception{ }; int SearchOnONN(int target, const vector<int> &datalist){ cout<<"SearchOnONN"<<endl; for (int d1 : datalist) { for (int d2 : datalist) { if((d1+d2) == target){ cout<<d1<<","<<d2<<","<<target<<endl; return(d1); } } } throw ValueNotFoundException(); } int SearchOnONlogN(int target, vector<int> datalist){ cout<<"SearchOnONlogN"<<endl; int i=0; int j=datalist.size()-1; sort(datalist.begin(),datalist.end()); while(i!=j){ int sumdata=datalist[i]+datalist[j]; if(sumdata>target){ j--; } else if(sumdata<target){ i++; } else{ cout<<datalist[i]<<","<<datalist[j]<<","<<target<<endl; return datalist[i]; } } throw ValueNotFoundException(); } int SearchOnON(int target, vector<int> datalist){ cout<<"SearchOnON"<<endl; unordered_map<int, int> mp; for(int data : datalist){ int d=target-data; auto itr = mp.find(d); if( itr != mp.end() ) { cout<<data<<","<<itr->first<<","<<target<<endl; return data; } else{ mp[data]=data; } } throw ValueNotFoundException(); } int main(void){ int target=70; vector<int> datalist; for(int i=0;i<50;i++) datalist.push_back(i); random_shuffle(datalist.begin(), datalist.end()); cout<<SearchOnONN(target,datalist)<<endl; cout<<SearchOnONlogN(target,datalist)<<endl; cout<<SearchOnON(target,datalist)<<endl; }
GitHubリポジトリ
上記のコードはすべて下記のGitHubリポジトリにて公開しています。
AtsushiSakai/CodingInterviewCode: Coding interview coce
ハッシュテーブル
今回の書籍では、
ハッシュテーブルの強力さが紹介されていますが、
ハッシュテーブルに関しては、
こちらの記事が非常にわかりやすいです。
書籍の中で述べられている通り、
ハッシュテーブルを使うことで、
大量のデータの中からの検索を高速化することができます。
Pythoでは、dictonaryを
C++ではunordered_map (C++11から使えます)を使うことで
ハッシュテーブルを利用することができます。
最後に
一度コーディング面談を受けてみたいですね。
参考資料
MyEnigma Supporters
もしこの記事が参考になり、
ブログをサポートしたいと思われた方は、
こちらからよろしくお願いします。