2014亚马逊在线笔试题目

参考http://www.cnblogs.com/jiabei521/p/3348780.html出的题目

1、

题目的意思是

　　1xN的棋盘上，每个格子有一定的分值，现在有m个卡片，每个卡片上有1~4四种数值，代表走几步，类似小时候的飞行棋游戏，现在有个人站在位置0的初始点，抽取一张卡片，然后根据卡片上的数值向前移动，然后获取移动后人所在的位置的分值，然后累加，求最后所能得到的最大分数。

解题思路：

　　就是将m个卡片全排列，每种排列代表一种走法，然后算最大累积分值，直接利用c++的next_permutation枚举全排列函数即可。

源代码：　

#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>

using namespace std;

int main(){
    int n,m;
    cin >> n >>m ;
    vector<int> score(n,0), cards(m,0);
    for(int i = 0 ; i < n; ++ i) cin >> score[i];
    for(int i = 0;  i < m; ++ i) cin >> cards[i];
    int res = 0;
    do{
        int sum = score[0],index = 0;
        for(int i = 0; i < m; ++ i){
            index +=cards[i];
            if(index >= n) break;
            sum +=score[index];
        }
        res = max(res,sum);
    }while(next_permutation(cards.begin(),cards.end()));
    cout<<res<<endl;
}

2、Amazon Campus(2013-Sep-24)Question 2 / 2 (Amazon Campus（17）:Find the differences of items in amazon)

Amazon has millions of different items in different categories right now, so when sellers want to sell items in our website, sellers want to find the right categories their items belong to.  Suppose we want to build a system to help sellers find the minimal differences items and then find the right category. The difference index is a number that sum of single-word edits (insertion, deletion, substitution) required to change one phrase into the other:
For example, we get two lines from standard input Hadoop in practice
Hadoop operations
The difference index  of ‘Hadoop in practice’ and ‘Hadoop operations’ is 2. Because we can remove ‘practice’ and substitute ‘in’ with ‘operations’, then ‘Hadoop in practice’ can convert to ‘Hadoop operations’

For example, we get two lines from standard input
Hadoop cookbook
Hadoop operations
The difference index of ‘Hadoop cookbook’ and ‘Hadoop operations’ is 1. Because we can substitute ‘cookbook’ with ‘operations’ then convert 'Hadoop cookbook' can convert to 'Hadoop operations'

For example, we get two lines from standard input:
Ruby in action
Hadoop operations
The difference index of ‘Ruby in action’ and ‘Hadoop operations’ is 3. Because we can substitute ‘Ruby’ with ‘Hadoop’, ‘in’ with ‘operations’ and remove ‘action’ then 'Ruby in action' can convert to 'Hadoop operations'

字符串距离的变形题

将字符串按照空格分割，然后放入vector中，然后利用动态规划求解

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

vector<string> split(string& str){
    stringstream ss;
    ss << str;
    vector<string> res;
    string tmp;
    while(ss >> tmp) res.push_back(tmp);
    return res;
}

int distanceBetweenString(string& str1,string& str2){
    if(str1 == str2) return 0;
    vector<string> word1=split(str1);
    vector<string> word2=split(str2);
    int len1 = word1.size(),len2 = word2.size();
    if(len1 == 0) return len2;
    if(len2 == 0) return len1;
    vector<vector<int> > dp(len1+1, vector<int>(len2+1,0));
    for(int i = 0; i <= len1; ++ i) dp[i][0] = i;
    for(int j = 0; j <= len2; ++ j) dp[0][j] = j;
    for(int i =1; i <= len1; ++ i){
        for(int j = 1; j <= len2; ++ j){
            dp[i][j] = min(dp[i-1][j-1]+(word1[i-1] != word2[j-1]? 1: 0),min(dp[i-1][j]+1, dp[i][j-1]+1));
        }
    }
    return dp[len1][len2];
}

int main(){
    string str1,str2;
    getline(cin,str1);
    getline(cin,str2);
    cout<<distanceBetweenString(str1,str2)<<endl;
}