シリコンバレー就職

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

広告

その他、ネットを色々探します。

母音を数える

Write a program to count the number of vowels in a string.

Amazon Interview Question for Software Engineer in Tests

using namespace std;

int countVowels(const string &s)
{
    set<char> vowels;
    vowels.insert('a');
    vowels.insert('e');
    vowels.insert('i');
    vowels.insert('o');
    vowels.insert('u');

    int count = 0;

    for( auto c: s )
    {
        if( vowels.count(c) != 0 )
            count++;
    }

    return count;
}

int main()
{
    cout << countVowels("January.") << endl;
}

増加して減少に転ずる配列の最大値を求める

You have given an array in which numbers are first increasing and then decreasing. Find the maximum element in O(log n).

Amazon Interview | Set 97 (On-Campus for SDE1)

O(log n)というのがポイントかな。普通に配列を全部見ていくとO(N)なので不適。計算量をO(log n)に抑えるには反復するごとに半分の長さに絞り込んでいく必要がありそう。詳しくは「[初心者向け] プログラムの計算量を求める方法」つまり二分検索的なやり方が欲しいところです。

using namespace std;

int findMax(vector<int> &v)
{
    int left = 0;
    int right = v.size();

    if( v.size() < 3 )
    {
        cout << "invalid input: ";
        return -9999;
    }

    while( left <= right )
    {
        int mid = left + (right - left) / 2;

        if( 0 < mid && mid < v.size() && v[mid-1] < v[mid] && v[mid] > v[mid+1] )
        {
            return v[mid];
        }

        if( 0 < mid && v[mid-1] < v[mid] )
        {
            left = mid + 1;
        }

        if( mid < v.size() && v[mid] > v[mid+1] )
        {
            right = mid - 1;
        }
    }

    cout << "invalid input: ";
    return -9999;
}


int main()
{
    vector<int> v1 = {1, 2, 3, 4, 5, 6, 7, 6, 5, 4, 3, 2, 1};
    vector<int> v2 = {1, 2, 3, 4, 5, 6, 7, 6, 5, 4, 3, 2};
    vector<int> v3 = {6, 7, 6, 5, 4, 3, 2, 1};
    vector<int> v4 = {1, 2, 3, 4, 5, 6, 7, 6};
    vector<int> v5 = {7, 6, 5, 4, 3, 2, 1};
    vector<int> v6 = {1, 2, 3, 4, 5, 6, 7};
    vector<int> v7 = {1, 2}; // invalid
    vector<int> v8 = {}; // invalid

    cout << findMax(v1) << endl;
    cout << findMax(v2) << endl;
    cout << findMax(v3) << endl;
    cout << findMax(v4) << endl;
    cout << findMax(v5) << endl;
    cout << findMax(v6) << endl;
    cout << findMax(v7) << endl;
    cout << findMax(v8) << endl;
}

確認すべき事項

  • 入力配列は常に正当か？
  • つまり上がりっぱなしの配列はないか
  • 下がりっぱなしの配列はないか
  • 上がって下がるためには最低要素3必要だが、それは大丈夫か
  • NULLチェックは必要か

あたりは聞いたほうがいいかも知れません。配列の値の範囲は聞いてもいいけどどうでもいいと思います。

リストの要素の入れ替え

Swap the data of alternate nodes of a list.

Amazon Interview | Set 97 (On-Campus for SDE1)

リストは自前で実装する必要があるかも知れません。双方向リストか単方向リストか、確認すべき点はありますが、簡単な実装をしてみます。

using namespace std;


class Node
{
public:
    Node( int d ) : data(d), next(nullptr)
    {
    }

    void append_back(int d)
    {
        Node *n = this;

        while( n->next != nullptr )
        {
            n = n->next;
        }

        n->next = new Node(d);
    }

    void swap(int v1, int v2)
    {
        Node *v1_ptr = nullptr;
        Node *v2_ptr = nullptr;

        int depth = 0;
        Node *n = this;

        while( n != nullptr )
        {
            if( depth == v1 )
            {
                v1_ptr = n;
            }

            if( depth == v2 )
            {
                v2_ptr = n;
            }

            n = n->next;
            depth++;
        }

        if( v1_ptr != nullptr && v2_ptr != nullptr )
        {
            int temp = v2_ptr->data;
            v2_ptr->data = v1_ptr->data;
            v1_ptr->data = temp;
        }
    }

    void print()
    {
        Node *n = this;
        while( n->next != nullptr )
        {
            cout << n->data << " ";
            n = n->next;
        }
        cout << n->data << endl;

    }

    Node *next;
    int data;
};



int main()
{
    Node n(0);

    for( int i = 1; i < 10; i++ )
        n.append_back(i);

    n.print();

    n.swap(3, 5);
    n.print();

    n.swap(3, 100);
    n.print();

    n.swap(-1, 3);
    n.print();

    n.swap(0, 9);
    n.print();
}

結果

0 1 2 3 4 5 6 7 8 9
0 1 2 5 4 3 6 7 8 9
0 1 2 5 4 3 6 7 8 9
0 1 2 5 4 3 6 7 8 9
9 1 2 5 4 3 6 7 8 0

うまく入れ替わっているほか、範囲外アクセスしても大丈夫の様子。最初に書いたときはループの脱出条件を間違えていました。本番ではやらかさないように気をつけないと。

確認すべき事項

  • リストはリンクトリスト（linked list）か？配列なら簡単
  • リストの実装は必要か
  • 入れ替えるのは値だけでいいか、構造体そのものを入れ替えるのか
  • 範囲外を指定されたときの動作

広告

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