シリコンバレー就職

Amazonの電話面接（技術）の準備 その1

広告

いま4つくらい進行中の面接を抱えています。英語で面接するのは不慣れだし、さっさと決めて、面接対策なんか終わりにして、英語の練習なりプログラミングの勉強をしたいと思っています。

ネットで検索するとAmazonの問題は色々出てきます。いくつか解いてきましょう。

/* We have a system which vends out IP addresses to new devices which come online on the network. It internally keeps a log file of all IP addresses
 * in use. So come up with an algorithm to find me an available IP address that is not present in the log file.
 */

public class AssignUnique {

public String[] getUniqueIPAddress(String filePath) {

    }

    // 255.255.255.255
    // 255.255.255.254
}

ファイルに書かれているIPアドレスを全部記録して、使えるIPアドレスを1つ返すようです。しかしなぜか関数の戻り値が配列です。

とりあえず愚直に書いてみましょう。

int main()
{
    FILE *in = fopen("ip.txt", "rt");
    set<string> existing_ip_addresses;

    if( in != NULL )
    {
        while( true )
        {
            char line[1024];
            if ( fgets(line, 1024, in) == NULL )
                break;

            string s = line;

            cout << s << endl;
            existing_ip_addresses.insert(s);
        }
    }

    for( int a = 1; a < 255; a++ )
        for( int b = 1; b < 255; b++ )
            for( int c = 1; c < 255; c++ )
                for( int d = 1; d < 255; d++ )
                {
                    char ip_address[1024];
                    sprintf(ip_address, "%d.%d.%d.%d", a, b, c, d);

                    string s = ip_address;
                    if( existing_ip_addresses.count(s) == 0 )
                    {
                        printf("%s\n", ip_address);
                        return 0;
                    }
                }
}

ip.txtの中身は

255.255.255.255
255.255.255.254

です。

実行すると1.1.1.1を出力して終わります。直感としてはこれはあまり正しくない気がします。

最初から列挙して見つかったら返す実装ですが、友人と話していてランダムに生成したほうがaverage caseでは早いという話でした。なるほど、それもそうですね。

まず、ip.txtのフォーマットを聞いていません。これは確認するべきでしょう。余分なスペースとか表現のゆらぎはないか、あるのならそれを除去する必要があります。

余談ですが、feof(in)をループの終了判定にするのはよくないそうです。場合によってはループが1回多く実行されてしまいます。それを含めて入力が本当にIPアドレスとして適正か判断する必要があるかも知れません。Is there any possibility that …という聞き方はすっと出てくる必要がありそうです。

IPアドレスはただの文字列で保持していて、setに入れて既出でなければOKとしていましたが、int型の変数4つで保持したほうがいいかも知れません。そうするとsplitする関数が必要ですが、C++にはsplitはないようです。もしこれを書くのなら

vector<string> split(const string &input, const string &delimiter)
{
    vector<string> result;
    string::size_type position = 0;

    while( position != string::npos )
    {
        string::size_type p = input.find(delimiter, position);

        if(p == string::npos)
        {
            result.push_back(input.substr(position));
            break;
        }
        else {
            result.push_back(input.substr(position, p - position));
        }

        position = p + delimiter.size();
    }

    return result;
}

といったルーチンもすぐに書けるようにしておくべきでしょうか。

出力するIPアドレスのレンジも聞いていません。192.168.1.1から192.168.1.254で出力するべきなのかも知れません。空いているIPアドレスがないときは何を返すかなど色々クリアにしなければならないポイントがありそうです。

広告

RECOMMENDこちらの記事も人気です。