読者です 読者をやめる 読者になる 読者になる

MyEnigma

とあるエンジニアのブログです。#Robotics #Programing #C++ #Python #MATLAB #Vim #Mathematics #Book #Movie #Traveling #Mac #iPhone

世界最前線のIT企業のコーディング面接の例題を実際にコーディングしてみる

c++ Python Programming

目次

はじめに

下記の本を読んだのですが、

本の中に出てくる

コーディング面接の例題を

実際に解いてみたくなったので、

コーディングしてみることにしました。

 

問題の詳細は、

上記の本を参照下さい。

すべてのプログラマが楽しめる内容だと思います。

 

問題

入力として、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.hatenablog.com

myenigma.hatenablog.com

myenigma.hatenablog.com

myenigma.hatenablog.com

myenigma.hatenablog.com