フィボナッチ数を求めるコード

フィボナッチ数の漸化式を考えてみれば - f(n+2) = f(n) + f(n+1) -, いうまでもなく再帰を書きたくなるだろうし，実際にそういう解答をする人も多いし，そんなコードのサンプルをあげているサイトも多いし．．という．まぁ曲者である．Java，C++等をはじめとするコードでそんなコードを書いて，大きな値の引数を渡せばあっというまにスタックオーバーフローで動かない．現代のコンパイラやインタプリタならきっと末尾再帰で最適化してくれる，なんていうことを期待してコードを書くのはやめたほうがよいと思う．

フィボナッチ数のように，複数の再帰呼び出しを必要とするロジックなら素直にループで書こう．

    private static void fib( int max ) {

        int total = 0;
        int prev1 = 0;
        int prev2 = 1;

        for( int i = 0;i < max;i++ ) {
            if( i == 0 ) prev1 = 0;
            else if( i == 1 ) prev2 = 1;
            else {
                prev2 = prev1;
                prev1 = total;
            }
            total = prev1 + prev2;
        }

        System.out.println( total );

    }

Java - インターセクションの検出

インターセクションを検出するコードで，以下のサイトの解答例にはなかなか感心したので紹介．
シンプルでよいコードである．成程，HashSetのcontains()ならO(1)だ．

http://codereview.stackexchange.com/questions/9909/intersection-of-arrays-java

テストしたと書いていながら若干間違いがあるので，以下のように書き直し．

package org.tanuneko;

import java.util.*;

public class Intersect {

    private static List<Integer> intersect( final List<Integer> a, final List<Integer> b ) {

        Set<Integer> canAdd = new HashSet<Integer>(a);
        List<Integer> result = new ArrayList<>();
        for( int n : b ) {
            if( canAdd.contains(n) ) {
                result.add(n);
                canAdd.remove(n);
            }
        }
        return result;
    }

    public static void main( String args[] ) {

        List<Integer> a = Arrays.asList( 4,2,6,1,8,9,5 );
        List<Integer> b = Arrays.asList( 8,6,3,5,0,10,1 );

        System.out.println( intersect( a,b ) );
    }

}

メシウマという言葉

メシウマというネットスラングがあり，その意味は他人の不幸を肴に飯がうまい，という意味であるが，何とも心が貧しい感じで関心しない．

好きな球団が勝利して，そのあとの飯がうまい，というのが良いと思うが．

自己結合

自己結合は必ず使いこなせたほうが良い，というのはいうまでもないことだが，意外とわかってない人もどうやら多いようだ．

自己結合は，言ってみればなんのこともない，単にある外部キーが同テーブル上にあるプライマリキーと結合するだけである．良い好例と説明がこちらにあるので，理解があいまいだと思われる方は是非とも一読されたい．以下はSQLite3.5.9上で動作する解答例．

drop table if exists Employee
go
create table Employee (
 Id int not null primary key,
 Name varchar(64) not null,
 ManagerId int,
 Salary int not null 
)
go
insert into Employee (Id,Name,ManagerId,Salary) values( 1, "Kotora", 3, 500000 )
go
insert into Employee (Id,Name,ManagerId,Salary) values( 2, "Kodanuki",3,  5000 )
go
insert into Employee (Id,Name,Salary) values( 3, "Tanu", 100000 )
go
insert into Employee (Id,Name,Salary) values( 4, "Ushi", 5000 )

select e2.Name,"earns more than" as fact,e1.Name from Employee e1
join Employee e2 on e1.Id = e2.ManagerId
where e2.Salary > e1.Salary

BTreeの判定

何かよいインタビュー用の問題はないかリサーチしていたところ，ツリー構造のデータが二分木であるかどうか判定するコードを書け，というのが結構あることがわかった．

確かに基礎を見るにはよい問いかもしれない．
深さ優先ではこんな感じだろうか．

#include <iostream>
#include <string>
using namespace std;

typedef struct Node_Struct {
 int value;
 struct Node_Struct* l;
 struct Node_Struct* r;
} Node;

Node * add(Node* base, int value) {

 if (base == NULL) {
  cout << "adding " << value << " to this node" << endl;
  base = new Node;
  base->l = base->r = NULL;
  base->value = value;
 }
 else if (base->value > value) {
  cout << base->value << ">" << value << ".. L" << endl;
  base->l = add(base->l,value);
 }
 else {
  cout << base->value << "<" << value << ".. R" << endl;
  base->r = add( base->r, value);
 }
 return base;

}

void dump(const Node* n) {
 cout << "{" << "value:" << n->value << "}" << endl;
}

void traverse_r( Node* n ) {

 if (n == NULL)
  return;

 if (n->l != NULL)
  traverse_r(n->l);
 dump(n);
 if (n->r != NULL)
  traverse_r(n->r);

 
}


Node* build_btree( Node* n) {

 n = add(n, 15);
 n = add(n, 30);
 n = add(n, 48);
 n = add(n, 10);
 n = add(n, 15);
 n = add(n, 72);
 n = add(n, 60);
 n = add(n, 66);
 n = add(n, 26);
 n = add(n, 55);
 return n;

}

bool is_btree_d(Node *n, bool decision) {
 
 if (n == NULL || decision == false)
  return decision;
 if (n->l != NULL && n->r != NULL) {
  cout << n->l->value << ":" << n->r->value << endl;
  decision = n->l->value < n->r->value ? true : false;
 }

 cout << "movin to l" << endl;
 decision = is_btree_d(n->l, decision);
 cout << "moving to r" << endl;
 decision = is_btree_d(n->r, decision);
 return decision;
 
}

int main() {

 Node* n = NULL;
 n = build_btree(n);
 traverse_r( n );
 cout << "is this btree valid? - " << is_btree_d(n, true) << endl;

 return 0;
}

Java - Mapのイテレーション

Mapのイテレーションをするコードをレビューすることもあるし，もはやそのやり方も人口に膾炙していると思う．しかし，keySet()を最初に取得し，keySetのイテレータを通して要素にアクセスするコードを見るのもまた事実でもある．コードの静的解析ツールを走らせばすぐに指摘してくれるはずなので，レビュー前にはぜひ修正をしてもらいたいものである．

import java.util.HashMap;
import java.util.Map;

public class MapIter {

    public static void main( String args[] ) {

        Map<String,String> data = new HashMap<String,String>();
        data.put( "F", "Fine Fare" );
        data.put( "B", "Biking" );
        data.put( "C", "C Town Town Town" );

        for( Map.Entry<String,String> ent : data.entrySet() ) {
            System.out.printf("%s:%s\n",ent.getKey(),ent.getValue());
        }

    }
}

デッドロック

時々私が使う面接の質問のひとつはデッドロックを起こすコードを書いてみてください，というものである．多くの候補者は理論的にはわかってはいるものの，コードでいざ書く段になるとなぜか正しい答えを書けないのである．

以下にサンプルのコードを示す．以下のコードや，Oracle Javaのデッドロックの参考例，哲学者の食事問題などを参考にしてほしい．

class Friend extends Thread implements Runnable {

    private Friend myFriend;
    private String name;

    public Friend( final String name ) {
        this.name = name;
    }

    public synchronized void vow() {
        System.out.printf( "Hey my friend %s..\n", name );
        myFriend.vow();
    }

    public void run() {
        vow();
    }

    public void setMyFriend( Friend myFriend ) {
        this.myFriend = myFriend;
    }

    public static void main( String args[] ) {
        Friend me = new Friend( "John Flansburgh" );
        Friend dude = new Friend( "John Linnell" );
        me.setMyFriend( dude );
        dude.setMyFriend( me );
        me.start();
        dude.start();
        System.out.println( "Have a nice day." );
    }
}

走り書き2

バブルソートの走り書きのついでに選択ソートも。。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void dump(int dump) {
 cout << dump << ",";
}

void selsort(vector<int>& v) {

 cout << "before:";
 for_each(v.begin(), v.end(), dump);
 cout << endl;

 int min;
 int t;
 for (int i = 0; i < v.size() - 1; i++) {
  min = i;
  for (int j = i + 1; j < v.size(); j++) {
   if (v[j] < v[min]) {
    min = j;
   }
  }
  t = v[i];
  v[i] = v[min];
  v[min] = t;
 }

 cout << "after:";
 for_each(v.begin(), v.end(), dump);
 cout << endl;

}


int main() {

 int nums[] = { 32, 22, 25, 10, 9, 38, 40, 42, 50, 51, 10, 32, 45, 27 };
 vector<int> v;
 for (int i = 0; i < sizeof(nums) / sizeof(int); i++)
  v.push_back(nums[i]);

 selsort(v);

}

走り書き

妙にバブルソート(!)が書きたくなったので，走り書きをした．
サイダーが飲みたくなった．

import java.util.List;


public class Bubb {

    static void bubble( int[] nums ) {

        int t;
        for( int i = 0;i < nums.length - 1;i++ ) {
            for( int j = i + 1; j < nums.length; j++ ) {
                if( nums[i] > nums[j] ) {
                    t = nums[i];
                    nums[i] = nums[j];
                    nums[j] = t;
                }
            }
        }
    }

    public static void main( String args[] ) {

        int[] nums = { 32, 17, 21, 26, 35, 40, 10, 5, 8, 9, 48, 23, 16, 17 };
        bubble( nums );
        for( int i = 0;i < nums.length;i++ ) {
            System.out.println( nums[ i ] );
        }

    }
}